Category : Files from Magazines
Archive   : PJ94.ZIP
Filename : DLRING.ADS

-- ========================= begin comment ===========================
-- dlring.ads
--
-- ******* PACKAGE SPECIFICATION ******
-- for a simple doubly-linked ring
-- data structure - partial implementation
--
-- There are many ways to implement a doubly-linked ring.
-- This listing is the Ada solution submitted by one of my
-- undergraduate computer science students. It can be improved
-- and made more reliable. Notably, the use of a counter to
-- control subprograms that traverse the ring contains some
-- potential dangers. It might be better to have a "marked"
-- node that serves as the starting and ending point for any
-- traversal algorithm. This is a good data structure on which
-- to experiment. Try to make it more efficient. Try to make it
-- more reliable. Add some additional functionality to it.
-- ========================= end of comment =========================

with TEXT_IO;
generic -- define generic formal parameters

type DLRing_Type is private;
with function EQUAL (LEFT, RIGHT : DLRing_Type) return BOOLEAN;

package DLRing is
--
type DIRECTION_TYPE is (FORWARD, BACKWARD); -- rotation
type FINGER_TYPE is limited private;

procedure ROTATE (DIRECTION : in DIRECTION_TYPE;
FINGER : in out FINGER_TYPE);

procedure INSERT (ITEM : in DLRing_Type;
FINGER : in out FINGER_TYPE);

procedure REPLACE (ITEM : in DLRing_Type;
FINGER : in out FINGER_TYPE);

procedure DELETE (FINGER : in out FINGER_TYPE;
EMPTY_ERROR : out BOOLEAN);

procedure PEEK (ITEM : out DLRing_Type;
FINGER : in out FINGER_TYPE;
EMPTY_ERROR : out BOOLEAN);

procedure SEARCH (FINGER : in out FINGER_TYPE;
ITEM : in DLRing_Type;
FOUND : out BOOLEAN);

function Is_Count (Finger : Finger_Type) return Natural;

private
type CELL; -- an incomplete type
type POINTER is access CELL; -- set up a pointer type
type FINGER_TYPE is -- keeps track of where
record -- we are in the ring
PTR : POINTER;
CNTR : NATURAL := 0;
end record;
end DLRing;
-- ++++++++++++++++ End of Package Specification ++++++++++++++++++++