CVS difference for ai05s/ai05-0159-1.txt

--- ai05s/ai05-0159-1.txt	2009/10/22 03:43:10	1.4
+++ ai05s/ai05-0159-1.txt	2009/10/23 06:06:31	1.5
@@ -171,7 +171,7 @@
 Implementation Advice
 
 Bounded queue objects should be implemented without implicit pointers or dynamic
-allocation. 
+allocation.
 
 
 A.18.26 Containers.Unbounded_Priority_Queues
@@ -230,7 +230,7 @@
      (Left, Right : Queues.Element_Type) return Boolean is <>;
 
 package Ada.Containers.Bounded_Priority_Queues is
-   pragma Pure;  
+   pragma Pure;
 
    type Queue (Capacity : Count_Type) is
      synchronized new Queues.Queue with private;
@@ -265,7 +265,7 @@
 Implementation Advice
 
 Bounded priority queue objects should be implemented without implicit
-pointers or dynamic allocation. 
+pointers or dynamic allocation.
 
 
 !discussion
@@ -293,4 +293,154 @@
 
 !appendix
 
-****************************************************************
\ No newline at end of file
+From: Martin Dowie
+Date: Tuesday, July 28, 2009  2:53 AM
+
+1. For the priority queue, what is the expected behaviour of trying to add 2
+   identical elements to the queue? It would seem that the 2nd would not be
+   added (as "Before (x, x) = False"). I appreciate that to get both messages
+   added would probably require "multiset" support - are "Multi" variants of the
+   existing containers planned?
+
+2. For the bounded variants, is the intent that they should not use dynamic
+   memory (same as the new bounded containers)? If so, should there be some
+   words added to state this?
+
+3. The queues are all specified to be FIFO - could LIFO also be added relatively
+   cheaply? Not as common but still useful.
+
+****************************************************************
+
+From: Randy Brukardt
+Date: Tuesday, August 11, 2009  1:42 PM
+
+Sorry about the long delay on posting this one; it got blocked by a useless
+filter in the mailing list software (that unfortunately can't be turned off) and
+I was on vacation.
+
+> 1. For the priority queue, what is the expected behaviour of trying to
+> add 2 identical elements to the queue? It would seem that the 2nd
+> would not be added (as "Before (x, x) = False"). I appreciate that to
+> get both messages added would probably require "multiset" support -
+> are "Multi"
+> variants of the existing containers planned?
+
+I would have expected the reverse: that two identical elements get queued
+(probably in an unspecified order). That's how the queues in my mail filter work
+(the only time I've used priority queues in practice) [They're actually more
+like delay queues, as the "priority" is the retry time. Surely you don't want to
+loose a message just because it happens to have the same retry time as another.]
+
+In any case, this will need to be clarified.
+
+> 2. For the bounded variants, is the intent that they should not use
+> dynamic memory (same as the new bounded containers)?
+> If so, should there be some words added to state this?
+
+That is my understanding, and yes, of course, they will need all of the
+appropriate wording that AI05-0001-1 uses for bounded forms.
+
+> 3. The queues are all specified to be FIFO - could LIFO also be added
+> relatively cheaply? Not as common but still useful.
+
+Not sure it is worth it. We're really only trying to provide the most basic and
+common of protected containers because generally the "protection" needed is
+something that depends on the entire algorithm; naively dropping in protected
+containers could easily generate race or deadlock conditions.
+
+In any case, "LIFO" is a stack, which is generally thought of as a totally
+different data structure, with different names for the operations. Trying to use
+queue terminology for it would be pretty unnatural. So there wouldn't be much if
+any reuse potential here.
+
+****************************************************************
+
+From: Simon Wright
+Date: Tuesday, August 11, 2009  3:45 PM
+
+>> 1. For the priority queue, what is the expected behaviour of trying
+>> to add 2 identical elements to the queue? It would seem that the 2nd
+>> would not be added (as "Before (x, x) = False"). I appreciate that to
+>> get both messages added would probably require "multiset" support -
+>> are "Multi"
+>> variants of the existing containers planned?
+>
+> I would have expected the reverse: that two identical elements get
+> queued (probably in an unspecified order).
+
+As a data point here, the BC ordered queue queues 'identical' items in FIFO
+order (preferring defined behaviour). Whether an unspecified order is
+satisfactory must, I think, depend on the application.
+
+****************************************************************
+
+From: Jeffrey R. Carter
+Date: Tuesday, August 11, 2009  4:12 PM
+
+> I would have expected the reverse: that two identical elements get
+> queued (probably in an unspecified order). That's how the queues in my
+> mail filter work (the only time I've used priority queues in practice)
+> [They're actually more like delay queues, as the "priority" is the
+> retry time. Surely you don't want to loose a message just because it
+> happens to have the same retry time as another.]
+
+If they're specified as FIFO, the priority queue must really be
+FIFO-within-priorities, so it must queue the 2nd after the 1st.
+
+****************************************************************
+
+From: Martin Dowie
+Date: Monday, August 24, 2009  7:03 AM
+
+Thanks for all that - making more sense now...
+
+Would it be useful to add a "Peek" operation too? One that returned the highest
+priority element in the queue without actually removing it from the queue?
+
+****************************************************************
+
+From: Matthew Heaney
+Date: Thursday, October 8, 2009  12:28 AM
+
+> 1. For the priority queue, what is the expected behaviour of trying to
+> add 2 identical elements to the queue? It would seem that the 2nd
+> would not be added (as "Before (x, x) = False"). I appreciate that to
+> get both messages added would probably require "multiset" support -
+> are "Multi"
+> variants of the existing containers planned?
+
+There are two separate issues here.
+
+The first issue is the matter of the priority queue.  Yes, you should be able to
+add multiple items that are equivalent.  And yes, new elements that are
+equivalent to existing elements should probably go after existing elements.
+(But this will have to be decided at the ARG meeting next month.)
+
+The second issue is multiset support.  This is orthogonal to priority queues
+(because the language doesn't specify how the queues are implemented).  On the
+specific matter of multiset support, I lobbied last year for their inclusion in
+the language standard, but wasn't able to make my case with sufficient cogency,
+so they didn't make the cut.
+
+However, an unbounded multiset is part of the GNAT distribution, so if you're
+using GNAT then you have one already.  I am in the process of integrating the
+bounded forms into GNAT, and so GNAT will have a bounded multiset too.
+
+For now I have implemented the bounded priority queues using the multisets, but
+eventually I'll probably replace that implementation with a proper heap.
+
+
+> 2. For the bounded variants, is the intent that they should not use
+> dynamic memory (same as the new bounded containers)? If so, should
+> there be some words added to state this?
+
+Right, the bounded forms do not use dynamic memory allocation.
+
+
+> 3. The queues are all specified to be FIFO - could LIFO also be added
+> relatively cheaply? Not as common but still useful.
+
+That's just a stack.  Use a vector or a list container, wrapped in a protected
+object.
+
+****************************************************************