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