1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173 | -- Abstract :
--
-- A simple unbounded sorted vector of definite items.
--
-- Copyright (C) 2019 - 2021 Free Software Foundation, Inc.
--
-- This library 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 3, or (at your option) any later
-- version. This library is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHAN-
-- TABILITY or FITNESS FOR A PARTICULAR PURPOSE.
-- As a special exception under Section 7 of GPL version 3, you are granted
-- additional permissions described in the GCC Runtime Library Exception,
-- version 3.1, as published by the Free Software Foundation.
pragma License (Modified_GPL);
with Ada.Finalization;
with Ada.Iterator_Interfaces;
with Ada.Unchecked_Deallocation;
generic
type Element_Type is private;
type Key_Type is private;
with function To_Key (Item : in Element_Type) return Key_Type;
with function Key_Compare (Left, Right : in Key_Type) return Compare_Result;
Default_Element : in Element_Type;
package SAL.Gen_Unbounded_Definite_Vectors_Sorted is
use all type Ada.Containers.Count_Type;
type Vector is new Ada.Finalization.Controlled with private with
Constant_Indexing => Constant_Ref,
Default_Iterator => Iterate,
Iterator_Element => Element_Type;
Empty_Vector : constant Vector;
overriding procedure Finalize (Container : in out Vector);
overriding procedure Adjust (Container : in out Vector);
procedure Clear (Container : in out Vector)
renames Finalize;
function Length (Container : in Vector) return Ada.Containers.Count_Type;
function Capacity (Container : in Vector) return Ada.Containers.Count_Type;
procedure Set_Capacity
(Container : in out Vector;
Length : in Ada.Containers.Count_Type);
-- Allocates uninitialized memory; does not change Container.First,
-- Container.Last.
function "&" (Left, Right : in Element_Type) return Vector;
function "&" (Left : in Vector; Right : in Element_Type) return Vector;
function Contains (Container : in Vector; Key : in Key_Type) return Boolean;
procedure Insert
(Container : in out Vector;
New_Item : in Element_Type);
-- Insert New_Item in sorted position. Items are sorted in increasing
-- order according to Element_Compare.
--
-- Raises Duplicate_Key if To_Key (New_Item) is already in Container.
type Find_Reference_Type (Element : access Element_Type) is private with
Implicit_Dereference => Element;
function Find
(Container : aliased in Vector;
Key : in Key_Type)
return Find_Reference_Type;
-- Result.Element is null if Key not in Container. User must not modify Key.
type Find_Reference_Constant_Type (Element : access constant Element_Type) is private with
Implicit_Dereference => Element;
function Find_Constant
(Container : aliased in Vector;
Key : in Key_Type)
return Find_Reference_Constant_Type;
-- Result.Element is null if Key not in Container.
type Cursor is private;
No_Element : constant Cursor;
function Has_Element (Position : Cursor) return Boolean;
package Iterator_Interfaces is new Ada.Iterator_Interfaces (Cursor, Has_Element);
function Iterate (Container : aliased in Vector) return Iterator_Interfaces.Reversible_Iterator'Class;
type Constant_Reference_Type (Element : not null access constant Element_Type) is private with
Implicit_Dereference => Element;
function Constant_Ref (Container : aliased Vector; Position : in Cursor) return Constant_Reference_Type
with Inline,
Pre => To_Index (Position) in Container.First_Index .. Container.Last_Index;
function First_Index (Container : in Vector) return Peek_Type is (Peek_Type'First);
function Last_Index (Container : in Vector) return Base_Peek_Type
with Inline;
function To_Index (Position : in Cursor) return Base_Peek_Type;
function Constant_Ref (Container : aliased Vector; Index : in Peek_Type) return Constant_Reference_Type
with Inline,
Pre => Index in Container.First_Index .. Container.Last_Index;
private
type Array_Type is array (SAL.Peek_Type range <>) of aliased Element_Type;
type Array_Access is access Array_Type;
procedure Free is new Ada.Unchecked_Deallocation (Array_Type, Array_Access);
No_Index : constant Base_Peek_Type := 0;
type Vector is new Ada.Finalization.Controlled with
record
Elements : Array_Access;
-- Elements may be non-null with First = No_Index, after
-- Set_Capacity. If First /= No_Index and Last >= First, Elements /=
-- null.
Last : Base_Peek_Type := No_Index;
end record;
type Vector_Access is access constant Vector;
for Vector_Access'Storage_Size use 0;
type Cursor is record
Index : Base_Peek_Type := No_Index;
end record;
type Iterator (Container : not null access constant Vector) is new Iterator_Interfaces.Reversible_Iterator
with null record;
overriding function First (Object : Iterator) return Cursor;
overriding function Last (Object : Iterator) return Cursor;
overriding function Next
(Object : Iterator;
Position : Cursor) return Cursor;
overriding function Previous
(Object : Iterator;
Position : Cursor) return Cursor;
type Find_Reference_Type (Element : access Element_Type) is
record
Dummy : Integer := raise Program_Error with "uninitialized reference";
end record;
type Find_Reference_Constant_Type (Element : access constant Element_Type) is
record
Dummy : Integer := raise Program_Error with "uninitialized reference";
end record;
type Constant_Reference_Type (Element : not null access constant Element_Type) is
record
Dummy : Integer := raise Program_Error with "uninitialized reference";
end record;
Empty_Vector : constant Vector := (Ada.Finalization.Controlled with others => <>);
No_Element : constant Cursor := (others => <>);
----------
-- Visible for child package
procedure Grow (Elements : in out Array_Access; Index : in Base_Peek_Type);
end SAL.Gen_Unbounded_Definite_Vectors_Sorted;
|