CVS difference for ai05s/ai05-0159-1.txt
--- ai05s/ai05-0159-1.txt 2009/06/09 05:27:09 1.2
+++ ai05s/ai05-0159-1.txt 2009/10/17 00:28:07 1.3
@@ -1,4 +1,4 @@
-!standard A.18.24 09-06-02 AI05-0159-1/01
+!standard A.18.24 09-10-15 AI05-0159-1/02
!class Amendment 05-10-24
!status work item 06-03-15
!status received 05-10-02
@@ -57,7 +57,20 @@
end Ada.Containers.Queues;
+[ARG]
+
+Any interest in a Peek?
+
+Conditional deque:
+
+ procedure Dequeue
+ (Container : in out Queue;
+ Element : out Element_Type;
+ Available : out Boolean) is abstract;
+[END ARG]
+
+
procedure Enqueue
(Container : in out Queue;
New_Item : Element_Type) is abstract;
@@ -70,7 +83,7 @@
Element : out Element_Type) is abstract;
Removes the element at the head of the queue, and returns a copy of
-the element. Is Is_Empty is True, then Dequeue waits on the entry for
+the element. Is Is_Empty is True, then Dequeue waits on the entry for
an item to become available.
function Is_Empty (Container : Queue) return Boolean is abstract;
@@ -105,9 +118,10 @@
end Ada.Containers.Unbounded_Queues;
-[Editor's comment: We need some wording here to describe how these work!
-In particular, Is_Full is never true for one of these queues, right?]
+Is_Full always returns False, because storage for new items is
+allocated dynamically.
+
A.18.25 Containers.Bounded_Queues
Static Semantics
@@ -131,61 +145,61 @@
-- not specified by the language
end Ada.Containers.Bounded_Queues;
+
+The type Queue needs finalization if and only type
+Element_Type needs finalization.
+
+[ARG]
+Is the above what we want?
+[End ARG]
+
+Is_Full returns True when the number of elements that have been
+enqueued equals the Capacity; otherwise it returns False.
+
+Implementation Advice
-[Editor's comment: We need some wording here to describe how these work!
-In particular, Is_Full becomes True only after Capacity items are
-queued. We can't leave this to chance!]
-
-A.18.26 Containers.Priority_Queues
-
-The language-defined generic package Containers.Priority_Queues
-provides interface type Queue, and a set of operations for that type.
-Interface Queue specifies a queue that orders its elements per a
-specified relation.
+Bounded queue objects should be implemented without implicit pointers or dynamic
+allocation.
+
+A.18.26 Containers.Unbounded_Priority_Queues
+
Static Semantics
-The generic library package Containers.Priority_Queues has the
-following declaration:
+The language-defined generic package
+Containers.Unbounded_Priority_Queues provides type Queue, which
+implements the interface type Containers.Queues.Queue.
+with Ada.Containers.Queues;
generic
- type Element_Type is private;
-
-[ARG]
-Do we pass order relation here, or in child package?
+ with package Queues is new Ada.Containers.Queues (<>);
+ with function "<"
+ (Left, Right : Queues.Element_Type) return Boolean is <>;
-One possible answer is that the order relation should be defined here
-(in the root package), so that other generic packages (outside of this
-subsystem) can import the order relation as a generic actual
-parameter.
-[END ARG]
+package Ada.Containers.Unbounded_Priority_Queues is
+ pragma Preelaborate;
-package Ada.Containers.Priority_Queues is
- pragma Pure;
+ type Queue is synchronized new Queues.Queue with private;
- type Queue is synchronized interface;
+private
- procedure Insert
- (Container : in out Queue;
- New_Item : Element_Type) is abstract;
- pragma Implemented (Insert, By_Entry);
+ -- not specified by the language
- procedure Remove
- (Container : in out Queue;
- Element : out Element_Type) is abstract;
- pragma Implemented (Remove, By_Entry);
+end Ada.Containers.Unbounded_Priority_Queues;
[ARG]
-We went back and forth during the meeting about the names to use here,
-but I don't remember what names we finally settled on. Should
-"Remove" be "Delete" or "Delete_First"?
-[END ARG]
- function Is_Empty (Container : Queue) return Boolean is abstract;
+We might need to refactor this description, so that it applies to both
+priority queue forms.
- function Is_Full (Container : Queue) return Boolean is abstract;
+[Editor's note: Well, either that or duplicate it in the bounded form.
+Doing neither is just wrong.]
-end Ada.Containers.Priority_Queues;
+[END ARG]
+
+Two elements E1 and E2 are equivalent if both E1 < E2 and E2 < E1
+return False, using the generic formal "<" operator for
+elements.
The actual function for the generic formal function "<" on
Element_Type values is expected to return the same value each time it
@@ -194,70 +208,33 @@
transitive. If the actual for "<" behaves in some other manner, the
behavior of this package is unspecified. Which subprograms of this
package call "<" and how many times they call it, is unspecified.
-
-If the value of an element stored in a set is changed other than by an
-operation in this package such that at least one of "<" gives
-different results, the behavior of this package is unspecified.
-
- procedure Insert
- (Container : in out Queue;
- New_Item : Element_Type) is abstract;
-
-Adds New_Item to Container, per the specified order. If Is_Full is
-True, then Insert waits on the entry for storage to become available.
-
- procedure Remove
- (Container : in out Queue;
- Element : out Element_Type) is abstract;
-
-Removes the element at the head of the queue, and returns a copy of
-the element. Is Is_Empty is True, then Remove waits on the entry for
-an item to become available.
-
- function Is_Empty (Container : Queue) return Boolean is abstract;
-
-Returns True if Container contains items.
-
- function Is_Full (Container : Queue) return Boolean is abstract;
-
-Returns True if Container is able to contain more items.
-
-
-A.18.27 Containers.Unbounded_Priority_Queues
-
-Static Semantics
-
-The language-defined generic package
-Containers.Unbounded_Priority_Queues provides type Queue, which
-implements the interface type Containers.Priority_Queues.Queue.
-with Ada.Containers.Priority_Queues;
-generic
- with package Queues is new Ada.Containers.Priority_Queues (<>);
- with function "<"
- (Left, Right : Queues.Element_Type) return Boolean is <>;
+[ARG]
-package Ada.Containers.Unbounded_Priority_Queues is
- pragma Preelaborate;
+Do we need that last sentence?
- type Queue is synchronized new Queues.Queue with private;
+[END ARG]
-private
+If the value of an element stored in a set is changed other than by an
+operation in this package such that "<" gives a different result, the
+behavior of this package is unspecified.
- -- not specified by the language
+Enque inserts an item according to the order specified by the generic
+formal "<" operator. If the queue already contains an element
+equivalent to New_Item, then the new item is inserted after existing
+equivalent elements.
-end Ada.Containers.Unbounded_Priority_Queues;
+Is_Full always returns False, because storage for new items is
+allocated dynamically.
-A.18.28 Containers.Bounded_Priority_Queues
+A.18.27 Containers.Bounded_Priority_Queues
-Static Semantics
-
The language-defined generic package
Containers.Bounded_Priority_Queues provides type Queue, which
-implements the interface type Containers.Priority_Queues.Queue.
+implements the interface type Containers.Queues.Queue.
-with Ada.Containers.Priority_Queues;
+with Ada.Containers.Queues;
generic
with package Queues is new Ada.Containers.Queues (<>);
with function "<"
@@ -274,6 +251,23 @@
-- not specified by the language
end Ada.Containers.Bounded_Priority_Queues;
+
+
+The type Queue needs finalization if and only type
+Element_Type needs finalization.
+
+[ARG]
+Is the above what we want?
+[End ARG]
+
+Is_Full returns True when the number of elements that have been
+enqueued equals the Capacity; otherwise it returns False.
+
+Implementation Advice
+
+Bounded priority queue objects should be implemented without implicit
+pointers or dynamic allocation.
+
!discussion
Questions? Ask the ACAA Technical Agent