pragma Preelaborate (Ordered_Sets);
|
Type Summary
Cursor |
| Primitive Operations: |
"<",
"<",
"<",
">",
">",
">",
Ceiling,
Delete,
Element,
Find,
First,
Floor,
Has_Element,
Insert,
Last,
Next,
Next,
Previous,
Previous
|
Iterate_Process |
Reverse_Iterate_Process |
Set |
| Primitive Operations: |
"-",
"=",
"and",
"or",
"xor",
Ceiling,
Clear,
Delete,
Delete,
Delete_First,
Delete_Last,
Difference,
Difference,
Find,
First,
First_Element,
Floor,
Insert,
Intersection,
Intersection,
Is_Disjoint,
Is_Empty,
Is_In,
Is_Subset,
Iterate,
Last,
Last_Element,
Length,
Move,
Reverse_Iterate,
Symmetric_Difference,
Symmetric_Difference,
Union,
Union
|
|
Constants and Named Numbers
Empty_Set : constant Set;
|
|
Represents the empty ordered set. If an object of type Set
is not otherwise initialized, it will be initialized to the same value
as Empty_Set.
|
No_Element : constant Cursor;
|
|
Represents a cursor that designates no element. If an object of type
Cursor is not otherwise initialized, it will be initialized
to the same value as No_Element.
|
|
Other Items:
|
type Set is tagged private;
|
|
The type Set needs finalization (see 7.6).
|
|
|
function "=" (Left, Right : Set) return Boolean;
|
|
If Left and Right denote the same object, then
the function returns True. If Left and
Right have different lengths, then the function returns
False. Otherwise, it compares elements in sequential order using
the generic formal equality operator for elements. Any exception raised
during evaluation of element equality is propagated. If a corresponding
pair of elements compare False, the function returns
False. Otherwise if all corresponding elements compare
True, the function returns True.
|
|
function Length (Container : Set) return Count_Type;
|
|
Returns the number of elements in Container.
|
|
function Is_Empty (Container : Set) return Boolean;
|
|
Equivalent to Length (Container) = 0.
|
|
procedure Clear (Container : in out Set);
|
|
Removes all the elements in Set, and sets the length to 0.
|
|
function Element (Position : Cursor) return Element_Type;
|
|
If Position equals No_Element, then
Constraint_Error is propagated. Otherwise, it
returns the element designated by Position.
|
|
procedure Move (Target : in out Set;
Source : in out Set);
|
|
If the length of Target is greater than 0, then Move
raises Constraint_Error.
Otherwise, the elements are removed from Source and moved
to Target. The length of Source is 0 after a
successful call to Move.
|
|
procedure Insert (Container : in out Set;
New_Item : in Element_Type;
Position : out Cursor;
Success : out Boolean);
|
Insert compares New_Item to the elements in
Container using the generic formal less-than operator for
elements. If an element equivalent (see below) to New_Item
is already in Container, Success is
False and Position designates the element.
Otherwise, it allocates a new element which is initialized to
New_Item. Success returns True and
Position designates the newly-inserted element. Any
exceptions raised during allocation are propagated and Container
is not modified.
NOTE:
A nice function might be:
procedure Insert (Container : in out Set;
New_Item : in Element_Type);
This is a convenience function that omits the last two params.
END NOTE.
|
|
procedure Delete (Container : in out Set;
Item : in Element_Type);
|
|
Delete searches Container for an element equivalent to
Item. If there is an element in Container
equivalent to Item, the element is removed from
Container.
|
|
procedure Delete (Container : in out Set;
Position : in out Cursor);
|
|
If Position equals No_Element, the operation
has no effect. Otherwise, Delete removes the element
designated by Position from Container.
Position is set to No_Element on return.
|
|
procedure Delete_First (Container : in out Set);
|
|
If Container is empty, the operation has no effect.
Otherwise the element designated by First (Container) is
removed from Container.
|
|
procedure Delete_Last (Container : in out Set);
|
|
If Container is empty, the operation has no effect.
Otherwise the element designated by Last (Container) is
removed from Container.
|
|
procedure Union (Target : in out Set;
Source : in Set);
|
|
The elements of Source that are not equivalent to items
already in Target are inserted into Target.
|
|
function Union (Left, Right : Set) return Set;
|
|
Returns a set comprising all of the elements of Left, and
the elements of Right that are not equivalent to elements
of Left.
|
|
|
procedure Intersection (Target : in out Set;
Source : in Set);
|
|
All the elements of Target that are not equivalent to the
corresponding elements of Source are deleted from
Target.
|
|
function Intersection (Left, Right : Set) return Set;
|
|
Returns a set comprising all the elements of Left that are
equivalent to the corresponding elements of Right.
|
|
|
procedure Difference (Target : in out Set;
Source : in Set);
|
|
If Target denotes the same object as Source,
then the operation clears Target. Otherwise, it deletes the
elements of Target that are equivalent to elements of
Source.
|
|
function Difference (Left, Right : Set) return Set;
|
|
Returns a set comprising the elements of Left that are not
equivalent to the corresponding elements of Right.
|
|
|
procedure Symmetric_Difference (Target : in out Set;
Source : in Set);
|
|
If Target denotes the same object as Source,
then the operation clears Target. Otherwise, it deletes the
elements of Target that are equivalent to elements of
Source, and inserts the elements are Source
that are not equivalent to the corresponding elements of Target
.
|
|
function Symmetric_Difference (Left, Right : Set) return Set;
|
|
Returns a set comprising the elements of Left that are not
equivalent to the corresponding elements of Right, and the
elements of Right that are not equivalent to the
corresponding elements of Left.
|
|
|
function Is_Subset (Item : Set;
Container : Set)
return Boolean;
|
|
If an element of Item is not equivalent to some element of
Container, the function returns False.
Otherwise it returns True.
|
|
function Is_Disjoint (Item : Set;
Container : Set)
return Boolean;
|
|
If an element of Item is equivalent to some element of
Container, then Is_Disjoint returns
False. Otherwise it returns True.
|
|
function Is_In (Item : Element_Type;
Container : Set)
return Boolean;
|
|
Equivalent to Find (Set, Item) /= No_Element.
|
|
function Find (Container : Set;
Item : Element_Type)
return Cursor;
|
|
The Find operation searches for the element equivalent to
Item. If it finds an equivalent element, it returns a
cursor designating the element. Otherwise it returns No_Element
.
|
|
function Ceiling (Container : Set;
Item : Element_Type)
return Cursor;
|
|
The Ceiling operation searches for the smallest element not
less than Item, using the generic formal less-than operator
for elements. If there is an element in Set that is not
less than Item, it returns a cursor designating the node
containing the element. Otherwise it returns No_Element.
|
|
function Floor (Container : Set;
Item : Element_Type)
return Cursor;
|
|
The Floor operation searches for the largest element not
greater than Item, using the generic formal less-than
operator for elements. If there is an element in Set that
is not greater than Item, it returns a cursor designating
the node containing the element. Otherwise it returns No_Element
.
|
|
function First (Container : Set) return Cursor;
|
|
Returns a cursor that designates the smallest element. If
Container is empty, it returns No_Element.
|
|
function First_Element (Container : Set) return Element_Type;
|
|
If Container is empty, then Constraint_Error
is propagated. Otherwise, it returns the element
designated by First (Container).
|
|
function Last (Container : Set) return Cursor;
|
|
Returns a cursor that designates the greatest element. If
Container is empty, it returns No_Element.
|
|
function Last_Element (Container : Set) return Element_Type;
|
|
If Container is empty, then Constraint_Error
is propagated. Otherwise, it returns the element
designated by Last (Container).
|
|
function Next (Position : Cursor) return Cursor;
|
|
If Position equals No_Element, then
No_Element is returned. Otherwise it returns the successor of the
element designated by Position.
|
|
function Previous (Position : Cursor) return Cursor;
|
|
If Position equals No_Element, then
No_Element is returned. Otherwise it returns the predecessor of
the element designated by Position.
|
|
procedure Next (Position : in out Cursor);
|
|
Equivalent to Position := Next (Position).
|
|
procedure Previous (Position : in out Cursor);
|
|
Equivalent to Position := Previous (Position).
|
|
function Has_Element (Position : Cursor) return Boolean;
|
|
Returns True if Position designates an
element, and returns False otherwise.
|
|
function "<" (Left, Right : Cursor) return Boolean;
|
|
Equivalent to Element (Left) < Element (Right).
|
|
function ">" (Left, Right : Cursor) return Boolean;
|
|
Equivalent to Element (Right) < Element (Left).
|
|
|
|
|
|
|
procedure Iterate
(Container : in Set;
Process : Iterate_Process);
|
Ada0Y not null access procedure (Position : in Cursor));
The best we can do in Ada95 is to generate a run-time error, so if
Process is null a Program_Error
is raised.
Invokes Process.all with a cursor that designates each
element in Container.
|
|
|
procedure Reverse_Iterate
(Container : in Set;
Process : Reverse_Iterate_Process);
|
Ada0Y not null access procedure (Position : in Cursor));
The best we can do in Ada95 is to generate a run-time error, so if
Process is null a Program_Error
is raised.
Iterates over the elements in Container as per
Iterate, with the difference that the nodes are traversed in
reverse order.
|
|
generic
type Key_Type (<>) is limited private;
with function Key (Element : in Element_Type) return Key_Type;
with function "<" (Left : Key_Type; Right : Element_Type)
return Boolean is <>;
with function ">" (Left : Key_Type; Right : Element_Type)
return Boolean is <>;
package Generic_Keys is
|
|
The package Generic_Keys provides operations that allow
set manipulation in terms of a key (typically, a portion of an
element) instead of a complete element.
The formal function Key is intended to extract a key
value from an element. For any two elements E1 and
E2, it is expected that (E1 < E2) = (Key(E1) < E2)
= (Key(E2) > E1). If Key, "<", or
">" behaves in some other manner, the behavior of this
package is unspecified. Which subprograms of this package call
Key, "<" and ">", and how
many times the functions are called, is unspecified.
|
Type Summary
|
Other Items:
|
|
|
|
|
|
|
|
|
|
function ">" (Left : Key_Type; Right : Cursor)
return Boolean;
|
|
MJH: this is my preferred declaration, but Randy B.
likes not having to make a separate instantion.
ENDMJH.
generic
with function Key (Element : in Element_Type) return Key_Type;
procedure Generic_Update_Element
(Container : in out Set;
Position : in Cursor;
Process : not null access
procedure (Element : in out Element_Type));
|
|
|
procedure Update_Element
(Container : in out Set;
Position : in Cursor;
Process : Update_Element_Process);
|
Ada0Y
not null access procedure (Element : in out Element_Type));
The best we can do in Ada95 is to generate a run-time error, so if
Process is null a Program_Error
is raised.
|
|
|
end Generic_Keys;
|
|
|
private
|