Power-Programmierung/CD1.mdf/pascal/library/dos/btree/llist/llist.pas

Pascal/Delphi Source File | 1990-01-14 | 6.1 KB | 283 lines

UNIT llist;

{Version 1.0, distributed as LLIST10.ZIP}

{This unit contains objects for doubly-linked lists.  See also DEMO.PAS
and TEST.PAS in this archive.  For Turbo Pascal 5.5.

Please distribute this unit with its demo and test programs.  Also,
please retain in this unit credit to its original author and any
subsequent authors.

Donated to the public domain by Wayne E. Conrad, January, 1990.  If you
have any problems or suggestions, please contact me at my BBS:

    Pascalaholics Anonymous
    [phone]
    2400 bps
    The home of WBBS
    Lots of source code
}


INTERFACE


{This abstract type is for each node in a list.  It contains the data and
methods needed to manage a node on the list, but it does not contain any
useful data.  A descendant object should be created which contains the
data you want in each node, as well as any methods to operate upon that
data.}

TYPE
  linked_list_ptr = ^linked_list_node;
  linked_list_node =
    OBJECT
    prev: linked_list_ptr;
    next: linked_list_ptr;
    CONSTRUCTOR init;
    DESTRUCTOR done;
    PROCEDURE remove;
    FUNCTION get_prev: linked_list_ptr;
    FUNCTION get_next: linked_list_ptr;
    PROCEDURE add_after (VAR node: linked_list_node);
    PROCEDURE add_before (VAR node: linked_list_node);
    END;


{There must be one of these objects for each linked list.}

TYPE
  linked_list_anchor =
    OBJECT
    first: linked_list_node;
    last : linked_list_node;
    CONSTRUCTOR init;
    DESTRUCTOR done;
    PROCEDURE remove_all_nodes;
    PROCEDURE destruct_all_nodes;
    PROCEDURE dispose_all_nodes;
    FUNCTION get_first: linked_list_ptr;
    FUNCTION get_last: linked_list_ptr;
    FUNCTION empty: Boolean;
    PROCEDURE add_to_head (VAR node: linked_list_node);
    PROCEDURE add_to_tail (VAR node: linked_list_node);
    END;


IMPLEMENTATION


{----- Methods for linked_list_anchor -----}

{Initialize the anchor to an empty list.  This method must be called
before the anchor is used.}

CONSTRUCTOR linked_list_anchor.init;
BEGIN
  first.init;
  last.init;
  first.next := @last;
  last.prev := @first
END;


{All nodes on the list are removed from the list.}

PROCEDURE linked_list_anchor.remove_all_nodes;
VAR
  p   : linked_list_ptr;
  next: linked_list_ptr;
BEGIN
  p := get_first;
  WHILE (p <> NIL) DO
    BEGIN
    next := p^.get_next;
    p^.remove;
    p := next
    END
END;


{All nodes on the list are destructed.  All nodes will be removed from
the list, in addition to whatever else the destructor cares to do.}

PROCEDURE linked_list_anchor.destruct_all_nodes;
VAR
  p   : linked_list_ptr;
  next: linked_list_ptr;
BEGIN
  p := get_first;
  WHILE (p <> NIL) DO
    BEGIN
    next := p^.get_next;
    p^.done;
    p := next
    END
END;


{All nodes on the list are Disposed.  All nodes will be destructed,
removing them from the list, and their memory returned to the heap.}

PROCEDURE linked_list_anchor.dispose_all_nodes;
VAR
  p   : linked_list_ptr;
  next: linked_list_ptr;
BEGIN
  p := get_first;
  WHILE (p <> NIL) DO
    BEGIN
    next := p^.get_next;
    Dispose (p, done);
    p := next
    END
END;


{Destruct the anchor.  All nodes on the list are removed from the list.
The nodes themselves are not destructed or disposed!  If you want to do
THAT, invoke the "destruct_all_nodes" or "dispose_all_nodes" methods.}

DESTRUCTOR linked_list_anchor.done;
VAR
  p   : linked_list_ptr;
  next: linked_list_ptr;
BEGIN
  remove_all_nodes
END;


{Returns a pointer to the first node in the list, or NIL if the list is
empty.}

FUNCTION linked_list_anchor.get_first: linked_list_ptr;
BEGIN
  IF empty THEN
    get_first := NIL
  ELSE
    get_first := first.next
END;


{Returns a pointer to the last node in the list, or NIL if the list is
empty.}

FUNCTION linked_list_anchor.get_last: linked_list_ptr;
BEGIN
  IF empty THEN
    get_last := NIL
  ELSE
    get_last := last.prev
END;


{Returns True if the list is empty.}

FUNCTION linked_list_anchor.empty: Boolean;
BEGIN
  empty := first.next = @last
END;


{Add the node to the head of this list.  If the node is already on a
list, it is removed from that list first.}

PROCEDURE linked_list_anchor.add_to_head (VAR node: linked_list_node);
BEGIN
  node.add_after (first)
END;


{Add the node to the tail of this list.  If the node is already on a
list, it is removed from that list first.}

PROCEDURE linked_list_anchor.add_to_tail (VAR node: linked_list_node);
BEGIN
  node.add_before (last)
END;


{----- Methods for linked_list_node -----}


{Construct the node.  Must be invoked before the node is used.}

CONSTRUCTOR linked_list_node.init;
BEGIN
  prev := NIL;
  next := NIL
END;


{Destruct the node.  If it's on a list, remove it.}

DESTRUCTOR linked_list_node.done;
BEGIN
  remove
END;


{If the node is on a list, remove it.}

PROCEDURE linked_list_node.remove;
BEGIN
  IF prev <> NIL THEN
    prev^.next := next;
  IF next <> NIL THEN
    next^.prev := prev;
  prev := NIL;
  next := NIL
END;

{Get the pointer to the previous node, or NIL if there is no previous
node.}

FUNCTION linked_list_node.get_prev: linked_list_ptr;
BEGIN
  IF prev^.prev = NIL THEN
    get_prev := NIL
  ELSE
   get_prev := prev
END;


{Get the pointer to the next node, or NIL if there is no next node.}

FUNCTION linked_list_node.get_next: linked_list_ptr;
BEGIN
  IF next^.next = NIL THEN
    get_next := NIL
  ELSE
    get_next := next
END;


{If this node is in a list, remove it.  Then insert this node into
whatever list p is in, putting it after p.}

PROCEDURE linked_list_node.add_after (VAR node: linked_list_node);
BEGIN
  remove;
  next := node.next;
  prev := @node;
  next^.prev := @Self;
  prev^.next := @Self
END;


{If this node is in a list, remove it.  Then insert this node into
whatever list p is in, putting it before p.}

PROCEDURE linked_list_node.add_before (VAR node: linked_list_node);
BEGIN
  remove;
  prev := node.prev;
  next := @node;
  prev^.next := @Self;
  next^.prev := @Self
END;


END.