| 0,0 → 1,184 |
|---|
| (* |
| BSD 2-Clause License |
| |
| Copyright (c) 2018, 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 create* (list: LIST): LIST; |
| BEGIN |
| IF list = NIL THEN |
| NEW(list) |
| END; |
| |
| list.first := NIL; |
| list.last := NIL |
| |
| RETURN list |
| END create; |
| |
| |
| END LISTS. |