(*
BSD 2-Clause License
Copyright (c) 2018-2019, Anton Krotov
All rights reserved.
*)
MODULE LISTS;
IMPORT C := COLLECTIONS;
TYPE
ITEM* = POINTER TO RECORD (C.ITEM)
prev*, next*: ITEM
END;
LIST* = POINTER TO RECORD
first*, last*: ITEM
END;
PROCEDURE push* (list: LIST; item: ITEM);
BEGIN
ASSERT(list # NIL);
ASSERT(item # NIL);
IF list.first = NIL THEN
list.first := item;
list.last := item;
item.prev := NIL;
item.next := NIL
ELSE
ASSERT(list.last # NIL);
item.prev := list.last;
list.last.next := item;
item.next := NIL;
list.last := item
END
END push;
PROCEDURE pop* (list: LIST): ITEM;
VAR
last: ITEM;
BEGIN
ASSERT(list # NIL);
last := list.last;
IF last # NIL THEN
IF last = list.first THEN
list.first := NIL;
list.last := NIL
ELSE
list.last := last.prev;
list.last.next := NIL
END;
last.next := NIL;
last.prev := NIL
END
RETURN last
END pop;
PROCEDURE insert* (list: LIST; cur, nov: ITEM);
VAR
next: ITEM;
BEGIN
ASSERT(list # NIL);
ASSERT(nov # NIL);
ASSERT(cur # NIL);
next := cur.next;
IF next # NIL THEN
next.prev := nov;
nov.next := next;
cur.next := nov;
nov.prev := cur
ELSE
push(list, nov)
END
END insert;
PROCEDURE insertL* (list: LIST; cur, nov: ITEM);
VAR
prev: ITEM;
BEGIN
ASSERT(list # NIL);
ASSERT(nov # NIL);
ASSERT(cur # NIL);
prev := cur.prev;
IF prev # NIL THEN
prev.next := nov;
nov.prev := prev;
cur.prev := nov;
nov.next := cur
ELSE
nov.prev := NIL;
cur.prev := nov;
nov.next := cur;
list.first := nov
END
END insertL;
PROCEDURE delete* (list: LIST; item: ITEM);
VAR
prev, next: ITEM;
BEGIN
ASSERT(list # NIL);
ASSERT(item # NIL);
prev := item.prev;
next := item.next;
IF (next # NIL) & (prev # NIL) THEN
prev.next := next;
next.prev := prev
ELSIF (next = NIL) & (prev = NIL) THEN
list.first := NIL;
list.last := NIL
ELSIF (next = NIL) & (prev # NIL) THEN
prev.next := NIL;
list.last := prev
ELSIF (next # NIL) & (prev = NIL) THEN
next.prev := NIL;
list.first := next
END
END delete;
PROCEDURE count* (list: LIST): INTEGER;
VAR
item: ITEM;
res: INTEGER;
BEGIN
ASSERT(list # NIL);
res := 0;
item := list.first;
WHILE item # NIL DO
INC(res);
item := item.next
END
RETURN res
END count;
PROCEDURE getidx* (list: LIST; idx: INTEGER): ITEM;
VAR
item: ITEM;
BEGIN
ASSERT(list # NIL);
ASSERT(idx >= 0);
item := list.first;
WHILE (item # NIL) & (idx > 0) DO
item := item.next;
DEC(idx)
END
RETURN item
END getidx;
PROCEDURE create* (list: LIST): LIST;
BEGIN
IF list = NIL THEN
NEW(list)
END;
list.first := NIL;
list.last := NIL
RETURN list
END create;
END LISTS.