Collections: DynArray

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск

Интерфейс

type DynArray<DataType> = class
  /// Количество элементов (размер) массива
  property Count: integer;

  /// Емкость массива (отведенная память)
  property Capacity: integer;

  /// Позволяет обращаться к элементам массива по индексу 
  /// (например, apples[5])
  property Elem[index: integer]: DataType;


  /// Создает массив размера pSize
  constructor Create(pSize: integer := 0);
 
  /// Выделяет новую память. Емкость увеличивается до newCap.
  /// (Если newCap меньше текущей емкости, ничего не происходит) 
  procedure Reserve(newCap: integer);

  /// Устанавливает новый размер массива равным newSize
  procedure Resize(newSize: integer);
 
  /// Добавляет элемент x в конец массива 
  procedure Add(x: DataType);

  /// Вставляет элемент x в позицию pos
  procedure Insert(pos: integer; x: DataType);

  /// Удаляет элемент массива из позиции pos
  procedure Remove(pos: integer);
 
  /// Возвращает индекс первого элемента массива равного x
  /// или -1, если такого элемента нет
  function Find(x: DataType): integer;
 
  /// Выводит содержимое массива на консоль
  procedure Println();

  /// Выводит содержимое массива на консоль в обратном порядке
  procedure PrintlnReverse();
end;

Реализация

interface

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);
 
    /// <summary>
    /// Выделяет новую память. Емкость увеличивается.
    /// (Если newCap меньше текущей емкости, ничего не происходит) 
    /// </summary>
    /// <param name="newCap">Новая емкость массива</param>
    procedure Reserve(newCap: integer);
    /// <summary>
    /// Устанавливает новый размер массива 
    /// </summary>
    /// <param name="newSize">Новый размер массива</param>
    procedure Resize(newSize: integer);
 
    /// <summary>
    /// Добавляет элемент в конец массива 
    /// </summary>
    /// <param name="x">Добавляемый элемент</param>
    procedure Add(x: DataType);
    /// <summary>
    /// Вставляет элемент в указанную позицию
    /// </summary>
    /// <param name="pos">Позиция, в которую вставляется элемент</param>
    /// <param name="x">Вставляемый элемент</param>
    procedure Insert(pos: integer; x: DataType);
    /// <summary>
    /// Удаляет элемент массива из указанной позиции
    /// </summary>
    /// <param name="pos">Позиция, из которой удаляется элемент</param>
    procedure Remove(pos: integer);
 
    /// <summary>
    /// Возвращает индекс первого элемента массива равного искомому
    /// или -1, если такого элемента нет
    /// </summary>
    /// <param name="x">Искомый элемент</param>
    function Find(x: DataType): 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;
 
    // ---------------------------------- Вывод ----------------------------------
    /// Выводит содержимое массива на консоль
    procedure Println();
    /// Выводит содержимое массива на консоль в обратном порядке
    procedure PrintlnReverse();
  end;

implementation

// ---------------------------- Стандартные методы ---------------------------
{Создает массив размера pSize}
constructor DynArray<DataType>.Create(pSize: integer);
begin
  if pSize < 0 then
    raise new Exception('Попытка присвоить размеру массива отрицательное значение ' + IntToStr(pSize) + '!');
 
  size := pSize;
  cap := INC_CAP_FACTOR*pSize + MIN_CAP; // Устанавливаем емкость "с запасом"
  SetLength(data, cap);
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 < 0 then
    raise new Exception('Попытка присвоить размеру массива отрицательное значение ' + IntToStr(newSize) + '!');
 
  if newSize > cap then
  begin
    Reserve(INC_CAP_FACTOR * newSize);
    for var i := size to newSize - 1 do // явным образом заполняем новые элементы
      data[i] := default(DataType);
  end;
  size := newSize;
end;
 
{Добавляет элемент x в конец массива }
procedure DynArray<DataType>.Add(x: DataType);
begin
  Resize(size + 1);
  data[size-1] := x;
end;
 
{Вставляет x элемент в позицию pos}
procedure DynArray<DataType>.Insert(pos: integer; x: DataType);
begin
  if (pos < 0) or (pos > size-1) then 
     raise new Exception(
     'Попытка вставки за границей массива в позицию ' + IntToStr(pos) + '!');
 
  Resize(size + 1);
  for var i := size - 2 downto pos do
    data[i+1] := data[i];
  data[pos] := x;
end;
 
{Удаляет элемент массива из позиции pos}
procedure DynArray<DataType>.Remove(pos: integer);
begin
  if (pos < 0) or (pos > size-1) then 
     raise new Exception(
     'Попытка удаления за границей массива из позиции ' + IntToStr(pos) + '!');
 
  for var i := pos to size - 2 do // сдвиг элементов влево на 1, начиная с позиции pos
    data[i] := data[i+1];
  Resize(size - 1);
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;
 
// ---------------------------- Доступ к элементам ---------------------------
{Устанавливает элемент с индексом 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;
 
// ---------------------------------- Вывод ----------------------------------
{Выводит содержимое массива на консоль}
procedure DynArray<DataType>.Println();
begin
  for var i := 0 to size - 1 do
      write(data[i], ' '); 
  writeln();
end;
 
{Выводит содержимое массива на консоль в обратном порядке}
procedure DynArray<DataType>.PrintlnReverse();
begin
  for var i := size - 1 downto 0 do
      write(data[i], ' '); 
  writeln();
end;

Примеры использования

uses Collections;

begin
  // Создание объекта динамического массива
  var d := new DynArray<integer>(0);
  
  // Вывод размера массива
  writeln('Размер массива = ', d.Count);  writeln();
  
  // Добавление элемента в массив
  d.Add(15);  d.Add(-9);  d.Add(136);
  
  // Вывод содержимого массива
  writeln('Содержимое всего массива:');
  d.Println;  writeln();
  
  // Вставка элемента x в позицию pos
  d.Insert(2, 47);
  
  writeln('Содержимое всего массива после вставки элемента:');
  d.Println;  writeln();
  
  // Доступ к элементу по индексу
  d[0] := 61;
  writeln('Содержимое всего массива после изменения первого элемента:');
  d.Println;  writeln();
  
  d.Insert(d.Count-1, -8);
  writeln('Содержимое всего массива после вставки элемента:');
  d.Println;  writeln();
  
  // Удаление элемента
  d.Remove(3);
  writeln('Содержимое всего массива после удаления элемента:');
  d.Println;  writeln();
  
  // Изменение размера с помощью метода
  d.Resize(d.Count + 3);
  writeln('Размер массива = ', d.Count);  writeln();
  
  // Изменение размера с помощью свойства
  d.Count := d.Count - 1;
  writeln('Размер массива = ', d.Count);  writeln();
  
  writeln('Емкость массива = ', d.Capacity);
  // Увеличение емкости массива
  d.Reserve(d.Capacity + 5);
  writeln('Емкость массива после увеличения = ', d.Capacity);
  // Попытка уменьшить емкость массива
  d.Reserve(3);
  writeln('Емкость массива после попытки уменьшения = ', d.Capacity); writeln();
  
  // Вывод индекса искомого элемента массива
  writeln('Индекс элемента 47 = ', d.Find(47));
  writeln('Индекс элемента -54 = ', d.Find(54), ' (т.е. такого элемента в массиве нет)');  writeln();
  
  // Обработка исключения при выходе за границы диапазона
  try
    d.Remove(d.Count + 3);
  except
    on e: Exception do
      writeln(e);
  end;
end.

См. также

Collections (полный текст модуля):

Источник — «http://it.mmcs.sfedu.ru/_wiki/index.php?title=Collections:_DynArray&oldid=2093»