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 | -- Abstract :
--
-- Unbounded sparse sets.
--
-- Copyright (C) 2020 - 2022 Free Software Foundation All Rights Reserved.
--
-- 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.
pragma License (Modified_GPL);
with Ada.Iterator_Interfaces;
with SAL.Gen_Unbounded_Definite_Red_Black_Trees;
generic
type Index_Type is private;
-- Index_Type must have a valid default initialization; it is used as
-- Gen_Unbounded_Definite_Red_Black_Trees.Element_Type.
with function Index_Compare (Left, Right : in Index_Type) return Compare_Result;
package SAL.Gen_Unbounded_Sparse_Ordered_Sets is
package Pkg renames Gen_Unbounded_Sparse_Ordered_Sets;
type Set is tagged private
with
Constant_Indexing => Constant_Ref,
Default_Iterator => Iterate,
Iterator_Element => Index_Type;
-- We'd like to have Constant_Indexing return a Boolean, so we could
-- use 'if Set (Item) then'. But then the default iterator would
-- always return True, instead of Index_Type; we can't specify a
-- different Constant_Indexing function for the default iterator.
procedure Clear (Set : in out Pkg.Set);
-- Set Set to empty.
function Count (Set : in Pkg.Set) return Ada.Containers.Count_Type;
procedure Insert (Set : in out Pkg.Set; Item : in Index_Type);
-- No error if already present.
function Contains (Set : in Pkg.Set; Item : in Index_Type) return Boolean;
procedure Delete (Set : in out Pkg.Set; Item : in Index_Type);
-- Invalid while an iterator is active; not enforced.
type Cursor is private;
function Has_Element (Position : in Cursor) return Boolean;
function Element (Position : in Cursor) return Index_Type;
type Constant_Reference_Type (Element : not null access constant Index_Type) is private with
Implicit_Dereference => Element;
function Constant_Ref
(Container : aliased in Set;
Position : in Cursor)
return Constant_Reference_Type
with Inline;
package Iterators is new Ada.Iterator_Interfaces (Cursor, Has_Element);
type Iterator (<>) is new Iterators.Forward_Iterator with private;
function Iterate (Container : aliased in Set'Class) return Iterator;
-- Returns Index_Type of elements that were inserted.
overriding function First (Iterator : in Pkg.Iterator) return Cursor;
overriding function Next (Iterator : in Pkg.Iterator; Position : in Cursor) return Cursor;
private
function Key (Item : in Index_Type) return Index_Type
is (Item);
package Boolean_Trees is new SAL.Gen_Unbounded_Definite_Red_Black_Trees
(Element_Type => Index_Type,
Key_Type => Index_Type,
Key => Key,
Key_Compare => Index_Compare);
type Set is tagged record
Tree : aliased Boolean_Trees.Tree;
end record;
type Constant_Reference_Type (Element : not null access constant Index_Type)
is record
Dummy : Integer := raise Program_Error with "uninitialized reference";
end record;
type Cursor is record
Cur : Boolean_Trees.Cursor;
end record;
Empty_Set : constant Set := (Tree => Boolean_Trees.Empty_Tree);
type Iterator (Container : not null access constant Boolean_Trees.Tree) is new Iterators.Forward_Iterator
with record
Iter : Boolean_Trees.Iterator (Container);
end record;
end SAL.Gen_Unbounded_Sparse_Ordered_Sets;
|