https://gitlab.com/budden/nkp/blob/3107 ... Страниц.kp
Код: Выделить всё
MODULE КонтСписокНаВектореСтраниц;
(**
Список на массиве с постраничной организацией хранения.
Имеется вектор страниц, содержащий страницы с элементами.
Размер страницы равен размерСтраницы
Вектор страниц растёт квантами по шагРостаВектораСтраниц
Память, выделенная под структуру списка, не освобождается при уменьшении
размера списка. Однако, элементы списка, к-рые при уменьшении длины
списка выходят за пределы списка, списком не удерживаются.
Основано на ListLinear (С) Кушнир П.М.
Отличия от оригинала:
- код переведён на русский язык
- документация в формате ББ устранена, вместо
этого прокомментирован исходный текст
- в списке хранится ANYPTR, а не наследник специально созданного
абстрактного типа ListItem
- в оригинале при уменьшении длины списка элементы, вышедшие за пределы
списка, удерживались списком (утечка памяти)
- добавлена вставка, в т.ч. в конец
- добавлено удаление с конца
- процедура Яви, создающая список, всегда принимает длину списка.
- питоно-образное форматирование
(C) Кушнир П. М., Будяк Д.В
лицензия = "Docu/BB-License"
**)
CONST
шагРостаВектораСтраниц = 16;
размерСтраницы = 64;
TYPE
(** ЭлтСписка - то, что хранится в списке. Т.е., любая запись **)
ЭлтСписка = ANYPTR;
Страница = POINTER TO ARRAY OF ЭлтСписка;
ВекторСтраниц = POINTER TO ARRAY OF Страница;
Список* = POINTER TO LIMITED RECORD
длина-: INTEGER;
векторСтраниц: ВекторСтраниц;
используетсяСтраниц: INTEGER END;
PROCEDURE ДобавьСтраницЕслиНадо (сп: Список; будетДлина: INTEGER);
VAR
i, count: INTEGER;
векторСтраниц: ВекторСтраниц;
ш : INTEGER;
BEGIN
count := (будетДлина DIV размерСтраницы + 1);
IF count > LEN(сп.векторСтраниц) THEN
ш := шагРостаВектораСтраниц;
NEW(векторСтраниц, count DIV ш * ш + ш);
FOR i := 0 TO LEN(сп.векторСтраниц) - 1 DO векторСтраниц[i] := сп.векторСтраниц[i] END;
сп.векторСтраниц := векторСтраниц END;
FOR i := сп.используетсяСтраниц TO count - 1 DO NEW(сп.векторСтраниц[i], размерСтраницы) END;
IF count > сп.используетсяСтраниц THEN сп.используетсяСтраниц := count END
END ДобавьСтраницЕслиНадо;
PROCEDURE Яви* (длина: INTEGER): Список;
VAR рез: Список;
BEGIN
NEW(рез);
рез.используетсяСтраниц := 1;
NEW(рез.векторСтраниц, шагРостаВектораСтраниц);
NEW(рез.векторСтраниц[0], размерСтраницы);
рез.длина := 0;
IF длина > размерСтраницы THEN ДобавьСтраницЕслиНадо(рез, длина) END;
RETURN рез END Яви;
PROCEDURE На (сп: Список; и: INTEGER; элт: ЭлтСписка);
BEGIN
сп.векторСтраниц[и DIV размерСтраницы][и MOD размерСтраницы] := элт END На;
PROCEDURE Дай (сп: Список; и: INTEGER): ЭлтСписка;
BEGIN
RETURN сп.векторСтраниц[и DIV размерСтраницы][и MOD размерСтраницы] END Дай;
PROCEDURE ЗадайДлину (сп: Список; новаяДлина: INTEGER);
VAR й:INTEGER;
BEGIN
IF новаяДлина < 0 THEN новаяДлина := 0 END;
IF новаяДлина > размерСтраницы * сп.используетсяСтраниц THEN
ДобавьСтраницЕслиНадо(сп, новаяДлина) END;
(* Отличие от оригинала *)
FOR й := новаяДлина TO сп.длина - 1 DO
На(сп, й, NIL) END;
сп.длина := новаяДлина END ЗадайДлину;
PROCEDURE (э: Список) ЗадайДлину* (длина: INTEGER), NEW;
BEGIN
ASSERT(длина > - 1, 20);
ЗадайДлину(э, длина) END ЗадайДлину;
PROCEDURE (э: Список) Дай* (и: INTEGER): ЭлтСписка, NEW;
BEGIN
ASSERT((и >= 0) & (и < э.длина), 20);
RETURN Дай(э, и) END Дай;
PROCEDURE (э: Список) На* (и: INTEGER; элт: ЭлтСписка), NEW;
BEGIN
ASSERT((и >= 0) & (и < э.длина), 20);
На(э, и, элт) END На;
PROCEDURE (э: Список) Удали* (и: INTEGER), NEW;
VAR i: INTEGER;
BEGIN
ASSERT((и >= 0) & (и < э.длина), 20);
FOR i := и + 1 TO э.длина - 1 DO
На(э, i - 1, Дай(э, i)) END;
ЗадайДлину(э, э.длина - 1) END Удали;
PROCEDURE (э: Список) УдалиСКонца* (номерСКонцаСчитаяОт0: INTEGER), NEW;
BEGIN
э.Удали(э.длина - 1 - номерСКонцаСчитаяОт0) END УдалиСКонца;
(** Элемент получит заданный индекс.
и = 0 - вставить в начало. и = э.длина - вставить в конец.
См. также ВставитьВКонец *)
PROCEDURE (э: Список) Вставь* (и: INTEGER; элт: ЭлтСписка): ЭлтСписка, NEW;
VAR i: INTEGER;
BEGIN
ASSERT((и >= 0) & (и <= э.длина), 20);
ЗадайДлину(э, э.длина + 1);
FOR i := э.длина - 1 TO и + 1 BY -1 DO
На(э, i, Дай(э, i - 1)) END;
На(э, и, элт);
RETURN элт END Вставь;
(* Если и = 0, то вставляет в конец списка. и = 1 - вставляет перед последним элементом и т.п. *)
PROCEDURE (э: Список) ВставьВКонец* (и: INTEGER; элт: ЭлтСписка): ЭлтСписка, NEW;
BEGIN
RETURN э.Вставь(э.длина - и, элт) END ВставьВКонец;
END КонтСписокНаВектореСтраниц.