Annotated Ada Reference Manual — Legal Information

A.18.9 The Package Containers.Ordered_Sets

Static Semantics

1/2

{AI95-00302-03} The generic library package Containers.Ordered_Sets has the following declaration:

2/2

generic
   type Element_Type is private;
   with function "<" (Left, Right : Element_Type) return Boolean is <>;
   with function "=" (Left, Right : Element_Type) return Boolean is <>;
package Ada.Containers.Ordered_Sets is
   pragma Preelaborate(Ordered_Sets);

3/2

function Equivalent_Elements (Left, Right : Element_Type) return Boolean;

4/2

type Set is tagged private;
pragma Preelaborable_Initialization(Set);

5/2

type Cursor is private;
pragma Preelaborable_Initialization(Cursor);

6/2

Empty_Set : constant Set;

7/2

No_Element : constant Cursor;

8/2

function "=" (Left, Right : Set) return Boolean;

9/2

function Equivalent_Sets (Left, Right : Set) return Boolean;

10/2

function To_Set (New_Item : Element_Type) return Set;

11/2

function Length (Container : Set) return Count_Type;

12/2

function Is_Empty (Container : Set) return Boolean;

13/2

procedure Clear (Container : in out Set);

14/2

function Element (Position : Cursor) return Element_Type;

15/2

   procedure Replace_Element (Container : in out Set;
                              Position  : in     Cursor;
                              New_Item  : in     Element_Type);

16/2

   procedure Query_Element
     (Position : in Cursor;
      Process  : not null access procedure (Element : in Element_Type));

17/2

procedure Move (Target : in out Set;
Source : in out Set);

18/2

   procedure Insert (Container : in out Set;
                     New_Item  : in     Element_Type;
                     Position  :    out Cursor;
                     Inserted  :    out Boolean);

19/2

procedure Insert (Container : in out Set;
New_Item : in Element_Type);

20/2

procedure Include (Container : in out Set;
New_Item : in Element_Type);

21/2

procedure Replace (Container : in out Set;
New_Item : in Element_Type);

22/2

procedure Exclude (Container : in out Set;
Item : in Element_Type);

23/2

procedure Delete (Container : in out Set;
Item : in Element_Type);

24/2

procedure Delete (Container : in out Set;
Position : in out Cursor);

25/2

procedure Delete_First (Container : in out Set);

26/2

procedure Delete_Last (Container : in out Set);

27/2

procedure Union (Target : in out Set;
Source : in Set);

28/2

function Union (Left, Right : Set) return Set;

29/2

function "or" (Left, Right : Set) return Set renames Union;

30/2

procedure Intersection (Target : in out Set;
Source : in Set);

31/2

function Intersection (Left, Right : Set) return Set;

32/2

function "and" (Left, Right : Set) return Set renames Intersection;

33/2

procedure Difference (Target : in out Set;
Source : in Set);

34/2

function Difference (Left, Right : Set) return Set;

35/2

function "-" (Left, Right : Set) return Set renames Difference;

36/2

procedure Symmetric_Difference (Target : in out Set;
Source : in Set);

37/2

function Symmetric_Difference (Left, Right : Set) return Set;

38/2

function "xor" (Left, Right : Set) return Set renames
Symmetric_Difference;

39/2

function Overlap (Left, Right : Set) return Boolean;

40/2

function Is_Subset (Subset : Set;
Of_Set : Set) return Boolean;

41/2

function First (Container : Set) return Cursor;

42/2

function First_Element (Container : Set) return Element_Type;

43/2

function Last (Container : Set) return Cursor;

44/2

function Last_Element (Container : Set) return Element_Type;

45/2

function Next (Position : Cursor) return Cursor;

46/2

procedure Next (Position : in out Cursor);

47/2

function Previous (Position : Cursor) return Cursor;

48/2

procedure Previous (Position : in out Cursor);

49/2

   function Find (Container : Set;
                  Item      : Element_Type)
      return Cursor;

50/2

   function Floor (Container : Set;
                   Item      : Element_Type)
      return Cursor;

51/2

   function Ceiling (Container : Set;
                     Item      : Element_Type)
      return Cursor;

52/2

function Contains (Container : Set;
Item : Element_Type) return Boolean;

53/2

function Has_Element (Position : Cursor) return Boolean;

54/2

function "<" (Left, Right : Cursor) return Boolean;

55/2

function ">" (Left, Right : Cursor) return Boolean;

56/2

function "<" (Left : Cursor; Right : Element_Type)
return Boolean;

57/2

function ">" (Left : Cursor; Right : Element_Type)
return Boolean;

58/2

function "<" (Left : Element_Type; Right : Cursor)
return Boolean;

59/2

function ">" (Left : Element_Type; Right : Cursor)
return Boolean;

60/2

   procedure Iterate
     (Container : in Set;
      Process   : not null access procedure (Position : in Cursor));

61/2

   procedure Reverse_Iterate
     (Container : in Set;
      Process   : not null access procedure (Position : in Cursor));

62/2

   generic
      type Key_Type (<>) is private;
      with function Key (Element : Element_Type) return Key_Type;
      with function "<" (Left, Right : Key_Type)
         return Boolean is <>;
   package Generic_Keys is

63/2

function Equivalent_Keys (Left, Right : Key_Type)
return Boolean;

64/2

function Key (Position : Cursor) return Key_Type;

65/2

       function Element (Container : Set;
                         Key       : Key_Type)
          return Element_Type;

66/2

       procedure Replace (Container : in out Set;
                          Key       : in     Key_Type;
                          New_Item  : in     Element_Type);

67/2

procedure Exclude (Container : in out Set;
Key : in Key_Type);

68/2

procedure Delete (Container : in out Set;
Key : in Key_Type);

69/2

       function Find (Container : Set;
                      Key       : Key_Type)
          return Cursor;

70/2

       function Floor (Container : Set;
                       Key       : Key_Type)
          return Cursor;

71/2

       function Ceiling (Container : Set;
                         Key       : Key_Type)
          return Cursor;

72/2

function Contains (Container : Set;
Key : Key_Type) return Boolean;

73/2

       procedure Update_Element_Preserving_Key
         (Container : in out Set;
          Position  : in     Cursor;
          Process   : not null access procedure
                          (Element : in out Element_Type));

74/2

end Generic_Keys;

75/2

private

76/2

... -- not specified by the language

77/2

end Ada.Containers.Ordered_Sets;

78/2

{AI95-00302-03} Two elements E1 and E2 are equivalent if both E1 < E2 and E2 < E1 return False, using the generic formal "<" operator for elements.{equivalent element (of a ordered set)} Function Equivalent_Elements returns True if Left and Right are equivalent, and False otherwise.

79/2

{AI95-00302-03} The actual function for the generic formal function "<" on Element_Type values is expected to return the same value each time it is called with a particular pair of key values. It should define a strict ordering relationship, that is, be irreflexive, asymmetric, and transitive. If the actual for "<" behaves in some other manner, the behavior of this package is unspecified. Which subprograms of this package call "<" and how many times they call it, is unspecified.{unspecified [partial]}

80/2

{AI95-00302-03} If the value of an element stored in a set is changed other than by an operation in this package such that at least one of "<" or "=" give different results, the behavior of this package is unspecified.{unspecified [partial]}

80.a/2

Discussion: See A.18.6, “The Package Containers.Ordered_Maps” for a suggested implementation, and for justification of the restrictions regarding "<" and "=". Note that sets only need to store elements, not key/element pairs.

81/2

{AI95-00302-03} {first element (of a ordered set)} {last element (of a ordered set)} {successor element (of a ordered set)} The first element of a nonempty set is the one which is less than all the other elements in the set. The last element of a nonempty set is the one which is greater than all the other elements in the set. The successor of an element is the smallest element that is larger than the given element. The predecessor of an element is the largest element that is smaller than the given element. All comparisons are done using the generic formal "<" operator for elements.

82/2

procedure Delete_First (Container : in out Set);

83/2

{AI95-00302-03} If Container is empty, Delete_First has no effect. Otherwise the element designated by First (Container) is removed from Container. Delete_First tampers with the cursors of Container.

84/2

procedure Delete_Last (Container : in out Set);

85/2

{AI95-00302-03} If Container is empty, Delete_Last has no effect. Otherwise the element designated by Last (Container) is removed from Container. Delete_Last tampers with the cursors of Container.

86/2

function First_Element (Container : Set) return Element_Type;

87/2

{AI95-00302-03} Equivalent to Element (First (Container)).

88/2

function Last (Container : Set) return Cursor;

89/2

{AI95-00302-03} Returns a cursor that designates the last element in Container. If Container is empty, returns No_Element.

90/2

function Last_Element (Container : Set) return Element_Type;

91/2

{AI95-00302-03} Equivalent to Element (Last (Container)).

92/2

function Previous (Position : Cursor) return Cursor;

93/2

{AI95-00302-03} If Position equals No_Element, then Previous returns No_Element. Otherwise Previous returns a cursor designating the element that precedes the one designated by Position. If Position designates the first element, then Previous returns No_Element.

94/2

procedure Previous (Position : in out Cursor);

95/2

{AI95-00302-03} Equivalent to Position := Previous (Position).

96/2

function Floor (Container : Set;
Item : Element_Type) return Cursor;

97/2

{AI95-00302-03} Floor searches for the last element which is not greater than Item. If such an element is found, a cursor that designates it is returned. Otherwise No_Element is returned.

98/2

function Ceiling (Container : Set;
Item : Element_Type) return Cursor;

99/2

{AI95-00302-03} Ceiling searches for the first element which is not less than Item. If such an element is found, a cursor that designates it is returned. Otherwise No_Element is returned.

100/2

function "<" (Left, Right : Cursor) return Boolean;

101/2

{AI95-00302-03} Equivalent to Element (Left) < Element (Right).

102/2

function ">" (Left, Right : Cursor) return Boolean;

103/2

{AI95-00302-03} Equivalent to Element (Right) < Element (Left).

104/2

function "<" (Left : Cursor; Right : Element_Type) return Boolean;

105/2

{AI95-00302-03} Equivalent to Element (Left) < Right.

106/2

function ">" (Left : Cursor; Right : Element_Type) return Boolean;

107/2

{AI95-00302-03} Equivalent to Right < Element (Left).

108/2

function "<" (Left : Element_Type; Right : Cursor) return Boolean;

109/2

{AI95-00302-03} Equivalent to Left < Element (Right).

110/2

function ">" (Left : Element_Type; Right : Cursor) return Boolean;

111/2

{AI95-00302-03} Equivalent to Element (Right) < Left.

112/2

procedure Reverse_Iterate
(Container : in Set;
Process : not null access procedure (Position : in Cursor));

113/2

{AI95-00302-03} Iterates over the elements in Container as per Iterate, with the difference that the elements are traversed in predecessor order, starting with the last element.

114/2

{AI95-00302-03} For any two elements E1 and E2, the boolean values (E1 < E2) and (Key(E1) < Key(E2)) are expected to be equal. If the actuals for Key or Generic_Keys."<" behave in some other manner, the behavior of this package is unspecified. Which subprograms of this package call Key and Generic_Keys."<", and how many times the functions are called, is unspecified.{unspecified [partial]}

115/2

{AI95-00302-03} In addition to the semantics described in A.18.7, the subprograms in package Generic_Keys named Floor and Ceiling, are equivalent to the corresponding subprograms in the parent package, with the difference that the Key subprogram parameter is compared to elements in the container using the Key and "<" generic formal functions. The function named Equivalent_Keys in package Generic_Keys returns True if both Left < Right and Right < Left return False using the generic formal "<" operator, and returns True otherwise.

Implementation Advice

116/2

{AI95-00302-03} If N is the length of a set, then the worst-case time complexity of the Insert, Include, Replace, Delete, Exclude and Find operations that take an element parameter should be O((log N)**2) or better. The worst-case time complexity of the subprograms that take a cursor parameter should be O(1).

116.a/2

Implementation Advice: The worst-case time complexity of the Insert, Include, Replace, Delete, Exclude and Find operations of Containers.Ordered_Sets that take an element parameter should be O((log N)**2). The worst-case time complexity of the subprograms of Containers.Ordered_Sets that take a cursor parameter should be O(1).

116.b/2

Implementation Note: {AI95-00302-03} See A.18.6, “The Package Containers.Ordered_Maps” for implementation notes regarding some of the operations of this package.

Extensions to Ada 95

116.c/2

{AI95-00302-03} {extensions to Ada 95} The generic package Containers.Ordered_Sets is new.