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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
(DynArray)
м Unit Collections» переименована в «Collections»)
 
(не показано 50 промежуточных версий 3 участников)
Строка 1: Строка 1:
 +
[[Категория:Коды]]
 
__TOC__
 
__TOC__
== Вспомогательные модули ==
+
== Collections ==
=== Nodes ===
 
 
<source lang="Delphi">
 
<source lang="Delphi">
 
/// Модуль содержит шаблоны классов
 
/// Модуль содержит шаблоны классов
///  SingleNode узла с одним полем связи
+
///  Stack стек
///  DoubleNode узла с двумя полями связи
+
///  Queue очередь
unit Nodes;
+
///  DynArray — динамический массив
 
+
///  SimpleSet — простое множество на основе динамического массива
 +
///  AssocArray — простой ассоциативный массив на основе динамического массива пар
 +
///  LinkedList — двусвязный список
 +
unit Collections;
 +
 
interface
 
interface
 
+
 +
// -------------------------------- SingleNode ---------------------------------
 
type
 
type
 
//-------------------------------------------SINGLE_NODE-------------------------------------------
 
 
   /// Узел с одним полем связи
 
   /// Узел с одним полем связи
   SingleNode<DataType> = class
+
   SingleNode<T> = class
     /// Значение узла
+
  private
     data: DataType;
+
     /// Значение, содержащееся в узле
 +
     fData: T;
 
     /// Ссылка на следующий элемент
 
     /// Ссылка на следующий элемент
     next: SingleNode<DataType>;
+
     fNext: SingleNode<T>;
   
+
  public
 
     /// <summary>
 
     /// <summary>
     /// Конструктор
+
     /// Создает узел с одним полем связи
 
     /// </summary>
 
     /// </summary>
     /// <param name="pData">Значение узла</param>
+
     /// <param name="pData">Значение в узле</param>
 
     /// <param name="pNext">Ссылка на следующий элемент</param>
 
     /// <param name="pNext">Ссылка на следующий элемент</param>
     constructor Create(pData: DataType; pNext: SingleNode<DataType>);
+
     constructor Create(data: T; next: SingleNode<T>);
  end;
+
    begin
 
+
      fData := data;
// -------------------------------------------DOUBLE_NODE------------------------------------------ 
+
      fNext := next;
  /// Узел с двумя полями связи
+
    end;
  DoubleNode<DataType> = class
+
     /// Значение, содержащееся в узле
     /// Значение узла
+
     property Data: T read fData write fData;
     data: DataType;
 
 
     /// Ссылка на следующий элемент
 
     /// Ссылка на следующий элемент
     next: DoubleNode<DataType>;
+
     property Next: SingleNode<T> read fNext write fNext;
    /// Ссылка на предыдущий элемент
+
   end;  
    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.
 
</source>
 
 
 
== Составляющие классы ==
 
=== 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>
 
<source lang="Delphi">
 
/// Модуль содержит шаблон класса
 
///  Stack — стек
 
unit StackUnit;
 
 
 
interface
 
 
 
uses Nodes;  // для использования типа SingleNode<DataType> —
 
              // узла с одним полем связи
 
             
 
const
 
  /// Ширина поля вывода
 
  PRINT_FIELD_WIDTH = 5;
 
  /// Разделитель при выводе элементов
 
  DELIMETR = '  ';
 
  /// Количество элементов, выводимых в одной строке при выводе
 
  ELEMS_IN_LINE = 5;
 
 
  /// Сообщение о пустоте стека
 
  EMPTY_STACK = 'Стек пуст';
 
 
   
 
   
 +
// ----------------------------------- Stack -----------------------------------
 
type
 
type
   /// Шаблон класса Stack [Стек]
+
   /// Шаблон класса Stack
   Stack<DataType> = class
+
   Stack<T> = class
 
   private  
 
   private  
 
     /// Вершина стека
 
     /// Вершина стека
     fTop: SingleNode<DataType> := nil;   // field Top
+
     fTop: SingleNode<T> := nil;  
   
 
 
   public  
 
   public  
// ---------------------------- Стандартные методы ---------------------------
 
 
     /// Создает пустой стек
 
     /// Создает пустой стек
 
     constructor Create;
 
     constructor Create;
     /// Создает стек, заполненный элементами, переданными в качестве параметров
+
     /// <summary>
    constructor Create(params xDatas: array of DataType);
 
 
 
     /// Кладет элемент x на вершину стека
 
     /// Кладет элемент x на вершину стека
     procedure Push(x: DataType);
+
    /// </summary>
     /// Возвращает элемент типа DataType, снимая его с вершины стека
+
    /// <param name="x">Новый элемент</param>
     function Pop: DataType;
+
     procedure Push(x: T);
     /// Возвращает значение элемента на вершине стека
+
     /// Возвращает значение элемента на вершине, снимая его со стека
     function Top: DataType;
+
     function Pop: T;  
   
+
     /// Возвращает значение элемента на вершине стека, не снимая его
 +
     function Top: T;
 
     /// Возвращает истину, если стек пуст
 
     /// Возвращает истину, если стек пуст
     function IsEmpty: boolean;  
+
     function IsEmpty: boolean;  
// ----------------------------- Вывод содержимого ---------------------------
+
     /// Преобразует содержимое стека в строку
    /// <summary>
+
     function ToString: string; override;
     /// Выводит подряд содержимое стека
+
     /// Выводит содержимое стека на консоль
     /// </summary>
+
     procedure Print;
     /// <param name="delim">Разделитель между элементами в строке</param>
+
     /// Выводит содержимое стека на консоль с переходом на новую строку
    /// <param name="elemsInLine">Количество элементов, выводимых в одной строке</param>
 
     procedure Print(delim: string := DELIMETR; elemsInLine: integer := ELEMS_IN_LINE);
 
     /// Выводит содержимое стека в каждой строке
 
 
     procedure Println;
 
     procedure Println;
 
   end;
 
   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;
 
 
   
 
   
{Выводит содержимое стека в каждой строке}
+
// ----------------------------------- Queue -----------------------------------
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.
 
</source>
 
 
 
=== 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>
 
<source lang="Delphi">
 
/// Модуль содержит шаблон класса
 
//Queue — очередь
 
unit QueueUnit;
 
 
 
interface
 
 
 
uses Nodes;  // для использования типа SingleNode<DataType> —
 
              // узла с одним полем связи
 
 
 
 
const
 
  /// Ширина поля вывода
 
  PRINT_FIELD_WIDTH = 5;
 
  /// Разделитель при выводе элементов
 
  DELIMETR = '  ';
 
  /// Количество элементов, выводимых в одной строке при выводе
 
  ELEMS_IN_LINE = 5;
 
 
 
  /// Сообщение о пустоте очереди
 
  EMPTY_QUEUE = 'Очередь пуста';
 
 
 
 
type   
 
type   
   /// Шаблон класса Queue [Очередь]
+
   /// Шаблон класса Queue
   Queue<DataType> = class
+
   Queue<T> = class
 
   private
 
   private
 
     /// Голова очереди
 
     /// Голова очереди
     head: SingleNode<DataType>;
+
     fHead: SingleNode<T>;
 
     /// Хвост очереди
 
     /// Хвост очереди
     tail: SingleNode<DataType>;
+
     fTail: SingleNode<T>;
   
 
 
   public
 
   public
// ---------------------------- Стандартные методы ---------------------------
 
 
     /// Создает пустую очередь
 
     /// Создает пустую очередь
 
     constructor Create;
 
     constructor Create;
     /// Создает очередь, заполненную элементами, переданными в качестве параметров
+
     /// <summary>
    constructor Create(params xDatas: array of DataType);
 
   
 
 
     /// Добавляет элемент x в хвост очереди
 
     /// Добавляет элемент x в хвост очереди
     procedure Enqueue(x: DataType);
+
    /// </summary>
     /// Возвращает элемент типа DataType, убирая его из головы очереди
+
    /// <param name="x">Добавляемый элемент</param>
     function Dequeue: DataType;
+
     procedure Enqueue(x: T);
 +
     /// Возвращает значение элемента в голове, удаляя его из очереди
 +
     function Dequeue: T;
 +
    /// Возвращает значение элемента в голове очереди, не удаляя его
 +
    function First: T;
 
     /// Возвращает истину, если очередь пуста
 
     /// Возвращает истину, если очередь пуста
   
 
 
     function IsEmpty: boolean;
 
     function IsEmpty: boolean;
// ----------------------------- Вывод содержимого ---------------------------
+
     /// Преобразует содержимое очереди в строку
    /// <summary>
+
     function ToString: string; override;
     /// Выводит подряд содержимое очереди от головы к хвосту
+
     /// Выводит содержимое очереди на консоль
     /// </summary>
+
     procedure Print;
     /// <param name="delim">Разделитель между элементами в строке</param>
+
     /// Выводит содержимое очереди на консоль с переходом на новую строку
    /// <param name="elemsInLine">Количество элементов, выводимых в одной строке</param>
 
     procedure Print(delim: string := DELIMETR; elemsInLine: integer := ELEMS_IN_LINE);
 
     /// Выводит содержимое очереди от головы к хвосту в каждой строке
 
 
     procedure Println;
 
     procedure Println;
 
   end;
 
   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.
 
</source>
 
 
=== 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>
 
<source lang="Delphi">
 
/// Модуль содержит шаблон класса
 
///  DynArray — динамический массив с автоконтролем памяти
 
unit DynArrayUnit;
 
 
interface
 
 
   
 
   
 +
// --------------------------------- DynArray ----------------------------------
 
const
 
const
  /// Ширина поля вывода
 
  PRINT_FIELD_WIDTH = 5;
 
  /// Разделитель при выводе элементов
 
  DELIMETR = '  ';
 
  /// Количество элементов, выводимых в одной строке при выводе
 
  ELEMS_IN_LINE = 5;
 
 
 
 
   /// Минимальная емкость, устанавливаемая при создании массива
 
   /// Минимальная емкость, устанавливаемая при создании массива
 
   MIN_CAP = 4;
 
   MIN_CAP = 4;
 
   /// Коэффициент увеличения емкости массива при её нехватке
 
   /// Коэффициент увеличения емкости массива при её нехватке
 
   INC_CAP_FACTOR = 2;
 
   INC_CAP_FACTOR = 2;
 
+
 
type
 
type
   /// Шаблон класса DynArray [Динамический массив с автоконтролем памяти]
+
   /// Шаблон класса DynArray (Динамический массив с автоконтролем памяти)
   DynArray<DataType> = class
+
   DynArray<T> = class
 
   private
 
   private
 
     /// Встроенный динамический массив, содержащий данные
 
     /// Встроенный динамический массив, содержащий данные
     data: array of DataType;
+
     fData: array of T;
 
     /// Размер массива
 
     /// Размер массива
     size: integer;
+
     fSize: integer;
 
     /// Емкость массива
 
     /// Емкость массива
     cap: integer;
+
     fCap: integer;
   
+
     /// Устанавливает элемент с индексом index равным x
     /// Устанавливает элемент с индексом ind равным x
+
     procedure SetElem(index: integer; x: T);
     procedure SetElem(ind: integer; x: DataType);
+
     /// Возвращает элемент массива с индексом index
     /// Возвращает элемент массива с индексом ind
+
     function GetElem(index: integer): T;
     function GetElem(ind: integer): DataType;
 
   
 
 
   public
 
   public
// ---------------------------- Стандартные методы ---------------------------
+
     /// Создает пустой массив
     /// Создает массив размера pSize
+
     constructor Create;
     constructor Create(pSize: integer := 0);
+
     /// Создает массив размера size
     /// Создает массив, заполненный элементами, переданными в качестве параметров
+
     constructor Create(size: integer);
     constructor Create(params xDatas: array of DataType);
+
     /// <summary>
      
+
     /// Выделяет новую память. Емкость увеличивается до NewSize.
     /// Выделяет новую память. Емкость увеличивается до newCap
+
     /// (Если newCap меньше текущей емкости, ничего не происходит)  
     /// (Если newCap меньше текущей емкости, ничего не происходит)
+
    /// </summary>
 +
    /// <param name="newCap">Новая емкость массива</param>
 
     procedure Reserve(newCap: integer);
 
     procedure Reserve(newCap: integer);
     /// Устанавливает размер массива равным newSize
+
    /// <summary>
 +
     /// Устанавливает новый размер массива равным newSize
 +
    /// </summary>
 +
    /// <param name="newSize">Новый размер массива</param>
 
     procedure Resize(newSize: integer);
 
     procedure Resize(newSize: integer);
      
+
     /// <summary>
     /// Добавляет элементы, переданные в качестве параметров, в конец массива
+
     /// Добавляет элемент x в конец массива  
     procedure Add(params xDatas: array of DataType);
+
    /// </summary>
     /// Вставляет в массив элементы, переданные в качестве параметров,
+
    /// <param name="x">Добавляемый элемент</param>
     /// начиная с позиции pos
+
     procedure Add(x: T);
     procedure Insert(pos: integer; params xDatas: array of DataType);
+
    /// <summary>
     /// Удаляет count элементов массива, начиная с позиции pos.
+
     /// Вставляет элемент x в указанную позицию pos
     /// (По умолчанию удаляется один элемент)
+
    /// </summary>
     procedure Delete(pos: integer; count: integer := 1);
+
    /// <param name="pos">Позиция, в которую вставляется элемент</param>
      
+
     /// <param name="x">Вставляемый элемент</param>
 +
     procedure Insert(pos: integer; x: T);
 +
    /// <summary>
 +
     /// Удаляет элемент массива из указанной позиции pos
 +
     /// </summary>
 +
    /// <param name="pos">Позиция, из которой удаляется элемент</param>
 +
     procedure Remove(pos: integer);
 +
     /// <summary>
 
     /// Возвращает индекс первого элемента массива равного x
 
     /// Возвращает индекс первого элемента массива равного x
 
     /// или -1, если такого элемента нет
 
     /// или -1, если такого элемента нет
     function Find(x: DataType): integer;
+
     /// </summary>
    /// Возвращает индекс элемента массива равного x, начиная с позиции from,
+
     /// <param name="x">Искомый элемент</param>
     /// или -1, если такого элемента нет}
+
     function Find(x: T): integer;
     function Find(x: DataType; from: integer): integer;
 
// --------------------------------- Свойства --------------------------------
 
 
     /// Количество элементов (размер) массива
 
     /// Количество элементов (размер) массива
     property Count: integer read size write Resize;
+
     property Count: integer read fSize write Resize;
     /// Емкость массива (отведенная память)
+
     /// Емкость массива  
     property Capacity: integer read cap write Reserve;
+
     property Capacity: integer read fCap write Reserve;
 
     /// Позволяет обращаться к элементам массива по индексу  
 
     /// Позволяет обращаться к элементам массива по индексу  
    /// (например, apples[5])
+
     property Elem[index: integer]: T read GetElem write SetElem; default;
     property Elem[index: integer]: DataType read GetElem write SetElem; default;
+
    /// Преобразует содержимое массива в строку
  // ----------------------------- Вывод содержимого ---------------------------
+
    function ToString: string; override;
 +
    /// Выводит содержимое массива на консоль
 +
    procedure Print;
 +
    /// Выводит содержимое массива на консоль с переходом на новую строку
 +
    procedure Println;
 +
  end;
 +
   
 +
// -------------------------------- SimpleSet ----------------------------------
 +
type
 +
  /// Шаблон класса SimpleSet (Простое множество на основе динамического массива)
 +
  SimpleSet<T> = class
 +
  private
 +
    /// Элементы множества
 +
    fData: DynArray<T>;
 +
  public
 +
    /// Создает множество
 +
    constructor Create;
 +
    /// <summary>
 +
    /// Добавляет элемент x во множество, если его там еще нет
 +
    /// </summary>
 +
    /// <param name="x">Добавляемый элемент</param>   
 +
    procedure Add(x: T);
 
     /// <summary>
 
     /// <summary>
     /// Выводит содержимое массива в прямом порядке
+
     /// Удаляет элемент x из множества, если он там есть
 
     /// </summary>
 
     /// </summary>
     /// <param name="delim">Разделитель между элементами в строке</param>
+
     /// <param name="x">Удаляемый элемент</param>
    /// <param name="elemsInLine">Количество элементов, выводимых в одной строке</param>
+
     procedure Remove(x: T);
     procedure Print(delim: string := DELIMETR; elemsInLine: integer := ELEMS_IN_LINE);
 
 
     /// <summary>
 
     /// <summary>
     /// Выводит содержимое массива в обратном порядке
+
     /// Возвращает истину, если множество содержит элемент x
 
     /// </summary>
 
     /// </summary>
     /// <param name="delim">Разделитель между элементами в строке</param>
+
     /// <param name="x">Искомый элемент</param>        
     /// <param name="elemsInLine">Количество элементов, выводимых в одной строке</param>
+
    function Contains(x: T): boolean; 
     procedure PrintReverse(delim: string := DELIMETR; elemsInLine: integer := ELEMS_IN_LINE);
+
    /// Преобразует содержимое массива в строку
     /// Выводит содержимое массива в прямом порядке в каждой строке
+
    function ToString: string; override;
 +
     /// Выводит содержимое массива на консоль
 +
    procedure Print;
 +
    /// Выводит содержимое множества на консоль с переходом на новую строку
 +
    procedure Println;
 +
end;
 +
 +
// -------------------------------- AssocArray ---------------------------------
 +
type
 +
  /// Шаблон класса AssocArray
 +
  AssocArray<KeyType, ValueType> = class
 +
  private
 +
    /// Ключи
 +
    fKeys: DynArray<KeyType>;
 +
    /// Значения, соответствующие ключам
 +
    fValues: DynArray<ValueType>;
 +
 
 +
    /// Устанавливает значение элемента с ключом key равным value
 +
     procedure SetElem(key: KeyType; value: ValueType);
 +
    /// Возвращает значение элемента с ключом key
 +
    function GetElem(key: KeyType): ValueType;
 +
  public
 +
    /// Создает ассоциативный массив
 +
    constructor Create;
 +
    /// Позволяет обращаться к элементам массива по ключу
 +
    property Elem[key: KeyType]: ValueType read GetElem write SetElem; default;
 +
    /// Преобразует содержимое ассоциативного массива в строку
 +
    function ToString: string; override;
 +
    /// Выводит содержимое ассоциативного массива на консоль
 +
    procedure Print;
 +
     /// Выводит содержимое ассоциативного массива на консоль с переходом на новую строку
 
     procedure Println;
 
     procedure Println;
    /// Выводит содержимое массива в обратном порядке в каждой строке
 
    procedure PrintlnReverse;
 
 
   end;
 
   end;
 
+
 
+
// ----------------------------- LinkedListNode --------------------------------
// ================================================================= IMPLEMENTATION ===================================================================
+
type
 +
  /// Узел с двумя полями связи
 +
  LinkedListNode<T> = class
 +
  private
 +
    /// Значение, содержащееся в узле
 +
    fData: T;
 +
    /// Ссылка на предыдущий элемент
 +
    fPrev: LinkedListNode<T>;
 +
    /// Ссылка на следующий элемент
 +
    fNext: LinkedListNode<T>;
 +
  public
 +
    /// <summary>
 +
    /// Создает новый узел
 +
    /// </summary>
 +
    /// <param name="T">Значение узла</param>
 +
    /// <param name="Prev">Ссылка на предыдущий элемент</param>
 +
    /// <param name="Next">Ссылка на следующий элемент</param>
 +
    constructor Create(data: T; prev, next: LinkedListNode<T>);
 +
    begin
 +
      fData := data;
 +
      fNext := next;
 +
      fPrev := prev;
 +
    end;
 +
    /// Значение, содержащееся в узле
 +
    property Value: T read fData write fData;
 +
    /// Ссылка на предыдущий элемент — только на чтение
 +
    property Prev: LinkedListNode<T> read fPrev;
 +
    /// Ссылка на следующий элемент — только на чтение
 +
    property Next: LinkedListNode<T> read fNext;
 +
  end;
 +
 
 +
 
 +
// -------------------------------- LinkedList ---------------------------------
 +
type
 +
  /// Двусвязный линейный список
 +
  LinkedList<T> = class
 +
  private
 +
    /// Первый элемент (голова)
 +
    fFirst: LinkedListNode<T>;
 +
    /// Последний элемент (хвост)
 +
    fLast: LinkedListNode<T>;
 +
  public
 +
    /// Создает пустой список
 +
    constructor Create;
 +
    /// Первый элемент (голова) — только на чтение
 +
    property First: LinkedListNode<T> read fFirst;
 +
    /// Последний элемент (хвост) — только на чтение
 +
    property Last: LinkedListNode<T> read fLast;
 +
    /// <summary>
 +
    /// Добавляет элемент x в начало списка
 +
    /// </summary>
 +
    /// <param name="x">Добавляемый элемент</param>
 +
    procedure AddFirst(x: T);
 +
    /// <summary>
 +
    /// Добавляет элемент x в конец списка
 +
    /// </summary>
 +
    /// <param name="x">Добавляемый элемент</param>
 +
    procedure AddLast(x: T);
 +
    /// Удаляет первый элемент списка
 +
    procedure RemoveFirst();
 +
    /// Удаляет последний элемент списка
 +
    procedure RemoveLast();
 +
    /// <summary>
 +
    /// Добавляет элемент x перед node
 +
    /// </summary>
 +
    /// <param name="node">Ссылка на элемент, перед которым нужно добавить новый</param>
 +
    /// <param name="x">Добавляемый элемент</param>
 +
    procedure AddBefore(node: LinkedListNode<T>; x: T);
 +
    /// <summary>
 +
    /// Добавляет элемент x после node
 +
    /// </summary>
 +
    /// <param name="node">Ссылка на элемент, после которого нужно добавить новый</param>
 +
    /// <param name="x">Добавляемый элемент</param>
 +
    procedure AddAfter(node: LinkedListNode<T>; x: T);
 +
    /// <summary>
 +
    /// Удаляет элемент node
 +
    /// </summary>
 +
    /// <param name="node">Ссылка на элемент, который нужно удалить</param>
 +
    procedure Remove(node: LinkedListNode<T>);
 +
    /// Преобразует содержимое списка в строку
 +
    function ToString: string; override;
 +
    /// Выводит содержимое списка на консоль
 +
    procedure Print;
 +
    /// Выводит содержимое списка на консоль с переходом на новую строку
 +
    procedure Println;
 +
  end;
 +
 +
//==============================================================================
 
implementation
 
implementation
 
+
// ---------------------------- Стандартные методы ---------------------------
+
//Сообщения исключений
{Создает массив размера pSize}
+
const PopNilStackExceptionMessage = 'Попытка снятия элемента с пустого стека';
constructor DynArray<DataType>.Create(pSize: integer);
+
TopNilStackExceptionMessage = 'Попытка получения элемента с пустого стека';
 +
       
 +
DequeueNilQueueExceptionMessage = 'Попытка удаления элемента из пустой очереди';
 +
FirstNilQueueExceptionMessage = 'Попытка получения элемента из пустой очереди';
 +
       
 +
NegativeArraySizeExceptionMessage = 'Попытка присвоить размеру массива отрицательное значение ';
 +
      InsOutOfArrayBoundExceptionMessage ='Попытка вставки за границей массива в позицию ';
 +
      RemOutOfArrayBoundExceptionMessage ='Попытка удаления за границей массива из позиции ';
 +
      SetElemOutOfBoundExceptionMessage = 'Попытка присвоить значение элементу за границей массива с индексом ';
 +
      GetElemOutOfBoundExceptionMessage = 'Попытка получить значение элемента за границей массива с индексом ';
 +
     
 +
RemoveFromNilListExceptionMessage = 'Попытка удаления из пустого списка';
 +
AddNilNodeExceptionMessage = 'Параметр node является нулевой ссылкой';
 +
RemoveNilNodeExceptionMessage = 'Параметр node является нулевой ссылкой';
 +
 +
// ----------------------------------- Stack -----------------------------------
 +
constructor Stack<T>.Create;
 +
begin
 +
  fTop := nil;
 +
end;
 +
 +
procedure Stack<T>.Push(x: T);
 +
begin
 +
  fTop := new SingleNode<T>(x, fTop);
 +
end;
 +
 +
function Stack<T>.Pop: T;
 
begin
 
begin
   size := pSize;
+
   if IsEmpty then
   cap := 2*pSize + MIN_CAP; // Устанавливаем емкость "с запасом"
+
    raise new Exception(PopNilStackExceptionMessage);
  SetLength(data, cap);
+
 +
  Result := fTop.data;
 +
   fTop := fTop.next; // элемент удаляется из вершины стека (т.е. вершиной становится следующий элемент)
 
end;
 
end;
{Создает массив, заполненный элементами, переданными в качестве параметров}
+
constructor DynArray<DataType>.Create(params xDatas: array of DataType);
+
function Stack<T>.Top: T;
 
begin
 
begin
   Create(xDatas.Length);  // Сначала нужно создать массив требуемого размера
+
   if IsEmpty then
 
+
    raise new Exception(TopNilStackExceptionMessage);
   for var i := 0 to xDatas.Length - 1 do
+
   
    data[i] := xDatas[i];
+
   Result := fTop.data;
 
end;
 
end;
  
{Выделяет новую память. Емкость увеличивается до newCap
+
function Stack<T>.IsEmpty: boolean;
(Если newCap меньше текущей емкости, ничего не происходит)}
 
procedure DynArray<DataType>.Reserve(newCap: integer);
 
 
begin
 
begin
   if newCap > cap then
+
   Result := (fTop = nil);
  begin
 
    SetLength(data, newCap);
 
    cap := newCap;
 
  end;
 
 
end;
 
end;
 
+
{Устанавливает размер массива равным newSize}
+
function Stack<T>.ToString: string;
procedure DynArray<DataType>.Resize(newSize: integer);
 
 
begin
 
begin
   if newSize <= cap then
+
   Result := '';
    size := newSize
+
  var curElem := fTop;
   else
+
   while curElem <> nil do
 
   begin
 
   begin
     Reserve(INC_CAP_FACTOR * newSize);
+
     Result += curElem.data.ToString + ' ';
    for var i := size to newSize - 1 do // явным образом заполняем новые элементы
+
     curElem := curElem.next;
      data[i] := default(DataType);
 
     size := newSize;
 
 
   end;
 
   end;
 
end;
 
end;
 
+
{Добавляет элементы, переданные в качестве параметров, в конец массива}
+
procedure Stack<T>.Print;
procedure DynArray<DataType>.Add(params xDatas: array of DataType);
 
 
begin
 
begin
   Resize(size + xDatas.Length);
+
   write(ToString);
  for var i := 0 to xDatas.Length - 1 do
 
    data[size-xDatas.Length + i] := xDatas[i];
 
 
end;
 
end;
 
+
   
{Вставляет в массив элементы, переданные в качестве параметров,
+
procedure Stack<T>.Println;
  начиная с позиции pos}
 
procedure DynArray<DataType>.Insert(pos: integer; params xDatas: array of DataType);
 
 
begin
 
begin
   Assert((0 <= pos) and (pos <= size-1));
+
   writeln(ToString);
 
 
  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;
 
end;
 
+
{Удаляет count элементов массива, начиная с позиции pos.
+
// ----------------------------------- Queue -----------------------------------
(По умолчанию удаляется один элемент)}
+
constructor Queue<T>.Create;
procedure DynArray<DataType>.Delete(pos: integer; count: integer);
 
 
begin
 
begin
   Assert((0 <= pos) and (pos <= size-1));
+
   fHead := nil;
  Assert((0 <= count) and (count <= size));
+
   fTail := nil;
 
 
  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;
 
end;
 
+
   
{Возвращает индекс первого элемента массива равного x
+
procedure Queue<T>.Enqueue(x: T);
  или -1, если такого элемента нет}
 
function DynArray<DataType>.Find(x: DataType): integer;
 
 
begin
 
begin
   result := -1;
+
   if IsEmpty then
  for var i := 0 to size - 1 do
+
  begin
     if data[i] = x then
+
    fHead := new SingleNode<T>(x, nil);
     begin
+
    fTail := fHead;
      result := i;
+
  end
      exit;
+
  else
    end;
+
  begin
 +
     fTail.next := new SingleNode<T>(x, nil);
 +
     fTail := fTail.next; // элемент удаляется из хвоста очереди (т.е. хвостом становится следующий элемент)
 +
  end;
 
end;
 
end;
{Возвращает индекс элемента массива равного x, начиная с позиции from,
+
   
  или -1, если такого элемента нет}
+
function Queue<T>.Dequeue: T;
function DynArray<DataType>.Find(x: DataType; from: integer): integer;
 
 
begin
 
begin
   Assert((0 <= from) and (from <= size-1));
+
   if IsEmpty then
 
+
    raise new Exception(DequeueNilQueueExceptionMessage);
   result := -1;
+
   for var i := from to size - 1 do
+
   Result := fHead.data;
    if data[i] = x then
+
   fHead := fHead.next;  // элемент удаляется из головы очереди (т.е. головой становится следующий элемент)
     begin
+
  if fHead = nil then
      result := i;
+
     fTail := nil;
      exit;
 
    end;
 
 
end;
 
end;
 
+
// ---------------------------- Доступ к элементам ---------------------------
+
function Queue<T>.First: T;
{Устанавливает элемент с индексом ind равным x}
 
procedure DynArray<DataType>.SetElem(ind: integer; x: DataType);
 
 
begin
 
begin
   Assert((0 <= ind) and (ind <= size-1));
+
   if IsEmpty then
   data[ind] := x;
+
    raise new Exception(FirstNilQueueExceptionMessage);
 +
   
 +
   Result := fHead.data;
 
end;
 
end;
{Возвращает элемент массива с индексом ind}
+
function DynArray<DataType>.GetElem(ind: integer): DataType;
+
function Queue<T>.IsEmpty: boolean;
 
begin
 
begin
   Assert((0 <= ind) and (ind <= size-1));
+
   Result := (fHead = nil);
   result := data[ind];
+
   if Result then
 +
    Assert(fTail = nil);
 
end;
 
end;
 
+
// ----------------------------- Вывод содержимого ---------------------------
+
function Queue<T>.ToString: string;
{Выводит содержимое массива в прямом порядке
 
    delim — разделитель между элементами в строке
 
    elemsInLine — количество элементов, выводимых в одной строке}
 
procedure DynArray<DataType>.Print(delim: string; elemsInLine: integer);
 
 
begin
 
begin
   for var i := 1 to size do
+
   Result := '';
    if (i mod elemsInLine) <> 0 then
+
  var curElem := fHead;
      write(data[i-1]:PRINT_FIELD_WIDTH, delim)
+
  while curElem <> fTail do
    else          // если вывели elemsInLine элементов, переходим на новую строку
+
  begin
      writeln(data[i-1]:PRINT_FIELD_WIDTH);
+
    Result += curElem.data.ToString + ' ';
 +
    curElem := curElem.next;
 +
  end;
 +
  Result += curElem.data.ToString;
 
end;
 
end;
{Выводит содержимое массива в обратном порядке
+
 
    delim — разделитель между элементами в строке
+
procedure Queue<T>.Print;
    elemsInLine — количество элементов, выводимых в одной строке}
 
procedure DynArray<DataType>.PrintReverse(delim: string; elemsInLine: integer);
 
 
begin
 
begin
   for var i := 1 to size do
+
   write(ToString);
    if (i mod elemsInLine) <> 0 then
+
end;  
      write(data[size-i]:PRINT_FIELD_WIDTH, delim)
+
    else          // если вывели elemsInLine элементов, переходим на новую строку
+
procedure Queue<T>.Println;
      writeln(data[size-i]:PRINT_FIELD_WIDTH);
 
end;
 
 
 
{Выводит содержимое массива в прямом порядке в каждой строке}
 
procedure DynArray<DataType>.Println;
 
 
begin
 
begin
   for var i := 0 to size - 1 do
+
   writeln(ToString);
    writeln(data[i]);
 
 
end;
 
end;
{Выводит содержимое массива в обратном порядке в каждой строке}
+
procedure DynArray<DataType>.PrintlnReverse;
+
// ---------------------------------- DynArray ---------------------------------
 +
constructor DynArray<T>.Create;
 
begin
 
begin
   for var i := size - 1 downto 0 do
+
   Create(0);
    writeln(data[i]);
 
 
end;
 
end;
  
 
+
constructor DynArray<T>.Create(size: integer);
end.
+
begin
</source>
+
  if size < 0 then
 
+
    raise new Exception(NegativeArraySizeExceptionMessage + size.ToString);
== Collections ==
 
<source lang="Delphi">
 
/// Модуль содержит шаблоны классов
 
///  Stack — стек
 
///  Queue — очередь
 
///  DynArray — динамический массив с автоконтролем памяти
 
unit Collections;
 
 
   
 
   
 +
  fSize := size;
 +
  fCap := INC_CAP_FACTOR*size + MIN_CAP; // Устанавливаем емкость "с запасом"
 +
  SetLength(fData, fCap);
 +
end;
 
   
 
   
interface
+
procedure DynArray<T>.Reserve(newCap: integer);
+
begin
uses Nodes;  // для использования типа SingleNode<DataType>
+
   if newCap > fCap then
              // узла с одним полем связи
+
   begin
+
     SetLength(fData, newCap);
const
+
     fCap := newCap;
  /// Ширина поля вывода
 
  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;
 
   end;
 +
end;
 
   
 
   
// ----------------------------------------------QUEUE---------------------------------------------
+
procedure DynArray<T>.Resize(newSize: integer);
const
+
begin
  /// Сообщение о пустоте очереди
+
  if newSize < 0 then
  EMPTY_QUEUE = 'Очередь пуста';
+
     raise new Exception(NegativeArraySizeExceptionMessage + newSize.ToString);
 
 
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;
 
 
   
 
   
// --------------------------------------------DYN_ARRAY-------------------------------------------
+
   if newSize > fCap then
const
+
   begin
   /// Минимальная емкость, устанавливаемая при создании массива
+
     Reserve(INC_CAP_FACTOR * newSize);
  MIN_CAP = 4;
+
     for var i := fSize to newSize - 1 do // явным образом заполняем новые элементы
  /// Коэффициент увеличения емкости массива при её нехватке
+
      fData[i] := default(T);
  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;
 
   end;
 +
  fSize := newSize;
 +
end;
 
   
 
   
// ================================================================= IMPLEMENTATION ===================================================================
+
procedure DynArray<T>.Add(x: T);
implementation
 
 
// ----------------------------------------------STACK---------------------------------------------
 
 
// ---------------------------- Стандартные методы ---------------------------
 
{Стандартный конструктор}
 
constructor Stack<DataType>.Create;
 
 
begin
 
begin
   fTop := nil;
+
   Resize(fSize + 1);
 +
  fData[fSize-1] := x;
 
end;
 
end;
{Создает стек, заполненный элементами, переданными в качестве параметров}
+
constructor Stack<DataType>.Create(params xDatas: array of DataType);  
+
procedure DynArray<T>.Insert(pos: integer; x: T);
 
begin
 
begin
   fTop := nil;
+
   if (pos < 0) or (pos > fSize-1) then
   for var i := 0 to xDatas.Length - 1 do
+
    raise new Exception(InsOutOfArrayBoundExceptionMessage + pos.ToString);
     Push(xDatas[i]);
+
 +
  Resize(fSize + 1);
 +
   for var i := fSize - 2 downto pos do  // сдвиг элементов на 1 вправо, до позиции pos
 +
     fData[i+1] := fData[i];
 +
  fData[pos] := x;
 
end;
 
end;
 
   
 
   
{Кладет элемент x на вершину стека}
+
procedure DynArray<T>.Remove(pos: integer);
procedure Stack<DataType>.Push(x: DataType);
 
 
begin
 
begin
   fTop := new SingleNode<DataType>(x, fTop);
+
   if (pos < 0) or (pos > fSize-1) then
 +
    raise new Exception(RemOutOfArrayBoundExceptionMessage + pos.ToString);
 +
 +
  for var i := pos to fSize - 2 do      // сдвиг элементов влево на 1, начиная с позиции pos
 +
    fData[i] := fData[i+1];
 +
  Resize(fSize - 1);
 
end;
 
end;
 
   
 
   
{Возвращает элемент типа DataType, снимая его с вершины стека}
+
function DynArray<T>.Find(x: T): integer;
function Stack<DataType>.Pop: DataType;
 
 
begin
 
begin
   Assert(not IsEmpty);
+
   Result := -1;
   result := fTop.data;
+
   for var i := 0 to fSize - 1 do
  fTop := fTop.next; // элемент снимается с вершины стека
+
    if fData[i] = (x) then
                      // (т.е. вершиной становится следующий элемент)
+
    begin
 +
      Result := i;
 +
      exit;
 +
    end;
 
end;
 
end;
 
   
 
   
{Возвращает значение элемента на вершине стека}
+
procedure DynArray<T>.SetElem(index: integer; x: T);
function Stack<DataType>.Top: DataType;
 
 
begin
 
begin
   Assert(not IsEmpty);
+
   if (index < 0) or (index > fSize-1) then
   result := fTop.data;
+
    raise new Exception(SetElemOutOfBoundExceptionMessage + index.ToString);
 +
 +
   fData[index] := x;
 
end;
 
end;
 
   
 
   
{Возвращает истину, если стек пуст}
+
{Возвращает элемент массива с индексом index}
function Stack<DataType>.IsEmpty: boolean;
+
function DynArray<T>.GetElem(index: integer): T;
 
begin
 
begin
   result := (fTop = nil);
+
   if (index < 0) or (index > fSize-1) then
 +
    raise new Exception(GetElemOutOfBoundExceptionMessage + index.ToString);
 +
 +
  Result := fData[index];
 
end;
 
end;
 
   
 
   
// ----------------------------- Вывод содержимого ---------------------------
+
function DynArray<T>.ToString: string;
{Выводит подряд содержимое стека
 
    delim — разделитель между элементами в строке
 
    elemsInLine — количество элементов, выводимых в одной строке}
 
procedure Stack<DataType>.Print(delim: string; elemsInLine: integer);
 
 
begin
 
begin
   if IsEmpty then
+
   Result := '';
    writeln(EMPTY_STACK)
+
   for var i := 0 to fSize - 2 do
   else
 
 
   begin
 
   begin
     var elemsInd := 1;  // индекс элемента стека
+
     var o: Object := fData[i];
                        // нужен для вывода по строкам
+
     Result += o.ToString + ' ';
    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;
 +
  var o := fData[fSize-1];
 +
  Result += o.ToString;
 +
    //Result += fData[i].ToString + ' ';
 +
  //Result += fData[fSize-1].ToString;
 
end;
 
end;
 
   
 
   
{Выводит содержимое стека в каждой строке}
+
procedure DynArray<T>.Print;
procedure Stack<DataType>.Println;
 
 
begin
 
begin
   if IsEmpty then
+
   write(ToString);
    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---------------------------------------------
+
procedure DynArray<T>.Println;
 +
begin
 +
  writeln(ToString);
 +
end;
 
   
 
   
// ---------------------------- Стандартные методы ---------------------------
+
// -------------------------------- SimpleSet ----------------------------------
{Создает пустую очередь}
+
constructor SimpleSet<T>.Create;
constructor Queue<DataType>.Create;
 
 
begin
 
begin
   head := nil;
+
   fData := new DynArray<T>;
  tail := nil;
 
 
end;
 
end;
{Создает очередь, заполненную элементами, переданными в качестве параметров}
+
 
constructor Queue<DataType>.Create(params xDatas: array of DataType);  
+
procedure SimpleSet<T>.Add(x: T);
 
begin
 
begin
   head := nil;
+
   if fData.Find(x) = -1 then
  tail := nil;
+
     fData.Add(x);
  for var i := 0 to xDatas.Length - 1 do
 
     Enqueue(xDatas[i]);
 
 
end;
 
end;
 
   
 
   
{Добавляет элемент x в хвост очереди}
+
procedure SimpleSet<T>.Remove(x: T);
procedure Queue<DataType>.Enqueue(x: DataType);
 
 
begin
 
begin
   if IsEmpty then
+
   var xPos := fData.Find(x);
  begin
+
   if xPos <> -1 then
    head := new SingleNode<DataType>(x, nil);
+
     fData.Remove(xPos);
    tail := head;
 
   end
 
  else  // if not IsEmpty
 
  begin
 
    tail.next := new SingleNode<DataType>(x, nil);
 
     tail := tail.next;  // элемент убирается из хвоста очереди
 
                        // (т.е. хвостом становится следующий элемент)
 
  end;
 
 
end;
 
end;
 
   
 
   
{Возвращает элемент типа DataType, убирая его из головы очереди}
+
function SimpleSet<T>.Contains(x: T): boolean;
function Queue<DataType>.Dequeue: DataType;
 
 
begin
 
begin
   Assert(not IsEmpty);
+
   Result := (fData.Find(x) <> -1);
  result := head.data;
+
end;
 
   
 
   
   head := head.next; // элемент убирается из головы очереди
+
function SimpleSet<T>.ToString: string;
                      // (т.е. головой становится следующий элемент)
+
begin
   if head = nil then
+
   Result := fData.ToString;
    tail := nil;
+
end;
 +
 
 +
procedure SimpleSet<T>.Print;
 +
begin
 +
  write(ToString);
 +
end;
 +
 
 +
procedure SimpleSet<T>.Println;
 +
begin
 +
   writeln(ToString);
 
end;
 
end;
 
   
 
   
{Возвращает истину, если очередь пуста}
+
// -------------------------------- AssocArray ---------------------------------
function Queue<DataType>.IsEmpty: boolean;
+
constructor AssocArray<KeyType,ValueType>.Create;
 
begin
 
begin
   result := (head = nil);
+
   fKeys := new DynArray<KeyType>;
   if result then
+
   fValues := new DynArray<ValueType>;
    Assert(tail = nil);
 
 
end;
 
end;
  
// ----------------------------- Вывод содержимого ---------------------------
+
procedure AssocArray<KeyType,ValueType>.SetElem(key: KeyType; value: ValueType);
{Выводит подряд содержимое очереди от головы к хвосту
 
    delim — разделитель между элементами в строке
 
    elemsInLine — количество элементов, выводимых в одной строке}
 
procedure Queue<DataType>.Print(delim: string; elemsInLine: integer);
 
 
begin
 
begin
   if IsEmpty then
+
  var ind := fKeys.Find(key);
     writeln(EMPTY_QUEUE)
+
   if ind <> -1 then
 +
     fValues[ind] := value
 
   else
 
   else
 
   begin
 
   begin
     var elemsInd := 1;  // индекс элемента стека
+
     fKeys.Add(key);
                        // нужен для вывода по строкам
+
     fValues.Add(value);
    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;
 
end;
 
end;
 
+
{Выводит содержимое очереди от головы к хвосту в каждой строке}
+
function AssocArray<KeyType,ValueType>.GetElem(key: KeyType): ValueType;
procedure Queue<DataType>.Println;
 
 
begin
 
begin
   if IsEmpty then
+
  var ind := fKeys.Find(key);
     writeln(EMPTY_QUEUE)
+
   if ind <> -1 then
 +
     Result := fValues[ind]
 
   else
 
   else
 
   begin
 
   begin
     var curElem := head;
+
     fKeys.Add(key);
     while curElem <> nil do
+
     fValues.Add(default(ValueType));
    begin
+
    Result := default(ValueType);
      writeln(curElem.data:PRINT_FIELD_WIDTH);
 
      curElem := curElem.next;;
 
    end;
 
 
   end;
 
   end;
 
end;
 
end;
  
// --------------------------------------------DYN_ARRAY-------------------------------------------   
+
function AssocArray<KeyType, ValueType>.ToString: string;
 
+
const NewLine = #13#10;
// ---------------------------- Стандартные методы ---------------------------
 
{Создает массив размера pSize}
 
constructor DynArray<DataType>.Create(pSize: integer);
 
 
begin
 
begin
   size := pSize;
+
   Result := '';
   cap := 2*pSize + MIN_CAP; // Устанавливаем емкость "с запасом"
+
   for var i := 0 to fKeys.Count - 2 do
   SetLength(data, cap);
+
  begin
 +
    var oKey: Object := fKeys[i];
 +
    var oVal: Object := fValues[i];
 +
    Result += oKey.ToString + ' ' + oVal.ToString + NewLine;
 +
  end;
 +
  var oKey: Object := fKeys[fKeys.Count-1];
 +
  var oVal: Object := fValues[fKeys.Count-1];
 +
  Result += oKey.ToString + ' ' + oVal.ToString;
 +
    //Result += fKeys[i].ToString + ' ' + fValues[i].ToString + NewLine;
 +
   //Result += fKeys[fKeys.Count-1].ToString + ' ' + fValues[fKeys.Count-1].ToString
 
end;
 
end;
{Создает массив, заполненный элементами, переданными в качестве параметров}
+
 
constructor DynArray<DataType>.Create(params xDatas: array of DataType);
+
procedure AssocArray<KeyType, ValueType>.Print;
 
begin
 
begin
   Create(xDatas.Length);  // Сначала нужно создать массив требуемого размера
+
   write(ToString);
 
 
  for var i := 0 to xDatas.Length - 1 do
 
    data[i] := xDatas[i];
 
 
end;
 
end;
  
{Выделяет новую память. Емкость увеличивается до newCap
+
procedure AssocArray<KeyType, ValueType>.Println;
(Если newCap меньше текущей емкости, ничего не происходит)}
 
procedure DynArray<DataType>.Reserve(newCap: integer);
 
 
begin
 
begin
   if newCap > cap then
+
   writeln(ToString);
  begin
 
    SetLength(data, newCap);
 
    cap := newCap;
 
  end;
 
 
end;
 
end;
  
{Устанавливает размер массива равным newSize}
+
// -------------------------------- LinkedList ---------------------------------
procedure DynArray<DataType>.Resize(newSize: integer);
+
constructor LinkedList<T>.Create;
 
begin
 
begin
   if newSize <= cap then
+
   fFirst := nil;
    size := newSize
+
   fLast := nil;
   else
 
  begin
 
    Reserve(INC_CAP_FACTOR * newSize);
 
    for var i := size to newSize - 1 do // явным образом заполняем новые элементы
 
      data[i] := default(DataType);
 
    size := newSize;
 
  end;
 
 
end;
 
end;
  
{Добавляет элементы, переданные в качестве параметров, в конец массива}
+
procedure LinkedList<T>.AddFirst(x: T);
procedure DynArray<DataType>.Add(params xDatas: array of DataType);
 
 
begin
 
begin
   Resize(size + xDatas.Length);
+
   var val := new LinkedListNode<T>(x, nil, fFirst);
   for var i := 0 to xDatas.Length - 1 do
+
  if fFirst <> nil then
     data[size-xDatas.Length + i] := xDatas[i];
+
    fFirst.fPrev := val;
 +
    
 +
  fFirst := val;
 +
  if fLast = nil then
 +
     fLast := fFirst;
 
end;
 
end;
  
{Вставляет в массив элементы, переданные в качестве параметров,
+
procedure LinkedList<T>.AddLast(x: T);
начиная с позиции pos}
 
procedure DynArray<DataType>.Insert(pos: integer; params xDatas: array of DataType);
 
 
begin
 
begin
   Assert((0 <= pos) and (pos <= size-1));
+
   var val := new LinkedListNode<T>(x, fLast, nil);
    
+
   if fLast <> nil then
  Resize(size + xDatas.Length);
+
    fLast.fNext := val;
  for var i := size - 2 downto pos+xDatas.Length - 1 do // сдвиг элементов вправо, начиная с позиции pos
+
      
     data[i+1] := data[i-xDatas.Length + 1];
+
  fLast := val;
   for var i := 0 to xDatas.Length - 1 do                // заполнение "освободившихся" элементов новыми значениями
+
   if fFirst = nil then
     data[pos+i] := xDatas[i];
+
     fFirst := fLast;
 
end;
 
end;
  
{Удаляет count элементов массива, начиная с позиции pos.
+
procedure LinkedList<T>.RemoveFirst();
(По умолчанию удаляется один элемент)}
 
procedure DynArray<DataType>.Delete(pos: integer; count: integer);
 
 
begin
 
begin
   Assert((0 <= pos) and (pos <= size-1));
+
   if fFirst = nil then
  Assert((0 <= count) and (count <= size));
+
    raise new Exception(RemoveFromNilListExceptionMessage);
 
    
 
    
   if (size - pos) < count then         // если количество удаляемых элементов больше,
+
  fFirst := fFirst.fNext;
                                        // чем их осталось до конца массива
+
   if fFirst = nil then
     count := size - pos;
+
     fLast := nil
   for var i := pos to size-1 - count do // сдвиг элементов влево на count, начиная с позиции pos
+
   else
     data[i] := data[i + count];
+
     fFirst.fPrev := nil;
  Resize(size - count);                 // "отрезание" лишних count элементов
 
 
end;
 
end;
  
{Возвращает индекс первого элемента массива равного x
+
procedure LinkedList<T>.RemoveLast();
или -1, если такого элемента нет}
 
function DynArray<DataType>.Find(x: DataType): integer;
 
 
begin
 
begin
   result := -1;
+
   if fLast = nil then
   for var i := 0 to size - 1 do
+
    raise new Exception(RemoveFromNilListExceptionMessage);
    if data[i] = x then
+
   
     begin
+
   fLast := fLast.fPrev;
      result := i;
+
  if fLast = nil then
      exit;
+
     fFirst := nil
     end;
+
  else
 +
     fLast.fNext := nil;
 
end;
 
end;
{Возвращает индекс элемента массива равного x, начиная с позиции from,
+
 
или -1, если такого элемента нет}
+
procedure LinkedList<T>.AddBefore(node: LinkedListNode<T>; x: T);  
function DynArray<DataType>.Find(x: DataType; from: integer): integer;
 
 
begin
 
begin
   Assert((0 <= from) and (from <= size-1));
+
   if node = nil then
    
+
    raise new Exception(AddNilNodeExceptionMessage);
   result := -1;
+
   
   for var i := from to size - 1 do
+
   if node = fFirst then
     if data[i] = x then
+
    AddFirst(x)
     begin
+
   else
      result := i;
+
   begin
      exit;
+
    var val := new LinkedListNode<T>(x, node.fPrev, node);
    end;
+
     node.fPrev.fNext := val;
 +
     node.fPrev := val;
 +
  end;
 
end;
 
end;
  
// ---------------------------- Доступ к элементам ---------------------------
+
procedure LinkedList<T>.AddAfter(node: LinkedListNode<T>; x: T);
{Устанавливает элемент с индексом ind равным x}
 
procedure DynArray<DataType>.SetElem(ind: integer; x: DataType);
 
 
begin
 
begin
   Assert((0 <= ind) and (ind <= size-1));
+
   if node = nil then
  data[ind] := x;
+
    raise new Exception(AddNilNodeExceptionMessage);
 +
   
 +
  if node = fLast then
 +
    AddLast(x)
 +
  else
 +
  begin
 +
    var val := new LinkedListNode<T>(x, node, node.fNext);
 +
    node.fNext.fPrev := val;
 +
    node.fNext := val;
 +
  end;
 
end;
 
end;
{Возвращает элемент массива с индексом ind}
+
 
function DynArray<DataType>.GetElem(ind: integer): DataType;
+
procedure LinkedList<T>.Remove(node: LinkedListNode<T>);
 
begin
 
begin
   Assert((0 <= ind) and (ind <= size-1));
+
   if node = nil then
   result := data[ind];
+
    raise new Exception(RemoveNilNodeExceptionMessage);
 +
    
 +
  if node = fFirst then
 +
    RemoveFirst
 +
  else if node = fLast then
 +
    RemoveLast
 +
  else
 +
  begin
 +
    node.fPrev.fNext := node.fNext;
 +
    node.fNext.fPrev := node.fPrev;
 +
  end;
 
end;
 
end;
  
// ----------------------------- Вывод содержимого ---------------------------
+
function LinkedList<T>.ToString: string;
{Выводит содержимое массива в прямом порядке
 
    delim — разделитель между элементами в строке
 
    elemsInLine — количество элементов, выводимых в одной строке}
 
procedure DynArray<DataType>.Print(delim: string; elemsInLine: integer);
 
 
begin
 
begin
   for var i := 1 to size do
+
   Result := '';
    if (i mod elemsInLine) <> 0 then
+
  var cur := fFirst;
      write(data[i-1]:PRINT_FIELD_WIDTH, delim)
+
  while cur <> nil do
     else          // если вывели elemsInLine элементов, переходим на новую строку
+
  begin
      writeln(data[i-1]:PRINT_FIELD_WIDTH);
+
    var o: Object := cur.Value;
 +
    Result += o.ToString + ' ';
 +
     //Result := cur.Value.ToString + ' ';
 +
    cur := cur.Next;
 +
  end;
 
end;
 
end;
{Выводит содержимое массива в обратном порядке
+
 
    delim — разделитель между элементами в строке
+
procedure LinkedList<T>.Print;
    elemsInLine — количество элементов, выводимых в одной строке}
 
procedure DynArray<DataType>.PrintReverse(delim: string; elemsInLine: integer);
 
 
begin
 
begin
   for var i := 1 to size do
+
   write(ToString);
    if (i mod elemsInLine) <> 0 then
 
      write(data[size-i]:PRINT_FIELD_WIDTH, delim)
 
    else          // если вывели elemsInLine элементов, переходим на новую строку
 
      writeln(data[size-i]:PRINT_FIELD_WIDTH);
 
 
end;
 
end;
  
{Выводит содержимое массива в прямом порядке в каждой строке}
+
procedure LinkedList<T>.Println;
procedure DynArray<DataType>.Println;
 
 
begin
 
begin
   for var i := 0 to size - 1 do
+
   writeln(ToString);
    writeln(data[i]);
 
 
end;
 
end;
{Выводит содержимое массива в обратном порядке в каждой строке}
+
 
procedure DynArray<DataType>.PrintlnReverse;
 
begin
 
  for var i := size - 1 downto 0 do
 
    writeln(data[i]);
 
end;
 
 
 
end.
 
end.
 
</source>
 
</source>
 +
 +
== См. также ==
 +
* [[Unit Collections: Stack | Stack]]
 +
* [[Unit Collections: Queue | Queue]]
 +
* [[Unit Collections: DynArray | DynArray]]
 +
* [[Unit Collections: SimpleSet | SimpleSet]]
 +
* [[Unit Collections: AssocArray | AssocArray]]
 +
* [[Unit Collections: LinkedList | LinkedList]]

Текущая версия на 11:48, 9 мая 2009

Содержание

Collections

/// Модуль содержит шаблоны классов
///   Stack — стек
///   Queue — очередь
///   DynArray — динамический массив
///   SimpleSet — простое множество на основе динамического массива
///   AssocArray — простой ассоциативный массив на основе динамического массива пар
///   LinkedList — двусвязный список
unit Collections;
 
interface
 
// -------------------------------- SingleNode ---------------------------------
type
  /// Узел с одним полем связи
  SingleNode<T> = class
  private
    /// Значение, содержащееся в узле
    fData: T;
    /// Ссылка на следующий элемент
    fNext: SingleNode<T>;
  public
    /// <summary>
    /// Создает узел с одним полем связи
    /// </summary>
    /// <param name="pData">Значение в узле</param>
    /// <param name="pNext">Ссылка на следующий элемент</param>
    constructor Create(data: T; next: SingleNode<T>);
    begin
      fData := data;
      fNext := next;
    end;
    /// Значение, содержащееся в узле
    property Data: T read fData write fData;
    /// Ссылка на следующий элемент
    property Next: SingleNode<T> read fNext write fNext;
  end; 
 
// ----------------------------------- Stack -----------------------------------
type
  /// Шаблон класса Stack
  Stack<T> = class
  private 
    /// Вершина стека
    fTop: SingleNode<T> := nil; 
  public 
    /// Создает пустой стек
    constructor Create;
    /// <summary>
    /// Кладет элемент x на вершину стека
    /// </summary>
    /// <param name="x">Новый элемент</param>
    procedure Push(x: T);
    /// Возвращает значение элемента на вершине, снимая его со стека
    function Pop: T; 
    /// Возвращает значение элемента на вершине стека, не снимая его
    function Top: T;
    /// Возвращает истину, если стек пуст
    function IsEmpty: boolean; 
    /// Преобразует содержимое стека в строку
    function ToString: string; override;
    /// Выводит содержимое стека на консоль
    procedure Print;
    /// Выводит содержимое стека на консоль с переходом на новую строку
    procedure Println;
  end;
 
// ----------------------------------- Queue -----------------------------------
type  
  /// Шаблон класса Queue
  Queue<T> = class
  private
    /// Голова очереди
    fHead: SingleNode<T>;
    /// Хвост очереди
    fTail: SingleNode<T>;
  public
    /// Создает пустую очередь
    constructor Create;
    /// <summary>
    /// Добавляет элемент x в хвост очереди
    /// </summary>
    /// <param name="x">Добавляемый элемент</param>
    procedure Enqueue(x: T);
    /// Возвращает значение элемента в голове, удаляя его из очереди
    function Dequeue: T;
    /// Возвращает значение элемента в голове очереди, не удаляя его
    function First: T;
    /// Возвращает истину, если очередь пуста
    function IsEmpty: boolean;
    /// Преобразует содержимое очереди в строку
    function ToString: string; override;
    /// Выводит содержимое очереди на консоль
    procedure Print;
    /// Выводит содержимое очереди на консоль с переходом на новую строку
    procedure Println;
  end;
 
// --------------------------------- DynArray ----------------------------------
const
  /// Минимальная емкость, устанавливаемая при создании массива
  MIN_CAP = 4;
  /// Коэффициент увеличения емкости массива при её нехватке
  INC_CAP_FACTOR = 2;
 
type
  /// Шаблон класса DynArray (Динамический массив с автоконтролем памяти)
  DynArray<T> = class
  private
    /// Встроенный динамический массив, содержащий данные
    fData: array of T;
    /// Размер массива
    fSize: integer;
    /// Емкость массива
    fCap: integer;
    /// Устанавливает элемент с индексом index равным x
    procedure SetElem(index: integer; x: T);
    /// Возвращает элемент массива с индексом index
    function GetElem(index: integer): T;
  public
    /// Создает пустой массив
    constructor Create;
    /// Создает массив размера size
    constructor Create(size: integer);
    /// <summary>
    /// Выделяет новую память. Емкость увеличивается до NewSize.
    /// (Если newCap меньше текущей емкости, ничего не происходит) 
    /// </summary>
    /// <param name="newCap">Новая емкость массива</param>
    procedure Reserve(newCap: integer);
    /// <summary>
    /// Устанавливает новый размер массива равным newSize
    /// </summary>
    /// <param name="newSize">Новый размер массива</param>
    procedure Resize(newSize: integer);
    /// <summary>
    /// Добавляет элемент x в конец массива 
    /// </summary>
    /// <param name="x">Добавляемый элемент</param>
    procedure Add(x: T);
    /// <summary>
    /// Вставляет элемент x в указанную позицию pos
    /// </summary>
    /// <param name="pos">Позиция, в которую вставляется элемент</param>
    /// <param name="x">Вставляемый элемент</param>
    procedure Insert(pos: integer; x: T);
    /// <summary>
    /// Удаляет элемент массива из указанной позиции pos
    /// </summary>
    /// <param name="pos">Позиция, из которой удаляется элемент</param>
    procedure Remove(pos: integer);
    /// <summary>
    /// Возвращает индекс первого элемента массива равного x
    /// или -1, если такого элемента нет
    /// </summary>
    /// <param name="x">Искомый элемент</param>
    function Find(x: T): integer;
    /// Количество элементов (размер) массива
    property Count: integer read fSize write Resize;
    /// Емкость массива 
    property Capacity: integer read fCap write Reserve;
    /// Позволяет обращаться к элементам массива по индексу 
    property Elem[index: integer]: T read GetElem write SetElem; default;
    /// Преобразует содержимое массива в строку
    function ToString: string; override;
    /// Выводит содержимое массива на консоль
    procedure Print;
    /// Выводит содержимое массива на консоль с переходом на новую строку
    procedure Println;
  end;
 
// -------------------------------- SimpleSet ----------------------------------
type 
  /// Шаблон класса SimpleSet (Простое множество на основе динамического массива)
  SimpleSet<T> = class 
  private
    /// Элементы множества
    fData: DynArray<T>;
  public
    /// Создает множество
    constructor Create;
    /// <summary>
    /// Добавляет элемент x во множество, если его там еще нет
    /// </summary>
    /// <param name="x">Добавляемый элемент</param>    
    procedure Add(x: T);
    /// <summary>
    /// Удаляет элемент x из множества, если он там есть
    /// </summary>
    /// <param name="x">Удаляемый элемент</param>
    procedure Remove(x: T);
    /// <summary>
    /// Возвращает истину, если множество содержит элемент x
    /// </summary>
    /// <param name="x">Искомый элемент</param>          
    function Contains(x: T): boolean;   
    /// Преобразует содержимое массива в строку
    function ToString: string; override;
    /// Выводит содержимое массива на консоль
    procedure Print;
    /// Выводит содержимое множества на консоль с переходом на новую строку
    procedure Println;
end;
 
// -------------------------------- AssocArray ---------------------------------
type
  /// Шаблон класса AssocArray 
  AssocArray<KeyType, ValueType> = class
  private
    /// Ключи
    fKeys: DynArray<KeyType>;
    /// Значения, соответствующие ключам
    fValues: DynArray<ValueType>;

    /// Устанавливает значение элемента с ключом key равным value
    procedure SetElem(key: KeyType; value: ValueType);
    /// Возвращает значение элемента с ключом key
    function GetElem(key: KeyType): ValueType;
  public
    /// Создает ассоциативный массив
    constructor Create;
    /// Позволяет обращаться к элементам массива по ключу
    property Elem[key: KeyType]: ValueType read GetElem write SetElem; default;
    /// Преобразует содержимое ассоциативного массива в строку
    function ToString: string; override;
    /// Выводит содержимое ассоциативного массива на консоль
    procedure Print;
    /// Выводит содержимое ассоциативного массива на консоль с переходом на новую строку
    procedure Println;
  end;
 
// ----------------------------- LinkedListNode --------------------------------
type
  /// Узел с двумя полями связи
  LinkedListNode<T> = class
  private
    /// Значение, содержащееся в узле
    fData: T;
    /// Ссылка на предыдущий элемент
    fPrev: LinkedListNode<T>;
    /// Ссылка на следующий элемент
    fNext: LinkedListNode<T>;
  public
    /// <summary>
    /// Создает новый узел
    /// </summary>
    /// <param name="T">Значение узла</param>
    /// <param name="Prev">Ссылка на предыдущий элемент</param>
    /// <param name="Next">Ссылка на следующий элемент</param>
    constructor Create(data: T; prev, next: LinkedListNode<T>);
    begin
      fData := data;
      fNext := next;
      fPrev := prev;
    end;
    /// Значение, содержащееся в узле
    property Value: T read fData write fData;
    /// Ссылка на предыдущий элемент — только на чтение
    property Prev: LinkedListNode<T> read fPrev;
    /// Ссылка на следующий элемент — только на чтение
    property Next: LinkedListNode<T> read fNext;
  end;
  
  
// -------------------------------- LinkedList ---------------------------------
type
  /// Двусвязный линейный список
  LinkedList<T> = class
  private
    /// Первый элемент (голова)
    fFirst: LinkedListNode<T>;
    /// Последний элемент (хвост)
    fLast: LinkedListNode<T>;
  public
    /// Создает пустой список
    constructor Create;
    /// Первый элемент (голова) — только на чтение
    property First: LinkedListNode<T> read fFirst;
    /// Последний элемент (хвост) — только на чтение
    property Last: LinkedListNode<T> read fLast;
    /// <summary>
    /// Добавляет элемент x в начало списка
    /// </summary>
    /// <param name="x">Добавляемый элемент</param>
    procedure AddFirst(x: T);
    /// <summary>
    /// Добавляет элемент x в конец списка
    /// </summary>
    /// <param name="x">Добавляемый элемент</param>
    procedure AddLast(x: T);
    /// Удаляет первый элемент списка
    procedure RemoveFirst();
    /// Удаляет последний элемент списка
    procedure RemoveLast();
    /// <summary>
    /// Добавляет элемент x перед node
    /// </summary>
    /// <param name="node">Ссылка на элемент, перед которым нужно добавить новый</param>
    /// <param name="x">Добавляемый элемент</param>
    procedure AddBefore(node: LinkedListNode<T>; x: T); 
    /// <summary>
    /// Добавляет элемент x после node
    /// </summary>
    /// <param name="node">Ссылка на элемент, после которого нужно добавить новый</param>
    /// <param name="x">Добавляемый элемент</param>
    procedure AddAfter(node: LinkedListNode<T>; x: T);
    /// <summary>
    /// Удаляет элемент node
    /// </summary>
    /// <param name="node">Ссылка на элемент, который нужно удалить</param>
    procedure Remove(node: LinkedListNode<T>);
    /// Преобразует содержимое списка в строку
    function ToString: string; override;
    /// Выводит содержимое списка на консоль
    procedure Print;
    /// Выводит содержимое списка на консоль с переходом на новую строку
    procedure Println;
  end;
 
//==============================================================================
implementation
 
//Сообщения исключений
const	PopNilStackExceptionMessage =				'Попытка снятия элемента с пустого стека';
			TopNilStackExceptionMessage =				'Попытка получения элемента с пустого стека';
        
			DequeueNilQueueExceptionMessage =		'Попытка удаления элемента из пустой очереди';
			FirstNilQueueExceptionMessage =				'Попытка получения элемента из пустой очереди';
        
			NegativeArraySizeExceptionMessage =	'Попытка присвоить размеру массива отрицательное значение ';
      InsOutOfArrayBoundExceptionMessage ='Попытка вставки за границей массива в позицию ';
      RemOutOfArrayBoundExceptionMessage ='Попытка удаления за границей массива из позиции ';
      SetElemOutOfBoundExceptionMessage =	'Попытка присвоить значение элементу за границей массива с индексом ';
      GetElemOutOfBoundExceptionMessage =	'Попытка получить значение элемента за границей массива с индексом ';
      
			RemoveFromNilListExceptionMessage =	'Попытка удаления из пустого списка';
			AddNilNodeExceptionMessage =				'Параметр node является нулевой ссылкой';
			RemoveNilNodeExceptionMessage =			'Параметр node является нулевой ссылкой';
			
// ----------------------------------- Stack -----------------------------------
constructor Stack<T>.Create;
begin
  fTop := nil;
end;
 
procedure Stack<T>.Push(x: T);
begin
  fTop := new SingleNode<T>(x, fTop);
end;
 
function Stack<T>.Pop: T;
begin
  if IsEmpty then 
     raise new Exception(PopNilStackExceptionMessage);
 
  Result := fTop.data;
  fTop := fTop.next;  // элемент удаляется из вершины стека (т.е. вершиной становится следующий элемент)
end;
 
function Stack<T>.Top: T;
begin
  if IsEmpty then 
     raise new Exception(TopNilStackExceptionMessage);
 
  Result := fTop.data;
end;

function Stack<T>.IsEmpty: boolean;
begin
  Result := (fTop = nil);
end;
 
function Stack<T>.ToString: string;
begin
  Result := '';
  var curElem := fTop;
  while curElem <> nil do
  begin
    Result += curElem.data.ToString + ' ';
    curElem := curElem.next;
  end;
end;
 
procedure Stack<T>.Print;
begin
  write(ToString);
end;
 
procedure Stack<T>.Println;
begin
  writeln(ToString);
end;
 
// ----------------------------------- Queue -----------------------------------
constructor Queue<T>.Create;
begin
  fHead := nil;
  fTail := nil;
end;
 
procedure Queue<T>.Enqueue(x: T);
begin
  if IsEmpty then
  begin
    fHead := new SingleNode<T>(x, nil);
    fTail := fHead;
  end
  else
  begin
    fTail.next := new SingleNode<T>(x, nil);
    fTail := fTail.next;  // элемент удаляется из хвоста очереди (т.е. хвостом становится следующий элемент)
  end;
end;
 
function Queue<T>.Dequeue: T;
begin
  if IsEmpty then 
     raise new Exception(DequeueNilQueueExceptionMessage);
 
  Result := fHead.data;
  fHead := fHead.next;  // элемент удаляется из головы очереди (т.е. головой становится следующий элемент)
  if fHead = nil then
    fTail := nil;
end;
 
function Queue<T>.First: T;
begin
  if IsEmpty then 
     raise new Exception(FirstNilQueueExceptionMessage);
     
  Result := fHead.data;
end;
 
function Queue<T>.IsEmpty: boolean;
begin
  Result := (fHead = nil);
  if Result then
    Assert(fTail = nil);
end;
 
function Queue<T>.ToString: string;
begin
  Result := '';
  var curElem := fHead;
  while curElem <> fTail do
  begin
    Result += curElem.data.ToString + ' ';
    curElem := curElem.next;
  end;
  Result += curElem.data.ToString;
end;

procedure Queue<T>.Print;
begin
  write(ToString);
end; 
 
procedure Queue<T>.Println;
begin
  writeln(ToString);
end;
 
// ---------------------------------- DynArray ---------------------------------
constructor DynArray<T>.Create;
begin
  Create(0);
end;

constructor DynArray<T>.Create(size: integer);
begin
  if size < 0 then
    raise new Exception(NegativeArraySizeExceptionMessage + size.ToString);
 
  fSize := size;
  fCap := INC_CAP_FACTOR*size + MIN_CAP; // Устанавливаем емкость "с запасом"
  SetLength(fData, fCap);
end;
 
procedure DynArray<T>.Reserve(newCap: integer);
begin
  if newCap > fCap then 
  begin
    SetLength(fData, newCap);
    fCap := newCap;
  end;
end;
 
procedure DynArray<T>.Resize(newSize: integer);
begin
  if newSize < 0 then
    raise new Exception(NegativeArraySizeExceptionMessage + newSize.ToString);
 
  if newSize > fCap then
  begin
    Reserve(INC_CAP_FACTOR * newSize);
    for var i := fSize to newSize - 1 do // явным образом заполняем новые элементы
      fData[i] := default(T);
  end;
  fSize := newSize;
end;
 
procedure DynArray<T>.Add(x: T);
begin
  Resize(fSize + 1);
  fData[fSize-1] := x;
end;
 
procedure DynArray<T>.Insert(pos: integer; x: T);
begin
  if (pos < 0) or (pos > fSize-1) then 
     raise new Exception(InsOutOfArrayBoundExceptionMessage + pos.ToString);
 
  Resize(fSize + 1);
  for var i := fSize - 2 downto pos do  // сдвиг элементов на 1 вправо, до позиции pos
    fData[i+1] := fData[i];
  fData[pos] := x;
end;
 
procedure DynArray<T>.Remove(pos: integer);
begin
  if (pos < 0) or (pos > fSize-1) then 
    raise new Exception(RemOutOfArrayBoundExceptionMessage + pos.ToString);
 
  for var i := pos to fSize - 2 do      // сдвиг элементов влево на 1, начиная с позиции pos
    fData[i] := fData[i+1];
  Resize(fSize - 1);
end;
 
function DynArray<T>.Find(x: T): integer;
begin
  Result := -1;
  for var i := 0 to fSize - 1 do
    if fData[i] = (x) then
    begin
      Result := i;
      exit;
    end;
end;
 
procedure DynArray<T>.SetElem(index: integer; x: T);
begin
  if (index < 0) or (index > fSize-1) then 
    raise new Exception(SetElemOutOfBoundExceptionMessage + index.ToString);
 
  fData[index] := x;
end;
 
{Возвращает элемент массива с индексом index}
function DynArray<T>.GetElem(index: integer): T;
begin
  if (index < 0) or (index > fSize-1) then 
     raise new Exception(GetElemOutOfBoundExceptionMessage + index.ToString);
 
  Result := fData[index];
end;
 
function DynArray<T>.ToString: string;
begin
  Result := '';
  for var i := 0 to fSize - 2 do
  begin
    var o: Object := fData[i];
    Result += o.ToString + ' ';
  end;
  var o := fData[fSize-1];
  Result += o.ToString;
    //Result += fData[i].ToString + ' '; 
  //Result += fData[fSize-1].ToString;
end;
 
procedure DynArray<T>.Print;
begin
  write(ToString);
end;
 
procedure DynArray<T>.Println;
begin
  writeln(ToString);
end;
 
// -------------------------------- SimpleSet ----------------------------------
constructor SimpleSet<T>.Create;
begin
  fData := new DynArray<T>;
end;

procedure SimpleSet<T>.Add(x: T);
begin
  if fData.Find(x) = -1 then 
    fData.Add(x);
end;
 
procedure SimpleSet<T>.Remove(x: T);
begin
  var xPos := fData.Find(x);
  if xPos <> -1 then
    fData.Remove(xPos);
end;
 
function SimpleSet<T>.Contains(x: T): boolean;
begin
  Result := (fData.Find(x) <> -1);
end;
 
function SimpleSet<T>.ToString: string;
begin
  Result := fData.ToString;
end;

procedure SimpleSet<T>.Print;
begin
  write(ToString);
end;

procedure SimpleSet<T>.Println;
begin
  writeln(ToString);
end;
 
// -------------------------------- AssocArray ---------------------------------
constructor AssocArray<KeyType,ValueType>.Create;
begin
  fKeys := new DynArray<KeyType>;
  fValues := new DynArray<ValueType>;
end;

procedure AssocArray<KeyType,ValueType>.SetElem(key: KeyType; value: ValueType);
begin
  var ind := fKeys.Find(key);
  if ind <> -1 then
    fValues[ind] := value
  else
  begin
    fKeys.Add(key);
    fValues.Add(value);
  end;
end;
 
function AssocArray<KeyType,ValueType>.GetElem(key: KeyType): ValueType;
begin
  var ind := fKeys.Find(key);
  if ind <> -1 then
    Result := fValues[ind]
  else
  begin
    fKeys.Add(key);
    fValues.Add(default(ValueType));
    Result := default(ValueType);
  end;
end;

function AssocArray<KeyType, ValueType>.ToString: string;
const NewLine = #13#10;
begin
  Result := '';
  for var i := 0 to fKeys.Count - 2 do
  begin
    var oKey: Object := fKeys[i];
    var oVal: Object := fValues[i];
    Result += oKey.ToString + ' ' + oVal.ToString + NewLine;
  end;
  var oKey: Object := fKeys[fKeys.Count-1];
  var oVal: Object := fValues[fKeys.Count-1];
  Result += oKey.ToString + ' ' + oVal.ToString;
    //Result += fKeys[i].ToString + ' ' + fValues[i].ToString + NewLine;
  //Result += fKeys[fKeys.Count-1].ToString + ' ' + fValues[fKeys.Count-1].ToString
end;

procedure AssocArray<KeyType, ValueType>.Print;
begin
  write(ToString);
end;

procedure AssocArray<KeyType, ValueType>.Println;
begin
  writeln(ToString);
end;

// -------------------------------- LinkedList ---------------------------------
constructor LinkedList<T>.Create;
begin
  fFirst := nil;
  fLast := nil;
end;

procedure LinkedList<T>.AddFirst(x: T);
begin
  var val := new LinkedListNode<T>(x, nil, fFirst);
  if fFirst <> nil then
    fFirst.fPrev := val;
  
  fFirst := val;
  if fLast = nil then
    fLast := fFirst;
end;

procedure LinkedList<T>.AddLast(x: T);
begin
  var val := new LinkedListNode<T>(x, fLast, nil);
  if fLast <> nil then
    fLast.fNext := val;
    
  fLast := val;
  if fFirst = nil then
    fFirst := fLast;
end;

procedure LinkedList<T>.RemoveFirst();
begin
  if fFirst = nil then
    raise new Exception(RemoveFromNilListExceptionMessage);
  
  fFirst := fFirst.fNext;
  if fFirst = nil then
    fLast := nil
  else
    fFirst.fPrev := nil;
end;

procedure LinkedList<T>.RemoveLast();
begin
  if fLast = nil then
    raise new Exception(RemoveFromNilListExceptionMessage);
    
  fLast := fLast.fPrev;
  if fLast = nil then
    fFirst := nil
  else
    fLast.fNext := nil;
end;

procedure LinkedList<T>.AddBefore(node: LinkedListNode<T>; x: T); 
begin
  if node = nil then
    raise new Exception(AddNilNodeExceptionMessage);
    
  if node = fFirst then
    AddFirst(x)
  else
  begin
    var val := new LinkedListNode<T>(x, node.fPrev, node);
    node.fPrev.fNext := val;
    node.fPrev := val;
  end;
end;

procedure LinkedList<T>.AddAfter(node: LinkedListNode<T>; x: T);
begin
  if node = nil then
    raise new Exception(AddNilNodeExceptionMessage);
    
  if node = fLast then
    AddLast(x)
  else
  begin
    var val := new LinkedListNode<T>(x, node, node.fNext);
    node.fNext.fPrev := val;
    node.fNext := val;
  end;
end;

procedure LinkedList<T>.Remove(node: LinkedListNode<T>);
begin
  if node = nil then
    raise new Exception(RemoveNilNodeExceptionMessage);
  
  if node = fFirst then
    RemoveFirst
  else if node = fLast then
    RemoveLast
  else
  begin
    node.fPrev.fNext := node.fNext;
    node.fNext.fPrev := node.fPrev;
  end;
end;

function LinkedList<T>.ToString: string;
begin
  Result := '';
  var cur := fFirst;
  while cur <> nil do
  begin
    var o: Object := cur.Value;
    Result += o.ToString + ' ';
    //Result := cur.Value.ToString + ' ';
    cur := cur.Next;
  end;
end;

procedure LinkedList<T>.Print;
begin
  write(ToString);
end;

procedure LinkedList<T>.Println;
begin
  writeln(ToString);
end;

end.

См. также