Collections: DynArray — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Juliet (обсуждение | вклад) м («Unit Collections: DynArray» переименована в «Collections: DynArray») |
Juliet (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
− | [[Категория: | + | [[Категория:Collections]] |
== Интерфейс == | == Интерфейс == | ||
<source lang="Delphi"> | <source lang="Delphi"> |
Текущая версия на 11:52, 9 мая 2009
Интерфейс
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 (полный текст модуля):