1--  Copyright 1994 Grady Booch
2--  Copyright 2005 Martin Krischik
3--  Copyright 1994-1997 David Weller
4--  Copyright 1998-2014 Simon Wright <simon@pushface.org>
5
6--  This package is free software; you can redistribute it and/or
7--  modify it under terms of the GNU General Public License as
8--  published by the Free Software Foundation; either version 2, or
9--  (at your option) any later version. This package is distributed in
10--  the hope that it will be useful, but WITHOUT ANY WARRANTY; without
11--  even the implied warranty of MERCHANTABILITY or FITNESS FOR A
12--  PARTICULAR PURPOSE. See the GNU General Public License for more
13--  details. You should have received a copy of the GNU General Public
14--  License distributed with this package; see file COPYING.  If not,
15--  write to the Free Software Foundation, 59 Temple Place - Suite
16--  330, Boston, MA 02111-1307, USA.
17
18--  As a special exception, if other files instantiate generics from
19--  this unit, or you link this unit with other files to produce an
20--  executable, this unit does not by itself cause the resulting
21--  executable to be covered by the GNU General Public License.  This
22--  exception does not however invalidate any other reasons why the
23--  executable file might be covered by the GNU Public License.
24
25with Ada.Finalization;
26with Ada.Streams;
27with System.Storage_Pools;
28with BC.Support.Indefinite_Reference;
29
30generic
31   type Item (<>) is private;
32   with function "=" (L, R : Item) return Boolean is <>;
33   type Item_Ptr is access Item;
34   Storage : in out System.Storage_Pools.Root_Storage_Pool'Class;
35package BC.Support.Indefinite_Unbounded is
36
37   pragma Preelaborate;
38
39   type Unb_Node is private;
40   --  An unpacked container whose items are stored on the heap.
41   --  Items are effectively indexed from 1.
42
43   function "=" (Left, Right : Unb_Node) return Boolean;
44
45   procedure Clear (Obj : in out Unb_Node);
46   --  Empty the container of all Items
47
48   procedure Insert (Obj : in out Unb_Node; Elem : Item);
49   --  Add an item to the front of the container
50
51   procedure Insert (Obj : in out Unb_Node; Elem : Item; Before : Positive);
52   --  Add an item to the container, before the given index
53
54   procedure Append (Obj : in out Unb_Node; Elem : Item);
55   --  Add an item to the end of the container
56
57   procedure Append (Obj : in out Unb_Node; Elem : Item; After : Positive);
58   --  Add an item to the container, after the given index
59
60   procedure Remove (Obj : in out Unb_Node; From : Positive);
61   --  Remove the item at the given index
62
63   procedure Replace (Obj : in out Unb_Node; Index : Positive; Elem : Item);
64   --  Replace the item at index with the new elem
65
66   function Length (Obj : Unb_Node) return Natural;
67   --  Returns the number of items in the container
68
69   function First (Obj : Unb_Node) return Item;
70   --  Returns the item at the front of the container
71
72   function Last (Obj : Unb_Node) return Item;
73   --  Returns the item at the end of the container
74
75   function Item_At (Obj : Unb_Node; Index : Positive) return Item;
76   function Item_At (Obj : Unb_Node; Index : Positive) return Item_Ptr;
77   --  Returns the item at the given index
78
79   function Location (Obj : Unb_Node; Elem : Item; Start : Positive := 1)
80                     return Natural;
81   --  Returns the first index in which the given item is
82   --  found. Returns 0 if unsuccessful.
83
84private
85
86   type Node;
87   type Node_Ref is access Node;
88   for Node_Ref'Storage_Pool use Storage;
89   package Smart
90   is new BC.Support.Indefinite_Reference (
91      T => Item,
92      P => Item_Ptr);
93   type Node is record
94      Element : Smart.Pointer;
95      Next : Node_Ref;
96      Previous : Node_Ref;
97   end record;
98
99   type Unb_Node is new Ada.Finalization.Controlled with record
100      Rep : Node_Ref;
101      Last : Node_Ref;
102      Size : Natural := 0;
103      Cache : Node_Ref;
104      Cache_Index : Natural := 0; -- 0 means invalid
105   end record;
106
107   procedure Adjust (U : in out Unb_Node);
108   procedure Finalize (U : in out Unb_Node);
109
110   procedure Write_Unb_Node
111     (Stream : access Ada.Streams.Root_Stream_Type'Class;
112      Obj : Unb_Node);
113
114   procedure Read_Unb_Node
115     (Stream : access Ada.Streams.Root_Stream_Type'Class;
116      Obj : out Unb_Node);
117
118   for Unb_Node'Write use Write_Unb_Node;
119   for Unb_Node'Read use Read_Unb_Node;
120
121end BC.Support.Indefinite_Unbounded;
122