@Part(precontainers-2, Root="ada.mss") @comment{ $Source: e:\\cvsroot/ARM/Source/pre_con2.mss,v $ } @comment{ $Revision: 1.11 $ $Date: 2011/08/17 00:29:40 $ $Author: randy $ } @LabeledAddedSubclause{Version=[3],Name=[The Generic Package Containers.Multiway_Trees]} @begin{Intro} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[The language-defined generic package Containers.Multiway_Trees provides private types Tree and Cursor, and a set of operations for each type. A multiway tree container is well-suited to represent nested structures.]} @begin{Discussion} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[This tree just provides a basic structure, and make no promises about balancing or other automatic organization. In this sense, it is different than the indexed (Map, Set) forms. Rather, it provides a building block on which to construct more complex and more specialized tree containers.]} @end{Discussion} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[A multiway tree container object manages a tree of internal @i, each of which contains an element and pointers to the parent, first child, last child, next (successor) sibling, and previous (predecessor) sibling internal nodes.@Defn2{Term=[node],Sec=[of a tree]} A cursor designates a particular node within a tree (and by extension the element contained in that node, if any). A cursor keeps designating the same node (and element) as long as the node is part of the container, even if the node is moved within the container.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[A @i is a particular node (which @i) and all of its child nodes (including all of the children of the child nodes, recursively). @Defn2{Term=[subtree],Sec=[of a tree]}@Defn{roots the subtree}@Defn2{Term=[subtree],Sec=[node which roots]} There is a special node, the @i, which is always present and has no associated element value. The root node provides a place to add nodes to an otherwise empty tree and represents the bottom of the tree.@Defn2{Term=[root],Sec=[of a tree]}@Defn2{Term=[root node],Sec=[of a tree]}]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[A node that has no children is called a @i.@Defn2{Term=[leaf node],Sec=[of a tree]} The @i of a node are the parent node, the parent of the parent node, and so on until a node with no parent is reached.@Defn2{Term=[ancestor],Sec=[of a tree node]} Similarly, the @i of a node are the child nodes, the children of each child node, and so on.@Defn2{Term=[descendant],Sec=[of a tree node]}]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The nodes of a subtree could be visited in several different orders. For a @i, the last step of visiting a node is to visit the nodes of its child list in order, recursively.@Defn{depth-first order}]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[For the depth-first order, when each child node is visited, the child list of the child node is visited before the next sibling of the child node is visited.]} @end{Ramification} @end{Intro} @begin{StaticSem} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],KeepNext=[T],Type=[Leading],Text=[The generic library package Containers.Multiway_Trees has the following declaration:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[@key{with} Ada.Iterator_Interfaces; @key{generic} @key{type} Element_Type @key{is private}; @key{with function} "=" (Left, Right : Element_Type) @key{return} Boolean @key{is} <>; @key{package} Ada.Containers.Multiway_Trees @key{is}@ChildUnit{Parent=[Ada.Containers],Child=[Multiway_Trees]} @key{pragma} Preelaborate(Multiway_Trees); @key{pragma} Remote_Types(Multiway_Trees);]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[ @key{type} @AdaTypeDefn{Tree} @key{is tagged private} @key{with} Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type; @key{pragma} Preelaborable_Initialization(Tree);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{type} @AdaTypeDefn{Cursor} @key{is private}; @key{pragma} Preelaborable_Initialization(Cursor);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @AdaObjDefn{Empty_Tree} : @key{constant} Tree;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @AdaObjDefn{No_Element} : @key{constant} Cursor;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Has_Element} (Position : Cursor) @key{return} Boolean;]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[ @key{package} @AdaPackDefn{Tree_Iterator_Interfaces} @key{is new} Ada.Iterator_Interfaces (Cursor, Has_Element);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Equal_Subtree} (Left_Position : Cursor; Right_Position: Cursor) @key{return} Boolean;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} "=" (Left, Right : Tree) @key{return} Boolean;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Is_Empty} (Container : Tree) @key{return} Boolean;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Node_Count} (Container : Tree) @key{return} Count_Type;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Subtree_Node_Count} (Position : Cursor) @key{return} Count_Type;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Depth} (Position : Cursor) @key{return} Count_Type;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Is_Root} (Position : Cursor) @key{return} Boolean;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Is_Leaf} (Position : Cursor) @key{return} Boolean;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Root} (Container : Tree) @key{return} Cursor;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Clear} (Container : @key{in out} Tree);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Element} (Position : Cursor) @key{return} Element_Type;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Replace_Element} (Container : @key{in out} Tree; Position : @key{in} Cursor; New_Item : @key{in} Element_Type);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Query_Element} (Position : @key{in} Cursor; Process : @key{not null access procedure} (Element : @key{in} Element_Type));]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Update_Element} (Container : @key{in out} Tree; Position : @key{in} Cursor; Process : @key{not null access procedure} (Element : @key{in out} Element_Type));]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[ @key[type] @AdaTypeDefn{Constant_Reference_Type} (Element : @key[not null access constant] Element_Type) @key[is private] @key[with] Implicit_Dereference => Element;]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[ @key[type] @AdaTypeDefn{Reference_Type} (Element : @key[not null access] Element_Type) @key[is private] @key[with] Implicit_Dereference => Element;]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[ @key[function] @AdaSubDefn{Constant_Reference} (Container : @key[aliased in] Tree; Position : @key[in] Cursor) @key[return] Constant_Reference_Type;]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[ @key[function] @AdaSubDefn{Reference} (Container : @key[aliased in out] Tree; Position : @key[in] Cursor) @key[return] Reference_Type;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Assign} (Target : @key{in out} Tree; Source : @key{in} Tree);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Copy} (Source : Tree) @key{return} Tree;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Move} (Target : @key{in out} Tree; Source : @key{in out} Tree);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Delete_Leaf} (Container : @key{in out} Tree; Position : @key{in out} Cursor);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Delete_Subtree} (Container : @key{in out} Tree; Position : @key{in out} Cursor);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Swap} (Container : @key{in out} Tree; I, J : @key{in} Cursor);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Find} (Container : Tree; Item : Element_Type) @key{return} Cursor;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Find_In_Subtree} (Position : Cursor; Item : Element_Type) @key{return} Cursor;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Ancestor_Find} (Position : Cursor; Item : Element_Type) @key{return} Cursor;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Contains} (Container : Tree; Item : Element_Type) @key{return} Boolean;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Iterate} (Container : @key{in} Tree; Process : @key{not null access procedure} (Position : @key{in} Cursor));]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Iterate_Subtree} (Position : @key{in} Cursor; Process : @key{not null access procedure} (Position : @key{in} Cursor));]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Iterate} (Container : @key{in} Tree) @key{return} Tree_Iterator_Interfaces.Forward_Iterator'Class;]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Iterate_Subtree} (Position : @key{in} Cursor) @key{return} Tree_Iterator_Interfaces.Forward_Iterator'Class;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Child_Count} (Parent : Cursor) @key{return} Count_Type;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Child_Depth} (Parent, Child : Cursor) @key{return} Count_Type;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Insert_Child} (Container : @key{in out} Tree; Parent : @key{in} Cursor; Before : @key{in} Cursor; New_Item : @key{in} Element_Type; Count : @key{in} Count_Type := 1);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Insert_Child} (Container : @key{in out} Tree; Parent : @key{in} Cursor; Before : @key{in} Cursor; New_Item : @key{in} Element_Type; Position : @key{out} Cursor; Count : @key{in} Count_Type := 1);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Insert_Child} (Container : @key{in out} Tree; Parent : @key{in} Cursor; Before : @key{in} Cursor; Position : @key{out} Cursor; Count : @key{in} Count_Type := 1);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Prepend_Child} (Container : @key{in out} Tree; Parent : @key{in} Cursor; New_Item : @key{in} Element_Type; Count : @key{in} Count_Type := 1);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Append_Child} (Container : @key{in out} Tree; Parent : @key{in} Cursor; New_Item : @key{in} Element_Type; Count : @key{in} Count_Type := 1);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Delete_Children} (Container : @key{in out} Tree; Parent : @key{in} Cursor);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Copy_Subtree} (Target : @key{in out} Tree; Parent : @key{in} Cursor; Before : @key{in} Cursor; Source : @key{in} Cursor);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Splice_Subtree} (Target : @key{in out} Tree; Parent : @key{in} Cursor; Before : @key{in} Cursor; Source : @key{in out} Tree; Position : @key{in out} Cursor);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Splice_Subtree} (Container: @key{in out} Tree; Parent : @key{in} Cursor; Before : @key{in} Cursor; Position : @key{in} Cursor);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Splice_Children} (Target : @key{in out} Tree; Target_Parent : @key{in} Cursor; Before : @key{in} Cursor; Source : @key{in out} Tree; Source_Parent : @key{in} Cursor);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Splice_Children} (Container : @key{in out} Tree; Target_Parent : @key{in} Cursor; Before : @key{in} Cursor; Source_Parent : @key{in} Cursor);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Parent} (Position : Cursor) @key{return} Cursor;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{First_Child} (Parent : Cursor) @key{return} Cursor;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{First_Child_Element} (Parent : Cursor) @key{return} Element_Type;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Last_Child} (Parent : Cursor) @key{return} Cursor;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Last_Child_Element} (Parent : Cursor) @key{return} Element_Type;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Next_Sibling} (Position : Cursor) @key{return} Cursor;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Previous_Sibling} (Position : Cursor) @key{return} Cursor;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Next_Sibling} (Position : @key{in out} Cursor);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Previous_Sibling} (Position : @key{in out} Cursor);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Iterate_Children} (Parent : @key{in} Cursor; Process : @key{not null access procedure} (Position : @key{in} Cursor));]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Reverse_Iterate_Children} (Parent : @key{in} Cursor; Process : @key{not null access procedure} (Position : @key{in} Cursor));]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Iterate_Children} (Container : @key[in] Tree; Parent : @key[in] Cursor) @key[return] Tree_Iterator_Interfaces.Reversible_Iterator'Class;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key{private} ... -- @RI[not specified by the language] @key[end] Ada.Containers.Multiway_Trees;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[The actual function for the generic formal function "=" on Element_Type values is expected to define a reflexive and symmetric relationship and return the same result value each time it is called with a particular pair of values. If it behaves in some other manner, the functions Find, Reverse_Find, Equal_Subtree, and "=" on tree values return an unspecified value. The exact arguments and number of calls of this generic formal function by the functions Find, Reverse_Find, Equal_Subtree, and "=" on tree values are unspecified.@PDefn{unspecified}]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[The type Tree is used to represent trees. The type Tree needs finalization@PDefn2{Term=,Sec=} (see @RefSecNum{Assignment and Finalization}).]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[Empty_Tree represents the empty Tree object. It contains only the root node (Node_Count (Empty_Tree) returns 1). If an object of type Tree is not otherwise initialized, it is initialized to the same value as Empty_Tree.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[No_Element represents a cursor that designates no element. If an object of type Cursor is not otherwise initialized, it is initialized to the same value as No_Element.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[The predefined "=" operator for type Cursor returns True if both cursors are No_Element, or designate the same element in the same container.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[Execution of the default implementation of the Input, Output, Read, or Write attribute of type Cursor raises Program_Error.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[Tree'Write writes Node_Count (Tree) - 1 elements to the stream. Tree'Read reads Node_Count (Tree) - 1 elements from the stream.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[@Redundant[Some operations of this generic package have access-to-subprogram parameters. To ensure such operations are well-defined, they guard against certain actions by the designated subprogram. In particular, some operations check for "tampering with cursors" of a container because they depend on the set of elements of the container remaining constant, and others check for "tampering with elements" of a container because they depend on elements of the container not being replaced.]]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[@Defn2{Term=[tamper with cursors],Sec=[of a tree]} A subprogram is said to @i{tamper with cursors} of a tree object @i if:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[it inserts or deletes elements of @i, that is, it calls the Clear, Delete_Leaf, Insert_Child, or Delete_Children procedures with @i as a parameter; or]} @begin{Honest} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Operations which are defined to be equivalent to a call on one of these operations also are included. Similarly, operations which call one of these as part of their definition are included.]} @end{Honest} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[it reorders the elements of @i, that is, it calls the Splice_Subtree or Splice_Children procedures with @i as a parameter; or]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[it finalizes @i; or]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[it calls Assign with @i as the Target parameter; or]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[it calls the Move procedure with @i as a parameter.]} @begin{Reason} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Swap copies elements rather than reordering them, so it doesn't tamper with cursors.]} @end{Reason} @end{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[@Defn2{Term=[tamper with elements],Sec=[of a tree]} A subprogram is said to @i{tamper with elements} of a tree object @i if:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[it tampers with cursors of @i; or]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[it replaces one or more elements of @i, that is, it calls the Replace_Element or Swap procedures with @i as a parameter.]} @begin{Reason} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Complete replacement of an element can cause its memory to be deallocated while another operation is holding onto a reference to it. That can't be allowed. However, a simple modification of (part of) an element is not a problem, so Update_Element does not cause a problem.]} @end{Reason} @end{Itemize} @begin{DescribeCode} @begin{Example} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgRef{Version=[3],Kind=[Deleted]} @ChgAdded{Version=[2],KeepNext=[T],Text=[@Chg{Version=[3],New=[],Old=[@key{function} Has_Element (Position : Cursor) @key{return} Boolean;]}]} @end{Example} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgRef{Version=[3],Kind=[Deleted],ARef=[AI05-0212-1]} @ChgAdded{Version=[2],Type=[Trailing],Text=[@Chg{Version=[3],New=[],Old=[Returns True if Position designates an element, and returns False otherwise.]}]} @begin{Honest} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgRef{Version=[3],Kind=[Deleted],ARef=[AI05-0212-1]} @ChgAdded{Version=[2],Text=[@Chg{Version=[3],New=[],Old=[This function may not detect cursors that designate deleted elements; such cursors are invalid (see below) and the result of calling Has_Element with an invalid cursor is unspecified (but not erroneous).]}]} @end{Honest} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Equal_Subtree (Left_Position : Cursor; Right_Position: Cursor) @key{return} Boolean;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1],ARef=[AI05-0264-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Left_Position or Right_Position equals No_Element, propagates Constraint_Error. If the number of child nodes of the element designated by Left_Position is different from the number of child nodes of the element designated by Right_Position, the function returns False. If Left_Position designates a root node and Right_Position does not, the function returns False. If Right_Position designates a root node and Left_Position does not, the function returns False. Unless both cursors designate a root node, the elements are compared using the generic formal equality operator. If the result of the element comparison is False, the function returns False. Otherwise, it calls Equal_Subtree on a cursor designating each child element of the element designated by Left_Position and a cursor designated the corresponding child element of the element designated by Right_Position. If any such call returns False, the function returns False; otherwise, it returns True. Any exception raised during the evaluation of element equality is propagated.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Left_Position and Right_Position do not need to be from the same tree.]} @end{Ramification} @begin{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[This wording describes the canonical semantics. However, the order and number of calls on the formal equality function is unspecified for all of the operations that use it in this package, so an implementation can call it as many or as few times as it needs to get the correct answer. Similarly, a global rule (see the introduction of @RefSecNum{Predefined Language Environment}) says that language-defined routines are not affected by overriding of other language-defined routines. This means that no reasonable program can tell how many times Equal_Subtree is called, and thus an implementation can call it as many or as few times as it needs to get the correct answer. Specifically, there is no requirement to call the formal equality or Equal_Subtree additional times once the answer has been determined.]} @end{ImplNote} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} "=" (Left, Right : Tree) @key{return} Boolean;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Left and Right denote the same tree object, then the function returns True. Otherwise, it calls Equal_Subtree with a cursor designating the root node of Left and Right; the result is returned. Any exception raised during the evaluation of Equal_Subtree is propagated.]} @begin{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Similar considerations apply here as apply to Equal_Subtree. The actual number of calls performed is unspecified.]} @end{ImplNote} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Node_Count (Container : Tree) @key{return} Count_Type;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Node_Count returns the number of nodes in Container.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Since all tree objects have a root node, this can never return a value of 0. Node_Count (Some_Tree) should always equal Subtree_Node_Count (Root (Some_Tree)).]} @end{Ramification} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Subtree_Node_Count (Position : Cursor) @key{return} Count_Type;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position is No_Element, Subtree_Node_Count returns 0; otherwise, Subtree_Node_Count returns the number of nodes in the subtree that is rooted by Position.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Is_Empty (Container : Tree) @key{return} Boolean;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Equivalent to Node_Count (Container) = 1.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[An empty tree contains just the root node.]} @end{Ramification} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Depth (Position : Cursor) @key{return} Count_Type;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position equals No_Element, Depth returns 0; otherwise, Depth returns the number of ancestor nodes of the node designated by Position (including the node itself).]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Depth (Root (Some_Tree)) = 1.]} @end{Ramification} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Is_Root (Position : Cursor) @key{return} Boolean;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Is_Root returns True if the Position designates the root node of some tree; and returns False otherwise.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Is_Leaf (Position : Cursor) @key{return} Boolean;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Is_Leaf returns True if Position designates a node that does not have any child nodes; and returns False otherwise.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Is_Leaf returns False if passed No_Element, since No_Element does not designate a node. Is_Leaf can be passed a cursor that designates the root node; Is_Leaf will return True if passed the root node of an empty tree.]} @end{Ramification} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Root (Container : Tree) @key{return} Cursor;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Root returns a cursor that designates the root node of Container.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[There is always a root node, even in an empty container, so this function never returns No_Element.]} @end{Ramification} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Clear (Container : @key{in out} Tree);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Removes all the elements from Container.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The root node is not removed; all trees have a root node.]} @end{Ramification} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Element (Position : Cursor) @key{return} Element_Type;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position equals No_Element, then Constraint_Error is propagated; if Position designates the root node of a tree, then Program_Error is propagated. Otherwise, Element returns the element designated by Position.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The root node does not contain an element, so that value cannot be read or written.]} @end{Ramification} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Replace_Element (Container : @key{in out} Tree; Position : @key{in} Cursor; New_Item : @key{in} Element_Type);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0264-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container (including if it designates the root node), then Program_Error is propagated. Otherwise, Replace_Element assigns the value New_Item to the element designated by Position.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Query_Element (Position : @key{in} Cursor; Process : @key{not null access procedure} (Element : @key{in} Element_Type));]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position equals No_Element, then Constraint_Error is propagated; if Position designates the root node of a tree, then Program_Error is propagated. Otherwise, Query_Element calls Process.@key{all} with the element designated by Position as the argument. Program_Error is propagated if Process.@key{all} tampers with the elements of Container. Any exception raised by Process.@key{all} is propagated.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Update_Element (Container : @key{in out} Tree; Position : @key{in} Cursor; Process : @key{not null access procedure} (Element : @key{in out} Element_Type));]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0264-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container (including if it designates the root node), then Program_Error is propagated. Otherwise, Update_Element calls Process.@key{all} with the element designated by Position as the argument. Program_Error is propagated if Process.@key{all} tampers with the elements of Container. Any exception raised by Process.@key{all} is propagated.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[If Element_Type is unconstrained and definite, then the actual Element parameter of Process.@key{all} shall be unconstrained.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[This means that the elements cannot be directly allocated from the heap; it must be possible to change the discriminants of the element in place.]} @end{Ramification} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key{type} Constant_Reference_Type (Element : @key[not null access constant] Element_Type) @key[is private] @key[with] Implicit_Dereference => Element;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key[type] Reference_Type (Element : @key[not null access] Element_Type) @key[is private] @key[with] Implicit_Dereference => Element;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Constant_Reference_Type and Reference_Type need finalization.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The default initialization of an object of type Constant_Reference_Type or Reference_Type propagates Program_Error.]} @begin{Reason} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[It is expected that Reference_Type (and Constant_Reference_Type) will be a controlled type, for which finalization will have some action to terminate the tampering check for the associated container. If the object is created by default, however, there is no associated container. Since this is useless, and supporting this case would take extra work, we define it to raise an exception.]} @end{Reason} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[function] Constant_Reference (Container : @key[aliased in] Tree; Position : @key[in] Cursor) @key[return] Constant_Reference_Type;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[This function (combined with the Constant_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read access to the individual elements of a container starting with a cursor.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Constant_Reference returns an object whose discriminant is an access value that designates the element designated by Position. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Constant_Reference exists and has not been finalized.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[function] Reference (Container : @key[aliased in out] Tree; Position : @key[in] Cursor) @key[return] Reference_Type;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[This function (combined with the Variable_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read and write access to the individual elements of a container starting with a cursor.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Reference returns an object whose discriminant is an access value that designates the element designated by Position. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Reference exists and has not been finalized.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Assign (Target : @key{in out} Tree; Source : @key{in} Tree);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Target denotes the same object as Source, the operation has no effect. Otherwise, the elements of Source are copied to Target as for an @nt{assignment_statement} assigning Source to Target.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Each element in Target has a parent element that corresponds to the parent element of the Source element, and has child elements that correspond to the child elements of the Source element.]} @end{Ramification} @begin{Discussion} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0005-1]} @ChgAdded{Version=[3],Text=[This routine exists for compatibility with the bounded tree container. For an unbounded tree, @exam{Assign(A, B)} and @exam{A := B} behave identically. For a bounded tree, := will raise an exception if the container capacities are different, while Assign will not raise an exception if there is enough room in the target.]} @end{Discussion} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Copy (Source : Tree) @key{return} Tree;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Returns a tree with the same structure as Source and whose elements are initialized from the corresponding elements of Source.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Move (Target : @key{in out} Tree; Source : @key{in out} Tree);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Target denotes the same object as Source, then the operation has no effect. Otherwise, Move first calls Clear (Target). Then, the nodes other than the root node in Source are moved to Target (in the same positions). After Move completes, Node_Count (Target) is the number of nodes originally in Source, and Node_Count (Source) is 1.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Delete_Leaf (Container : @key{in out} Tree; Position : @key{in out} Cursor);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container (including if it designates the root node), then Program_Error is propagated. If the element designated by position has any child elements, then Constraint_Error is propagated. Otherwise, Delete_Leaf removes (from Container) the element designated by Position. Finally, Position is set to No_Element.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The check on Position checks that the cursor does not belong to some other Container. This check implies that a reference to the container is included in the cursor value. This wording is not meant to require detection of dangling cursors; such cursors are defined to be invalid, which means that execution is erroneous, and any result is allowed (including not raising an exception).]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The root node cannot be deleted.]} @end{Ramification} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Delete_Subtree (Container : @key{in out} Tree; Position : @key{in out} Cursor);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0264-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position equals No_Element, then Constraint_Error is propagated. If Position does not designate an element in Container (including if it designates the root node), then Program_Error is propagated. Otherwise, Delete_Subtree removes (from Container) the subtree designated by Position (that is, the node designated by Position and all of the descendant nodes of that node), and Position is set to No_Element.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The root node cannot be deleted. To delete the entire contents of the tree, call Clear(Container).]} @end{Ramification} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Swap (Container : @key{in out} Tree; I, J : @key{in} Cursor);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If either I or J equals No_Element, then Constraint_Error is propagated. If either I or J do not designate an element in Container (including if either designates the root node), then Program_Error is propagated. Otherwise, Swap exchanges the values of the elements designated by I and J.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[After a call to Swap, I designates the element value previously designated by J, and J designates the element value previously designated by I. The position of the elements do not change; for instance, the parent node and the first child node of I are unchanged by the operation.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The root nodes do not contain element values, so they cannot be swapped.]} @end{Ramification} @begin{Honest} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The implementation is not required to actually copy the elements if it can do the swap some other way. But it is allowed to copy the elements if needed.]} @end{Honest} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Find (Container : Tree; Item : Element_Type) @key{return} Cursor;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Find searches the elements of Container for an element equal to Item (using the generic formal equality operator). The search starts at the root node. The search checks the tree in a depth-first order. If no equal element is found, then Find returns No_Element. Otherwise, it returns a cursor designating the first equal element encountered.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Find_In_Subtree (Position : Cursor; Item : Element_Type) @key{return} Cursor;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position equals No_Element, then Constraint_Error is propagated. Find_In_Subtree searches a subtree of the elements of Container for an element equal to Item (using the generic formal equality operator). The search starts at the element designated by Position. The search checks the subtree rooted by Position in a depth-first order. If no equal element is found, then Find returns No_Element. Otherwise, it returns a cursor designating the first equal element encountered.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Find_In_Subtree does not check any siblings of the element designated by Position. The root node does not contain an element, and therefore it can never be returned, but it can be explicitly passed to Position.]} @end{Ramification} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Ancestor_Find (Position : Cursor; Item : Element_Type; @key{return} Cursor;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position equals No_Element, then Constraint_Error is propagated. Otherwise, Ancestor_Find searches for an element equal to Item (using the generic formal equality operator). The search starts at the node designated by Position, and checks each ancestor proceeding toward the root of the subtree. If no equal element is found, then Ancestor_Find returns No_Element. Otherwise, it returns a cursor designating the first equal element encountered.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[No_Element is returned if Position is the root node.]} @end{Ramification} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Contains (Container : Tree; Item : Element_Type) @key{return} Boolean;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Equivalent to Find (Container, Item) /= No_Element.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Iterate (Container : @key{in} Tree; Process : @key{not null access procedure} (Position : @key{in} Cursor));]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Iterate calls Process.@key{all} with a cursor that designates each element in Container, starting with the root node and proceeding in a depth-first order. Program_Error is propagated if Process.@key{all} tampers with the cursors of Container. Any exception raised by Process.@key{all} is propagated.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Process is not called with the root node, which does not have an associated element.]} @end{Ramification} @begin{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The purpose of the tamper with cursors check is to prevent erroneous execution from the Position parameter of Process.@key{all} becoming invalid. This check takes place when the operations that tamper with the cursors of the container are called. The check cannot be made later (say in the body of Iterate), because that could cause the Position cursor to be invalid and potentially cause execution to become erroneous @em defeating the purpose of the check.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[See Iterate for vectors (@RefSecNum{The Generic Package Containers.Vectors}) for a suggested implementation of the check.]} @end{ImplNote} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Iterate_Subtree (Position : @key{in} Cursor; Process : @key{not null access procedure} (Position : @key{in} Cursor));]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position equals No_Element, then Constraint_Error is propagated. Iterate calls Process.@key{all} with a cursor that designates each element in the subtree rooted by the node designated by Position, starting with the node designated by Position and proceeding in a depth-first order. Program_Error is propagated if Process.@key{all} tampers with the cursors of the tree containing Position. Any exception raised by Process.@key{all} is propagated.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Position can be passed a cursor designating the root node; in that case, Process is not called with the root node, which does not have an associated element.]} @end{Ramification} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Iterate (Container : @key{in} Tree) @key{return} Tree_Iterator_Interfaces.Forward_Iterator'Class;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Iterate returns an iterator object that will generate a loop parameter designating each node in Container, starting with the root node and proceeding in a depth-first order. Program_Error is propagated if any operation (in particular, the @nt{sequence_of_statements} of the @nt{loop_statement} whose @nt{iterator_specification} denotes this object) tampers with the cursors of Container while the returned object exists. The returned object from Iterate needs finalization.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Iterate_Subtree (Position : @key{in} Cursor) @key{return} Tree_Iterator_Interfaces.Forward_Iterator'Class;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Iterate_Subtree returns an iterator object that will generate a loop parameter designating each element in the subtree rooted by the node designated by Position, starting with the node designated by Position and proceeding in a depth-first order. If Position equals No_Element, then Constraint_Error is propagated. Program_Error is propagated if any operation (in particular, the @nt{sequence_of_statements} of the @nt{loop_statement} whose @nt{iterator_specification} denotes this object) tampers with the cursors of the container in which the node designated by Position exists while the returned object exists. The returned object from Iterate_Subtree needs finalization.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Child_Count (Parent : Cursor) @key{return} Count_Type;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Child_Count returns the number of child nodes of the node designated by Parent.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Child_Depth (Parent, Child : Cursor) @key{return} Count_Type;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Child or Parent is equal to No_Element, then Constraint_Error is propagated. Otherwise, Child_Depth returns the number of ancestor nodes of Child (including Child itself), up to but not including Parent; in this case Program_Error is propagated if Parent is not an ancestor of Child.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Program_Error is propagated if Parent and Child are nodes in different containers.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Child_Depth (Root (Some_Tree), Child) + 1 = Depth (Child) as the root is not counted.]} @end{Ramification} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Insert_Child (Container : @key{in out} Tree; Parent : @key{in} Cursor; Before : @key{in} Cursor; New_Item : @key{in} Element_Type; Count : @key{in} Count_Type := 1);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then Constraint_Error is propagated. If Parent does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and Container.Parent (Before) is not equal to Parent, then Constraint_Error is propagated. Otherwise, Insert_Child allocates Count nodes containing copies of New_Item and inserts them as children of Parent. If Parent already has child nodes, then the new nodes are inserted prior to the node designated by Before, or, if Before equals No_Element, the new nodes are inserted after the last existing child node of Parent. Any exception raised during allocation of internal storage is propagated, and Container is not modified.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Insert_Child (Container : @key{in out} Tree; Parent : @key{in} Cursor; Before : @key{in} Cursor; New_Item : @key{in} Element_Type; Position : @key{out} Cursor; Count : @key{in} Count_Type := 1);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1],ARef=[AI05-0257-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then Constraint_Error is propagated. If Parent does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and Container.Parent (Before) is not equal to Parent, then Constraint_Error is propagated. Otherwise, Insert_Child allocates Count nodes containing copies of New_Item and inserts them as children of Parent. If Parent already has child nodes, then the new nodes are inserted prior to the node designated by Before, or, if Before equals No_Element, the new nodes are inserted after the last existing child node of Parent. Position designates the first newly-inserted node, or if Count equals 0, then Position is assigned the value of Before. Any exception raised during allocation of internal storage is propagated, and Container is not modified.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Insert_Child (Container : @key{in out} Tree; Parent : @key{in} Cursor; Before : @key{in} Cursor; Position : @key{out} Cursor; Count : @key{in} Count_Type := 1);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0257-1],ARef=[AI05-0264-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then Constraint_Error is propagated. If Parent does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and Container.Parent (Before) is not equal to Parent, then Constraint_Error is propagated. Otherwise, Insert_Child allocates Count nodes, the elements contained in the new nodes are initialized by default (see @RefSecNum{Object Declarations}), and the new nodes are inserted as children of Parent. If Parent already has child nodes, then the new nodes are inserted prior to the node designated by Before, or, if Before equals No_Element, the new nodes are inserted after the last existing child node of Parent. Position designates the first newly-inserted node, or if Count equals 0, then Position is assigned the value of Before. Any exception raised during allocation of internal storage is propagated, and Container is not modified.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Prepend_Child (Container : @key{in out} Tree; Parent : @key{in} Cursor; New_Item : @key{in} Element_Type; Count : @key{in} Count_Type := 1);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Equivalent to Insert_Child (Container, Parent, First_Child (Container, Parent), New_Item, Count).]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Append_Child (Container : @key{in out} Tree; Parent : @key{in} Cursor; New_Item : @key{in} Element_Type; Count : @key{in} Count_Type := 1);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Equivalent to Insert_Child (Container, Parent, Last_Child (Container, Parent), New_Item, Count).]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Delete_Children (Container : @key{in out} Tree; Parent : @key{in} Cursor);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then Constraint_Error is propagated. If Parent does not designate a node in Container, Program_Error is propagated. Otherwise, Delete_Children removes (from Container) all of the child elements of Parent along with their dependent elements.]} @begin{Discussion} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[This routine deletes all of the child subtrees of Parent at once. Use Delete_Subtree to delete an individual subtree.]} @end{Discussion} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Copy_Subtree (Target : @key{in out} Tree; Parent : @key{in} Cursor; Before : @key{in} Cursor; Source : @key{in} Cursor);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then Constraint_Error is propagated. If Parent does not designate a node in Target, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate a node in Target, then Program_Error is propagated. If Before is not equal to No_Element, and Target.Parent (Before) is not equal to Parent, then Constraint_Error is propagated. If Source designates a root node, then Constraint_Error is propagated. If Source is equal to No_Element, then the operation has no effect. Otherwise, the subtree rooted by Source (which can be from any tree; it does not have to be a subtree of Target) is copied (new nodes are allocated to create a new subtree with the same structure as the Source subtree, with each element initialized from the corresponding element of the Source subtree) and inserted into Target as a child of Parent. If Parent already has child nodes, then the new nodes are inserted prior to the node designated by Before, or, if Before equals No_Element, the new nodes are inserted after the last existing child node of Parent. The parent of the newly created subtree is set to Parent, and the overall count of Target is incremented by Subtree_Node_Count (Source). Any exception raised during allocation of internal storage is propagated, and Container is not modified.]} @begin{Discussion} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[We only need one routine here, as the source object is not modified, so we can use the same routine for both copying within and between containers.]} @end{Discussion} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[We do not allow copying a subtree that includes a root node, as that would require inserting a node with no value in the middle of the target tree. To copy an entire tree to another tree object, use Copy.]} @end{Ramification} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Splice_Subtree (Target : @key{in out} Tree; Parent : @key{in} Cursor; Before : @key{in} Cursor; Source : @key{in out} Tree; Position : @key{in out} Cursor);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then Constraint_Error is propagated. If Parent does not designate a node in Target, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate a node in Target, then Program_Error is propagated. If Before is not equal to No_Element, and Target.Parent (Before) is not equal to Parent, then Constraint_Error is propagated. If Position equals No_Element, Constraint_Error is propagated. If Position does not designate a node in Source or designates a root node, then Program_Error is propagated. If Source denotes the same object as Target, then: if Position equals Before there is no effect; if Position designates an ancestor of Parent or is equal to Parent, Constraint_Error is propagated; otherwise, the subtree rooted by the element designated by Position is moved to be a child of Parent. If Parent already has child nodes, then the moved nodes are inserted prior to the node designated by Before, or, if Before equals No_Element, the moved nodes are inserted after the last existing child node of Parent. In each of these cases, Position and the count of Target are unchanged, and the parent of the element designated by Position is set to Parent.]} @begin{Reason} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[We can't allow moving the subtree of Position to a descendant node of the subtree, as the descendant node will be part of the subtree being moved. The result would be a circularly linked tree, or one with inaccessible nodes. Thus we have to check Position against Parent, even though such a check is @i(Depth(Source)).]} @end{Reason} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[Otherwise (if Source does not denote the same object as Target), the subtree designated by Position is removed from Source and moved to Target. The subtree is inserted as a child of Parent. If Parent already has child nodes, then the moved nodes are inserted prior to the node designated by Before, or, if Before equals No_Element, the moved nodes are inserted after the last existing child node of Parent. In each of these cases, the count of Target is incremented by Subtree_Node_Count (Position), and the count of Source is decremented by Subtree_Node_Count (Position), Position is updated to represent an element in Target.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[If Source is the same as Target, and Position = Before, or Next_Sibling(Position) = Before, Splice_Subtree has no effect, as the subtree does not have to move to meet the postcondition.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[We do not allow splicing a subtree that includes a root node, as that would require inserting a node with no value in the middle of the target tree. Splice the children of the root node instead.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[For this reason there is no operation to splice an entire tree, as that would necessarily involve splicing a root node.]} @end{Ramification} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Splice_Subtree (Container: @key{in out} Tree; Parent : @key{in} Cursor; Before : @key{in} Cursor; Position : @key{in} Cursor);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then Constraint_Error is propagated. If Parent does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and Target.Parent (Before) is not equal to Parent, then Constraint_Error is propagated. If Position equals No_Element, Constraint_Error is propagated. If Position does not designate a node in Container or designates a root node, then Program_Error is propagated. If Position equals Before, there is no effect. If Position designates an ancestor of Parent or is equal to Parent, Constraint_Error is propagated. Otherwise, the subtree rooted by the element designated by Position is moved to be a child of Parent. If Parent already has child nodes, then the moved nodes are inserted prior to the node designated by Before, or, if Before equals No_Element, the moved nodes are inserted after the last existing child node of Parent. The parent of the element designated by Position is set to Parent.]} @begin{Reason} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[We can't allow moving the subtree of Position to a descendant node of the subtree, as the descendant node will be part of the subtree being moved.]} @end{Reason} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Splice_Children (Target : @key{in out} Tree; Target_Parent : @key{in} Cursor; Before : @key{in} Cursor; Source : @key{in out} Tree; Source_Parent : @key{in} Cursor);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Target_Parent equals No_Element, then Constraint_Error is propagated. If Target_Parent does not designate a node in Target, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate an element in Target, then Program_Error is propagated. If Source_Parent equals No_Element, then Constraint_Error is propagated. If Source_Parent does not designate a node in Source, then Program_Error is propagated. If Before is not equal to No_Element, and Target.Parent (Before) is not equal to Target_Parent, then Constraint_Error is propagated.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[If Source denotes the same object as Target, then:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[if Target_Parent equals Source_Parent there is no effect; else]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[if Source_Parent is an ancestor of Target_Parent, then Constraint_Error is propagated; else]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[the child elements (and their descendants) of Source_Parent are moved to be child elements of Target_Parent. If Target_Parent already has child elements, then the moved elements are inserted prior to the node designated by Before, or, if Before equals No_Element, the moved elements are inserted after the last existing child node of Target_Parent. The parent of each moved child element is set to Target_Parent.]} @end{Itemize} @begin{Reason} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[We can't allow moving the children of Source_Parent to a descendant node, as the descendant node will be part of one of the subtrees being moved.]} @end{Reason} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[Otherwise (if Source does not denote the same object as Target), the child elements (and their descendants) of Source_Parent are removed from Source and moved to Target. The child elements are inserted as children of Target_Parent. If Target_Parent already has child elements, then the moved elements are inserted prior to the node designated by Before, or, if Before equals No_Element, the moved elements are inserted after the last existing child node of Target_Parent. In each of these cases, the overall count of Target is incremented by Subtree_Count (Source_Node_Parent)-1, and the overall count of Source is decremented by Subtree_Count (Source_Node_Parent)-1.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The node designated by Source_Parent is not moved, thus we never need to update Source_Parent.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Move (Target, Source) could be written Splice_Children (Target, Target.Root, No_Element, Source, Source.Root);]} @end{Ramification} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Splice_Children (Container : @key{in out} Tree; Target_Parent : @key{in} Cursor; Before : @key{in} Cursor; Source_Parent : @key{in} Cursor);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1],ARef=[AI05-0264-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Target_Parent equals No_Element, then Constraint_Error is propagated. If Target_Parent does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate an element in Container, then Program_Error is propagated. If Source_Parent equals No_Element, then Constraint_Error is propagated. If Source_Parent does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and Container.Parent (Before) is not equal to Target_Parent, then Constraint_Error is propagated. If Target_Parent equals Source_Parent there is no effect. If Source_Parent is an ancestor of Target_Parent, then Constraint_Error is propagated. Otherwise, the child elements (and their descendants) of Source_Parent are moved to be child elements of Target_Parent. If Target_Parent already has child elements, then the moved elements are inserted prior to the node designated by Before, or, if Before equals No_Element, the moved elements are inserted after the last existing child node of Target_Parent. The parent of each moved child element is set to Target_Parent.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Parent (Position : Cursor) @key{return} Cursor;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position is equal to No_Element or designates a root node, No_Element is returned. Otherwise, a cursor designating the parent node of the node designated by Position is returned.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} First_Child (Parent : Cursor) @key{return} Cursor;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent is equal to No_Element, then Constraint_Error is propagated. Otherwise, First_Child returns a cursor designating the first child node of the node designated by Parent; if there is no such node, No_Element is returned.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} First_Child_Element (Parent : Cursor) @key{return} Element_Type;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Equivalent to Element (First_Child (Parent)).]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Last_Child (Parent : Cursor) @key{return} Cursor;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent is equal to No_Element, then Constraint_Error is propagated. Otherwise, Last_Child returns a cursor designating the last child node of the node designated by Parent; if there is no such node, No_Element is returned.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Last_Child_Element (Parent : Cursor) @key{return} Element_Type;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Equivalent to Element (Last_Child (Parent)).]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Next_Sibling (Position : Cursor) @key{return} Cursor;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position equals No_Element or designates the last child node of its parent, then Next_Sibling returns the value No_Element. Otherwise, it returns a cursor that designates the successor (with the same parent) of the node designated by Position.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Previous_Sibling (Position : Cursor) @key{return} Cursor;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position equals No_Element or designates the first child node of its parent, then Previous_Sibling returns the value No_Element. Otherwise, it returns a cursor that designates the predecessor (with the same parent) of the node designated by Position.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Next_Sibling (Position : @key{in out} Cursor);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Equivalent to Position := Next_Sibling (Position);]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Previous_Sibling (Position : @key{in out} Cursor);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Equivalent to Position := Previous_Sibling (Position);]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Iterate_Children (Parent : @key{in} Cursor; Process : @key{not null access procedure} (Position : @key{in} Cursor));]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then Constraint_Error is propagated.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Iterate_Children calls Process.@key{all} with a cursor that designates each child node of Parent, starting with the first child node and moving the cursor as per the function Next_Sibling.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Program_Error is propagated if Process.@key{all} tampers with the cursors of the tree containing Parent. Any exception raised by Process.@key{all} is propagated.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Reverse_Iterate_Children (Parent : @key{in} Cursor; Process : @key{not null access procedure} (Position : @key{in} Cursor));]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then Constraint_Error is propagated.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Reverse_Iterate_Children calls Process.@key{all} with a cursor that designates each child node of Parent, starting with the last child node and moving the cursor as per the function Previous_Sibling.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Program_Error is propagated if Process.@key{all} tampers with the cursors of the tree containing Parent. Any exception raised by Process.@key{all} is propagated.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Iterate_Children (Container : @key[in] Tree; Parent : @key[in] Cursor) @key[return] Tree_Iterator_Interfaces.Reversible_Iterator'Class;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Iterate_Children returns a reversible iterator object that will generate a loop parameter designating each child node of Parent. If Parent equals No_Element, then Constraint_Error is propagated. If Parent does not designate a node in Container, then Program_Error is propagated. Otherwise, when used as a forward iterator, the nodes are designated starting with the first child node and moving the cursor as per the function Next_Sibling; when used as a reverse iterator, the nodes are designated starting with the last child node and moving the cursor as per the function Previous_Sibling. Program_Error is propagated if any operation (in particular, the @nt{sequence_of_statements} of the @nt{loop_statement} whose @nt{iterator_specification} denotes this object) tampers with the cursors of Container while the returned object exists. The returned object from Iterate_Children needs finalization.]} @end{DescribeCode} @end{StaticSem} @begin{Bounded} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[@PDefn2{Term=(bounded error),Sec=(cause)} It is a bounded error for the actual function associated with a generic formal subprogram, when called as part of an operation of this package, to tamper with elements of any Tree parameter of the operation. Either Program_Error is raised, or the operation works as defined on the value of the Tree either prior to, or subsequent to, some or all of the modifications to the Tree.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[@PDefn2{Term=(bounded error),Sec=(cause)} It is a bounded error to call any subprogram declared in the visible part of Containers.Multiway_Trees when the associated container has been finalized. If the operation takes Container as an @key[in out] parameter, then it raises Constraint_Error or Program_Error. Otherwise, the operation either proceeds as it would for an empty container, or it raises Constraint_Error or Program_Error.]} @end{Bounded} @begin{Erron} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[A Cursor value is @i if any of the following have occurred since it was created:@Defn2{Term=[invalid cursor],Sec=[of a tree]} @PDefn2{Term=[cursor],Sec=[invalid]}]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The tree that contains the element it designates has been finalized;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The tree that contains the element it designates has been used as the Source or Target of a call to Move;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The tree that contains the element it designates has been used as the Target of a call to Assign or the target of an @nt{assignment_statement};]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The element it designates has been removed from the tree that previously contained the element.]} @begin{Reason} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[We talk about which tree the element was removed from in order to handle splicing nodes from one tree to another. The node still exists, but any cursors that designate it in the original tree are now invalid. This bullet covers removals caused by calls to Clear, Delete_Leaf, Delete_Subtree, Delete_Children, Splice_Children, and Splice_Subtree.]} @end{Reason} @end{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The result of "=" or Has_Element is unspecified if it is called with an invalid cursor parameter.@PDefn{unspecified} Execution is erroneous if any other subprogram declared in Containers.Multiway_Trees is called with an invalid cursor parameter.]} @begin{Discussion} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The list above is intended to be exhaustive. In other cases, a cursor value continues to designate its original element (or the root node). For instance, cursor values survive the insertion and deletion of other nodes.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[While it is possible to check for these cases, in many cases the overhead necessary to make the check is substantial in time or space. Implementations are encouraged to check for as many of these cases as possible and raise Program_Error if detected.]} @end{Discussion} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[Execution is erroneous if the tree associated with the result of a call to Reference or Constant_Reference is finalized before the result object returned by the call to Reference or Constant_Reference is finalized.]} @begin{Reason} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Each object of Reference_Type and Constant_Reference_Type probably contains some reference to the originating container. If that container is prematurely finalized (which is only possible via Unchecked_Deallocation, as accessibility checks prevent passing a container to Reference that will not live as long as the result), the finalization of the object of Reference_Type will try to access a non-existent object. This is a normal case of a dangling pointer created by Unchecked_Deallocation; we have to explicitly mention it here as the pointer in question is not visible in the specification of the type. (This is the same reason we have to say this for invalid cursors.)]} @end{Reason} @end{Erron} @begin{ImplReq} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[No storage associated with a multiway tree object shall be lost upon assignment or scope exit.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[The execution of an @nt{assignment_statement} for a tree shall have the effect of copying the elements from the source tree object to the target tree object.]} @begin{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[An assignment of a Tree is a @lquotes@;deep@rquotes copy; that is the elements are copied as well as the data structures. We say @lquotes@;effect of@rquotes in order to allow the implementation to avoid copying elements immediately if it wishes. For instance, an implementation that avoided copying until one of the containers is modified would be allowed.]} @end{ImplNote} @end{ImplReq} @begin{ImplAdvice} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[Containers.Multiway_Trees should be implemented similarly to a multiway tree. In particular, if @i{N} is the overall number of nodes for a particular tree, then the worst-case time complexity of Element, Parent, First_Child, Last_Child, Insert_Child with Count=1, and Delete should be @i{O}(log @i{N}).]} @ChgImplAdvice{Version=[3],Kind=[AddedNormal],Text=[@ChgAdded{Version=[3], Text=[The worst-case time complexity of the Element, Parent, First_Child, Last_Child, Insert_Child with Count=1, and Delete operations of Containers.Multiway_Trees should be @i{O}(log @i).]}]} @begin{Reason} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[We do not mean to overly constrain implementation strategies here. However, it is important for portability that the performance of large containers has roughly the same factors on different implementations. If a program is moved to an implementation that takes @i{O}(@i) time to access elements, that program could be unusable when the trees are large. We allow @i{O}(log @i) access because the proportionality constant and caching effects are likely to be larger than the log factor, and we don't want to discourage innovative implementations.]} @end{Reason} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[Move should not copy elements, and should minimize copying of internal data structures.]} @ChgImplAdvice{Version=[3],Kind=[AddedNormal],Text=[@ChgAdded{Version=[3], Text=[Containers.Multiway_Trees.Move should not copy elements, and should minimize copying of internal data structures.]}]} @begin{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Usually that can be accomplished simply by moving the pointer(s) to the internal data structures from the Source container to the Target container.]} @end{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[If an exception is propagated from a tree operation, no storage should be lost, nor any elements removed from a tree unless specified by the operation.]} @ChgImplAdvice{Version=[3],Kind=[AddedNormal],Text=[@ChgAdded{Version=[3], Text=[If an exception is propagated from a tree operation, no storage should be lost, nor any elements removed from a tree unless specified by the operation.]}]} @begin{Reason} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[This is important so that programs can recover from errors. But we don't want to require heroic efforts, so we just require documentation of cases where this can't be accomplished.]} @end{Reason} @end{ImplAdvice} @begin{Extend2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0257-1]} @ChgAdded{Version=[3],Text=[@Defn{extensions to Ada 2005} The generic package Containers.Multiway_Trees is new.]} @end{Extend2005} @LabeledAddedSubclause{Version=[2],Name=[The Generic Package Containers.Indefinite_Vectors]} @begin{Intro} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgAdded{Version=[2],Text=[The language-defined generic package Containers.Indefinite_Vectors provides a private type Vector and a set of operations. It provides the same operations as the package Containers.Vectors (see @RefSecNum{The Generic Package Containers.Vectors}), with the difference that the generic formal Element_Type is indefinite.]} @end{Intro} @begin{StaticSem} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgRef{Version=[3],Kind=[Revised],ARef=[AI05-0092-1]} @ChgAdded{Version=[2],Type=[Leading],Text=[The declaration of the generic library package Containers.Indefinite_Vectors@ChildUnit{Parent=[Ada.Containers],Child=[Indefinite_Vectors]} has the same contents @Chg{Version=[3],New=[and semantics ],Old=[]}as Containers.Vectors except:]} @begin{Itemize} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[The generic formal Element_Type is indefinite.]} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Keepnext=[T],Type=[Leading],Text=[The procedures with the profiles:]} @begin{Example} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Noprefix=[T],Keepnext=[F],Type=[Leading],Text=[@key{procedure} Insert (Container : @key{in out} Vector; Before : @key{in} Extended_Index; Count : @key{in} Count_Type := 1);]} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Noprefix=[T],Keepnext=[T],Type=[Leading],Text=[@key{procedure} Insert (Container : @key{in out} Vector; Before : @key{in} Cursor; Position : @key{out} Cursor; Count : @key{in} Count_Type := 1);]} @end{Example} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Noprefix=[T],Text=[are omitted.]} @begin{Discussion} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[These procedures are omitted because there is no way to create a default-initialized object of an indefinite type. Note that Insert_Space can be used instead of this routine in most cases. Omitting the routine completely allows any problems to be diagnosed by the compiler when converting from a definite to indefinite vector.]} @end{Discussion} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[The actual Element parameter of access subprogram Process of Update_Element may be constrained even if Element_Type is unconstrained.]} @end{Itemize} @end{StaticSem} @begin{Extend95} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgAdded{Version=[2],Text=[@Defn{extensions to Ada 95} The generic package Containers.Indefinite_Vectors is new.]} @end{Extend95} @LabeledAddedSubclause{Version=[2],Name=[The Generic Package Containers.Indefinite_Doubly_Linked_Lists]} @begin{Intro} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgAdded{Version=[2],Text=[The language-defined generic package Containers.Indefinite_Doubly_Linked_Lists provides private types List and Cursor, and a set of operations for each type. It provides the same operations as the package Containers.Doubly_Linked_Lists (see @RefSecNum{The Generic Package Containers.Doubly_Linked_Lists}), with the difference that the generic formal Element_Type is indefinite.]} @end{Intro} @begin{StaticSem} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgRef{Version=[3],Kind=[Revised],ARef=[AI05-0092-1]} @ChgAdded{Version=[2],Type=[Leading],Text=[The declaration of the generic library package Containers.@!Indefinite_@!Doubly_@!Linked_@!Lists@ChildUnit{Parent=[Ada.Containers],Child=[Indefinite_Doubly_Linked_Lists]} has the same contents @Chg{Version=[3],New=[and semantics ],Old=[]}as Containers.@!Doubly_@!Linked_@!Lists except:]} @begin{Itemize} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[The generic formal Element_Type is indefinite.]} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Keepnext=[T],Type=[Leading],Text=[The procedure with the profile:]} @begin{Example} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Noprefix=[T],Keepnext=[T],Type=[Leading],Text=[@key{procedure} Insert (Container : @key{in out} List; Before : @key{in} Cursor; Position : @key{out} Cursor; Count : @key{in} Count_Type := 1);]} @end{Example} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Noprefix=[T],Text=[is omitted.]} @begin{Discussion} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[This procedure is omitted because there is no way to create a default-initialized object of an indefinite type. We considered having this routine insert an empty element similar to the empty elements of a vector, but rejected this possibility because the semantics are fairly complex and very different from the existing definite container. That would make it more error-prone to convert a container from a definite type to an indefinite type; by omitting the routine completely, any problems will be diagnosed by the compiler.]} @end{Discussion} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[The actual Element parameter of access subprogram Process of Update_Element may be constrained even if Element_Type is unconstrained.]} @end{Itemize} @end{StaticSem} @begin{Extend95} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgAdded{Version=[2],Text=[@Defn{extensions to Ada 95} The generic package Containers.Indefinite_Doubly_Linked_Lists is new.]} @end{Extend95} @LabeledAddedSubclause{Version=[2],Name=[The Generic Package Containers.Indefinite_Hashed_Maps]} @begin{Intro} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgAdded{Version=[2],Text=[The language-defined generic package Containers.Indefinite_Hashed_Maps provides a map with the same operations as the package Containers.Hashed_Maps (see @RefSecNum{The Generic Package Containers.Hashed_Maps}), with the difference that the generic formal types Key_Type and Element_Type are indefinite.]} @end{Intro} @begin{StaticSem} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgRef{Version=[3],Kind=[Revised],ARef=[AI05-0092-1]} @ChgAdded{Version=[2],Type=[Leading],Text=[The declaration of the generic library package Containers.Indefinite_Hashed_Maps@ChildUnit{Parent=[Ada.Containers],Child=[Indefinite_Hashed_Maps]} has the same contents @Chg{Version=[3],New=[and semantics ],Old=[]}as Containers.Hashed_Maps except:]} @begin{Itemize} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[The generic formal Key_Type is indefinite.]} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[The generic formal Element_Type is indefinite.]} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Keepnext=[T],Type=[Leading],Text=[The procedure with the profile:]} @begin{Example} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Noprefix=[T],Keepnext=[T],Type=[Leading],Text=[@key{procedure} Insert (Container : @key{in out} Map; Key : @key{in} Key_Type; Position : @key{out} Cursor; Inserted : @key{out} Boolean);]} @end{Example} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Noprefix=[T],Text=[is omitted.]} @begin{Discussion} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[This procedure is omitted because there is no way to create a default-initialized object of an indefinite type. We considered having this routine insert an empty element similar to the empty elements of a vector, but rejected this possibility because the semantics are fairly complex and very different from the existing case. That would make it more error-prone to convert a container from a definite type to an indefinite type; by omitting the routine completely, any problems will be diagnosed by the compiler.]} @end{Discussion} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[The actual Element parameter of access subprogram Process of Update_Element may be constrained even if Element_Type is unconstrained.]} @end{Itemize} @end{StaticSem} @begin{Extend95} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgAdded{Version=[2],Text=[@Defn{extensions to Ada 95} The generic package Containers.Indefinite_Hashed_Maps is new.]} @end{Extend95} @LabeledAddedSubclause{Version=[2],Name=[The Generic Package Containers.Indefinite_Ordered_Maps]} @begin{Intro} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgAdded{Version=[2],Text=[The language-defined generic package Containers.Indefinite_Ordered_Maps provides a map with the same operations as the package Containers.Ordered_Maps (see @RefSecNum{The Generic Package Containers.Ordered_Maps}), with the difference that the generic formal types Key_Type and Element_Type are indefinite.]} @end{Intro} @begin{StaticSem} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgRef{Version=[3],Kind=[Revised],ARef=[AI05-0092-1]} @ChgAdded{Version=[2],Type=[Leading],Text=[The declaration of the generic library package Containers.Indefinite_Ordered_Maps@ChildUnit{Parent=[Ada.Containers],Child=[Indefinite_Ordered_Maps]} has the same contents @Chg{Version=[3],New=[and semantics ],Old=[]}as Containers.Ordered_Maps except:]} @begin{Itemize} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[The generic formal Key_Type is indefinite.]} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[The generic formal Element_Type is indefinite.]} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Keepnext=[T],Type=[Leading],Text=[The procedure with the profile:]} @begin{Example} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Noprefix=[T],Keepnext=[T],Type=[Leading],Text=[@key{procedure} Insert (Container : @key{in out} Map; Key : @key{in} Key_Type; Position : @key{out} Cursor; Inserted : @key{out} Boolean);]} @end{Example} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Noprefix=[T],Text=[is omitted.]} @begin{Discussion} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[This procedure is omitted because there is no way to create a default-initialized object of an indefinite type. We considered having this routine insert an empty element similar to the empty elements of a vector, but rejected this possibility because the semantics are fairly complex and very different from the existing case. That would make it more error-prone to convert a container from a definite type to an indefinite type; by omitting the routine completely, any problems will be diagnosed by the compiler.]} @end{Discussion} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[The actual Element parameter of access subprogram Process of Update_Element may be constrained even if Element_Type is unconstrained.]} @end{Itemize} @end{StaticSem} @begin{Extend95} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgAdded{Version=[2],Text=[@Defn{extensions to Ada 95} The generic package Containers.Indefinite_Ordered_Maps is new.]} @end{Extend95} @LabeledAddedSubclause{Version=[2],Name=[The Generic Package Containers.Indefinite_Hashed_Sets]} @begin{Intro} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgAdded{Version=[2],Text=[The language-defined generic package Containers.Indefinite_Hashed_Sets provides a set with the same operations as the package Containers.Hashed_Sets (see @RefSecNum{The Generic Package Containers.Hashed_Sets}), with the difference that the generic formal type Element_Type is indefinite.]} @end{Intro} @begin{StaticSem} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgRef{Version=[3],Kind=[Revised],ARef=[AI05-0092-1]} @ChgAdded{Version=[2],Type=[Leading],Text=[The declaration of the generic library package Containers.Indefinite_Hashed_Sets@ChildUnit{Parent=[Ada.Containers],Child=[Indefinite_Hashed_Sets]} has the same contents @Chg{Version=[3],New=[and semantics ],Old=[]}as Containers.Hashed_Sets except:]} @begin{Itemize} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[The generic formal Element_Type is indefinite.]} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[The actual Element parameter of access subprogram Process of Update_@!Element_@!Preserving_Key may be constrained even if Element_Type is unconstrained.]} @end{Itemize} @end{StaticSem} @begin{Extend95} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgAdded{Version=[2],Text=[@Defn{extensions to Ada 95} The generic package Containers.Indefinite_Hashed_Sets is new.]} @end{Extend95} @LabeledAddedSubclause{Version=[2],Name=[The Generic Package Containers.Indefinite_Ordered_Sets]} @begin{Intro} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgAdded{Version=[2],Text=[The language-defined generic package Containers.Indefinite_Ordered_Sets provides a set with the same operations as the package Containers.Ordered_Sets (see @RefSecNum{The Generic Package Containers.Ordered_Sets}), with the difference that the generic formal type Element_Type is indefinite.]} @end{Intro} @begin{StaticSem} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgRef{Version=[3],Kind=[Revised],ARef=[AI05-0092-1]} @ChgAdded{Version=[2],Type=[Leading],Text=[The declaration of the generic library package Containers.Indefinite_Ordered_Sets@ChildUnit{Parent=[Ada.Containers],Child=[Indefinite_Ordered_Sets]} has the same contents @Chg{Version=[3],New=[and semantics ],Old=[]}as Containers.Ordered_Sets except:]} @begin{Itemize} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[The generic formal Element_Type is indefinite.]} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[The actual Element parameter of access subprogram Process of Update_@!Element_@!Preserving_Key may be constrained even if Element_Type is unconstrained.]} @end{Itemize} @end{StaticSem} @begin{Extend95} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgAdded{Version=[2],Text=[@Defn{extensions to Ada 95} The generic package Containers.Indefinite_Ordered_Sets is new.]} @end{Extend95} @LabeledAddedSubclause{Version=[3],Name=[The Generic Package Containers.Indefinite_Multiway_Trees]} @begin{Intro} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[The language-defined generic package Containers.Indefinite_Multiway_Trees provides a multiway tree with the same operations as the package Containers.Multiway_Trees (see @RefSecNum{The Generic Package Containers.Multiway_Trees}), with the difference that the generic formal Element_Type is indefinite.]} @end{Intro} @begin{StaticSem} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[The declaration of the generic library package Containers.Indefinite_Multiway_Trees@ChildUnit{Parent=[Ada.Containers],Child=[Indefinite_Multiway_Trees]} has the same contents and semantics as Containers.Multiway_Trees except:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The generic formal Element_Type is indefinite.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Keepnext=[T],Type=[Leading],Text=[The procedure with the profile:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Keepnext=[T],Type=[Leading],Text=[@key{procedure} Insert_Child (Container : @key{in out} Tree; Parent : @key{in} Cursor; Before : @key{in} Cursor; Position : @key{out} Cursor; Count : @key{in} Count_Type := 1);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[is omitted.]} @begin{Discussion} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[This procedure is omitted because there is no way to create a default-initialized object of an indefinite type. We considered having this routine insert an empty element similar to the empty elements of a vector, but rejected this possibility because the semantics are fairly complex and very different from the existing case. That would make it more error-prone to convert a container from a definite type to an indefinite type; by omitting the routine completely, any problems will be diagnosed by the compiler.]} @end{Discussion} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The actual Element parameter of access subprogram Process of Update_Element may be constrained even if Element_Type is unconstrained.]} @end{Itemize} @end{StaticSem} @begin{Extend2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[@Defn{extensions to Ada 2005} The generic package Containers.Indefinite_Multiway_Trees is new.]} @end{Extend2005} @LabeledAddedSubclause{Version=[3],Name=[The Generic Package Containers.Indefinite_Holders]} @begin{Intro} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Text=[The language-defined generic package Containers.Indefinite_Holders provides a private type Holder and a set of operations for that type. A holder container holds a single element of an indefinite type.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Text=[A holder container allows the declaration of an object that can be used like an uninitialized variable or component of an indefinite type.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Text=[A holder container may be @i{empty}. An empty holder does not contain an element.@Defn{empty holder}]} @end{Intro} @begin{StaticSem} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],KeepNext=[T],Type=[Leading],Text=[The generic library package Containers.Indefinite_Holders has the following declaration:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal],Aref=[AI05-0069-1],Aref=[AI05-0084-1]} @ChgAdded{Version=[3],Text=[@key[generic] @key[type] Element_Type (<>) @key[is private]; @key[with function] "=" (Left, Right : Element_Type) @key[return] Boolean @key[is] <>; @key[package] Ada.Containers.Indefinite_Holders @key[is]@ChildUnit{Parent=[Ada.Containers],Child=[Indefinite_Holders]} @key[pragma] Preelaborate(Indefinite_Holders); @key[pragma] Remote_Types(Indefinite_Holders);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[type] @AdaTypeDefn{Holder} @key[is tagged private]; @key[pragma] Preelaborable_Initialization (Holder);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @AdaObjDefn{Empty_Holder} : @key[constant] Holder;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[function] "=" (Left, Right : Holder) @key[return] Boolean;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[function] @AdaSubDefn{To_Holder} (New_Item : Element_Type) @key[return] Holder;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[function] @AdaSubDefn{Is_Empty} (Container : Holder) @key[return] Boolean;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[procedure] @AdaSubDefn{Clear} (Container : @key[in out] Holder);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[function] @AdaSubDefn{Element} (Container : Holder) @key[return] Element_Type;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[procedure] @AdaSubDefn{Replace_Element} (Container : @key[in out] Holder; New_Item : @key[in] Element_Type);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[procedure] @AdaSubDefn{Query_Element} (Container : @key[in] Holder; Process : @key[not null access procedure] (Element : @key[in] Element_Type));]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[ @key[procedure] @AdaSubDefn{Update_Element} (Container : @key[in out] Holder; Process : @key[not null access procedure] (Element : @key[in out] Element_Type));]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[ @key[type] @AdaTypeDefn{Constant_Reference_Type} (Element : @key[not null access constant] Element_Type) @key[is private] @key[with] Implicit_Dereference => Element;]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[ @key[type] @AdaTypeDefn{Reference_Type} (Element : @key[not null access] Element_Type) @key[is private] @key[with] Implicit_Dereference => Element;]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[ @key[function] @AdaSubDefn{Constant_Reference} (Container : @key[aliased in] Holder) @key[return] Constant_Reference_Type;]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[ @key[function] @AdaSubDefn{Reference} (Container : @key[aliased in out] Holder) @key[return] Reference_Type;]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[ @key[procedure] @AdaSubDefn{Assign} (Target : @key[in out] Holder; Source : @key[in] Holder);]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[ @key[function] @AdaSubDefn{Copy} (Source : Holder) @key[return] Holder;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[procedure] @AdaSubDefn{Move} (Target : @key[in out] Holder; Source : @key[in out] Holder);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key{private}]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ ... -- @RI[not specified by the language]]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key{end} Ada.Containers.Indefinite_Holders;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Text=[The actual function for the generic formal function "=" on Element_Type values is expected to define a reflexive and symmetric relationship and return the same result value each time it is called with a particular pair of values. If it behaves in some other manner, the function "=" on holder values returns an unspecified value. The exact arguments and number of calls of this generic formal function by the function "=" on holder values are unspecified.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[If the actual function for "=" is not symmetric and consistent, the result returned by any of the functions defined to use "=" cannot be predicted. The implementation is not required to protect against "=" raising an exception, or returning random results, or any other "bad" behavior. And it can call "=" in whatever manner makes sense. But note that only the results of the function "=" is unspecified; other subprograms are not allowed to break if "=" is bad.]} @end{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Text=[The type Holder is used to represent holder containers. The type Holder needs finalization@PDefn2{Term=, Sec=} (see @RefSecNum{Assignment and Finalization}).]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Text=[Empty_Holder represents an empty holder object. If an object of type Holder is not otherwise initialized, it is initialized to the same value as Empty_Holder.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Text=[@Redundant[Some operations of this generic package have access-to-subprogram parameters. To ensure such operations are well-defined, they guard against certain actions by the designated subprogram. In particular, some operations check for @ldquote@;tampering with elements@rdquote of a container because they depend on elements of the container not being replaced.]]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[@Defn2{Term=[tamper with elements],Sec=[of a holder]} A subprogram is said to @i{tamper with elements} of a holder object @i if:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[It clears the element contained by @i, that is, it calls the Clear procedure with @i as a parameter;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[It replaces the element contained by @i, that is, it calls the Replace_Element procedure with H as a parameter;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[It calls the Move procedure with @i as a parameter;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[It finalizes @i.]} @begin{Reason} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Complete replacement of an element can cause its memory to be deallocated while another operation is holding onto a reference to it. That can't be allowed. However, a simple modification of (part of) an element is not a problem, so Update_Element does not cause a problem.]} @end{Reason} @end{Itemize} @begin{DescribeCode} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} "=" (Left, Right : Holder) @key{return} Boolean;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Left and Right denote the same holder object, then the function returns True. Otherwise, it compares the element contained in Left to the element contained in Right using the generic formal equality operator, returning the result of that operation. Any exception raised during the evaluation of element equality is propagated.]} @begin{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[This wording describes the canonical semantics. However, the order and number of calls on the formal equality @key[function] is unspecified, so an implementation need not call the equality function if the correct answer can be determined without doing so.]} @end{ImplNote} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[function] To_Holder (New_Item : Element_Type) @key[return] Holder;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Returns a non-empty holder containing an element initialized to New_Item.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[function] Is_Empty (Container : Holder) @key[return] Boolean;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Returns True if the holder is empty, and False if it contains an element.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[procedure] Clear (Container : @key[in out] Holder);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Removes the element from Container. Container is empty after a successful Clear operation.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[function] Element (Container : Holder) @key[return] Element_Type;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Container is empty, Constraint_Error is propagated. Otherwise, returns the element stored in Container.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[procedure] Replace_Element (Container : @key[in out] Holder; New_Item : @key[in] Element_Type);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Replace_Element assigns the value New_Item into Container, replacing any preexisting content of Container. Container is not empty after a successful call to Replace_Element.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[procedure] Query_Element (Container : @key[in] Holder; Process : @key[not null access procedure] (Element : @key[in] Element_Type));]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Container is empty, Constraint_Error is propagated. Otherwise, Query_Element calls Process.@key[all] with the contained element as the argument. Program_Error is raised if Process.@key[all] tampers with the elements of Container. Any exception raised by Process.@key[all] is propagated.]} @begin{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The @ldquote@;tamper with the elements@rdquote check is intended to prevent the Element parameter of Process from being modified or deleted outside of Process. The check prevents data loss (if Element_Type is passed by copy) or erroneous execution (if Element_Type is an unconstrained type).]} @end{ImplNote} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[procedure] Update_Element (Container : @key[in out] Holder; Process : @key[not null access procedure] (Element : @key[in out] Element_Type));]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Container is empty, Constraint_Error is propagated. Otherwise, Update_Element calls Process.@key[all] with the contained element as the argument. Program_Error is raised if Process.@key[all] tampers with the elements of Container. Any exception raised by Process.@key[all] is propagated.]} @begin{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The Element parameter of Process.@key[all] may be constrained even if Element_Type is unconstrained.]} @end{ImplNote} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[@key[type] Constant_Reference_Type (Element : @key[not null access constant] Element_Type) @key[is private] @key[with] Implicit_Dereference => Element;]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[type] Reference_Type (Element : @key[not null access] Element_Type) @key[is private] @key[with] Implicit_Dereference => Element;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Constant_Reference_Type and Reference_Type need finalization.@PDefn2{Term=,Sec=}]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[The default initialization of an object of type Constant_Reference_Type or Reference_Type propagates Program_Error.]} @begin{Reason} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[It is expected that Reference_Type (and Constant_Reference_Type) will be a controlled type, for which finalization will have some action to terminate the tampering check for the associated container. If the object is created by default, however, there is no associated container. Since this is useless, and supporting this case would take extra work, we define it to raise an exception.]} @end{Reason} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[function] Constant_Reference (Container : @key[aliased in] Holder) @key[return] Constant_Reference_Type;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[This routine (combined with the Implicit_Dereference aspect) provides a convenient way to gain read access to the contained element of a holder container.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[If Container is empty, Constraint_Error is propagated. Otherwise, Constant_Reference returns an object whose discriminant is an access value that designates the contained element. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Constant_Reference exists and has not been finalized.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[function] Reference (Container : @key[aliased in out] Holder) @key[return] Reference_Type;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[This function (combined with the Implicit_Dereference aspects) provides a convenient way to gain read and write access to the contained element of a holder container.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[If Container is empty, Constraint_Error is propagated. Otherwise, Reference returns an object whose discriminant is an access value that designates the contained element. Program_Error is propagated if any operation tampers with the elements of Container while the object returned by Reference exists and has not been finalized.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[procedure] Assign (Target : @key[in out] Holder; Source : @key[in] Holder);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Target denotes the same object as Source, the operation has no effect. If Source is empty, Clear (Target) is called. Otherwise, Replace_Element (Target, Element (Source)) is called.]} @begin{Discussion} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0005-1]} @ChgAdded{Version=[3],Text=[This routine exists for compatibility with the other containers. For a holder, @exam{Assign(A, B)} and @exam{A := B} behave identically.]} @end{Discussion} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[function] Copy (Source : Holder) @key[return] Holder;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Source is empty, returns an empty holder; otherwise, returns To_Holder (Element (Source)).]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[procedure] Move (Target : @key[in out] Holder; Source : @key[in out] Holder);]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If Target denotes the same object as Source, then the operation has no effect. Otherwise, the element contained by Source (if any) is removed from Source and inserted into Target, replacing any preexisting content. Source is empty after a successful call to Move.]} @end{DescribeCode} @end{StaticSem} @begin{Bounded} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0022-1],ARef=[AI05-0069-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[@PDefn2{Term=(bounded error),Sec=(cause)} It is a bounded error for the actual function associated with a generic formal subprogram, when called as part of an operation of this package, to tamper with elements of any Holder parameter ofto the operation. Either Program_Error is raised, or the operation works as defined on the value of the Holder either prior to, or subsequent to, some or all of the modifications to the Holder.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0027-1],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Text=[@PDefn2{Term=(bounded error),Sec=(cause)} It is a bounded error to call any subprogram declared in the visible part of Containers.Indefinite_Holders when the associated container has been finalized. If the operation takes Container as an @key[in out] parameter, then it raises Constraint_Error or Program_Error. Otherwise, the operation either proceeds as it would for an empty container, or it raises Constraint_Error or Program_Error.]} @end{Bounded} @begin{Erron} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[Execution is erroneous if the holder associated with the result of a call to Reference or Constant_Reference is finalized before the result object returned by the call to Reference or Constant_Reference is finalized.@PDefn2{Term=(erroneous execution),Sec=(cause)}]} @begin{Reason} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[Each object of Reference_Type and Constant_Reference_Type probably contains some reference to the originating container. If that container is prematurely finalized (which is only possible via Unchecked_Deallocation, as accessibility checks prevent passing a container to Reference that will not live as long as the result), the finalization of the object of Reference_Type will try to access a non-existent object. This is a normal case of a dangling pointer created by Unchecked_Deallocation; we have to explicitly mention it here as the pointer in question is not visible in the specification of the type. (This is the same reason we have to say this for invalid cursors.)]} @end{Reason} @end{Erron} @begin{ImplReq} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Text=[No storage associated with a holder object shall be lost upon assignment or scope exit.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Text=[The execution of an @nt{assignment_statement} for a holder shall have the effect of copying the element (if any) from the source holder object to the target holder object.]} @begin{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[An assignment of a holder is a @ldquote@;deep@rdquote copy; that is the elements are copied as well as the data structures. We say @ldquote@;effect of@rdquote in order to allow the implementation to avoid copying elements immediately if it wishes. For instance, an implementation that avoided copying until one of the containers is modified would be allowed.]} @end{ImplNote} @end{ImplReq} @begin{ImplAdvice} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Text=[Move should not copy elements, and should minimize copying of internal data structures.]} @ChgImplAdvice{Version=[3],Kind=[Added],Text=[@ChgAdded{Version=[3], Text=[Containers.Indefinite_Holders.Move should not copy elements, and should minimize copying of internal data structures.]}]} @begin{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Usually that can be accomplished simply by moving the pointer(s) to the internal data structures from the Source holder to the Target holder.]} @end{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1]} @ChgAdded{Version=[3],Text=[If an exception is propagated from a holder operation, no storage should be lost, nor should the element be removed from a holder unless specified by the operation.]} @ChgImplAdvice{Version=[3],Kind=[Added],Text=[@ChgAdded{Version=[3], Text=[If an exception is propagated from a holder operation, no storage should be lost, nor should the element be removed from a holder unless specified by the operation.]}]} @begin{Reason} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[This is important so that programs can recover from errors. But we don't want to require heroic efforts, so we just require documentation of cases where this can't be accomplished.]} @end{Reason} @end{ImplAdvice} @begin{Extend2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0069-1],ARef=[AI05-0084-1]} @ChgAdded{Version=[3],Text=[@Defn{extensions to Ada 2005} The generic package Containers.Indefinite_Holders is new.]} @end{Extend2005} @LabeledAddedSubclause{Version=[3],Name=[The Generic Package Containers.Bounded_Vectors]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[The language-defined generic package Containers.Bounded_Vectors provides a private type Vector and a set of operations. It provides the same operations as the package Containers.Vectors (see @RefSecNum{The Generic Package Containers.Vectors}), with the difference that the maximum storage is bounded.]} @begin{StaticSem} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[The declaration of the generic library package Containers.Bounded_Vectors has the same contents and semantics as Containers.Vectors except:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The @nt{pragma} Preelaborate is replaced with @nt{pragma} Pure.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[The type Vector is declared with a discriminant that specifies the capacity:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[ @key{type} Vector (Capacity : Count_Type) @key[is tagged private];]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The type Vector needs finalization if and only if type Element_Type needs finalization.]} @begin{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[The type Vector cannot depend on package Ada.Finalization unless the element type depends on that package. The objects returned from the Iterator and Reference functions probably do depend on package Ada.Finalization. Restricted environments may need to avoid use of those functions and their associated types.]} @end{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[In function Copy, if the Capacity parameter is equal to or greater than the length of Source, the vector capacity exactly equals the value of the Capacity parameter.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[The description of Reserve_Capacity is replaced with:]} @begin{Indent} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],NoPrefix=[T],Text=[If the specified Capacity is larger than the capacity of Container, then Reserve_Capacity propagates Capacity_Error. Otherwise, the operation has no effect.]} @end{Indent} @end{Itemize} @end{StaticSem} @begin{Bounded} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0160-1]} @ChgAdded{Version=[3],Text=[@PDefn2{Term=(bounded error),Sec=(cause)} It is a bounded error to use a bounded vector if it was the target of an @nt{assignment_statement} whose source was in the middle of an operation that disallows tampering with elements @Redundant[or cursors]. Either Program_Error is raised, or the operation proceeds as defined.]} @end{Bounded} @begin{ImplReq} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1],ARef=[AI05-0264-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[For each instance of Containers.Vectors and each instance of Containers.Bounded_Vectors, if the two instances meet the following conditions, then the output generated by the Vector'Output or Vector'Write subprograms of either instance shall be readable by the Vector'Input or Vector'Read of the other instance, respectively:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[the Element_Type parameters of the two instances are statically matching subtypes of the same type; and]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1]} @ChgAdded{Version=[3],Text=[the output generated by Element_Type'Output or Element_Type'Write is readable by Element_Type'Input or Element_Type'Read, respectively (where Element_Type denotes the type of the two actual Element_Type parameters); and]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1]} @ChgAdded{Version=[3],Text=[the preceding two conditions also hold for the Index_Type parameters of the instances.]} @end{Itemize} @end{ImplReq} @begin{ImplAdvice} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[Bounded vector objects should be implemented without implicit pointers or dynamic allocation.]} @ChgImplAdvice{Version=[3],Kind=[Added],Text=[@ChgAdded{Version=[3], Text=[Bounded vector objects should be implemented without implicit pointers or dynamic allocation.]}]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[The implementation advice for procedure Move to minimize copying does not apply.]} @ChgImplAdvice{Version=[3],Kind=[Added],Text=[@ChgAdded{Version=[3], Text=[The implementation advice for procedure Move to minimize copying does not apply to bounded vectors.]}]} @end{ImplAdvice} @begin{Extend2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1],ARef=[AI05-0160-1],ARef=[AI05-0184-1]} @ChgAdded{Version=[3],Text=[@Defn{extensions to Ada 2005} The generic package Containers.Bounded_Vectors is new.]} @end{Extend2005} @LabeledAddedSubclause{Version=[3],Name=[The Generic Package Containers.Bounded_Doubly_Linked_Lists]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[The language-defined generic package Containers.Bounded_Doubly_Linked_Lists provides a private type List and a set of operations. It provides the same operations as the package Containers.Doubly_Linked_Lists (see @RefSecNum{The Generic Package Containers.Doubly_Linked_Lists}), with the difference that the maximum storage is bounded.]} @begin{StaticSem} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[The declaration of the generic library package Containers.Bounded_Doubly_Linked_Lists has the same contents and semantics as Containers.Doubly_Linked_Lists except:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The @nt{pragma} Preelaborate is replaced with @nt{pragma} Pure.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[The type List is declared with a discriminant that specifies the capacity (maximum number of elements) as follows:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[ @key{type} List (Capacity : Count_Type) @key[is tagged private];]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The type List needs finalization if and only if type Element_Type needs finalization.]} @begin{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[The type List cannot depend on package Ada.Finalization unless the element type depends on that package. The objects returned from the Iterator and Reference functions probably do depend on package Ada.Finalization. Restricted environments may need to avoid use of those functions and their associated types.]} @end{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The allocation of internal storage includes a check that the capacity is not exceeded, and Capacity_Error is raised if this check fails.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[In procedure Assign, if Source length is greater than Target capacity, then Capacity_Error is propagated.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[The function Copy is replaced with:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[ @key[function] @AdaSubDefn{Copy} (Source : List; Capacity : Count_Type := 0) @key[return] List;]} @end{Example} @begin{Indent} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[If Capacity is 0, then the list capacity is the length of Source; if Capacity is equal to or greater than the length of Source, the list capacity equals the value of the Capacity parameter; otherwise, the operation propagates Capacity_Error.]} @end{Indent} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[In the three-parameter procedure Splice whose Source has type List, if the sum of the length of Target and the length of Source is greater than the capacity of Target, then Splice propagates Capacity_Error.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[In the four-parameter procedure Splice, if the length of Target equals the capacity of Target, then Splice propagates Capacity_Error.]} @end{Itemize} @end{StaticSem} @begin{Bounded} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0160-1]} @ChgAdded{Version=[3],Text=[@PDefn2{Term=(bounded error),Sec=(cause)} It is a bounded error to use a bounded list if it was the target of an @nt{assignment_statement} whose source was in the middle of an operation that disallows tampering with elements @Redundant[or cursors]. Either Program_Error is raised, or the operation proceeds as defined.]} @end{Bounded} @begin{ImplReq} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1],ARef=[AI05-0264-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[For each instance of Containers.Doubly_Linked_Lists and each instance of Containers.Bounded_Doubly_Linked_Lists, if the two instances meet the following conditions, then the output generated by the List'Output or List'Write subprograms of either instance shall be readable by the List'Input or List'Read of the other instance, respectively:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[the Element_Type parameters of the two instances are statically matching subtypes of the same type; and]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1]} @ChgAdded{Version=[3],Text=[the output generated by Element_Type'Output or Element_Type'Write is readable by Element_Type'Input or Element_Type'Read, respectively (where Element_Type denotes the type of the two actual Element_Type parameters).]} @end{Itemize} @end{ImplReq} @begin{ImplAdvice} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[Bounded list objects should be implemented without implicit pointers or dynamic allocation.]} @ChgImplAdvice{Version=[3],Kind=[Added],Text=[@ChgAdded{Version=[3], Text=[Bounded list objects should be implemented without implicit pointers or dynamic allocation.]}]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[The implementation advice for procedure Move to minimize copying does not apply.]} @ChgImplAdvice{Version=[3],Kind=[Added],Text=[@ChgAdded{Version=[3], Text=[The implementation advice for procedure Move to minimize copying does not apply to bounded lists.]}]} @end{ImplAdvice} @begin{Extend2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1],ARef=[AI05-0160-1],ARef=[AI05-0184-1]} @ChgAdded{Version=[3],Text=[@Defn{extensions to Ada 2005} The generic package Containers.Bounded_Doubly_Linked_Lists is new.]} @end{Extend2005} @LabeledAddedSubclause{Version=[3],Name=[The Generic Package Containers.Bounded_Hashed_Maps]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[The language-defined generic package Containers.Bounded_Hashed_Maps provides a private type Map and a set of operations. It provides the same operations as the package Containers.Hashed_Maps (see @RefSecNum{The Generic Package Containers.Hashed_Maps}), with the difference that the maximum storage is bounded.]} @begin{StaticSem} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[The declaration of the generic library package Containers.Bounded_Hashed_Maps has the same contents and semantics as Containers.Hashed_Maps except:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The @nt{pragma} Preelaborate is replaced with @nt{pragma} Pure.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[The type Map is declared with discriminants that specify both the capacity (number of elements) and modulus (number of distinct hash values) of the hash table as follows:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[ @key[type] Map (Capacity : Count_Type; Modulus : Hash_Type) @key[is tagged private];]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The type Map needs finalization if and only if type Key_Type or type Element_Type needs finalization.]} @begin{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[The type Map cannot depend on package Ada.Finalization unless the element or key type depends on that package. The objects returned from the Iterator and Reference functions probably do depend on package Ada.Finalization. Restricted environments may need to avoid use of those functions and their associated types.]} @end{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[The description of Reserve_Capacity is replaced with:]} @begin{Indent} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],NoPrefix=[T],Text=[If the specified Capacity is larger than the capacity of Container, then Reserve_Capacity propagates Capacity_Error. Otherwise, the operation has no effect.]} @end{Indent} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[An additional operation is added immediately following Reserve_Capacity:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[ @key[function] @AdaSubDefn{Default_Modulus} (Capacity : Count_Type) @key[return] Hash_Type;]} @end{Example} @begin{Indent} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[Default_Modulus returns an implementation-defined value for the number of distinct hash values to be used for the given capacity (maximum number of elements).]} @end{Indent} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[The function Copy is replaced with:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[ @key[function] @AdaSubDefn{Copy} (Source : Map; Capacity : Count_Type := 0; Modulus : Hash_Type := 0) @key[return] Map;]} @end{Example} @begin{Indent} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0264-1]} @ChgAdded{Version=[3],Noprefix=[T],Text=[Returns a map with key/element pairs initialized from the values in Source. If Capacity is 0, then the map capacity is the length of Source; if Capacity is equal to or greater than the length of Source, the map capacity is the value of the Capacity parameter; otherwise, the operation propagates Capacity_Error. If the Modulus argument is 0, then the map modulus is the value returned by a call to Default_Modulus with the map capacity as its argument; otherwise, the map modulus is the value of the Modulus parameter.]} @end{Indent} @end{Itemize} @end{StaticSem} @begin{Bounded} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0160-1]} @ChgAdded{Version=[3],Text=[@PDefn2{Term=(bounded error),Sec=(cause)} It is a bounded error to use a bounded map if it was the target of an @nt{assignment_statement} whose source was in the middle of an operation that disallows tampering with elements @Redundant[or cursors]. Either Program_Error is raised, or the operation proceeds as defined.]} @end{Bounded} @begin{ImplReq} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1],ARef=[AI05-0264-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[For each instance of Containers.Hashed_Maps and each instance of Containers.Bounded_Hashed_Maps, if the two instances meet the following conditions, then the output generated by the Map'Output or Map'Write subprograms of either instance shall be readable by the Map'Input or Map'Read of the other instance, respectively:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[the Element_Type parameters of the two instances are statically matching subtypes of the same type; and]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1]} @ChgAdded{Version=[3],Text=[the output generated by Element_Type'Output or Element_Type'Write is readable by Element_Type'Input or Element_Type'Read, respectively (where Element_Type denotes the type of the two actual Element_Type parameters); and]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1]} @ChgAdded{Version=[3],Text=[the preceding two conditions also hold for the Key_Type parameters of the instances.]} @end{Itemize} @end{ImplReq} @begin{ImplAdvice} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[Bounded map objects should be implemented without implicit pointers or dynamic allocation.]} @ChgImplAdvice{Version=[3],Kind=[Added],Text=[@ChgAdded{Version=[3], Text=[Bounded map objects should be implemented without implicit pointers or dynamic allocation.]}]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[The implementation advice for procedure Move to minimize copying does not apply.]} @ChgImplAdvice{Version=[3],Kind=[Added],Text=[@ChgAdded{Version=[3], Text=[The implementation advice for procedure Move to minimize copying does not apply to bounded maps.]}]} @end{ImplAdvice} @begin{Extend2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1],ARef=[AI05-0160-1],ARef=[AI05-0184-1]} @ChgAdded{Version=[3],Text=[@Defn{extensions to Ada 2005} The generic package Containers.Bounded_Hashed_Maps is new.]} @end{Extend2005} @LabeledAddedSubclause{Version=[3],Name=[The Generic Package Containers.Bounded_Ordered_Maps]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[The language-defined generic package Containers.Bounded_Ordered_Maps provides a private type Map and a set of operations. It provides the same operations as the package Containers.Ordered_Maps (see @RefSecNum{The Generic Package Containers.Ordered_Maps}), with the difference that the maximum storage is bounded.]} @begin{StaticSem} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[The declaration of the generic library package Containers.Bounded_Ordered_Maps has the same contents and semantics as Containers.Ordered_Maps except:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The @nt{pragma} Preelaborate is replaced with @nt{pragma} Pure.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[The type Map is declared with a discriminant that specifies the capacity (maximum number of elements) as follows:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[ @key[type] Map (Capacity : Count_Type) @key[is tagged private];]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The type Map needs finalization if and only if type Element_Type needs finalization.]} @begin{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[The type Map cannot depend on package Ada.Finalization unless the element type depends on that package. The objects returned from the Iterator and Reference functions probably do depend on package Ada.Finalization. Restricted environments may need to avoid use of those functions and their associated types.]} @end{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The allocation of a new node includes a check that the capacity is not exceeded, and Capacity_Error is raised if this check fails.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[In procedure Assign, if Source length is greater than Target capacity, then Capacity_Error is propagated.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[The function Copy is replaced with:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[ @key[function] @AdaSubDefn{Copy} (Source : Map; Capacity : Count_Type := 0) @key[return] Map;]} @end{Example} @begin{Indent} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[Returns a map with key/element pairs initialized from the values in Source. If Capacity is 0, then the map capacity is the length of Source; if Capacity is equal to or greater than the length of Source, the map capacity is the specified value; otherwise, the operation propagates Capacity_Error.]} @end{Indent} @end{Itemize} @end{StaticSem} @begin{Bounded} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0160-1]} @ChgAdded{Version=[3],Text=[@PDefn2{Term=(bounded error),Sec=(cause)} It is a bounded error to use a bounded map if it was the target of an @nt{assignment_statement} whose source was in the middle of an operation that disallows tampering with elements @Redundant[or cursors]. Either Program_Error is raised, or the operation proceeds as defined.]} @end{Bounded} @begin{ImplReq} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1],ARef=[AI05-0264-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[For each instance of Containers.Ordered_Maps and each instance of Containers.Bounded_Ordered_Maps, if the two instances meet the following conditions, then the output generated by the Map'Output or Map'Write subprograms of either instance shall be readable by the Map'Input or Map'Read of the other instance, respectively:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[the Element_Type parameters of the two instances are statically matching subtypes of the same type; and]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1]} @ChgAdded{Version=[3],Text=[the output generated by Element_Type'Output or Element_Type'Write is readable by Element_Type'Input or Element_Type'Read, respectively (where Element_Type denotes the type of the two actual Element_Type parameters); and]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1]} @ChgAdded{Version=[3],Text=[the preceding two conditions also hold for the Key_Type parameters of the instances.]} @end{Itemize} @end{ImplReq} @begin{ImplAdvice} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[Bounded map objects should be implemented without implicit pointers or dynamic allocation.]} @Comment{We omit the @ChgImplAdvice as it is identical to that of the previous clause.} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[The implementation advice for procedure Move to minimize copying does not apply.]} @Comment{We omit the @ChgImplAdvice as it is identical to that of the previous clause.} @end{ImplAdvice} @begin{Extend2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1],ARef=[AI05-0160-1],ARef=[AI05-0184-1]} @ChgAdded{Version=[3],Text=[@Defn{extensions to Ada 2005} The generic package Containers.Bounded_Ordered_Maps is new.]} @end{Extend2005} @LabeledAddedSubclause{Version=[3],Name=[The Generic Package Containers.Bounded_Hashed_Sets]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[The language-defined generic package Containers.Bounded_Hashed_Sets provides a private type Set and a set of operations. It provides the same operations as the package Containers.Hashed_Sets (see @RefSecNum{The Generic Package Containers.Hashed_Sets}), with the difference that the maximum storage is bounded.]} @begin{StaticSem} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[The declaration of the generic library package Containers.Bounded_Hashed_Sets has the same contents and semantics as Containers.Hashed_Sets except:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The @nt{pragma} Preelaborate is replaced with @nt{pragma} Pure.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[The type Set is declared with discriminants that specify both the capacity (number of elements) and modulus (number of distinct hash values) of the hash table as follows:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[ @key[type] Set (Capacity : Count_Type; Modulus : Hash_Type) @key[is tagged private];]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The type Set needs finalization if and only if type Key_Type or type Element_Type needs finalization.]} @begin{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[The type Set cannot depend on package Ada.Finalization unless the element or key type depends on that package. The objects returned from the Iterator and Reference functions probably do depend on package Ada.Finalization. Restricted environments may need to avoid use of those functions and their associated types.]} @end{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[The description of Reserve_Capacity is replaced with:]} @begin{Indent} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],NoPrefix=[T],Text=[If the specified Capacity is larger than the capacity of Container, then Reserve_Capacity propagates Capacity_Error. Otherwise, the operation has no effect.]} @end{Indent} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[An additional operation is added immediately following Reserve_Capacity:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[ @key[function] @AdaSubDefn{Default_Modulus} (Capacity : Count_Type) @key[return] Hash_Type;]} @end{Example} @begin{Indent} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[Default_Modulus returns an implementation-defined value for the number of distinct hash values to be used for the given capacity (maximum number of elements).]} @end{Indent} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[The function Copy is replaced with:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[ @key[function] @AdaSubDefn{Copy} (Source : Set; Capacity : Count_Type := 0; Modulus : Hash_Type := 0) @key[return] Set;]} @end{Example} @begin{Indent} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0264-1]} @ChgAdded{Version=[3],Noprefix=[T],Text=[Returns a set whose elements are initialized from the values in Source. If Capacity is 0, then the set capacity is the length of Source; if Capacity is equal to or greater than the length of Source, the set capacity is the value of the Capacity parameter; otherwise, the operation propagates Capacity_Error. If the Modulus argument is 0, then the set modulus is the value returned by a call to Default_Modulus with the set capacity as its argument; otherwise, the set modulus is the value of the Modulus parameter.]} @end{Indent} @end{Itemize} @end{StaticSem} @begin{Bounded} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0160-1]} @ChgAdded{Version=[3],Text=[@PDefn2{Term=(bounded error),Sec=(cause)} It is a bounded error to use a bounded set if it was the target of an @nt{assignment_statement} whose source was in the middle of an operation that disallows tampering with elements @Redundant[or cursors]. Either Program_Error is raised, or the operation proceeds as defined.]} @end{Bounded} @begin{ImplReq} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1],ARef=[AI05-0264-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[For each instance of Containers.Hashed_Sets and each instance of Containers.Bounded_Hashed_Sets, if the two instances meet the following conditions, then the output generated by the Set'Output or Set'Write subprograms of either instance shall be readable by the Set'Input or Set'Read of the other instance, respectively:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[the Element_Type parameters of the two instances are statically matching subtypes of the same type; and]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1]} @ChgAdded{Version=[3],Text=[the output generated by Element_Type'Output or Element_Type'Write is readable by Element_Type'Input or Element_Type'Read, respectively (where Element_Type denotes the type of the two actual Element_Type parameters).]} @end{Itemize} @end{ImplReq} @begin{ImplAdvice} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[Bounded set objects should be implemented without implicit pointers or dynamic allocation.]} @ChgImplAdvice{Version=[3],Kind=[Added],Text=[@ChgAdded{Version=[3], Text=[Bounded set objects should be implemented without implicit pointers or dynamic allocation.]}]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[The implementation advice for procedure Move to minimize copying does not apply.]} @ChgImplAdvice{Version=[3],Kind=[Added],Text=[@ChgAdded{Version=[3], Text=[The implementation advice for procedure Move to minimize copying does not apply to bounded sets.]}]} @end{ImplAdvice} @begin{Extend2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1],ARef=[AI05-0160-1],ARef=[AI05-0184-1]} @ChgAdded{Version=[3],Text=[@Defn{extensions to Ada 2005} The generic package Containers.Bounded_Hashed_Sets is new.]} @end{Extend2005} @LabeledAddedSubclause{Version=[3],Name=[The Generic Package Containers.Bounded_Ordered_Sets]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[The language-defined generic package Containers.Bounded_Ordered_Sets provides a private type Set and a set of operations. It provides the same operations as the package Containers.Ordered_Sets (see @RefSecNum{The Generic Package Containers.Ordered_Sets}), with the difference that the maximum storage is bounded.]} @begin{StaticSem} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[The declaration of the generic library package Containers.Bounded_Ordered_Sets has the same contents and semantics as Containers.Ordered_Sets except:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The @nt{pragma} Preelaborate is replaced with @nt{pragma} Pure.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[The type Set is declared with a discriminant that specifies the capacity (maximum number of elements) as follows:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[ @key{type} Set (Capacity : Count_Type) @key[is tagged private];]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The type Set needs finalization if and only if type Element_Type needs finalization.]} @begin{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[The type Set cannot depend on package Ada.Finalization unless the element type depends on that package. The objects returned from the Iterator and Reference functions probably do depend on package Ada.Finalization. Restricted environments may need to avoid use of those functions and their associated types.]} @end{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[If Insert (or Include) adds an element, a check is made that the capacity is not exceeded, and Capacity_Error is raised if this check fails.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[In procedure Assign, if Source length is greater than Target capacity, then Capacity_Error is propagated.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[The function Copy is replaced with:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[ @key[function] @AdaSubDefn{Copy} (Source : Set; Capacity : Count_Type := 0) @key[return] Set;]} @end{Example} @begin{Indent} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[Returns a set whose elements are initialized from the values in Source. If Capacity is 0, then the set capacity is the length of Source; if Capacity is equal to or greater than the length of Source, the set capacity is the specified value; otherwise, the operation propagates Capacity_Error.]} @end{Indent} @end{Itemize} @end{StaticSem} @begin{Bounded} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0160-1]} @ChgAdded{Version=[3],Text=[@PDefn2{Term=(bounded error),Sec=(cause)} It is a bounded error to use a bounded set if it was the target of an @nt{assignment_statement} whose source was in the middle of an operation that disallows tampering with elements @Redundant[or cursors]. Either Program_Error is raised, or the operation proceeds as defined.]} @end{Bounded} @begin{ImplReq} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1],ARef=[AI05-0264-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[For each instance of Containers.Ordered_Sets and each instance of Containers.Bounded_Ordered_Sets, if the two instances meet the following conditions, then the output generated by the Set'Output or Set'Write subprograms of either instance shall be readable by the Set'Input or Set'Read of the other instance, respectively:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[the Element_Type parameters of the two instances are statically matching subtypes of the same type; and]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1]} @ChgAdded{Version=[3],Text=[the output generated by Element_Type'Output or Element_Type'Write is readable by Element_Type'Input or Element_Type'Read, respectively (where Element_Type denotes the type of the two actual Element_Type parameters).]} @end{Itemize} @end{ImplReq} @begin{ImplAdvice} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[Bounded set objects should be implemented without implicit pointers or dynamic allocation.]} @Comment{We omit the @ChgImplAdvice as it is identical to that of the previous clause.} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],Text=[The implementation advice for procedure Move to minimize copying does not apply.]} @Comment{We omit the @ChgImplAdvice as it is identical to that of the previous clause.} @end{ImplAdvice} @begin{Extend2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1],ARef=[AI05-0160-1],ARef=[AI05-0184-1]} @ChgAdded{Version=[3],Text=[@Defn{extensions to Ada 2005} The generic package Containers.Bounded_Ordered_Sets is new.]} @end{Extend2005} @LabeledAddedSubclause{Version=[3],Name=[The Generic Package Containers.Bounded_Multiway_Trees]} @begin{Intro} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[The language-defined generic package Containers.Bounded_Multiway_Trees provides a private type Tree and a set of operations. It provides the same operations as the package Containers.Multiway_Trees (see @RefSecNum{The Generic Package Containers.Multiway_Trees}), with the difference that the maximum storage is bounded.]} @end{Intro} @begin{StaticSem} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[The declaration of the generic library package Containers.Bounded_Multiway_Trees has the same contents and semantics as Containers.Multiway_Trees except:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The @nt{pragma} Preelaborate is replaced with @nt{pragma} Pure.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[The type Tree is declared with a discriminant that specifies the capacity (maximum number of elements) as follows:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[ @key{type} Tree (Capacity : Count_Type) @key[is tagged private];]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The type Tree needs finalization if and only if type Element_Type needs finalization.]} @begin{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[The type Tree cannot depend on package Ada.Finalization unless the element type depends on that package. The objects returned from the Iterator and Reference functions probably do depend on package Ada.Finalization. Restricted environments may need to avoid use of those functions and their associated types.]} @end{ImplNote} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The allocation of internal storage includes a check that the capacity is not exceeded, and Capacity_Error is raised if this check fails.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[In procedure Assign, if Source length is greater than Target capacity, then Capacity_Error is propagated.]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Type=[Leading],Text=[Function Copy is declared as follows:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[ @key{function} Copy (Source : Tree; Capacity : Count_Type := 0) @key{return} List;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Noprefix=[T],Text=[If Capacity is 0, then the tree capacity is the count of Source; if Capacity is equal to or greater than Source.Count, the tree capacity equals the value of the Capacity parameter; otherwise, the operation propagates Capacity_Error.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[In the five-parameter procedure Splice_Subtree, if Source is not the same object as Target, and if the sum of Target.Count and Subtree_Node_Count (Position) is greater than Target.Capacity, then Splice_Subtree propagates Capacity_Error.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[In the five-parameter procedure Splice_Children, if Source is not the same object as Target, and if the sum of Target.Count and Subtree_Node_Count (Source_Parent)-1 is greater than Target.Capacity, then Splice_Children propagates Capacity_Error.]} @end{Itemize} @end{StaticSem} @begin{Bounded} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[@PDefn2{Term=(bounded error),Sec=(cause)} It is a bounded error to use a bounded tree if it was the target of an @nt{assignment_statement} whose source was in the middle of an operation that disallows tampering with elements @Redundant[or cursors]. Either Program_Error is raised, or the operation proceeds as defined.]} @end{Bounded} @begin{ImplReq} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1],ARef=[AI05-0264-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[For each instance of Containers.Multiway_Trees and each instance of Containers.Bounded_Multiway_Trees, if the two instances meet the following conditions, then the output generated by the Tree'Output or Tree'Write subprograms of either instance shall be readable by the Tree'Input or Tree'Read of the other instance, respectively:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[the Element_Type parameters of the two instances are statically matching subtypes of the same type; and]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0184-1]} @ChgAdded{Version=[3],Text=[the output generated by Element_Type'Output or Element_Type'Write is readable by Element_Type'Input or Element_Type'Read, respectively (where Element_Type denotes the type of the two actual Element_Type parameters).]} @end{Itemize} @end{ImplReq} @begin{ImplAdvice} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[Bounded tree objects should be implemented without implicit pointers or dynamic allocation.]} @ChgImplAdvice{Version=[3],Kind=[Added],Text=[@ChgAdded{Version=[3], Text=[Bounded tree objects should be implemented without implicit pointers or dynamic allocation.]}]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]} @ChgAdded{Version=[3],Text=[The implementation advice for procedure Move to minimize copying does not apply.]} @ChgImplAdvice{Version=[3],Kind=[Added],Text=[@ChgAdded{Version=[3], Text=[The implementation advice for procedure Move to minimize copying does not apply to bounded trees.]}]} @end{ImplAdvice} @begin{Extend2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0184-1]} @ChgAdded{Version=[3],Text=[@Defn{extensions to Ada 2005} The generic package Containers.Bounded_Multiway_Trees is new.]} @end{Extend2005} @LabeledAddedSubclause{Version=[2],Name=[Array Sorting]} @begin{Intro} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgRef{Version=[3],Kind=[Revised],ARef=[AI05-0001-1]} @ChgAdded{Version=[2],Text=[The language-defined generic procedures Containers.@!Generic_@!Array_Sort@Chg{Version=[3],New=[,],Old=[ and]} Containers.@!Generic_@!Constrained_@!Array_Sort@Chg{Version=[3],New=[, and Containers.@!Generic_Sort],Old=[]} provide sorting on arbitrary array types.]} @end{Intro} @begin{StaticSem} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgAdded{Version=[2],KeepNext=[T],Type=[Leading],Text=[The generic library procedure Containers.Generic_Array_Sort has the following declaration:]} @begin{Example} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[@key{generic} @key{type} Index_Type @key{is} (<>); @key{type} Element_Type @key{is private}; @key{type} Array_Type @key{is array} (Index_Type @key{range} <>) @key{of} Element_Type; @key{with function} "<" (Left, Right : Element_Type) @key{return} Boolean @key{is} <>; @key{procedure} Ada.Containers.Generic_Array_Sort (Container : @key{in out} Array_Type);@SubChildUnit{Parent=[Ada.Containers],Child=[Generic_Array_Sort]} @key{pragma} Pure(Ada.Containers.Generic_Array_Sort);]} @end{Example} @begin{DescribeCode} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[Reorders the elements of Container such that the elements are sorted smallest first as determined by the generic formal "<" operator provided. Any exception raised during evaluation of "<" is propagated.]} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgRef{Version=[3],Kind=[Revised],ARef=[AI05-0044-1]} @ChgAdded{Version=[2],Text=[The actual function for the generic formal function "<" of Generic_Array_Sort is expected to return the same value each time it is called with a particular pair of element values. It should define a strict @Chg{Version=[3],New=[weak ],Old=[]}ordering relationship@Chg{Version=[3], New=[ (see @RefSecNum{Containers})],Old=[, that is, be irreflexive, asymmetric, and transitive]}; it should not modify Container. If the actual for "<" behaves in some other manner, the behavior of the instance of Generic_Array_Sort is unspecified. How many times Generic_Array_Sort calls "<" is unspecified.@PDefn{unspecified}]} @begin{Ramification} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[This implies swapping the elements, usually including an intermediate copy. This of course means that the elements will be copied. Since the elements are nonlimited, this usually will not be a problem. Note that there is Implementation Advice below that the implementation should use a sort that minimizes copying of elements.]} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[The sort is not required to be stable (and the fast algorithm required will not be stable). If a stable sort is needed, the user can include the original location of the element as an extra "sort key". We considered requiring the implementation to do that, but it is mostly extra overhead -- usually there is something already in the element that provides the needed stability.]} @end{Ramification} @end{DescribeCode} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgAdded{Version=[2],KeepNext=[T],Type=[Leading],Text=[The generic library procedure Containers.@!Generic_@!Constrained_@!Array_Sort has the following declaration:]} @begin{Example} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[@key{generic} @key{type} Index_Type @key{is} (<>); @key{type} Element_Type @key{is private}; @key{type} Array_Type @key{is array} (Index_Type) @key{of} Element_Type; @key{with function} "<" (Left, Right : Element_Type) @key{return} Boolean @key{is} <>; @key{procedure} Ada.Containers.Generic_Constrained_Array_Sort@SubChildUnit{Parent=[Ada.Containers],Child=[Generic_Constrained_Array_Sort]} (Container : @key{in out} Array_Type); @key{pragma} Pure(Ada.Containers.Generic_Constrained_Array_Sort);]} @end{Example} @begin{DescribeCode} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[Reorders the elements of Container such that the elements are sorted smallest first as determined by the generic formal "<" operator provided. Any exception raised during evaluation of "<" is propagated.]} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgRef{Version=[3],Kind=[Revised],ARef=[AI05-0044-1]} @ChgAdded{Version=[2],Text=[The actual function for the generic formal function "<" of Generic_Constrained_Array_Sort is expected to return the same value each time it is called with a particular pair of element values. It should define a strict @Chg{Version=[3],New=[weak ],Old=[]}ordering relationship@Chg{Version=[3], New=[ (see @RefSecNum{Containers})],Old=[, that is, be irreflexive, asymmetric, and transitive]}; it should not modify Container. If the actual for "<" behaves in some other manner, the behavior of the instance of Generic_Constrained_Array_Sort is unspecified. How many times Generic_Constrained_Array_Sort calls "<" is unspecified.@PDefn{unspecified}]} @end{DescribeCode} @ChgRef{Version=[3],Kind=[Added],ARef=[AI05-0001-1]} @ChgAdded{Version=[3],KeepNext=[T],Type=[Leading],Text=[The generic library procedure Containers.@!Generic_@!Sort has the following declaration:]} @begin{Example} @ChgRef{Version=[3],Kind=[Added]} @ChgAdded{Version=[3],Text=[@key{generic} @key{type} Index_Type @key{is} (<>); @key{with function} Before (Left, Right : Index_Type) @key{return} Boolean; @key{with procedure} Swap (Left, Right : Index_Type); @key{procedure} Ada.Containers.Generic_Sort@SubChildUnit{Parent=[Ada.Containers],Child=[Generic_Sort]} (First, Last : Index_Type'Base); @key{pragma} Pure(Ada.Containers.Generic_Sort);]} @end{Example} @begin{DescribeCode} @ChgRef{Version=[3],Kind=[Added],ARef=[AI05-0001-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[Reorders the elements of an indexable structure, over the range First .. Last, such that the elements are sorted in the ordering determined by the generic formal function Before; Before should return True if Left is to be sorted before Right. The generic formal Before compares the elements having the given indices, and the generic formal Swap exchanges the values of the indicated elements. Any exception raised during evaluation of Before or Swap is propagated.]} @ChgRef{Version=[3],Kind=[Added]} @ChgAdded{Version=[3],Text=[The actual function for the generic formal function Before of Generic_Sort is expected to return the same value each time it is called with index values that identify a particular pair of element values. It should define a strict weak ordering relationship (see @RefSecNum{Containers}); it should not modify the elements. The actual function for the generic formal Swap should exchange the values of the indicated elements. If the actual for either Before or Swap behaves in some other manner, the behavior of Generic_Sort is unspecified. How many times the Generic_Sort calls Before or Swap is unspecified.@PDefn{unspecified}]} @end{DescribeCode} @end{StaticSem} @begin{ImplAdvice} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgAdded{Version=[2],Text=[ The worst-case time complexity of a call on an instance of Containers.Generic_Array_Sort or Containers.Generic_Constrained_Array_Sort should be @i{O}(@i**2) or better, and the average time complexity should be better than @i{O}(@i**2), where @i is the length of the Container parameter.]} @ChgImplAdvice{Version=[2],Kind=[AddedNormal],Text=[@ChgAdded{Version=[2], Text=[Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort should have an average time complexity better than @i{O}(@i{N}**2) and worst case no worse than @i{O}(@i{N}**2).]}]} @begin{Discussion} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[In other words, we're requiring the use of a sorting algorithm better than @i{O}(@i**2), such as Quicksort. No bubble sorts allowed!]} @end{Discussion} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgAdded{Version=[2],Text=[ Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort should minimize copying of elements.]} @ChgImplAdvice{Version=[2],Kind=[AddedNormal],Text=[@ChgAdded{Version=[2], Text=[Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort should minimize copying of elements.]}]} @begin{Honest} @ChgRef{Version=[2],Kind=[AddedNormal]} @ChgAdded{Version=[2],Text=[We do not mean @lquotes@;absolutely minimize@rquotes@; here; we're not intending to require a single copy for each element. Rather, we want to suggest that the sorting algorithm chosen is one that does not copy items unnecessarily. Bubble sort would not meet this advice, for instance.]} @end{Honest} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[ The worst-case time complexity of a call on an instance of Containers.Generic_Sort should be @i{O}(@i**2) or better, and the average time complexity should be better than @i{O}(@i**2), where @i is the difference between the Last and First parameters plus 1.]} @ChgImplAdvice{Version=[3],Kind=[Added],Text=[@ChgAdded{Version=[3], Text=[Containers.Generic_Sort should have an average time complexity better than @i{O}(@i{N}**2) and worst case no worse than @i{O}(@i{N}**2).]}]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[Containers.Generic_Sort should minimize should minimize to the generic formal Swap.]} @ChgImplAdvice{Version=[3],Kind=[Added],Text=[@ChgAdded{Version=[3], Text=[Containers.Generic_Sort should minimize to the generic formal Swap.]}]} @end{ImplAdvice} @begin{Extend95} @ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]} @ChgAdded{Version=[2],Text=[@Defn{extensions to Ada 95} The generic procedures Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort are new.]} @end{Extend95} @begin{Extend2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0001-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[@Defn{extensions to Ada 2005} The generic procedure Containers.Generic_Sort is new.]} @end{Extend2005} @begin{DiffWord2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0044-1]} @ChgAdded{Version=[3],Text=[@b Redefined "<" actuals to require a strict weak ordering; the old definition allowed indeterminant comparisons that would not have worked in a sort.]} @end{DiffWord2005} @LabeledAddedSubclause{Version=[3],Name=[The Generic Package Containers.Synchronized_Queue_Interfaces]} @begin{Intro} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Text=[The language-defined generic package Containers.Synchronized_Queue_Interfaces provides interface type Queue, and a set of operations for that type. Interface Queue specifies a first-in, first-out queue.]} @end{Intro} @begin{StaticSem} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],KeepNext=[T],Type=[Leading],Text=[The generic library package Containers.Synchronized_Queue_Interfaces has the following declaration:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key[generic] @key[type] Element_Type @key[is private]; @key[package] Ada.Containers.Synchronized_Queue_Interfaces @key[is]@ChildUnit{Parent=[Ada.Containers],Child=[Synchronized_Queue_Interfaces]} @key[pragma] Pure(Synchronized_Queue_Interfaces);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[type] @AdaTypeDefn{Queue} @key[is synchronized interface];]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[procedure] @AdaSubDefn{Enqueue} (Container : @key[in out] Queue; New_Item : @key[in] Element_Type) @key[is abstract] @key[with] Synchronization => By_Entry;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[procedure] @AdaSubDefn{Dequeue} (Container : @key[in out] Queue; Element : @key[out] Element_Type) @key[is abstract] @key[with] Synchronization => By_Entry;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[function] @AdaSubDefn{Current_Use} (Container : Queue) @key[return] Count_Type @key[is abstract]; @key[function] @AdaSubDefn{Peak_Use} (Container : Queue) @key[return] Count_Type @key[is abstract];]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key{end} Ada.Containers.Synchronized_Queue_Interfaces;]} @end{Example} @begin{DescribeCode} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[procedure] Enqueue (Container : @key[in out] Queue; New_Item : @key[in] Element_Type) @key[is abstract];]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1],ARef=[AI05-0264-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[A queue type that implements this interface may have a bounded @i@Defn2{Term=[capacity],Sec=[of a queue]}. If the queue object has a bounded capacity, and the number of existing elements equals the capacity, then Enqueue blocks until storage becomes available; otherwise, Enqueue does not block. In any case, it then copies New_Item onto the queue.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[procedure] Dequeue (Container : @key[in out] Queue; Element : @key[out] Element_Type) @key[is abstract];]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1],ARef=[AI05-0251-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[If the queue is empty, then Dequeue blocks until an item becomes available. In any case, it then assigns the element at the head of the queue to Element, and removes it from the queue.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[function] Current_Use (Container : Queue) @key[return] Count_Type @key[is abstract];]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Returns the number of elements currently in the queue.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],KeepNext=[T],Text=[@key[function] Peak_Use (Container : Queue) @key[return] Count_Type @key[is abstract];]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Type=[Trailing],Text=[Returns the maximum number of elements that have been in the queue at any one time.]} @end{DescribeCode} @end{StaticSem} @begin{Notes} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0251-1]} @ChgAdded{Version=[3],Text=[Unlike other language-defined containers, there are no queues whose element types are indefinite. Elements of an indefinite type can be handled by defining the element of the queue to be a holder container (see @RefSecNum{The Generic Package Containers.Indefinite_Holders}) of the indefinite type, or to be an explicit access type that designates the indefinite type.]} @begin{Reason} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[There are no indefinite queues as a useful definition for Dequeue is not possible. Dequeue cannot be a function as Ada does not have entries that are functions (thus conditional and timed calls would not be possible) and moreover protected functions do not allow modifying the queue object (thus it doesn't work even if we decided we didn't care about conditional and timed calls). If Dequeue is an entry, then the dequeued object would have to be an @key[out] parameter and that would require the queue client to guess the tag and constraints of the value that will be dequeued (otherwise Constraint_Error would be raised), and that is rarely going to be possible.]} @end{Reason} @end{Notes} @begin{Extend2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1],ARef=[AI05-0251-1]} @ChgAdded{Version=[3],Text=[@Defn{extensions to Ada 2005} The generic package Containers.Synchronized_Queue_Interfaces is new.]} @end{Extend2005} @LabeledAddedSubclause{Version=[3],Name=[The Generic Package Containers.Unbounded_Synchronized_Queues]} @begin{StaticSem} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Text=[The language-defined generic package Containers.Unbounded_Synchronized_Queues provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key[with] System; @key[with] Ada.Containers.Synchronized_Queue_Interfaces; @key[generic] @key[with package] Queue_Interfaces @key[is new] Ada.Containers.Synchronized_Queue_Interfaces (<>); Default_Ceiling: System.Any_Priority := System.Priority'Last; @key[package] Ada.Containers.Unbounded_Synchronized_Queues is@ChildUnit{Parent=[Ada.Containers],Child=[Unbounded_Synchronized_Queues]} @key[pragma] Preelaborate(Unbounded_Synchronized_Queues);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[package] Implementation @key[is] ... -- @RI[not specified by the language] @key[end] Implementation;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[protected type] @AdaTypeDefn{Queue} (Ceiling: System.Any_Priority := Default_Ceiling) @key[with] Priority => Ceiling @key[is] @key[new] Queue_Interfaces.Queue @key[with]]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[overriding] @key[entry] @AdaSubDefn{Enqueue} (New_Item: @key[in] Queue_Interfaces.Element_Type); @key[overriding] @key[entry] @AdaSubDefn{Dequeue} (Element: @key[out] Queue_Interfaces.Element_Type);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[overriding] @key[function] @AdaSubDefn{Current_Use} @key[return] Count_Type; @key[overriding] @key[function] @AdaSubDefn{Peak_Use} @key[return] Count_Type;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[private] ... -- @RI[not specified by the language] @key[end] Queue;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key{private}]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ ... -- @RI[not specified by the language]]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key{end} Ada.Containers.Unbounded_Synchronized_Queues;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Text=[The type Queue is used to represent task-safe queues.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Text=[The capacity for instances of type Queue is unbounded.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Enqueue never blocks; if more storage is needed for a new element, it is allocated dynamically. We don't need to explicitly specify that Queue needs finalization, because it is visibly protected.]} @end{Ramification} @begin{Discussion} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Nested package Implementation can be used to declare the types needed to implement the protected type Queue. This nested package is necessary as types cannot be declared in the private part of a protected type, and the types have to be declared within the generic unit in order to depend on the types imported with package Queue_Interfaces. Clients should never depend on the contents of nested package Implementation.]} @end{Discussion} @end{StaticSem} @begin{Extend2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Text=[@Defn{extensions to Ada 2005} The generic package Containers.Unbounded_Synchronized_Queues is new.]} @end{Extend2005} @LabeledAddedSubclause{Version=[3],Name=[The Generic Package Containers.Bounded_Synchronized_Queues]} @begin{StaticSem} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Text=[The language-defined generic package Containers.Bounded_Synchronized_Queues provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key[with] System; @key[with] Ada.Containers.Synchronized_Queue_Interfaces; @key[generic] @key[with package] Queue_Interfaces @key[is new] Ada.Containers.Synchronized_Queue_Interfaces (<>); Default_Capacity : Count_Type; Default_Ceiling: System.Any_Priority := System.Priority'Last; @key[package] Ada.Containers.Bounded_Synchronized_Queues is@ChildUnit{Parent=[Ada.Containers],Child=[Bounded_Synchronized_Queues]} @key[pragma] Preelaborate(Bounded_Synchronized_Queues);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[package] Implementation @key[is] ... -- @RI[not specified by the language] @key[end] Implementation;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[protected type] @AdaTypeDefn{Queue} (Capacity : Count_Type := Default_Capacity; Ceiling: System.Any_Priority := Default_Ceiling) @key[with] Priority => Ceiling @key[is] @key[new] Queue_Interfaces.Queue @key[with]]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[overriding] @key[entry] @AdaSubDefn{Enqueue} (New_Item: @key[in] Queue_Interfaces.Element_Type); @key[overriding] @key[entry] @AdaSubDefn{Dequeue} (Element: @key[out] Queue_Interfaces.Element_Type);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[overriding] @key[function] @AdaSubDefn{Current_Use} @key[return] Count_Type; @key[overriding] @key[function] @AdaSubDefn{Peak_Use} @key[return] Count_Type;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[private] ... -- @RI[not specified by the language] @key[end] Queue;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key{private}]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ ... -- @RI[not specified by the language]]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key{end} Ada.Containers.Bounded_Synchronized_Queues;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Keepnext=[T],Type=[Leading],Text=[The semantics are the same as for Unbounded_Synchronized_Queues, except:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The capacity for instances of type Queue is bounded and specified by the discriminant Capacity.]} @end{Itemize} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Since this type has a bounded capacity, Enqueue might block if the queue is full.]} @end{Ramification} @end{StaticSem} @begin{ImplAdvice} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Text=[Bounded queue objects should be implemented without implicit pointers or dynamic allocation.]} @ChgImplAdvice{Version=[3],Kind=[Added],Text=[@ChgAdded{Version=[3], Text=[Bounded queue objects should be implemented without implicit pointers or dynamic allocation.]}]} @end{ImplAdvice} @begin{Extend2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Text=[@Defn{extensions to Ada 2005} The generic package Containers.Bounded_Synchronized_Queues is new.]} @end{Extend2005} @LabeledAddedSubclause{Version=[3],Name=[The Generic Package Containers.Unbounded_Priority_Queues]} @begin{StaticSem} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Text=[The language-defined generic package Containers.Unbounded_Priority_Queues provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key[with] System; @key[with] Ada.Containers.Synchronized_Queue_Interfaces; @key[generic] @key[with package] Queue_Interfaces @key[is new] Ada.Containers.Synchronized_Queue_Interfaces (<>); @key[type] Queue_Priority @key[is private]; @key[with] @key[function] Get_Priority (Element: Queue_Interfaces.Element_Type) @key[return] Queue_Priority is <>; @key[with] @key[function] Before (Left, Right : Queue_Priority) @key[return] Boolean is <>; Default_Ceiling: System.Any_Priority := System.Priority'Last; @key[package] Ada.Containers.Unbounded_Priority_Queues @key[is]@ChildUnit{Parent=[Ada.Containers],Child=[Unbounded_Priority_Queues]} @key[pragma] Preelaborate(Unbounded_Priority_Queues);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[package] Implementation @key[is] ... -- @RI[not specified by the language] @key[end] Implementation;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[protected type] @AdaTypeDefn{Queue} (Ceiling: System.Any_Priority := Default_Ceiling) @key[with] Priority => Ceiling @key[is] @key[new] Queue_Interfaces.Queue @key[with]]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[overriding] @key[entry] @AdaSubDefn{Enqueue} (New_Item: @key[in] Queue_Interfaces.Element_Type); @key[overriding] @key[entry] @AdaSubDefn{Dequeue} (Element: @key[out] Queue_Interfaces.Element_Type);]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1],ARef=[AI05-0251-1]} @ChgAdded{Version=[3],Text=[ @key[not overriding] @key[procedure] @AdaSubDefn{Dequeue_Only_High_Priority} (At_Least : @key[in] Queue_Priority; Element : @key[in out] Queue_Interfaces.Element_Type; Success : @key[out] Boolean);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[overriding] @key[function] @AdaSubDefn{Current_Use} @key[return] Count_Type; @key[overriding] @key[function] @AdaSubDefn{Peak_Use} @key[return] Count_Type;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[private] ... -- @RI[not specified by the language] @key[end] Queue;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key{private}]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ ... -- @RI[not specified by the language]]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key{end} Ada.Containers.Unbounded_Priority_Queues;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Text=[The type Queue is used to represent task-safe priority queues.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Text=[The capacity for instances of type Queue is unbounded.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Text=[Two elements @i and @i are equivalent if Before(Get_Priority(@i), Get_Priority(@i)) and Before(Get_Priority(@i), Get_Priority(@i)) both return False.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1],ARef=[AI05-0248-1]} @ChgAdded{Version=[3],Text=[The actual functions for Get_Priority and Before are expected to return the same value each time they are called with the same actuals, and should not modify their actuals. Before should define a strict weak ordering relationship (see @RefSecNum{Containers}). If the actual functions behave in some other manner, the behavior of Unbounded_Priority_Queues is unspecified.]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Text=[Enqueue inserts an item according to the order specified by the Before function on the result of Get_Priority on the elements; Before should return True if Left is to be inserted before Right. If the queue already contains elements equivalent to New_Item, then it is inserted after the existing equivalent elements.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Enqueue never blocks; if more storage is needed for a new element, it is allocated dynamically. We don't need to explicitly specify that Queue needs finalization, because it is visibly protected.]} @end{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1],ARef=[AI05-0251-1]} @ChgAdded{Version=[3],Text=[For a call on Dequeue_Only_High_Priority, if the head of the non-empty queue is @i, and the function Before(At_Least, Get_Priority(@i)) returns False, then @i is assigned to Element and then removed from the queue, and Success is set to True; otherwise Success is set to False and Element is unchanged.]} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0251-1]} @ChgAdded{Version=[3],Text=[Unlike Dequeue, Dequeue_Only_High_Priority is not blocking; it always returns immediately.]} @end{Ramification} @begin{Reason} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0251-1]} @ChgAdded{Version=[3],Text=[The use of Before is "backwards" so that it acts like ">=" (it is defined similarly to ">"); thus we dequeue only when it is False.]} @end{Reason} @end{StaticSem} @begin{Extend2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1],ARef=[AI05-0251-1]} @ChgAdded{Version=[3],Text=[@Defn{extensions to Ada 2005} The generic package Containers.Unbounded_Priority_Queues is new.]} @end{Extend2005} @LabeledAddedSubclause{Version=[3],Name=[The Generic Package Containers.Bounded_Priority_Queues]} @begin{StaticSem} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Text=[The language-defined generic package Containers.Bounded_Priority_Queues provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key[with] System; @key[with] Ada.Containers.Synchronized_Queue_Interfaces; @key[generic] @key[with package] Queue_Interfaces @key[is new] Ada.Containers.Synchronized_Queue_Interfaces (<>); @key[type] Queue_Priority @key[is private]; @key[with function] Get_Priority (Element: Queue_Interfaces.Element_Type) @key[return] Queue_Priority is <>; @key[with function] Before (Left, Right : Queue_Priority) @key[return] Boolean is <>; Default_Capacity : Count_Type; Default_Ceiling: System.Any_Priority := System.Priority'Last; @key[package] Ada.Containers.Bounded_Priority_Queues @key[is]@ChildUnit{Parent=[Ada.Containers],Child=[Bounded_Priority_Queues]} @key[pragma] Preelaborate(Bounded_Priority_Queues);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[package] Implementation @key[is] ... -- @RI[not specified by the language] @key[end] Implementation;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[protected type] @AdaTypeDefn{Queue} (Capacity : Count_Type := Default_Capacity; Ceiling: System.Any_Priority := Default_Ceiling) @key[with] Priority => Ceiling @key[is] @key[new] Queue_Interfaces.Queue @key[with]]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[overriding] @key[entry] @AdaSubDefn{Enqueue} (New_Item: @key[in] Queue_Interfaces.Element_Type); @key[overriding] @key[entry] @AdaSubDefn{Dequeue} (Element: @key[out] Queue_Interfaces.Element_Type);]} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1],ARef=[AI05-0251-1]} @ChgAdded{Version=[3],Text=[ @key[not overriding] @key[procedure] @AdaSubDefn{Dequeue_Only_High_Priority} (At_Least : @key[in] Queue_Priority; Element : @key[in out] Queue_Interfaces.Element_Type; Success : @key[out] Boolean);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[overriding] @key[function] @AdaSubDefn{Current_Use} @key[return] Count_Type; @key[overriding] @key[function] @AdaSubDefn{Peak_Use} @key[return] Count_Type;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[private] ... -- @RI[not specified by the language] @key[end] Queue;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key{private}]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ ... -- @RI[not specified by the language]]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key{end} Ada.Containers.Bounded_Priority_Queues;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Keepnext=[T],Type=[Leading],Text=[The semantics are the same as for Unbounded_Priority_Queues, except:]} @begin{Itemize} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[The capacity for instances of type Queue is bounded and specified by the discriminant Capacity.]} @end{Itemize} @begin{Ramification} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[Since this type has a bounded capacity, Enqueue might block if the queue is full.]} @end{Ramification} @end{StaticSem} @begin{ImplAdvice} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1]} @ChgAdded{Version=[3],Text=[Bounded priority queue objects should be implemented without implicit pointers or dynamic allocation.]} @ChgImplAdvice{Version=[3],Kind=[Added],Text=[@ChgAdded{Version=[3], Text=[Bounded priority queue objects should be implemented without implicit pointers or dynamic allocation.]}]} @end{ImplAdvice} @begin{Extend2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0159-1],ARef=[AI05-0251-1]} @ChgAdded{Version=[3],Text=[@Defn{extensions to Ada 2005} The generic package Containers.Bounded_Priority_Queues is new.]} @end{Extend2005} @LabeledAddedSubclause{Version=[3],Name=[Example of Container Use]} @begin{Examples} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[The following example is an implementation of Dijkstra's shortest path algorithm in a directed graph with positive distances. The graph is represented by a map from nodes to sets of edges.]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key[with] Ada.Containers.Vectors; @key[with] Ada.Containers.Doubly_Linked_Lists; @key[use] Ada.Containers; @key[generic] @key[type] Node @key[is range] <>; @key[package] Shortest_Paths @key[is] @key[type] Distance @key[is new] Float @key[range] 0.0 .. Float'Last; @key[type] Edge @key[is record] To, From : Node; Length : Distance; @key[end record];]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[package] Node_Maps @key[is new] Vectors (Node, Node); -- @Examcom{The algorithm builds a map to indicate the node used to reach a given} -- @Examcom{node in the shortest distance.}]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[package] Adjacency_Lists @key[is new] Doubly_Linked_Lists (Edge); @key[use] Adjacency_Lists;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[package] Graphs @key[is new] Vectors (Node, Adjacency_Lists.List);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[package] Paths @key[is new] Doubly_Linked_Lists (Node);]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[function] Shortest_Path (G : Graphs.Vector; Source : Node; Target : Node) @key[return] Paths.List @key[with] Pre => G (Source) /= Adjacency_Lists.Empty_List;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key[end] Shortest_Paths;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key[package body] Shortest_Paths @key[is] @key[function] Shortest_Path (G : Graphs.Vector; Source : Node; Target : Node) @key[return] Paths.List @key[is] @key[use] Adjacency_Lists, Node_Maps, Paths, Graphs; Reached : @key[array] (Node) @key[of] Boolean := (@key[others] => False); -- @ExamCom{The set of nodes whose shortest distance to the source is known.}]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ Reached_From : @key[array] (Node) @key[of] Node; So_Far : @key[array] (Node) @key[of] Distance := (@key[others] => Distance'Last); The_Path : Paths.List := Paths.Empty_List; Nearest_Distance : Distance; Next : Node; @key[begin] Reached (Source) := True; So_Far (Source) := 0.0;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[while not] Reached (Target) @key[loop] Nearest_Distance := Distance'Last;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ -- @Examcom{Find closest node not reached yet, by iterating over all nodes.} -- @Examcom{A more efficient algorithm uses a priority queue for this step.}]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ Next := Source; @key[for] N @key[in] Node'First .. Node'Last @key[loop] @key[if not] Reached (N) @key[and then] So_Far (N) < Nearest_Distance @key[then] Next := N; Nearest_Distance := So_Far (N); @key[end if]; @key[end loop];]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[if] Next = Source @key[then] -- @Examcom{No next node found, graph is not connected} @key[return] Paths.Empty_List;]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[else] Reached (Next) := True; @key[end if];]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ -- @ExamCom{Update minimum distance to newly reachable nodes.}]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[for] E @key[of] G (Next) @key[loop] @key[if not] Reached (E.To) @key[then] Nearest_Distance := Distance'Min (So_Far (E.To) + So_Far (Next), So_Far (E.To));]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[if] Nearest_Distance < So_Far (E.To) @key[then] Reached_From (E.To) := Next; So_Far (E.To) := Nearest_Distance; @key[end if]; @key[end if]; @key[end loop]; @key[end loop];]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ -- @ExamCom{Rebuild path from target to source.}]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[declare] N : Node := Target; @key[begin] @key[while] N /= Source @key[loop] N := Reached_From (N); Prepend (The_Path, N); @key[end loop]; @key[end];]} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[ @key[return] The_Path; @key[end]; @key[end] Shortest_Paths;]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[Note that the effect of the Constant_Indexing aspect (on type Vector) and the Implicit_Dereference aspect (on type Reference_Type) is that]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[G (Next)]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[is a convenient short hand for]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[G.Constant_Reference (Next).Element.@key[all]]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[Similarly, the effect of the loop:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key[for] E @key[of] G (Next) @key[loop] @key[if not] Reached (E.To) @key[then] ... @key[end if]; @key[end loop];]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[is the same as:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key[for] C @key[in] G (Next).Iterate @key[loop] @key[declare] E : Edge @key[renames] G (Next)(C).@key[all]; @key[begin] @key[if not] Reached (E.To) @key[then] ... @key[end if]; @key[end]; @key[end loop];]} @end{Example} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Type=[Leading],Text=[which is the same as:]} @begin{Example} @ChgRef{Version=[3],Kind=[AddedNormal]} @ChgAdded{Version=[3],Text=[@key[declare] L : Adjacency_Lists.List @key[renames] G (Next); C : Adjacency_Lists.Cursor := L.First; @key[begin] @key[while] Has_Element (C) @key[loop] @key[declare] E : Edge @key[renames] L(C).@key[all]; @key[begin] @key[if not] Reached (E.To) @key[then] ... @key[end if]; @key[end]; C := L.Next (C); @key[end loop]; @key[end];]} @end{Example} @end{Examples} @begin{DiffWord2005} @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]} @ChgAdded{Version=[3],Text=[This example of container use is new.]} @end{DiffWord2005}