From: Jeffrey Carter <jrcarter@acm.org>
Subject: List Strawman JC01
Date: Wed, 05 Dec 2001 06:08:52 GMT
Date: 2001-12-05T06:08:52+00:00 [thread overview]
Message-ID: <3C0DB9D0.7184868A@acm.org> (raw)
Here's an attempt at providing an unbounded list specification that
adheres to the current consensus as I understand it. It also provides
some alternative naming conventions for consideration.
--
Jeff Carter
"You empty-headed animal-food-trough wiper."
Monty Python & the Holy Grail
-- Proposed standard unbounded list ADT adhering to the
-- consensus reached so far
with Ada.Finalization;
generic -- List_Strawman_JC01
type Element is private;
package List_Strawman_JC01 is -- Real name TBD
pragma Preelaborate;
type List_Handle is private; -- Initial value: Empty
-- [Keep the name List for parameters]
type Location is private; -- A position within a list;
-- Degree of safety TBD
-- Initial value: invalid
-- [Keep the shorter name Position for parameters]
procedure Clear (List : in out List_Handle);
-- Makes List Empty.
--
-- Time: O(N)
--
-- Postcondition: Is_Empty (List)
-- [Apparently unneeded List_Handle parameters are supplied
-- to some operations in case they're needed for safety.]
function Valid (Position : Location; List : List_Handle)
return Boolean;
-- Returns True if Position is a valid Location in List;
-- returns False otherwise.
--
-- Time: O(1)
-- Functions to obtain Locations from a List_Handle:
function First (List : List_Handle) return Location;
function Last (List : List_Handle) return Location;
-- These return the Location that designates the first or
-- last Element stored in List, respectively.
-- They return an invalid Location if List is empty.
--
-- Time: O(1)
-- Functions to obtain Locations from other Locations:
function Next (Position : Location; List : List_Handle)
return Location;
function Previous (Position : Location; List : List_Handle)
return Location;
-- These return the following or preceding Location in List
-- relative to Position.
-- Next (Last (List) ) returns an invalid Location.
-- Previous (First (List) ) returns an invalid Location.
-- When applied to an invalid Location, these return an
-- invalid location.
Storage_Exhausted : exception;
procedure Insert (Into : in out List_Handle;
Item : in Element;
Before : in Location;
Position: out Location);
-- Inserts Item into Into before the Element at Before.
-- Position becomes a valid Location in Into that
-- designates the position at which Item is stored.
-- If Before is invalid, Inserts Item as the first
-- Element in Into.
--
-- Raises Storage_Exhausted if memory cannot be allocated
-- to store Item in Into
--
-- Time: O(1)
--
-- Postcondition: not Is_Empty (Into)
procedure Append (Into : in out List_Handle;
Item : in Element;
After : in Location;
Position : out Location);
-- Similar to Insert, except Item is placed after the
-- Element at After.
-- If After is invalid, Item becomes the last Element
-- in Into.
--
-- Raises Storage_Exhausted if memory cannot be allocated
-- to store Item in Into
--
-- Time: O(1)
--
-- Postcondition: not Is_Empty (Into)
Invalid_Location : exception;
function Get (From : List_Handle; Position : Location)
return Element;
-- Returns the Element stored in From at Position.
-- Raises Invalid_Position if Position is invalid.
--
-- Time: O(1)
--
-- Precondition: Valid (Position, From) raises Invalid_Position
procedure Delete (From : in out List_Handle;
Position : in out Location);
-- Deletes the Element stored at Position in From.
-- Raises Invalid_Position if Position is invalid.
--
-- Time: O(1)
--
-- Precondition: Valid (Position, From) raises Invalid_Position
procedure Update (List : in List_Handle;
Item : in Element;
Position : in Location);
-- Modifies the Element stored at Position in List
-- to be Item.
-- Raises Invalid_Position if Position is invalid.
--
-- Time: O(1)
--
-- Precondition: Valid (Position, From) raises Invalid_Position
--
-- Postcondition: Get (List, Position) = Item
function Is_Empty (List : List_Handle) return Boolean;
-- Returns True if List is empty; False otherwise
--
-- Time: O(1)
function Length (List : List_Handle) return Natural;
-- Returns the number of Elements stored in List
--
-- Time: O(1) or O(N), depending on implementation
generic -- Iterate
with procedure Action (Item : in out Element;
Position : in Location;
Quit : out Boolean);
procedure Iterate (Over : in List_Handle);
-- Applies Action to each Element in Over, and its Location,
-- in turn.
-- Returns immediately if Quit is set to True (any remaining
-- Elements in Over are not processed).
--
-- Time: O(N)
generic -- Sort
with function "<" (Left : Element; Right : Element)
return Boolean;
procedure Sort (List : in out List_Handle);
-- Sorts List into ascending order as defined by "<"
--
-- Time : O(N log N)
-- Any other operations considered necessary
private -- List_Strawman_JC01
-- Dummy private part
type List_Handle is new Ada.Finalization.Controlled
with null record;
procedure Adjust (Object : in out List_Handle);
procedure Finalize (Object : in out List_Handle);
type Location is new Boolean;
end List_Strawman_JC01;
next reply other threads:[~2001-12-05 6:08 UTC|newest]
Thread overview: 39+ messages / expand[flat|nested] mbox.gz Atom feed top
2001-12-05 6:08 Jeffrey Carter [this message]
2001-12-05 19:14 ` List Strawman JC01 Ted Dennison
2001-12-06 0:14 ` Jeffrey Carter
2001-12-06 3:15 ` Jeffrey Carter
2001-12-06 16:11 ` Ted Dennison
2001-12-06 17:48 ` Jeffrey Carter
2001-12-07 15:06 ` Ted Dennison
2001-12-07 17:43 ` Stephen Leake
2001-12-07 18:59 ` Ted Dennison
2001-12-09 14:04 ` Mark Lundquist
2001-12-10 15:25 ` Ted Dennison
2001-12-10 15:46 ` Marin David Condic
2001-12-10 17:12 ` Ted Dennison
2001-12-07 18:10 ` Jeffrey Carter
2001-12-07 19:45 ` Ted Dennison
2001-12-07 22:47 ` Basic Properties of Lists Jeffrey Carter
2001-12-09 14:04 ` Mark Lundquist
2001-12-09 18:16 ` Chad R. Meiners
2001-12-09 21:21 ` Jeffrey Carter
2001-12-10 15:37 ` Ted Dennison
2001-12-10 22:13 ` Jeffrey Carter
2001-12-11 14:33 ` Ted Dennison
2001-12-09 14:04 ` List Strawman JC01 Mark Lundquist
2001-12-10 17:02 ` Ted Dennison
2001-12-10 17:13 ` Ted Dennison
2001-12-10 15:37 ` Marin David Condic
2001-12-10 16:10 ` Larry Hazel
2001-12-06 19:09 ` Stephen Leake
2001-12-06 22:45 ` Jeffrey Carter
2001-12-07 16:54 ` Ted Dennison
2001-12-07 17:18 ` Darren New
2001-12-07 17:44 ` Doubly-linked list ordering(s) (was: List Strawman JC01) Ted Dennison
2001-12-07 17:30 ` List Strawman JC01 Ted Dennison
2001-12-06 19:34 ` Mark Lundquist
2001-12-07 17:04 ` Ted Dennison
2001-12-07 22:27 ` Jeffrey Carter
2001-12-09 14:04 ` Mark Lundquist
2001-12-06 19:34 ` Mark Lundquist
2001-12-06 23:09 ` Nick Roberts
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox