ruberon/source/LISTS.ob07

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;
            item.prev  := NIL
        ELSE
            ASSERT(list.last # NIL);
            item.prev := list.last;
            list.last.next := item
        END;
        list.last := item;
        item.next := NIL
    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
        ELSE
            nov.prev := NIL;
            list.first := nov
        END;
        cur.prev := nov;
        nov.next := cur
    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 THEN
            IF prev # NIL THEN
                prev.next := next;
                next.prev := prev
            ELSE
                next.prev := NIL;
                list.first := next
            END
        ELSE
            IF prev # NIL THEN
                prev.next := NIL;
                list.last := prev
            ELSE
                list.first := NIL;
                list.last := NIL
            END
        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.