File : pragmarc-list_bounded_unprotected.ads
-- PragmAda Reusable Component (PragmARC)
-- Copyright (C) 2002 by PragmAda Software Engineering. All rights reserved.
-- **************************************************************************
--
-- General purpose list for sequential use only
-- A list has elements in sequence; each element has a position in that sequence
-- Positions are used to manipulate a list
-- Each list has a maximum length
--
-- History:
-- 2002 Oct 01 J. Carter V1.1--Added Context to Iterate; protect list IDs; use mode out to allow scalars
-- 2002 May 01 J. Carter V1.0--Initial release
--
with Ada.Finalization;
generic -- PragmARC.List_Bounded_Unprotected
type Element is limited private;
with procedure Assign (To : out Element; From : in Element) is <>;
package PragmARC.List_Bounded_Unprotected is
pragma Preelaborate;
type Handle (Max_Size : Positive) is limited private;
-- Initial value: empty
type Position is private;
-- A position is initially invalid until assigned a value by First, Last, or Off_List
-- Other positions accessible via Next and Prev
Invalid_Position : exception; -- Raised if a position is invalid
procedure Assign (To : out Handle; From : in Handle);
-- Makes To a copy of From
-- Raises Too_Short if To.Max_Size < Length (From)
-- Nothing is changed if Too_Short is raised
-- Time: O(N)
--
-- Precondition: To.Max_Size <= Length (From) raises Too_Short if violated
procedure Clear (List : in out Handle);
-- Makes List empty; all lists are initially empty --
-- Time: O(N)
--
-- Postcondition: Is_Empty (List)
-- Operations to obtain valid positions for lists:
function First (List : Handle) return Position; -- The position of the first item in List
function Last (List : Handle) return Position; -- The position of the last item in List
function Off_List (List : Handle) return Position;
-- Time: O(1)
--
-- Off_List (List) is the valid Position for List that is returned by Prev (First (List), List)
-- and by Next (Last (List), List)
-- First and Last return Off_List (List) if Is_Empty (List);
-- Operations to obtain valid positions from valid positions:
function Next (Pos : Position; List : Handle) return Position; -- raise Invalid_Position
function Prev (Pos : Position; List : Handle) return Position; -- raise Invalid_Position
-- Next and Prev raise Invalid_Position if Pos is invalid
-- Next (Last (L), L) = Prev (First (L), L) = Off_List (L)
-- Next (Off_List (L), L) = First (L)
-- Prev (Off_List (L), L) = Last (L)
--
-- Time: O(1)
-- Operations to manipulate lists
procedure Insert (Into : in out Handle; Item : in Element; Before : in Position; New_Pos : out Position);
-- Inserts Item before Before
-- Returns the position of Item in Into in New_pos
-- Before => Off_List (Into) is the same as Append with After => Last (Into)
-- Raises Full if Into is full
-- Raises Invalid_Position if Pos is invalid
-- Nothing is changed if Full or Invalid_Position are raised
--
-- Time: O(1)
--
-- Precondition: not Is_Full (Into) raise Full if violated
-- Postcondition: not Is_Empty (Into)
procedure Append (Into : in out Handle; Item : in Element; After : in Position; New_Pos : out Position);
-- Appends Item after After
-- Returns the position of Item in Into in New_Pos
-- After => Off_List (Into) is the same as Insert with Before => First (Into)
-- Raises Full if Into is full
-- Raises Invalid_Position if Pos is invalid
-- Nothing is changed if Full or Invalid_Position are raised
--
-- Time: O(1)
--
-- Precondition: not Is_Full (Into) raise Full if violated
-- Postcondition: not Is_Empty (Into)
procedure Delete (From : in out Handle; Pos : in out Position); -- raise Invalid_Position
-- Deletes the item at Pos
-- Pos is made invalid
-- Raises Empty if From is empty
-- Raises Invalid_Position if Pos is invalid or Off_List (From)
-- Nothing is changed if Invalid_Position is raised
--
-- Time: O(1)
--
-- Precondition: not Is_Empty (From) raise Empty if violated
-- Postcondition: not Is_Full (From)
function Get (From : Handle; Pos : Position) return Element; -- raise Invalid_Position
-- Returns the item at Pos
-- Raises Invalid_Position if Pos is invalid or Off_List (From)
-- Raises Empty if From is empty
--
-- Time: O(1)
procedure Put (Into : in out Handle; Pos : in Position; Item : in Element); -- raise Invalid_Position
-- Makes the Element stored at Pos be Item
-- Raises Invalid_Position if Pos is invalid or Off_List (Into)
-- Nothing is changed if Invalid_Position is raised
--
-- Time: O(1)
--
-- Postcondition: Get (Into, Pos) = Item
function Is_Empty (List : Handle) return Boolean;
-- Returns True if List is empty [Length (List) = 0]; returns False otherwise
--
-- Time: O(1)
function Is_Full (List : Handle) return Boolean;
-- Returns True if List is full [Length (List) = List.Max_Size];
-- returns False otherwise
--
-- Time: O(1)
function Length (List : Handle) return Natural;
-- Returns a count of the number of items in List
--
-- Time: O(N)
generic -- Iterate
type Context_Data (<>) is limited private;
with procedure Action (Item : in out Element; Context : in out Context_Data; Pos : in Position; Continue : out Boolean);
procedure Iterate (Over : in out Handle; Context : in out Context_Data);
-- Calls Action with each Element in Over, & its Position, in turn
-- Returns immediately if Continue is set to False (remainder of Over is not processed)
private -- PragmARC.List_Bounded_Unprotected
type List_ID is mod 2 ** 32;
Invalid_ID : constant List_ID := 0;
Null_Position : constant Natural := 0;
type Position is record
ID : List_ID := Invalid_ID;
Pos : Natural := Null_Position;
end record;
type Node is record
Prev : Natural;
ID : List_ID := Invalid_ID;
Value : Element;
Next : Natural;
end record;
type List_Storage is array (Positive range <>) of Node;
type Handle (Max_Size : Positive) is new Ada.Finalization.Limited_Controlled with record
ID : List_ID := Invalid_ID;
Head : Natural;
Tail : Natural;
Storage : List_Storage (1 .. Max_Size);
Free : Natural := 1;
end record;
procedure Initialize (Object : in out Handle);
end PragmARC.List_Bounded_Unprotected;
--
-- This is free software; you can redistribute it and/or modify it under
-- terms of the GNU General Public License as published by the Free Software
-- Foundation; either version 2, or (at your option) any later version.
-- This software is distributed in the hope that it will be useful, but WITH
-- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
-- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
-- for more details. Free Software Foundation, 59 Temple Place - Suite
-- 330, Boston, MA 02111-1307, USA.
--
-- As a special exception, if other files instantiate generics from this
-- unit, or you link this unit with other files to produce an executable,
-- this unit does not by itself cause the resulting executable to be
-- covered by the GNU General Public License. This exception does not
-- however invalidate any other reasons why the executable file might be
-- covered by the GNU Public License