1------------------------------------------------------------------------------
2--                                                                          --
3--                         GNAT RUN-TIME COMPONENTS                         --
4--                                                                          --
5--                            G N A T . L I S T S                           --
6--                                                                          --
7--                                 S p e c                                  --
8--                                                                          --
9--             Copyright (C) 2018-2019, Free Software Foundation, Inc.      --
10--                                                                          --
11-- GNAT is free software;  you can  redistribute it  and/or modify it under --
12-- terms of the  GNU General Public License as published  by the Free Soft- --
13-- ware  Foundation;  either version 3,  or (at your option) any later ver- --
14-- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
15-- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
16-- or FITNESS FOR A PARTICULAR PURPOSE.                                     --
17--                                                                          --
18-- As a special exception under Section 7 of GPL version 3, you are granted --
19-- additional permissions described in the GCC Runtime Library Exception,   --
20-- version 3.1, as published by the Free Software Foundation.               --
21--                                                                          --
22-- You should have received a copy of the GNU General Public License and    --
23-- a copy of the GCC Runtime Library Exception along with this program;     --
24-- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
25-- <http://www.gnu.org/licenses/>.                                          --
26--                                                                          --
27-- GNAT was originally developed  by the GNAT team at  New York University. --
28-- Extensive contributions were provided by Ada Core Technologies Inc.      --
29--                                                                          --
30------------------------------------------------------------------------------
31
32pragma Compiler_Unit_Warning;
33
34package GNAT.Lists is
35
36   ------------------------
37   -- Doubly_Linked_List --
38   ------------------------
39
40   --  The following package offers a doubly linked list abstraction with the
41   --  following characteristics:
42   --
43   --    * Creation of multiple instances, of different sizes
44   --    * Iterable elements
45   --
46   --  The following use pattern must be employed with this list:
47   --
48   --    List : Doubly_Linked_List := Create;
49   --
50   --    <various operations>
51   --
52   --    Destroy (List);
53   --
54   --  The destruction of the list reclaims all storage occupied by it.
55
56   generic
57      type Element_Type is private;
58
59      with function "="
60        (Left  : Element_Type;
61         Right : Element_Type) return Boolean;
62
63      with procedure Destroy_Element (Elem : in out Element_Type);
64      --  Element destructor
65
66   package Doubly_Linked_Lists is
67
68      ---------------------
69      -- List operations --
70      ---------------------
71
72      type Doubly_Linked_List is private;
73      Nil : constant Doubly_Linked_List;
74
75      --  The following exception is raised when the list is empty, and an
76      --  attempt is made to delete an element from it.
77
78      List_Empty : exception;
79
80      procedure Append
81        (L    : Doubly_Linked_List;
82         Elem : Element_Type);
83      --  Insert element Elem at the end of list L. This action will raise
84      --  Iterated if the list has outstanding iterators.
85
86      function Contains
87        (L    : Doubly_Linked_List;
88         Elem : Element_Type) return Boolean;
89      --  Determine whether list L contains element Elem
90
91      function Create return Doubly_Linked_List;
92      --  Create a new list
93
94      procedure Delete
95        (L    : Doubly_Linked_List;
96         Elem : Element_Type);
97      --  Delete element Elem from list L. The routine has no effect if Elem is
98      --  not present. This action will raise
99      --
100      --    * List_Empty if the list is empty.
101      --    * Iterated if the list has outstanding iterators.
102
103      procedure Delete_First (L : Doubly_Linked_List);
104      --  Delete an element from the start of list L. This action will raise
105      --
106      --    * List_Empty if the list is empty.
107      --    * Iterated if the list has outstanding iterators.
108
109      procedure Delete_Last (L : Doubly_Linked_List);
110      --  Delete an element from the end of list L. This action will raise
111      --
112      --    * List_Empty if the list is empty.
113      --    * Iterated if the list has outstanding iterators.
114
115      procedure Destroy (L : in out Doubly_Linked_List);
116      --  Destroy the contents of list L. This routine must be called at the
117      --  end of a list's lifetime. This action will raise Iterated if the
118      --  list has outstanding iterators.
119
120      function Equal
121        (Left  : Doubly_Linked_List;
122         Right : Doubly_Linked_List) return Boolean;
123      --  Determine whether lists Left and Right have the same characteristics
124      --  and contain the same elements.
125
126      function First (L : Doubly_Linked_List) return Element_Type;
127      --  Obtain an element from the start of list L. This action will raise
128      --  List_Empty if the list is empty.
129
130      procedure Insert_After
131        (L     : Doubly_Linked_List;
132         After : Element_Type;
133         Elem  : Element_Type);
134      --  Insert new element Elem after element After in list L. The routine
135      --  has no effect if After is not present. This action will raise
136      --  Iterated if the list has outstanding iterators.
137
138      procedure Insert_Before
139        (L      : Doubly_Linked_List;
140         Before : Element_Type;
141         Elem   : Element_Type);
142      --  Insert new element Elem before element Before in list L. The routine
143      --  has no effect if After is not present. This action will raise
144      --  Iterated if the list has outstanding iterators.
145
146      function Is_Empty (L : Doubly_Linked_List) return Boolean;
147      --  Determine whether list L is empty
148
149      function Last (L : Doubly_Linked_List) return Element_Type;
150      --  Obtain an element from the end of list L. This action will raise
151      --  List_Empty if the list is empty.
152
153      procedure Prepend
154        (L    : Doubly_Linked_List;
155         Elem : Element_Type);
156      --  Insert element Elem at the start of list L. This action will raise
157      --  Iterated if the list has outstanding iterators.
158
159      function Present (L : Doubly_Linked_List) return Boolean;
160      --  Determine whether list L exists
161
162      procedure Replace
163        (L        : Doubly_Linked_List;
164         Old_Elem : Element_Type;
165         New_Elem : Element_Type);
166      --  Replace old element Old_Elem with new element New_Elem in list L. The
167      --  routine has no effect if Old_Elem is not present. This action will
168      --  raise Iterated if the list has outstanding iterators.
169
170      function Size (L : Doubly_Linked_List) return Natural;
171      --  Obtain the number of elements in list L
172
173      -------------------------
174      -- Iterator operations --
175      -------------------------
176
177      --  The following type represents an element iterator. An iterator locks
178      --  all mutation operations, and ulocks them once it is exhausted. The
179      --  iterator must be used with the following pattern:
180      --
181      --    Iter := Iterate (My_List);
182      --    while Has_Next (Iter) loop
183      --       Next (Iter, Element);
184      --    end loop;
185      --
186      --  It is possible to advance the iterator by using Next only, however
187      --  this risks raising Iterator_Exhausted.
188
189      type Iterator is private;
190
191      function Has_Next (Iter : Iterator) return Boolean;
192      --  Determine whether iterator Iter has more elements to examine. If the
193      --  iterator has been exhausted, restore all mutation functionality of
194      --  the associated list.
195
196      function Iterate (L : Doubly_Linked_List) return Iterator;
197      --  Obtain an iterator over the elements of list L. This action locks all
198      --  mutation functionality of the associated list.
199
200      procedure Next
201        (Iter : in out Iterator;
202         Elem : out Element_Type);
203      --  Return the current element referenced by iterator Iter and advance
204      --  to the next available element. If the iterator has been exhausted
205      --  and further attempts are made to advance it, this routine restores
206      --  mutation functionality of the associated list, and then raises
207      --  Iterator_Exhausted.
208
209   private
210      --  The following type represents a list node
211
212      type Node;
213      type Node_Ptr is access all Node;
214      type Node is record
215         Elem : Element_Type;
216
217         Next : Node_Ptr := null;
218         Prev : Node_Ptr := null;
219      end record;
220
221      --  The following type represents a list
222
223      type Doubly_Linked_List_Attributes is record
224         Elements : Natural := 0;
225         --  The number of elements in the list
226
227         Iterators : Natural := 0;
228         --  Number of outstanding iterators
229
230         Nodes : aliased Node;
231         --  The dummy head of the list
232      end record;
233
234      type Doubly_Linked_List is access all Doubly_Linked_List_Attributes;
235      Nil : constant Doubly_Linked_List := null;
236
237      --  The following type represents an element iterator
238
239      type Iterator is record
240         Curr_Nod : Node_Ptr := null;
241         --  Reference to the current node being examined. The invariant of the
242         --  iterator requires that this field always points to a valid node. A
243         --  value of null indicates that the iterator is exhausted.
244
245         List : Doubly_Linked_List := null;
246         --  Reference to the associated list
247      end record;
248   end Doubly_Linked_Lists;
249
250end GNAT.Lists;
251