PACKAGE BODY Tables_Generic_List IS
------------------------------------------------------------------------
--| Implementation of the abstract data type for a table of
--| element records, each containing a key.
--| This implementation uses an instantiation of singly-linked lists.
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: September 1995                                     
------------------------------------------------------------------------
  
  USE Lists;

  PROCEDURE InitializeTable (Table : IN OUT TableType) IS
  -- initialize the table by creating the dummy node
    Dummy: Element;
  BEGIN -- InitializeTable

    Initialize(Table.Data);
    Lists.AddToRear (L => Table.Data, X => Dummy);
    Table.CurrentSize := 0;               -- dummy node doesn't count

  END InitializeTable;

-- local procedure, not exported to client, just used by the others.
  
  PROCEDURE Locate(Table        : TableType;
                   Target       : KeyType;
                   Previous     : OUT Position;
                   Current      : OUT Position;
                   SearchSuccess: OUT Boolean) IS
  --  Attempts to locate a node with key value Target in the
  --  list whose first node is pointed to by Previous.
  --  Pre : Target is defined; L is initialized.
  --  Post: If Target is located, SearchSuccess is set to True;
  --    otherwise, SearchSuccess is set to False.
  --    Previous points to the last list node with key < Target,
  --    Current points to the first one with key >= Target.
  --    We need the Temps because Previous and Current are OUT
                   
    CurrentKey     : KeyType; 
    TempPrevious   : Position;   
    TempCurrent    : Position;       -- keeps track of current node
    Found          : Boolean;

  BEGIN -- Locate
  
    IF IsEmpty(Table.Data) THEN            -- no dummy nodes!
      RAISE UninitializedTable;   -- unlikely; Locate not user operation
    END IF;

    -- Search for first node with key >= Target.
    -- Start with first actual node.
    Found := False;
    TempCurrent := First(Table.Data);   -- points to dummy node
    TempPrevious := TempCurrent;
 
    IF IsLast(Table.Data,TempCurrent) THEN  -- no "real" nodes- table empty
      Previous := TempPrevious;
      Current := TempCurrent;
      SearchSuccess := False;
      RETURN;
    END IF;


    TempPrevious := TempCurrent;    
    GoAhead(Table.Data, TempCurrent);   -- to first "real" node

    WHILE NOT IsPastEnd(Table.Data, TempCurrent)
      AND THEN NOT Found LOOP
    -- invariant:
    --   Target > key of each node pointed to by Current so far.
      CurrentKey := KeyOf (Retrieve(Table.Data, TempCurrent));
      IF (Target < CurrentKey) OR (Target = CurrentKey)THEN
        Found := True;
      ELSE
        TempPrevious := TempCurrent;     -- advance Previous
        GoAhead(Table.Data, TempCurrent);
      END IF;
    END LOOP;
    -- assert: Target is located or CurrentKey is larger than Target.

    -- Set Next and flag to indicate search results.
    Previous := TempPrevious;
    Current  := TempCurrent;

    SearchSuccess :=
      (NOT IsPastEnd(Table.Data, TempCurrent))
      AND THEN CurrentKey = Target;
    
  END Locate;

-- Operators

  FUNCTION SizeOfTable (Table : TableType) RETURN Natural IS
  BEGIN
    RETURN Table.CurrentSize;
  END SizeOfTable;

  PROCEDURE Search (Table   : TableType;
                    Target  : KeyType;
                    Success : OUT Boolean) IS 

    Previous      : Position;     -- pointer to node preceding Item
    Current       : Position;     -- pointer to node following Item
    CurrentKey : KeyType;
  BEGIN -- stub

  END Search;

  PROCEDURE Insert (Table   : IN OUT TableType;
                    Item    : Element;
                    Success : OUT Boolean) IS

    Previous      : Position;     -- pointer to node preceding Item
    Current       : Position;     -- pointer to node following Item
    SearchSuccess : Boolean;      -- search result
    ItemKey       : KeyType;      -- key of record Item

  BEGIN -- Insert

    IF IsEmpty(Table.Data) THEN
      RAISE UninitializedTable;
    END IF;

    -- Validate ItemKey and search for a valid key.
    ItemKey := KeyOf (Item);
      -- Search the list for ItemKey.
    Locate (Table, ItemKey, Previous, Current, SearchSuccess);

    -- Insert if ItemKey is in range and is a new key
    IF NOT SearchSuccess THEN             -- insert after Previous
      Success := True;                    -- Key is new iff search failed
      Insert(Table.Data, Item, Previous);  -- insert right here
      Table.CurrentSize := Table.CurrentSize + 1;
    ELSE
      Success := False;
    END IF;

  END Insert;

  PROCEDURE Delete (Table   : IN OUT TableType;
                    Target  : KeyType;
                    Success : OUT Boolean) IS
    Previous      : Position;     -- pointer to node preceding Item
    Current       : Position;     -- pointer to node following Item
  BEGIN -- stub

  END Delete;

  PROCEDURE Replace (Table   : IN OUT TableType;
                     Item    : Element;
                     Success : OUT Boolean) IS
    Previous      : Position;     -- pointer to node preceding Item
    Current       : Position;     -- pointer to node following Item
  BEGIN -- stub

  END Replace;

  PROCEDURE Retrieve (Table   : TableType;
                      Target  : KeyType;
                      Item    : OUT Element;
                      Success : OUT Boolean) IS 
    Previous      : Position;     -- pointer to node preceding Item
    Current       : Position;     -- pointer to node following Item
  BEGIN -- stub

  END Retrieve;

  PROCEDURE Traverse (Table : TableType) IS
    Current: Position;
  BEGIN -- Traverse

    IF IsEmpty(Table.Data) THEN
      RAISE UninitializedTable;
    END IF;
    
    Current := First(Table.Data);
    GoAhead(Table.Data, Current);   -- start with first node after dummy
    WHILE NOT IsPastEnd(Table.Data, Current) LOOP
      Visit (Retrieve(Table.Data, Current));        -- visit node
      GoAhead(Table.Data, Current);    
    END LOOP;

  END Traverse;

END Tables_Generic_List;