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 : Instance := 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 package Doubly_Linked_List is 64 65 --------------------- 66 -- List operations -- 67 --------------------- 68 69 type Instance is private; 70 Nil : constant Instance; 71 72 -- The following exception is raised when the list is empty, and an 73 -- attempt is made to delete an element from it. 74 75 List_Empty : exception; 76 77 procedure Append (L : Instance; Elem : Element_Type); 78 -- Insert element Elem at the end of list L. This action will raise 79 -- Iterated if the list has outstanding iterators. 80 81 function Contains (L : Instance; Elem : Element_Type) return Boolean; 82 -- Determine whether list L contains element Elem 83 84 function Create return Instance; 85 -- Create a new list 86 87 procedure Delete (L : Instance; Elem : Element_Type); 88 -- Delete element Elem from list L. The routine has no effect if Elem is 89 -- not present. This action will raise 90 -- 91 -- * List_Empty if the list is empty. 92 -- * Iterated if the list has outstanding iterators. 93 94 procedure Delete_First (L : Instance); 95 -- Delete an element from the start of list L. This action will raise 96 -- 97 -- * List_Empty if the list is empty. 98 -- * Iterated if the list has outstanding iterators. 99 100 procedure Delete_Last (L : Instance); 101 -- Delete an element from the end of list L. This action will raise 102 -- 103 -- * List_Empty if the list is empty. 104 -- * Iterated if the list has outstanding iterators. 105 106 procedure Destroy (L : in out Instance); 107 -- Destroy the contents of list L. This routine must be called at the 108 -- end of a list's lifetime. This action will raise Iterated if the 109 -- list has outstanding iterators. 110 111 function First (L : Instance) return Element_Type; 112 -- Obtain an element from the start of list L. This action will raise 113 -- List_Empty if the list is empty. 114 115 procedure Insert_After 116 (L : Instance; 117 After : Element_Type; 118 Elem : Element_Type); 119 -- Insert new element Elem after element After in list L. The routine 120 -- has no effect if After is not present. This action will raise 121 -- Iterated if the list has outstanding iterators. 122 123 procedure Insert_Before 124 (L : Instance; 125 Before : Element_Type; 126 Elem : Element_Type); 127 -- Insert new element Elem before element Before in list L. The routine 128 -- has no effect if After is not present. This action will raise 129 -- Iterated if the list has outstanding iterators. 130 131 function Is_Empty (L : Instance) return Boolean; 132 -- Determine whether list L is empty 133 134 function Last (L : Instance) return Element_Type; 135 -- Obtain an element from the end of list L. This action will raise 136 -- List_Empty if the list is empty. 137 138 procedure Prepend (L : Instance; Elem : Element_Type); 139 -- Insert element Elem at the start of list L. This action will raise 140 -- Iterated if the list has outstanding iterators. 141 142 procedure Replace 143 (L : Instance; 144 Old_Elem : Element_Type; 145 New_Elem : Element_Type); 146 -- Replace old element Old_Elem with new element New_Elem in list L. The 147 -- routine has no effect if Old_Elem is not present. This action will 148 -- raise Iterated if the list has outstanding iterators. 149 150 function Size (L : Instance) return Natural; 151 -- Obtain the number of elements in list L 152 153 ------------------------- 154 -- Iterator operations -- 155 ------------------------- 156 157 -- The following type represents an element iterator. An iterator locks 158 -- all mutation operations, and ulocks them once it is exhausted. The 159 -- iterator must be used with the following pattern: 160 -- 161 -- Iter := Iterate (My_List); 162 -- while Has_Next (Iter) loop 163 -- Next (Iter, Element); 164 -- end loop; 165 -- 166 -- It is possible to advance the iterator by using Next only, however 167 -- this risks raising Iterator_Exhausted. 168 169 type Iterator is private; 170 171 function Iterate (L : Instance) return Iterator; 172 -- Obtain an iterator over the elements of list L. This action locks all 173 -- mutation functionality of the associated list. 174 175 function Has_Next (Iter : Iterator) return Boolean; 176 -- Determine whether iterator Iter has more elements to examine. If the 177 -- iterator has been exhausted, restore all mutation functionality of 178 -- the associated list. 179 180 procedure Next (Iter : in out Iterator; Elem : out Element_Type); 181 -- Return the current element referenced by iterator Iter and advance 182 -- to the next available element. If the iterator has been exhausted 183 -- and further attempts are made to advance it, this routine restores 184 -- mutation functionality of the associated list, and then raises 185 -- Iterator_Exhausted. 186 187 private 188 -- The following type represents a list node 189 190 type Node; 191 type Node_Ptr is access all Node; 192 type Node is record 193 Elem : Element_Type; 194 195 Next : Node_Ptr := null; 196 Prev : Node_Ptr := null; 197 end record; 198 199 -- The following type represents a list 200 201 type Linked_List is record 202 Elements : Natural := 0; 203 -- The number of elements in the list 204 205 Iterators : Natural := 0; 206 -- Number of outstanding iterators 207 208 Nodes : aliased Node; 209 -- The dummy head of the list 210 end record; 211 212 type Instance is access all Linked_List; 213 Nil : constant Instance := null; 214 215 -- The following type represents an element iterator 216 217 type Iterator is record 218 List : Instance := null; 219 -- Reference to the associated list 220 221 Nod : Node_Ptr := null; 222 -- Reference to the current node being examined. The invariant of the 223 -- iterator requires that this field always points to a valid node. A 224 -- value of null indicates that the iterator is exhausted. 225 end record; 226 end Doubly_Linked_List; 227 228end GNAT.Lists; 229