Collections (Full Version)

Содержание

1 Вспомогательные модули
- 1.1 Nodes
2 Составляющие классы
3 Collections

Вспомогательные модули

Nodes

/// Модуль содержит шаблоны классов
///   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;
  prev := pPrev;
end;

end.

Составляющие классы

Stack

<xh4> Интерфейс </xh4>

Create
  Создает пустой стек

Create(params xDatas: array of DataType)
  Создает стек, заполненный элементами, переданными в качестве параметров
  
Push(x: DataType) 
  Кладет элемент x на вершину стека

Pop: DataType
  Возвращает элемент типа DataType, снимая его с вершины стека
   
Top: DataType
  Возвращает значение элемента на вершине стека

IsEmpty: boolean;
  Возвращает истину, если стек пуст
       
Print(delim: string; elemsInLine: integer)
  Выводит подряд содержимое стека 
  (delim — разделитель между элементами в строке, 
  elemsInLine — количество элементов, выводимых в одной строке)
   
Println
  Выводит содержимое стека в каждой строке

<xh4> Реализация </xh4>

/// Модуль содержит шаблон класса
///   Stack — стек
unit StackUnit;

interface
  
uses Nodes;   // для использования типа SingleNode<DataType> — 
              // узла с одним полем связи
              
const
  /// Ширина поля вывода
  PRINT_FIELD_WIDTH = 5;
  /// Разделитель при выводе элементов
  DELIMETR = '   ';
  /// Количество элементов, выводимых в одной строке при выводе
  ELEMS_IN_LINE = 5;
 
  /// Сообщение о пустоте стека
  EMPTY_STACK = 'Стек пуст';
 
type
  /// Шаблон класса Stack [Стек]
  Stack<DataType> = class
  private 
    /// Вершина стека
    fTop: SingleNode<DataType> := nil;   // field Top
    
  public 
// ---------------------------- Стандартные методы --------------------------- 
    /// Создает пустой стек
    constructor Create;
    /// Создает стек, заполненный элементами, переданными в качестве параметров
    constructor Create(params xDatas: 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;
  
  
// ================================================================= IMPLEMENTATION ===================================================================
implementation

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


end.

Queue

<xh4> Интерфейс </xh4>

Create
  Создает пустую очередь

Create(params xDatas: array of DataType)
  Создает очередь, заполненную элементами, переданными в качестве параметров
  
Enqueue(x: DataType) 
  Добавляет элемент x в хвост очереди

Dequeue: DataType
  Возвращает элемент типа DataType, убирая его из головы очереди
   
IsEmpty: boolean;
  Возвращает истину, если очередь пуста
       
Print(delim: string; elemsInLine: integer)
  Выводит подряд содержимое очереди от головы к хвосту
  (delim — разделитель между элементами в строке, 
  elemsInLine — количество элементов, выводимых в одной строке)
   
Println
  Выводит содержимое очереди от головы к хвосту в каждой строке

<xh4> Реализация </xh4>

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

interface

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

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

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

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

// ---------------------------- Стандартные методы ---------------------------
{Создает пустую очередь}
constructor Queue<DataType>.Create;
begin
  head := nil;
  tail := nil;
end;
{Создает очередь, заполненную элементами, переданными в качестве параметров}
constructor Queue<DataType>.Create(params xDatas: array of DataType); 
begin
  head := nil;
  tail := nil;
  for var i := 0 to xDatas.Length - 1 do
    Enqueue(xDatas[i]);
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;

// ----------------------------- Вывод содержимого ---------------------------
{Выводит подряд содержимое очереди от головы к хвосту
    delim — разделитель между элементами в строке
    elemsInLine — количество элементов, выводимых в одной строке}
procedure Queue<DataType>.Print(delim: string; elemsInLine: integer);
begin
  if IsEmpty then
    writeln(EMPTY_QUEUE)
  else
  begin
    var elemsInd := 1;  // индекс элемента стека
                        // нужен для вывода по строкам
    var curElem := head;
    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 Queue<DataType>.Println;
begin
  if IsEmpty then
    writeln(EMPTY_QUEUE)
  else
  begin
    var curElem := head;
    while curElem <> nil do
    begin
      writeln(curElem.data:PRINT_FIELD_WIDTH);
      curElem := curElem.next;;
    end;
  end;
end;


end.

DynArray

<xh4> Интерфейс </xh4>

Count
  Количество элементов (размер) массива

Capacity
  Емкость массива (отведенная память)


Create(pSize: integer)
  Создает массив размера pSize

Create(params xDatas: array of DataType)
  Создает массив, заполненный элементами, переданными в качестве параметров

Reserve(newCap: integer)
  Выделяет новую память. Емкость увеличивается до newCap
  (Если newCap меньше текущей емкости, ничего не происходит)

Resize(newSize: integer)
  Устанавливает размер массива равным newSize

Add(params xDatas: array of DataType)
  Добавляет элементы, переданные в качестве параметров, в конец массива

Insert(pos: integer; params xDatas: array of DataType)
  Вставляет в массив элементы, переданные в качестве параметров, 
  начиная с позиции pos

Delete(pos: integer; count: integer)
  Удаляет count элементов массива, начиная с позиции pos.
  (По умолчанию удаляется один элемент)

Find(x: DataType): integer
  Возвращает индекс первого элемента массива равного x
  или -1, если такого элемента нет

Find(x: DataType; from: integer): integer
  Возвращает индекс элемента массива равного x, начиная с позиции from,
  или -1, если такого элемента нет

Print(delim: string; elemsInLine: integer)
  Выводит содержимое массива в прямом порядке
  (delim — разделитель между элементами в строке
  elemsInLine — количество элементов, выводимых в одной строке)

PrintReverse(delim: string; elemsInLine: integer)
  Выводит содержимое массива в обратном порядке
  delim — разделитель между элементами в строке
  elemsInLine — количество элементов, выводимых в одной строке)

Println
  Выводит содержимое массива в прямом порядке в каждой строке

PrintlnReverse
  Выводит содержимое массива в прямом порядке в каждой строке

<xh4> Реализация </xh4>

/// Модуль содержит шаблон класса
///   DynArray — динамический массив с автоконтролем памяти
unit DynArrayUnit;

interface
 
const
  /// Ширина поля вывода
  PRINT_FIELD_WIDTH = 5;
  /// Разделитель при выводе элементов
  DELIMETR = '   ';
  /// Количество элементов, выводимых в одной строке при выводе
  ELEMS_IN_LINE = 5;
  
  /// Минимальная емкость, устанавливаемая при создании массива
  MIN_CAP = 4;
  /// Коэффициент увеличения емкости массива при её нехватке
  INC_CAP_FACTOR = 2;
  
type
  /// Шаблон класса DynArray [Динамический массив с автоконтролем памяти]
  DynArray<DataType> = class
  private
    /// Встроенный динамический массив, содержащий данные
    data: array of DataType;
    /// Размер массива
    size: integer;
    /// Емкость массива
    cap: integer;
    
    /// Устанавливает элемент с индексом ind равным x
    procedure SetElem(ind: integer; x: DataType);
    /// Возвращает элемент массива с индексом ind
    function GetElem(ind: integer): DataType;
    
  public
// ---------------------------- Стандартные методы ---------------------------
    /// Создает массив размера pSize
    constructor Create(pSize: integer := 0);
    /// Создает массив, заполненный элементами, переданными в качестве параметров
    constructor Create(params xDatas: array of DataType);
    
    /// Выделяет новую память. Емкость увеличивается до newCap
    /// (Если newCap меньше текущей емкости, ничего не происходит)
    procedure Reserve(newCap: integer);
    /// Устанавливает размер массива равным newSize
    procedure Resize(newSize: integer);
    
    /// Добавляет элементы, переданные в качестве параметров, в конец массива
    procedure Add(params xDatas: array of DataType);
    /// Вставляет в массив элементы, переданные в качестве параметров, 
    /// начиная с позиции pos
    procedure Insert(pos: integer; params xDatas: array of DataType);
    /// Удаляет count элементов массива, начиная с позиции pos.
    /// (По умолчанию удаляется один элемент)
    procedure Delete(pos: integer; count: integer := 1);
    
    /// Возвращает индекс первого элемента массива равного x
    /// или -1, если такого элемента нет
    function Find(x: DataType): integer;
    /// Возвращает индекс элемента массива равного x, начиная с позиции from,
    /// или -1, если такого элемента нет}
    function Find(x: DataType; from: integer): integer;
 // --------------------------------- Свойства --------------------------------
    /// Количество элементов (размер) массива
    property Count: integer read size write Resize;
    /// Емкость массива (отведенная память)
    property Capacity: integer read cap write Reserve;
    /// Позволяет обращаться к элементам массива по индексу 
    /// (например, apples[5])
    property Elem[index: integer]: DataType read GetElem write SetElem; default;
 // ----------------------------- Вывод содержимого ---------------------------
    /// <summary>
    /// Выводит содержимое массива в прямом порядке
    /// </summary>
    /// <param name="delim">Разделитель между элементами в строке</param>
    /// <param name="elemsInLine">Количество элементов, выводимых в одной строке</param>
    procedure Print(delim: string := DELIMETR; elemsInLine: integer := ELEMS_IN_LINE);
    /// <summary>
    /// Выводит содержимое массива в обратном порядке
    /// </summary>
    /// <param name="delim">Разделитель между элементами в строке</param>
    /// <param name="elemsInLine">Количество элементов, выводимых в одной строке</param>
    procedure PrintReverse(delim: string := DELIMETR; elemsInLine: integer := ELEMS_IN_LINE);
    /// Выводит содержимое массива в прямом порядке в каждой строке
    procedure Println;
    /// Выводит содержимое массива в обратном порядке в каждой строке
    procedure PrintlnReverse;
  end;


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

// ---------------------------- Стандартные методы ---------------------------
{Создает массив размера pSize}
constructor DynArray<DataType>.Create(pSize: integer);
begin
  size := pSize;
  cap := INC_CAP_FACTOR*pSize + MIN_CAP; // Устанавливаем емкость "с запасом"
  SetLength(data, cap);
end;
{Создает массив, заполненный элементами, переданными в качестве параметров}
constructor DynArray<DataType>.Create(params xDatas: array of DataType);
begin
  Create(xDatas.Length);  // Сначала нужно создать массив требуемого размера
  
  for var i := 0 to xDatas.Length - 1 do
    data[i] := xDatas[i];
end;

{Выделяет новую память. Емкость увеличивается до newCap
 (Если newCap меньше текущей емкости, ничего не происходит)}
procedure DynArray<DataType>.Reserve(newCap: integer);
begin
  if newCap > cap then 
  begin
    SetLength(data, newCap);
    cap := newCap;
  end;
end;

{Устанавливает размер массива равным newSize}
procedure DynArray<DataType>.Resize(newSize: integer);
begin
  if newSize <= cap then
    size := newSize
  else
  begin
    Reserve(INC_CAP_FACTOR * newSize);
    for var i := size to newSize - 1 do // явным образом заполняем новые элементы
      data[i] := default(DataType);
    size := newSize;
  end;
end;

{Добавляет элементы, переданные в качестве параметров, в конец массива}
procedure DynArray<DataType>.Add(params xDatas: array of DataType);
begin
  Resize(size + xDatas.Length);
  for var i := 0 to xDatas.Length - 1 do
    data[size-xDatas.Length + i] := xDatas[i];
end;

{Вставляет в массив элементы, переданные в качестве параметров, 
 начиная с позиции pos}
procedure DynArray<DataType>.Insert(pos: integer; params xDatas: array of DataType);
begin
  Assert((0 <= pos) and (pos <= size-1));
  
  Resize(size + xDatas.Length);
  for var i := size - 2 downto pos+xDatas.Length - 1 do // сдвиг элементов вправо, начиная с позиции pos
    data[i+1] := data[i-xDatas.Length + 1];
  for var i := 0 to xDatas.Length - 1 do                // заполнение "освободившихся" элементов новыми значениями
    data[pos+i] := xDatas[i];
end;

{Удаляет count элементов массива, начиная с позиции pos.
 (По умолчанию удаляется один элемент)}
procedure DynArray<DataType>.Delete(pos: integer; count: integer);
begin
  Assert((0 <= pos) and (pos <= size-1));
  Assert((0 <= count) and (count <= size));
  
  if (size - pos) < count then          // если количество удаляемых элементов больше,
                                        // чем их осталось до конца массива
    count := size - pos;
  for var i := pos to size-1 - count do // сдвиг элементов влево на count, начиная с позиции pos
    data[i] := data[i + count];
  Resize(size - count);                 // "отрезание" лишних count элементов
end;

{Возвращает индекс первого элемента массива равного x
 или -1, если такого элемента нет}
function DynArray<DataType>.Find(x: DataType): integer;
begin
  result := -1;
  for var i := 0 to size - 1 do
    if data[i] = x then
    begin
      result := i;
      exit;
    end;
end;
{Возвращает индекс элемента массива равного x, начиная с позиции from,
 или -1, если такого элемента нет}
function DynArray<DataType>.Find(x: DataType; from: integer): integer;
begin
  Assert((0 <= from) and (from <= size-1));
  
  result := -1;
  for var i := from to size - 1 do
    if data[i] = x then
    begin
      result := i;
      exit;
    end;
end;

// ---------------------------- Доступ к элементам ---------------------------
{Устанавливает элемент с индексом ind равным x}
procedure DynArray<DataType>.SetElem(ind: integer; x: DataType);
begin
  Assert((0 <= ind) and (ind <= size-1));
  data[ind] := x;
end;
{Возвращает элемент массива с индексом ind}
function DynArray<DataType>.GetElem(ind: integer): DataType;
begin
  Assert((0 <= ind) and (ind <= size-1));
  result := data[ind];
end;

// ----------------------------- Вывод содержимого ---------------------------
{Выводит содержимое массива в прямом порядке
    delim — разделитель между элементами в строке
    elemsInLine — количество элементов, выводимых в одной строке}
procedure DynArray<DataType>.Print(delim: string; elemsInLine: integer);
begin
  for var i := 1 to size do
    if (i mod elemsInLine) <> 0 then
      write(data[i-1]:PRINT_FIELD_WIDTH, delim) 
    else          // если вывели elemsInLine элементов, переходим на новую строку
      writeln(data[i-1]:PRINT_FIELD_WIDTH);
end;
{Выводит содержимое массива в обратном порядке
    delim — разделитель между элементами в строке
    elemsInLine — количество элементов, выводимых в одной строке}
procedure DynArray<DataType>.PrintReverse(delim: string; elemsInLine: integer);
begin
  for var i := 1 to size do
    if (i mod elemsInLine) <> 0 then
      write(data[size-i]:PRINT_FIELD_WIDTH, delim) 
    else          // если вывели elemsInLine элементов, переходим на новую строку
      writeln(data[size-i]:PRINT_FIELD_WIDTH);
end;

{Выводит содержимое массива в прямом порядке в каждой строке}
procedure DynArray<DataType>.Println;
begin
  for var i := 0 to size - 1 do
    writeln(data[i]);
end;
{Выводит содержимое массива в обратном порядке в каждой строке}
procedure DynArray<DataType>.PrintlnReverse;
begin
  for var i := size - 1 downto 0 do
    writeln(data[i]);
end;


end.

Collections

<xh4> Интерфейс </xh4> Stack

Create
  Создает пустой стек

Create(params xDatas: array of DataType)
  Создает стек, заполненный элементами, переданными в качестве параметров
  
Push(x: DataType) 
  Кладет элемент x на вершину стека

Pop: DataType
  Возвращает элемент типа DataType, снимая его с вершины стека
   
Top: DataType
  Возвращает значение элемента на вершине стека

IsEmpty: boolean;
  Возвращает истину, если стек пуст
       
Print(delim: string; elemsInLine: integer)
  Выводит подряд содержимое стека 
  (delim — разделитель между элементами в строке, 
  elemsInLine — количество элементов, выводимых в одной строке)
   
Println
  Выводит содержимое стека в каждой строке

Queue

Create
  Создает пустую очередь

Create(params xDatas: array of DataType)
  Создает очередь, заполненную элементами, переданными в качестве параметров
  
Enqueue(x: DataType) 
  Добавляет элемент x в хвост очереди

Dequeue: DataType
  Возвращает элемент типа DataType, убирая его из головы очереди
   
IsEmpty: boolean;
  Возвращает истину, если очередь пуста
       
Print(delim: string; elemsInLine: integer)
  Выводит подряд содержимое очереди от головы к хвосту
  (delim — разделитель между элементами в строке, 
  elemsInLine — количество элементов, выводимых в одной строке)
   
Println
  Выводит содержимое очереди от головы к хвосту в каждой строке

DynArray

Count
  Количество элементов (размер) массива

Capacity
  Емкость массива (отведенная память)


Create(pSize: integer)
  Создает массив размера pSize

Create(params xDatas: array of DataType)
  Создает массив, заполненный элементами, переданными в качестве параметров

Reserve(newCap: integer)
  Выделяет новую память. Емкость увеличивается до newCap
  (Если newCap меньше текущей емкости, ничего не происходит)

Resize(newSize: integer)
  Устанавливает размер массива равным newSize

Add(params xDatas: array of DataType)
  Добавляет элементы, переданные в качестве параметров, в конец массива

Insert(pos: integer; params xDatas: array of DataType)
  Вставляет в массив элементы, переданные в качестве параметров, 
  начиная с позиции pos

Delete(pos: integer; count: integer)
  Удаляет count элементов массива, начиная с позиции pos.
  (По умолчанию удаляется один элемент)

Find(x: DataType): integer
  Возвращает индекс первого элемента массива равного x
  или -1, если такого элемента нет

Find(x: DataType; from: integer): integer
  Возвращает индекс элемента массива равного x, начиная с позиции from,
  или -1, если такого элемента нет

Print(delim: string; elemsInLine: integer)
  Выводит содержимое массива в прямом порядке
  (delim — разделитель между элементами в строке
  elemsInLine — количество элементов, выводимых в одной строке)

PrintReverse(delim: string; elemsInLine: integer)
  Выводит содержимое массива в обратном порядке
  delim — разделитель между элементами в строке
  elemsInLine — количество элементов, выводимых в одной строке)

Println
  Выводит содержимое массива в прямом порядке в каждой строке

PrintlnReverse
  Выводит содержимое массива в прямом порядке в каждой строке

<xh4> Реализация </xh4>

/// Модуль содержит шаблоны классов
///   Stack — стек
///   Queue — очередь
///   DynArray — динамический массив с автоконтролем памяти
unit Collections;
 
 
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 xDatas : 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---------------------------------------------
const
  /// Сообщение о пустоте очереди
  EMPTY_QUEUE = 'Очередь пуста';
 
type  
  /// Шаблон класса Queue [Очередь]
  Queue<DataType> = class
  private
    /// Голова очереди
    head: SingleNode<DataType>;
    /// Хвост очереди
    tail: SingleNode<DataType>;
 
  public
    // ---------------------------- Стандартные методы ---------------------------
    /// Создает пустую очередь
    constructor Create;
    
    /// Создает очередь, заполненную элементами, переданными в качестве параметров
    constructor Create(params xDatas: array of DataType); 
 
    /// Добавляет элемент x в хвост очереди
    procedure Enqueue(x: DataType);
    
    /// Возвращает элемент типа DataType, убирая его из головы очереди
    function Dequeue: 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;
 
 
 
// --------------------------------------------DYN_ARRAY-------------------------------------------
const
  /// Минимальная емкость, устанавливаемая при создании массива
  MIN_CAP = 4;
  /// Коэффициент увеличения емкости массива при её нехватке
  INC_CAP_FACTOR = 2;
 
type
  /// Шаблон класса DynArray [Динамический массив с автоконтролем памяти]
  DynArray<DataType> = class
  private
    /// Встроенный динамический массив, содержащий данные
    data: array of DataType;
    /// Размер массива
    size: integer;
    /// Емкость массива
    cap: integer;
 
    /// Устанавливает элемент с индексом ind равным x
    procedure SetElem(ind: integer; x: DataType);
    /// Возвращает элемент массива с индексом ind
    function GetElem(ind: integer): DataType;
 
  public
    // ---------------------------- Стандартные методы ---------------------------
    /// Создает массив размера pSize
    constructor Create(pSize: integer := 0);
    
    /// Создает массив, заполненный элементами, переданными в качестве параметров
    constructor Create(params xDatas: array of DataType);
 
    /// Выделяет новую память. Емкость увеличивается до newCap
    /// (Если newCap меньше текущей емкости, ничего не происходит)
    procedure Reserve(newCap: integer);
    
    /// Устанавливает размер массива равным newSize
    procedure Resize(newSize: integer);
 
    /// Добавляет элементы, переданные в качестве параметров, в конец массива
    procedure Add(x: DataType);
    
    /// Добавляет элементы, переданные в качестве параметров, в конец массива
    procedure Add(params xDatas: array of DataType);
    
    /// Вставляет в массив элементы, переданные в качестве параметров, 
    /// начиная с позиции pos
    procedure Insert(pos: integer; params xDatas: array of DataType);
    
    /// Удаляет count элементов массива, начиная с позиции pos.
    /// (По умолчанию удаляется один элемент)
    procedure Delete(pos: integer; count: integer := 1);
 
    /// Возвращает индекс первого элемента массива равного x
    /// или -1, если такого элемента нет
    function Find(x: DataType): integer;
    
    /// Возвращает индекс элемента массива равного x, начиная с позиции from,
    /// или -1, если такого элемента нет}
    
    function Find(x: DataType; from: integer): integer;
    
    // --------------------------------- Свойства --------------------------------
    /// Количество элементов (размер) массива
    property Count: integer read size write Resize;
    /// Емкость массива (отведенная память)
    property Capacity: integer read cap write Reserve;
    /// Позволяет обращаться к элементам массива по индексу 
    /// (например, apples[5])
    property Elem[index: integer]: DataType read GetElem write SetElem; default;
    // ----------------------------- Вывод содержимого ---------------------------
    /// <summary>
    /// Выводит содержимое массива в прямом порядке
    /// </summary>
    /// <param name="delim">Разделитель между элементами в строке</param>
    /// <param name="elemsInLine">Количество элементов, выводимых в одной строке</param>
    procedure Print(delim : string := DELIMETR; elemsInLine : integer := ELEMS_IN_LINE);
    /// <summary>
    /// Выводит содержимое массива в обратном порядке
    /// </summary>
    /// <param name="delim">Разделитель между элементами в строке</param>
    /// <param name="elemsInLine">Количество элементов, выводимых в одной строке</param>
    procedure PrintReverse(delim: string := DELIMETR; elemsInLine: integer := ELEMS_IN_LINE);
    /// Выводит содержимое массива в прямом порядке в каждой строке
    procedure Println;
    /// Выводит содержимое массива в обратном порядке в каждой строке
    procedure PrintlnReverse;
  end;
  
  
// --------------------------------------------SimpleSet-------------------------------------------
type SimpleSet<DataType> = class 
  private
    data:=new DynArray<DataType>;
  public
    /// <summary>
    /// Добавляет элемент в множество
    /// </summary>
    /// <param name="x">Добавляемый элемент</param>    
    procedure Add(x:DataType);
          
    /// <summary>
    /// Удаляет элемент из множества
    /// </summary>
    /// <param name="x">Удаляемый элемент</param>
    procedure Remove(x:DataType);
          
    /// <summary>
    /// Проверяет, содержит ли множество элемент
    /// </summary>
    /// <param name="x">Искомый элемент</param>          
    function Contains(x:DataType):boolean;    
    
    ///Выводит содержимое множества на консоль
    procedure Print();
    
    ///Выводит содержимое множества на консоль
    procedure Println();
end;
  
  
  
  
  
  
 // ================================================================= IMPLEMENTATION ===================================================================
implementation
 
 
 
// ----------------------------------------------STACK---------------------------------------------
 
// ---------------------------- Стандартные методы ---------------------------
{Стандартный конструктор}
constructor Stack<DataType>.Create;
begin
  fTop := nil;
end;
 
{Создает стек, заполненный элементами, переданными в качестве параметров}
constructor Stack<DataType>.Create(params xDatas: array of DataType); 
begin
  fTop := nil;
  for var i := 0 to xDatas.Length - 1 do
    Push(xDatas[i]);
end;
 
{Кладет элемент x на вершину стека} 
procedure Stack<DataType>.Push(x: DataType);
begin
  fTop := new SingleNode<DataType>(x, fTop);
end;
 
{Возвращает элемент типа DataType, снимая его с вершины стека}
function Stack<DataType>.Pop: DataType;
begin
  if IsEmpty then 
     raise new Exception('Попытка снятия элемента с пустого стека!');
  result := fTop.data;
  fTop := fTop.next;  // элемент снимается с вершины стека
                      // (т.е. вершиной становится следующий элемент)
end;
 
{Возвращает значение элемента на вершине стека}
function Stack<DataType>.Top: DataType;
begin
  if IsEmpty then 
     raise new Exception('Попытка получения элемента с пустого стека!');
  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;
 
{Создает очередь, заполненную элементами, переданными в качестве параметров}
constructor Queue<DataType>.Create(params xDatas: array of DataType); 
begin
  head := nil;
  tail := nil;
  for var i := 0 to xDatas.Length - 1 do
    Enqueue(xDatas[i]);
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
  if IsEmpty then 
     raise new Exception('Попытка удаления элемента из пустой очереди!');
  result := head.data;
 
  head := head.next;  // элемент убирается из головы очереди
                      // (т.е. головой становится следующий элемент)
  if head = nil then
    tail := nil;
end;

{Возвращает элемент типа DataType, не убирая его из головы очереди}
function Queue<DataType>.Top: DataType;
begin
  if IsEmpty then 
     raise new Exception('Попытка получения элемента из пустой очереди!');
  result := head.data;
end;

{Возвращает истину, если очередь пуста}
function Queue<DataType>.IsEmpty: boolean;
begin
  result := (head = nil);
  if result then
    Assert(tail = nil);
end;
 
// ----------------------------- Вывод содержимого ---------------------------
{Выводит подряд содержимое очереди от головы к хвосту
    delim — разделитель между элементами в строке
    elemsInLine — количество элементов, выводимых в одной строке}
procedure Queue<DataType>.Print(delim: string; elemsInLine: integer);
begin
  if IsEmpty then
    writeln(EMPTY_QUEUE)
  else
  begin
    var elemsInd := 1;  // индекс элемента стека
                        // нужен для вывода по строкам
    var curElem := head;
    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 Queue<DataType>.Println;
begin
  if IsEmpty then
    writeln(EMPTY_QUEUE)
  else
  begin
    var curElem := head;
    while curElem <> nil do
    begin
      writeln(curElem.data:PRINT_FIELD_WIDTH);
      curElem := curElem.next;;
    end;
  end;
end;
 
 
 
// --------------------------------------------DYN_ARRAY-------------------------------------------    
 
// ---------------------------- Стандартные методы ---------------------------
{Создает массив размера pSize}
constructor DynArray<DataType>.Create(pSize: integer);
begin
  size := pSize;
  cap := INC_CAP_FACTOR*pSize + MIN_CAP; // Устанавливаем емкость "с запасом"
  SetLength(data, cap);
end;
 
{Создает массив, заполненный элементами, переданными в качестве параметров}
constructor DynArray<DataType>.Create(params xDatas: array of DataType);
begin
  Create(xDatas.Length);  // Сначала нужно создать массив требуемого размера
 
  for var i := 0 to xDatas.Length - 1 do
    data[i] := xDatas[i];
end;
 
{Выделяет новую память. Емкость увеличивается до newCap
 (Если newCap меньше текущей емкости, ничего не происходит)}
procedure DynArray<DataType>.Reserve(newCap: integer);
begin
  if newCap > cap then 
  begin
    SetLength(data, newCap);
    cap := newCap;
  end;
end;
 
{Устанавливает размер массива равным newSize}
procedure DynArray<DataType>.Resize(newSize: integer);
begin
  if newSize <= cap then
    size := newSize
  else
  begin
    Reserve(INC_CAP_FACTOR * newSize);
    for var i := size to newSize - 1 do // явным образом заполняем новые элементы
      data[i] := default(DataType);
    size := newSize;
  end;
end;
 
{Добавляет элемент в конец массива}
procedure DynArray<DataType>.Add(x: DataType);
begin
  Resize(size + 1);
  data[size-1] := x;
end;
 
{Добавляет элементы, переданные в качестве параметров, в конец массива}
procedure DynArray<DataType>.Add(params xDatas: array of DataType);
begin
  Resize(size + xDatas.Length);
  for var i := 0 to xDatas.Length - 1 do
    data[size-xDatas.Length + i] := xDatas[i];
end;
 
{Вставляет в массив элементы, переданные в качестве параметров, 
 начиная с позиции pos}
procedure DynArray<DataType>.Insert(pos: integer; params xDatas: array of DataType);
begin
  if (pos < 0) or (pos > size-1) then 
     raise new Exception('Попытка вставки за границей массива в позицию ' + IntToStr(pos) + ' !');
  Resize(size + xDatas.Length);
  for var i := size - 2 downto pos+xDatas.Length - 1 do // сдвиг элементов вправо, начиная с позиции pos
    data[i+1] := data[i-xDatas.Length + 1];
  for var i := 0 to xDatas.Length - 1 do                // заполнение "освободившихся" элементов новыми значениями
    data[pos+i] := xDatas[i];
end;
 
{Удаляет count элементов массива, начиная с позиции pos.
 (По умолчанию удаляется один элемент)}
procedure DynArray<DataType>.Delete(pos: integer; count: integer);
begin
  if (pos < 0) or (pos > size-1) then 
     raise new Exception('Попытка удаления за границей массива из позиции ' + IntToStr(pos) + ' !');
     
  Assert((0 <= count) and (count <= size));
 
  if (size - pos) < count then          // если количество удаляемых элементов больше,
                                        // чем их осталось до конца массива
    count := size - pos;
  for var i := pos to size-1 - count do // сдвиг элементов влево на count, начиная с позиции pos
    data[i] := data[i + count];
  Resize(size - count);                 // "отрезание" лишних count элементов
end;
 
{Возвращает индекс первого элемента массива равного x
 или -1, если такого элемента нет}
function DynArray<DataType>.Find(x: DataType): integer;
begin
  result := -1;
  for var i := 0 to size - 1 do
    if data[i] = x then
    begin
      result := i;
      exit;
    end;
end;
 
{Возвращает индекс элемента массива равного x, начиная с позиции from,
 или -1, если такого элемента нет}
function DynArray<DataType>.Find(x: DataType; from: integer): integer;
begin
  if (from < 0) or (from > size-1) then 
     raise new Exception('Попытка поиска за границей массива с позиции ' + IntToStr(from) + ' !');
 
  result := -1;
  for var i := from to size - 1 do
    if data[i] = x then
    begin
      result := i;
      exit;
    end;
end;
 
// ---------------------------- Доступ к элементам ---------------------------
{Устанавливает элемент с индексом ind равным x}
procedure DynArray<DataType>.SetElem(ind: integer; x: DataType);
begin
  if (ind < 0) or (ind > size-1) then 
     raise new Exception('Попытка установки элемента за границей массива из позиции ' + IntToStr(ind) + ' !');
  data[ind] := x;
end;
 
{Возвращает элемент массива с индексом ind}
function DynArray<DataType>.GetElem(ind: integer): DataType;
begin
  if (ind < 0) or (ind > size-1) then 
     raise new Exception('Попытка получения элемента за границей массива из позиции ' + IntToStr(ind) + ' !');
  result := data[ind];
end;
 
// ----------------------------- Вывод содержимого ---------------------------
{Выводит содержимое массива в прямом порядке
    delim — разделитель между элементами в строке
    elemsInLine — количество элементов, выводимых в одной строке}
procedure DynArray<DataType>.Print(delim: string; elemsInLine: integer);
begin
  for var i := 1 to size do
    if (i mod elemsInLine) <> 0 then
      write(data[i-1]:PRINT_FIELD_WIDTH, delim) 
    else          // если вывели elemsInLine элементов, переходим на новую строку
      writeln(data[i-1]:PRINT_FIELD_WIDTH);
end;
 
{Выводит содержимое массива в обратном порядке
    delim — разделитель между элементами в строке
    elemsInLine — количество элементов, выводимых в одной строке}
procedure DynArray<DataType>.PrintReverse(delim: string; elemsInLine: integer);
begin
  for var i := 1 to size do
    if (i mod elemsInLine) <> 0 then
      write(data[size-i]:PRINT_FIELD_WIDTH, delim) 
    else          // если вывели elemsInLine элементов, переходим на новую строку
      writeln(data[size-i]:PRINT_FIELD_WIDTH);
end;
 
{Выводит содержимое массива в прямом порядке в каждой строке}
procedure DynArray<DataType>.Println;
begin
  for var i := 0 to size - 1 do
    writeln(data[i]);
end;
 
{Выводит содержимое массива в обратном порядке в каждой строке}
procedure DynArray<DataType>.PrintlnReverse;
begin
  for var i := size - 1 downto 0 do
    writeln(data[i]);
end;
 
 
 
// --------------------------------------------SimpleSet-------------------------------------------  
{Удаляет элемент из множества}
procedure SimpleSet<DataType>.Remove(x:DataType);
begin
  if data.Find(x)<>-1 then
    data.Delete(data.Find(x),1);
end;

{Добавляет элемент во множество}     
procedure SimpleSet<DataType>.Add(x:DataType);
begin
  if data.Find(x)=-1 then 
    data.Add(x);
end;

{Определяет, содержится ли элемент во множестве}    
function SimpleSet<DataType>.Contains(x:DataType):boolean;
begin
  result:=data.Find(x)<>-1;
end;
     
{Печатает множество}     
procedure SimpleSet<DataType>.Print();
begin 
  data.print(DELIMETR,ELEMS_IN_LINE);
end;

{Печатает множество}     
procedure SimpleSet<DataType>.Println();
begin 
  data.Println();
end;


end.

Collections (Full Version)

Содержание

Вспомогательные модули

Nodes

Составляющие классы

Stack

Queue

DynArray

Collections

Навигация

Просмотры

Персональные инструменты

Навигация

Поиск

Инструменты