Collections — различия между версиями

/// Модуль содержит шаблоны классов
///   SingleNode — узла с одним полем связи
///   DoubleNode — узла с двумя полями связи
unit Nodes;

interface

type

//-------------------------------------------SINGLE_NODE-------------------------------------------
  /// Узел с одним полем связи
  SingleNode<DataType> = class
    /// Значение узла
    data: DataType;
    /// Ссылка на следующий элемент
    next: SingleNode<DataType>;
    
    /// <summary>
    /// Конструктор
    /// </summary>
    /// <param name="pData">Значение узла</param>
    /// <param name="pNext">Ссылка на следующий элемент</param>
    constructor Create(pData: DataType; pNext: SingleNode<DataType>);
  end;

// -------------------------------------------DOUBLE_NODE------------------------------------------  
  /// Узел с двумя полями связи
  DoubleNode<DataType> = class
    /// Значение узла
    data: DataType;
    /// Ссылка на следующий элемент
    next: DoubleNode<DataType>;
    /// Ссылка на предыдущий элемент
    prev: DoubleNode<DataType>;
    
    /// <summary>
    /// Конструктор
    /// </summary>
    /// <param name="pData">Значение узла</param>
    /// <param name="pNext">Ссылка на следующий элемент</param>
    /// <param name="pPrev">Ссылка на предыдущий элемент</param>
    constructor Create(pData: DataType; pPrev, pNext: DoubleNode<DataType>);
  end;

implementation

//-------------------------------------------SINGLE_NODE-------------------------------------------
{Конструктор
    pData — значение узла
    pNext — cсылка на следующий элемент}
constructor SingleNode<DataType>.Create(pData: DataType; pNext: SingleNode<DataType>);
begin
  data := pData;
  next := pNext;
end;

// -------------------------------------------DOUBLE_NODE------------------------------------------  
{Конструктор
    pData — значение узла
    pNext — cсылка на следующий элемент
    pPrev — ссылка на предыдущий элемент}
constructor DoubleNode<DataType>.Create(pData: DataType; pPrev, pNext: DoubleNode<DataType>);
begin
  data := pData;
  next := pNext;
  next := pNext;
end;

end.

/// Модуль содержит шаблоны классов
///   Stack — стек
///   Queue — очередь
unit Collections;


// ===================================================================== INTERFACE =====================================================================
interface

uses Nodes;   // для использования типа SingleNode<DataType> — 
              // узла с одним полем связи

const
  /// Ширина поля вывода
  PRINT_FIELD_WIDTH = 5;
  /// Разделитель при выводе элементов
  DELIMETR = '   ';
  /// Количество элементов, выводимых в одной строке при выводе
  ELEMS_IN_LINE = 5;

// ----------------------------------------------STACK---------------------------------------------
const
  /// Сообщение о пустоте стека
  EMPTY_STACK = 'Стек пуст';

type
  /// Шаблон класса Stack [Стек]
  Stack<DataType> = class
  private 
    /// Вершина стека
    fTop: SingleNode<DataType> := nil;   // field Top
  public 
// ---------------------------- Стандартные методы --------------------------- 
   /// Стандартный конструктор
    constructor Create;
    /// Конструктор.
    /// Создает стек, заполненный элементами, переданными в качестве параметров
    constructor Create(params datas: array of DataType); 
    
    /// Кладет элемент x на вершину стека
    procedure Push(x: DataType);
    /// Возвращает элемент типа DataType, снимая его с вершины стека
    function Pop: DataType;
    /// Возвращает значение элемента на вершине стека
    function Top: DataType;
    /// Возвращает истину, если стек пуст
    function IsEmpty: boolean;
// ----------------------------- Вывод содержимого ---------------------------
    /// <summary>
    /// Выводит подряд содержимое стека
    /// </summary>
    /// <param name="delim">Разделитель между элементами в строке</param>
    /// <param name="elemsInLine">Количество элементов, выводимых в одной строке</param>
    procedure Print(delim: string := DELIMETR; elemsInLine: integer := ELEMS_IN_LINE);
    /// Выводит содержимое стека в каждой строке
    procedure Println;
  end;

// ----------------------------------------------QUEUE---------------------------------------------
type  
  /// Шаблон класса Queue [Очередь]
  Queue<DataType> = class
  private
    /// Голова очереди
    head: SingleNode<DataType>;
    /// Хвост очереди
    tail: SingleNode<DataType>;
  public
// ---------------------------- Стандартные методы ---------------------------
    /// Стандартный конструктор
    constructor Create;
    /// Добавляет элемент x в хвост очереди
    procedure Enqueue(x: DataType);
    /// Возвращает элемент типа DataType, убирая его из головы очереди
    function Dequeue: DataType;
    /// Возвращает истину, если очередь пуста
    function IsEmpty: boolean;
  end;


// ================================================================= IMPLEMENTATION ===================================================================
implementation

// ----------------------------------------------STACK---------------------------------------------

// ---------------------------- Стандартные методы ---------------------------
{Стандартный конструктор}
constructor Stack<DataType>.Create;
begin
  fTop := nil;
end;
{Конструктор.
 Создает стек, заполненный элементами, переданными в качестве параметров}
constructor Stack<DataType>.Create(params datas: array of DataType); 
begin
  fTop := nil;
  for var i := 0 to datas.Length - 1 do
    Push(datas[i]);
end;

{Кладет элемент x на вершину стека} 
procedure Stack<DataType>.Push(x: DataType);
begin
  fTop := new SingleNode<DataType>(x, fTop);
end;

{Возвращает элемент типа DataType, снимая его с вершины стека}
function Stack<DataType>.Pop: DataType;
begin
  Assert(not IsEmpty);
  result := fTop.data;
  fTop := fTop.next;  // элемент снимается с вершины стека
                      // (т.е. вершиной становится следующий элемент)
end;

{Возвращает значение элемента на вершине стека}
function Stack<DataType>.Top: DataType;
begin
  Assert(not IsEmpty);
  result := fTop.data;
end;

{Возвращает истину, если стек пуст}
function Stack<DataType>.IsEmpty: boolean;
begin
  result := (fTop = nil);
end;

// ----------------------------- Вывод содержимого ---------------------------
{Выводит подряд содержимое стека
    delim — разделитель между элементами в строке
    elemsInLine — количество элементов, выводимых в одной строке}
procedure Stack<DataType>.Print(delim: string; elemsInLine: integer);
begin
  if IsEmpty then
    writeln(EMPTY_STACK)
  else
  begin
    var elemsInd := 1;  // индекс элемента стека
                        // нужен для вывода по строкам
    var curElem := fTop;
    while curElem <> nil do
    begin
      if (elemsInd mod elemsInLine) <> 0 then
        write(curElem.data:PRINT_FIELD_WIDTH, delim) 
      else              // вывели требуемое количество элементов в строке
        writeln(curElem.data:PRINT_FIELD_WIDTH, delim);
        
      curElem := curElem.next;
      elemsInd += 1;
    end;
  end;
end;

{Выводит содержимое стека в каждой строке}
procedure Stack<DataType>.Println;
begin
  if IsEmpty then
    writeln(EMPTY_STACK)
  else
  begin
    var curElem := fTop;
    while curElem <> nil do
    begin
      writeln(curElem.data:PRINT_FIELD_WIDTH);
      curElem := curElem.next;;
    end;
  end;
end;

// ----------------------------------------------QUEUE---------------------------------------------

// ---------------------------- Стандартные методы ---------------------------
{Конструктор}
constructor Queue<DataType>.Create;
begin
  head := nil;
  tail := nil;
end;

{Добавляет элемент x в хвост очереди} 
procedure Queue<DataType>.Enqueue(x: DataType);
begin
  if IsEmpty then
  begin
    head := new SingleNode<DataType>(x, nil);
    tail := head;
  end
  else  // if not IsEmpty
  begin
    tail.next := new SingleNode<DataType>(x, nil);
    tail := tail.next;  // элемент убирается из хвоста очереди
                        // (т.е. хвостом становится следующий элемент)
  end;
end;

{Возвращает элемент типа DataType, убирая его из головы очереди}
function Queue<DataType>.Dequeue: DataType;
begin
  Assert(not IsEmpty);
  result := head.data;
  
  head := head.next;  // элемент убирается из головы очереди
                      // (т.е. головой становится следующий элемент)
  if head = nil then
    tail := nil;
end;

{Возвращает истину, если очередь пуста}
function Queue<DataType>.IsEmpty: boolean;
begin
  result := (head = nil);
  if result then
    Assert(tail = nil);
end;
  
end.