CVS difference for ais/ai-30302.txt

Differences between 1.6 and version 1.7
Log of other versions for file ais/ai-30302.txt

--- ais/ai-30302.txt	2004/06/25 00:55:46	1.6
+++ ais/ai-30302.txt	2004/09/04 01:13:47	1.7
@@ -13272,21 +13272,3894 @@
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Wednesday, June 9, 2004  9:31 AM
+Sent: Sunday, June 27, 2004  5:35 PM
 
+Randy:
+
+I have a few comments about the Palma API release.  The actual text of my
+comments are bracketed by "MJH:" and "ENDMJH." pairs, and immediately
+follows the operation(s) to which they refer.
+
+vector:
+
+MJH:
+The partial view of type Vector is now tagged, like this:
+
+   type Vector is tagged private;
+
+Ditto for the other containers.
+ENDMJH.
+
+
+   function To_Vector (Count : Count_Type) return Vector;
+
+   function To_Vector (New_Item : Element_Type;
+                       Count    : Count_Type)
+      return Vector;
+
+MJH:
+We need to affirm whether the parameter should be named "Count" or "Length".
+ENDMJH.
+
+
+   function Capacity (Container : Vector) return Count_Type;
+
+   procedure Set_Capacity (Container : in out Vector;
+                           Capacity  : in     Count_Type);
+
+MJH:
+I declared the operations formerly named "Size" and "Resize" as above.
+ENDMJH.
+
+
+   generic
+      with procedure Process (Element : in out Element_Type);
+   procedure Generic_Update_Element_By_Index (Container : in Vector;
+                                              Index     : in
+Index_Type'Base);
+
+   generic
+      with procedure Process (Element : in out Element_Type);
+   procedure Generic_Update_Element (Position : in Cursor);
+
+MJH:
+We don't need different names for these operations anymore, since they're
+not generic and hence we can overload the names as follows (verify my syntax
+is correct):
+
+   procedure Update_Element (Container : in Vector;
+                             Index     : in Index_Type'Base;
+                             Process   : access procedure (Element : in out
+Element_Type));
+
+   procedure Update_Element (Position : in Cursor;
+                             Process  : access procedure (Element : in out
+Element_Type));
+
+ENDMJH.
+
+
+   procedure Set_Length (Container : in out Vector;
+                         Length    : in     Size_Type);
+
+MJH:
+Is this vector operation missing?
+
+   procedure Set_Length (Container : in out Container_Type;
+                         Length    : in     Size_Type;
+                         New_Item  : in     Element_Type);
+
+This would allow you to specify a value for elements that become active when
+Length > Length (Container).
+ENDMJH.      
+
+
+   procedure Swap (Container : in Vector;
+                   I, J      : in Index_Type'Base);
+
+   procedure Swap (Container : in out Vector;
+                   I, J      : in     Cursor);
+
+
+MJH:
+The declaration of the second Swap operation (the one for which I and J have
+type Cursor) appears to be incorrect.  Firstly, the Container parameter is
+inout.  (This was probably for symmetry with the cursor-based Swap for the
+List container -- see below.)  It would only need to be in-mode.  However, I
+think the real error is that there is a container parameter at all.  It is
+never that case that you need to pass a container when all you're doing is
+manipulating an element through a cursor (e.g. E := Element (C)).
+
+I think the cursor-based swap operation should be declared this way:
+
+   procedure Swap (I, J : in Cursor);
+
+The comment also applies to the (cursor-based) swap operation for the List
+containers.  
+
+(This change is really a consequence of clarifying the semantics of swap for
+list containers during the ARG meeting in Palma.)
+ENDMJH.
+
+MJH:
+Should be weaken the precondition, allowing I and J to have the value
+No_Element, in which case Swap is a no-op?
+ENDMJH.
+
+
+   function Is_In (Item      : Element_Type;
+                   Container : Vector)
+      return Boolean;
+
+MJH:
+As a consequence of making the vector type tagged, the parameters should be
+put in the opposite order, like this:
+
+   function Is_In (Container : Vector;
+                   Item      : Element_Type)
+      return Boolean;
+ENDMJH.
+
+
+   generic
+      with procedure Process (Position : in Cursor);
+   procedure Generic_Iteration (Container : in Vector);
+
+   generic
+      with procedure Process (Position : in Cursor);
+   procedure Generic_Reverse_Iteration (Container : in Vector);
+
+
+MJH:
+These operations aren't generic anymore.  Also, the name should probably be
+changed to use verb-style instead of noun-style (the existing name is
+consistent with the style for generic operations as Unchecked_Deallocation,
+etc):
+
+   procedure Iterate (Container : in Vector;
+                      Process   : access procedure (Position : in Cursor));
+
+   procedure Reverse_Iterate (Container : in Vector;
+                              Process   : access procedure (Position : in
+Cursor));
+
+ENDMJH.
+
+
+list:
+
+   procedure Swap (Container : in out List;
+                   I, J      : in     Cursor);
+
+MJH:
+
+The semantics of Swap were clarified in Palma so that only elements are
+swapped, and not nodes.  Hence there is no need for a container parameter,
+and the swap operation should be declared like this:
+
+   procedure Swap (I, J : in Cursor);
+
+This cursor-based swap operation for Vector should be declared similarly.
+
+ENDMJH.
+
+MJH:
+As for the Vector, the parameters for Is_In should be reordered so that the
+container parameter is the first parameter.
+ENDMJH.
+
+map:
+
+generic
+
+   type Key_Type is private;
+
+   type Element_Type is private;
+
+   with function Hash (Key : Key_Type)
+      return Hash_Type is <>;
+
+   with function Is_Equal_Key (Left, Right : Key_Type)
+      return Boolean is "=";
+
+   with function "=" (Left, Right : Element_Type)
+      return Boolean is <>;
+
+package AI302.Containers.Hashed_Maps is ...;
+
+MJH:
+
+There was a lot of talk between Tucker and Pascal about the declaration of
+generic formal region for the hashed map.  I think Tucker wanted it to look
+like this:
+
+generic
+
+   type Key_Type is private;
+
+   type Element_Type is private;
+
+   with function Hash (Key : Key_Type)
+      return Hash_Type;  --VERIFY WHETHER THERE'S NO DEFAULT
+
+   with function "=" (Left, Right : Key_Type)
+      return Boolean is <>;
+
+   with function Equivalent (Left, Right : Key_Type)
+      return Boolean is "=";
+
+   with function "=" (Left, Right : Element_Type)
+      return Boolean is <>;
+
+package AI302.Containers.Hashed_Maps is ...;
+
+We agreed that the map container would use keys to compute map container
+equality.  My question is exactly how this should be done.  Firstly, what is
+the purpose for passing in key equality as a generic formal parameter?  Is
+it merely to supply a default for Equivalent?  Or is it also used for some
+other purpose (perhaps to compute map equality)?  
+
+To compute map equality, we do something like this:
+
+(1) Compare lengths; if they're different, then return false.
+
+(2a) For each key in the left (say) map, see if it's in the right map.
+If it's not found, then return false.
+
+(2b) If the key is found, then compare the elements.  If they're not
+equal, then return false.
+
+My question is really about step (2a), about what it means to "compare
+keys."  When we check to see if the key of the left map is in the right map,
+we do what already during insertion and deletion, by computing the hash
+value and then calling Equivalent (formerly called "Is_Equal_Key").  So what
+is the purpose of key equailty "="?  Do we use key equality for some purpose
+other than providing a default for Equivalent?  Or do we somehow incorporate
+an explicit call to key "=" when we "compare keys" during computation of map
+equality?
+ENDMJH.
+
+MJH:
+Another point: the name "Equivalent" is also inconsistent with cursor
+operations named "Is_Equal_Key".  Was this intended?  Should we leave the
+formal operation named "Is_Equal_Key" as is, or change the cursor operations
+to use name the "Equivalent"?
+ENDMJH.
+
+
+   procedure Insert (Container : in out Map;
+                     Key       : in     Key_Type;
+                     New_Item  : in     Element_Type;
+                     Position  :    out Cursor;
+                     Success   :    out Boolean);
+
+   procedure Replace (Container : in out Map;
+                      Key       : in     Key_Type;
+                      New_Item  : in     Element_Type);
+
+   procedure Insert (Container : in out Map;
+                     Key       : in     Key_Type;
+                     Position  :    out Cursor;
+                     Success   :    out Boolean);
+
+
+MJH:
+
+We overloaded the insertion operations for list to include overloadings that
+omit a cursor parameter.  Should we provide similar overloadings for maps
+(and sets -- see below) too?  Something like this:
+
+   procedure Insert (Container : in out Map;
+                     Key       : in     Key_Type;
+                     New_Item  : in     Element_Type);
+
+(I have omitted an overloading that just accepts a key, since in general we
+need a cursor in order to give the element a value following the insertion
+proper.)
+ENDMJH.
+
+
+sets:
+
+   procedure Insert (Container : in out Set;
+                     New_Item  : in     Element_Type;
+                     Position  :    out Cursor;
+                     Success   :    out Boolean);
+
+MJH:
+
+The following overloading that omits the cursor parameter would be useful:
+
+   procedure Insert (Container : in out Set;
+                     New_Item  : in     Element_Type);
+
+I've had a need for this operation, as has Georg Bauhaus (per CLA).  It
+would also be consistent with list, which has an overloading that omits the
+cursor parameter.
+ENDMJH.
+
+MJH:
+
+We have a Replace operation for maps, but nothing similar for sets.  It make
+make sense to include this set operation too:
+
+   procedure Replace (Container : in out Set;
+                      New_Item  : in     Element_Type);
+
+ENDMJH.
+
+   function Is_Subset (Item      : Set;
+                       Container : Set)
+      return Boolean;
+
+   function Is_Disjoint (Item      : Set;
+                         Container : Set)
+      return Boolean;
+
+   function Is_In (Item      : Element_Type;
+                   Container : Set)
+      return Boolean;
+
+
+MJH:
+Since the container type is tagged, all of these operations need to reorder
+the parameters so that the container is first:
+
+   function Is_Subset (Container : Set;
+                       Item      : Set)
+      return Boolean;
+
+   function Is_Disjoint (Container : Set;
+                         Item      : Set)
+      return Boolean;
+
+   function Is_In (Container : Set;
+                   Item      : Element_Type)
+      return Boolean;
+ENDMJH.
+
+MJH:
+For both Is_Subset and Is_Disjoint, we should clarify the results when one
+or both of the params are empty sets.
+ENDMJH.
+
+   function Find (Container : Set;
+                  Item      : Element_Type)
+      return Cursor;
+
+MJH:
+Immediately following the declaration of the Find operation, the following
+two operations are declared:
+
+   function Ceiling (Container : Set;
+                     Item      : Element_Type)
+     return Cursor;
+
+   function Floor (Container : Set;
+                   Item      : Element_Type)
+     return Cursor;
+ENDMJH.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Sunday, June 27, 2004  6:34 PM
+
+> MJH:
+> For both Is_Subset and Is_Disjoint, we should clarify the 
+> results when one or both of the params are empty sets. ENDMJH.
+> 
+>    function Find (Container : Set;
+>                   Item      : Element_Type)
+>       return Cursor;
+> 
+> MJH:
+> Immediately following the declaration of the Find operation, 
+> the following two operations are declared:
+> 
+>    function Ceiling (Container : Set;
+>                      Item      : Element_Type)
+>      return Cursor;
+> 
+>    function Floor (Container : Set;
+>                    Item      : Element_Type)
+>      return Cursor;
+> ENDMJH.
+
+MJH:
+I forget to mention here that Ceiling and Floor should also be added to the
+set nested package Generic_Keys:
+
+      function Is_In (Container : Set;
+                      Key       : Key_Type)
+         return Boolean;
+
+      function Find (Container : Set;
+                     Key       : Key_Type)
+        return Cursor;
+
+      function Ceiling (Container : Set;
+                        Key       : Key_Type)
+         return Cursor;
+
+      function Floor (Container : Set;
+                      Key       : Key_Type)
+         return Cursor;
+
+ENDMJH.
+
+
+MJH:
+Note also that the generic operation Generic_Keys.Generic_Insertion has been
+removed.
+ENDMJH.
+
+****************************************************************
+
+From: Nick Roberts
+Sent: Sunday, June 27, 2004  5:50 PM
+
+[My comments are between NJR and ENDNJR.]
+
+"Matthew Heaney" <matthewjheaney@earthlink.net> wrote:
+
+   function To_Vector (Count : Count_Type) return Vector;
+
+   function To_Vector (New_Item : Element_Type;
+                       Count    : Count_Type)
+      return Vector;
+
+MJH:
+We need to affirm whether the parameter should be named "Count" or "Length".
+ENDMJH.
+
+NJR:
+The name 'Length' seems very approrpiate to me.
+ENDNJR
+
+MJH:
+Is this vector operation missing?
+
+   procedure Set_Length (Container : in out Container_Type;
+                         Length    : in     Size_Type;
+                         New_Item  : in     Element_Type);
+
+This would allow you to specify a value for elements that become active when
+Length > Length (Container).
+ENDMJH.
+
+NJR
+I think this procedure might make sense (but it might be considered
+overkill). I guess 'Count_Type' was meant instead of 'Size_Type'.
+ENDNJR
+
+   procedure Swap (I, J : in Cursor);
+
+NJR
+Might it be slightly clearer for the name to be 'Swap_Elements'?
+ENDNJR
+
+MJH:
+Should be [we] weaken the precondition, allowing I and J to have the value
+No_Element, in which case Swap is a no-op?
+ENDMJH.
+
+NJR
+All the algorithms that I can think of which swap elements in an array (of
+some kind) necessarily have a pre-test for validity before doing the swap. I
+therefore think it would be a useful bug-catcher to specify that an
+exception is raised if I or J is No_Element. By analogy to an Ada array,
+doing T := A(I); A(I) := A(J); A(J) := T; would raise Constraint_Error if I
+or J were out of the range of A.
+ENDNJR
+
+   function Is_In (Item      : Element_Type;
+                   Container : Vector)
+      return Boolean;
+
+MJH:
+As a consequence of making the vector type tagged, the parameters should be
+put in the opposite order, like this:
+
+   function Is_In (Container : Vector;
+                   Item      : Element_Type)
+      return Boolean;
+ENDMJH.
+
+NJR
+The obvious objection to this is that it would lack consistency with the
+Ada.Character.Maps packages. But I think I tentatively agree with Matt, in
+which case the name should probably be changed to something like 'Contains',
+'Includes', or 'Has'.
+ENDNJR
+
+   procedure Swap (I, J : in Cursor);
+
+NJR
+Again, maybe 'Swap_Elements' would be a slightly clearer name.
+ENDNJR
+
+MJH:
+As for the Vector, the parameters for Is_In [for lists] should be reordered
+so
+that the container parameter is the first parameter.
+ENDMJH.
+
+NJR
+Again, in which case the name should be something like 'Contains',
+'Includes', or 'Has'.
+ENDNJR
+
+MJH:
+Since the container type is tagged, all of these operations need to reorder
+the parameters so that the container is first:
+
+   function Is_Subset (Container : Set;
+                       Item      : Set)
+      return Boolean;
+
+   function Is_Disjoint (Container : Set;
+                         Item      : Set)
+      return Boolean;
+
+   function Is_In (Container : Set;
+                   Item      : Element_Type)
+      return Boolean;
+ENDMJH.
+
+NJR
+Again, the objection is that there would be a lack of consistency with
+Ada.Strings.Maps. If the order of the parameters were to be changed, it
+would seem that alternative names ought to be chosen for Is_Subset and
+Is_In. For example:
+
+   function Contains_All (Container : Set;
+                          Item      : Set)
+      return Boolean;
+
+   function Contains (Container : Set;
+                      Item      : Element_Type)
+      return Boolean;
+ENDNJR
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Sunday, June 27, 2004  10:45 PM
+
+> MJH:
+> Is this vector operation missing?
+> 
+>    procedure Set_Length (Container : in out Container_Type;
+>                          Length    : in     Size_Type;
+>                          New_Item  : in     Element_Type);
+> 
+> This would allow you to specify a value for elements that 
+> become active when Length > Length (Container). ENDMJH.
+> 
+> NJR
+> I think this procedure might make sense (but it might be 
+> considered overkill). I guess 'Count_Type' was meant instead 
+> of 'Size_Type'. 
+> ENDNJR.
+
+Yes, that was a cut and paste error.  The Length parameter should have type
+Count_Type.  (Size_Type is gone.)
+
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Sunday, June 27, 2004  10:52 PM
+
+> map:
+> 
+> package AI302.Containers.Hashed_Maps is ...;
+
+I forgot to mention the changes to these map two operations:
+
+
+   function Size (Container : Map) return Size_Type;
+
+   procedure Resize (Container : in out Map;
+                     Size      : in     Size_Type);
+
+MJH:
+
+I made the name changes here the same as for the vector:
+
+   function Capacity (Container : Map) return Count_Type;
+
+   procedure Set_Capacity (Container : in out Map;
+                           Capacity  : in     Count_Type);
+
+
+ENDMJH.
+
+****************************************************************
+
+From: Pascal Leroy
+Sent: Monday, June 28, 2004  2:17 AM
+
+Matt wrote:
+
+>    function Is_In (Item      : Element_Type;
+>                    Container : Vector)
+>       return Boolean;
+> 
+> MJH:
+> As a consequence of making the vector type tagged, the 
+> parameters should be put in the opposite order, like this:
+> 
+>    function Is_In (Container : Vector;
+>                    Item      : Element_Type)
+>       return Boolean;
+> ENDMJH.
+
+I disagree.  The reason why we care which parameter comes first is of
+course the Object.Operation notation introduced by AI 252.  However, in
+this case we want to actively prevent the use of this notation.  With your
+proposed change a call to Is_In could be written:
+
+	My_Vector.Is_In (My_Element)
+
+which reads exactly backwards.  This operation is a case where the
+parameters have a "natural" order and we don't want to change it.  (I wish
+we could redefine "in", but that's a different topic.)
+
+****************************************************************
+
+From: Cyrille Comar
+Sent: Monday, June 28, 2004  3:38 AM
+
+Maybe "Is_In" should be renamed "Contains" which has the opposite
+"natural" order:
+
+      My_Vector.Contains (My_Element)
+
+looks better...
+
+****************************************************************
+
+From: Pascal Leroy
+Sent: Monday, June 28, 2004  4:28 AM
+
+I like the idea.  I have never been very happy with the name Is_In anyway.
+
+****************************************************************
+
+From: Matthaw Heaney
+Sent: Monday, June 28, 2004  8:54 AM
+
+As Nick pointed out, the name Is_In comes from Ada.Strings.Maps (RM95 
+A.4.2 (13)).  (That package also has an Is_Subset operation, with 
+parameters in the same order as Is_In.)
+
+So I guess it's a choice between consistency with other parts of RM95, 
+or trying to take advantage of new syntax allowed by Ada 0Y.
+
+****************************************************************
+
+From: Georg Bauhaus
+Sent: Wednesday, June 30, 2004  7:25 AM
+
+!topic unchecked Insert for Sets and Maps
+!reference RM95-A.17 [AI95-00302-03]
+!from Author Georg Bauhaus 04-06-30
+!discussion
+
+There are similar Insert procedures for both Ordered_Sets
+and Hashed_Maps with highly useful Position and Success
+parameters.  Sometimes however, it seems somewhat
+disturbing to see declararations of variables for Position
+and Success that are not read because it is considered
+safe to ignore them.  It might be known that Insert will
+succeed without surprises (ceteris paribus).  Examples
+include adding initial values to a library level
+container, like 69 keywords, or adding known border values
+to ordered containers.
+
+A work around is to have wrapper procedures providing
+variables necessary for Insert. But does this not incur
+more verbiage and/or withing than is desirable?  Adding a
+convenient procedure to the containers seems easy.  In a
+sense, this might also make Ordered_Sets and Hashed_Maps
+correspond more closely to Vectors and Doubly_Linkes_List
+with regard to Insert procedures.
+
+(When using maps, I sometimes think of them as sparse
+arrays. With arrays, I can just write
+
+        ary(key) := value;
+
+and be done.)
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Wednesday, June 30, 2004  3:07 PM
+
+You have that operation already; it's called Replace:
+
+    Replace (Map, Key, New_Item => Value);
+
+However, there's nothing like that for the ordered sets.  It would 
+appear useful as an adjunct to Update_Element.
+
+I agree that having overloadings of Insert for sets and maps that omit 
+the Position and Success parameters would be handy.  It's often the case 
+that you know an insertion will succeed, so having to declare a Boolean 
+object that you don't bother inspecting is kind of a pain.
+
+****************************************************************
+
+From: Pascal Leroy
+Sent: Wednesday, June 30, 2004  3:30 PM
+
+These are sensible suggestions.  However, I have to remind you that if
+this AI is not approved at the Madison ARG meeting it won't be in the
+Amendment.  You should be cautious when considering the addition of new
+features: at this point we should really be crossing the t's and dotting
+the i's.
+
+This is especially important given that some countries expressed concerns
+regarding the maturity of this particular AI at the WG9 level.
+
+****************************************************************
+
+
+From: Marius Amado Alves
+Sent: Thursday, July 1, 2004  5:43 AM
+
+I think Matthew is 'more right' than Jeffrey. But please note I tend to 
+NOT advise changing the spec now, for the reasons Pascal gave. So this 
+is mainly academic now, and sorry for being slightly OT, but I love real 
+code examples. Two follow, from Mneson.Base (AI302 version 20040227). In 
+(1) I know in advance that the element is new. In (2) I want the set 
+semantics (unique elements) guaranteed by the container, so I don't care 
+about the success value. You'll note I tried hard to name the dummy 
+variables in accordance with the circumstances.
+
+(1)
+    -- ...
+             use String_Maps;
+             use Short_String_IO;
+             Found, Dont_Need : String_Maps.Cursor_Type;
+             Expected_True : Boolean;
+          begin
+             Found := Find (String_Table, Value);
+             if Found /= Null_Cursor then
+                X := Element (Found);
+             else -- new string
+                -- code here to store the value
+                -- in a Short_String_IO file
+                Insert
+                   (Map => String_Table,
+                    Key => Value,
+                    New_Item => X,
+                    Cursor => Dont_Need,
+                    Success => Expected_True);
+             end if;
+    -- ...
+
+(2)
+    procedure Connect (Source, Target : Vertex) is
+       use Link_Sets;
+       Dont_Need : Cursor_Type;
+       Dont_Care : Boolean;
+    begin
+       Insert
+         (Set => Links,
+          New_Item => (Source, Target),
+          Cursor => Dont_Need,
+          Success => Dont_Care);
+       Insert
+         (Set => Inv_Links,
+          New_Item => (Target, Source),
+          Cursor => Dont_Need,
+          Success => Dont_Care);
+    end;
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Thursday, July 1, 2004  9:31 AM
+
+Note that (1) isn't the most efficient way to do this, since Insert 
+duplicates the effort of Find.  I recommend doing it this way instead:
+
+   C : Cursor;
+   Not_Already_In_Map : Boolean;
+begin
+   Insert (String_Table, Value, C, Not_Already_In_Map);
+
+   if Not_Already_In_Map then
+      Replace_Element (C, By => X);
+   else
+      X := Element (C);
+   end if;
+end;
+
+Here, we use the item-less version of Insert to perform an insertion 
+attempt, and then give the item a proper value if the key was actually 
+inserted during this attempt.
+
+If the attempt fails, it's because the key was already in the map, so 
+you can then interrogate the item associated with that key.
+
+****************************************************************
+
+From: Marius Amado Alves
+Sent: Thursday, July 1, 2004 10:40 AM
+
+Yes I think it applies. Thanks. This kind of optimizations are in the 
+Mneson to do list. Everyone is welcome to join Mneson development ;-)
+
+****************************************************************
+
+From: Jeffrey Carter
+Sent: Wednesday, June 30, 2004  7:59 PM
+
+These are no doubt useful operations. However, as any student of 
+defensive programming knows, operations that you know will succeed 
+don't, often enough to be a problem. Since these components must ensure 
+their internal consistency whenever possible, these operations would 
+still have to check that they succeed, and raise an appropriate 
+exception if they don't.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Thursday, July 1, 2004  9:32 AM
+
+> These are no doubt useful operations. However, as any student of 
+> defensive programming knows, operations that you know will succeed 
+> don't, often enough to be a problem. Since these components must ensure 
+> their internal consistency whenever possible, these operations would 
+> still have to check that they succeed, and raise an appropriate 
+> exception if they don't.
+
+There may be some misunderstanding here.  The Success parameter merely 
+indicates whether the key was inserted during *this* insertion, not 
+whether the key was inserted into the container.  If Success returns 
+False, this simply means that the key was already in the container.
+
+So no matter what Success returns, you still have a guarantee that the 
+key is in the map.
+
+If this is a map, and it's important that the element associated with 
+the key is always stored in the map (even if the key is already in the 
+map), then use Replace.
+
+****************************************************************
+
+From: Jeffrey Carter
+Sent: Thursday, July 1, 2004  7:54 PM
+
+This is an un-Ada-like way to do things, and I'm sorry I didn't realize 
+this earlier. Insert might perform a replacement if the key already 
+exists, or it might consider it an error and raise an exception, but to 
+return a Boolean flag is too C-like for my tastes.
+
+****************************************************************
+
+From: Pascal Leroy
+Sent: Friday, July 2, 2004  2:33 AM
+
+I am starting to feel that way too, and I wish I had noticed this earlier.
+
+The notion of an out parameter that you can drop on the floor if you like
+looks like a real safety issue to me.  It is all too easy to forget to
+test this parameter.  I know that Matt's philosophy is to trust the
+programmer, but he has been repeatedly chided by the ARG for this.
+
+My preference would be to change the specification of Insert as follows:
+
+procedure Insert (Container : in out Map;
+                  Key       : in     Key_Type;
+                  New_Item  : in     Element_Type;
+                  Allow_Replacement : in Boolean;
+                  Position  :    out Cursor);
+
+If Allow_Replacement is True, Insert will replace any existing entry in
+the map with the given key/element pair.  If Allow_Replacement is False,
+Insert will raise an exception if the key is already in the map.  In the
+absence of an exception, Position will denote the newly inserted/replaced
+entry.
+
+I realize that I advocated avoiding changes to the specification, but this
+AI is going to be shot down by WG9 if it contains safety holes.
+
+****************************************************************
+
+From: Marius Amado Alves
+Sent: Friday, July 2, 2004  5:33 AM
+
+I don't see a safety hole here, just a different style of doing the same 
+thing. Remember the "Success" parameter does not reflect some kind of 
+'total' success of the operation, just that the element was already 
+there. Other, really abnormal, conditions raise exceptions as expected.
+
+Personally I'm even OK with the occasional Dont_Care dummy variable. But 
+the solution to this is trivial, just add the operation variants without 
+the out parameters as 'proxies' with the expected implementation e.g.
+
+    procedure Insert (Container, Item) is
+       Dont_Care : Boolean;
+       Dont_Need : Cursor;
+    begin
+       Insert (Container, Item, Dont_Care, Dont_Need);
+    end;
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Friday, July 2, 2004  8:03 AM
+
+> The notion of an out parameter that you can drop on the floor 
+> if you like looks like a real safety issue to me.  
+
+There are no safety issues.  
+
+If I have a set of integers, and I do this:
+
+   Insert (S, 42, C, B);
+   Insert (S, 42, C, B);
+
+Then in the first call, B returns True, and in the second case, B returns
+False.  There are no errors.  
+
+What people have been asking for is the ability to say this:
+
+   Insert (S, 42);
+   Insert (S, 42);
+
+Which everybody seems to agree is perfectly reasonable.
+
+> It is all too easy to forget to test this parameter.  
+
+The Boolean parameter indicates whether the key was already in the
+container.  There are many times for which there is no reason to test the
+return value, and that is why people are asking for an overloading of insert
+that doesn't have the extra parameters.
+
+> I know that 
+> Matt's philosophy is to trust the programmer, but he has been 
+> repeatedly chided by the ARG for this.
+
+True, but there is no safety issue here.
+
+> My preference would be to change the specification of Insert 
+> as follows:
+> 
+> procedure Insert (Container : in out Map;
+>                   Key       : in     Key_Type;
+>                   New_Item  : in     Element_Type;
+>                   Allow_Replacement : in Boolean;
+>                   Position  :    out Cursor);
+> 
+> If Allow_Replacement is True, Insert will replace any 
+> existing entry in the map with the given key/element pair.  
+
+We have a Replace operation already for maps that has that semantics.  (I
+was toying with the idea that it might be nice to have a Replace for sets
+too.)
+
+> If Allow_Replacement is False, Insert will raise an exception 
+> if the key is already in the map.  In the absence of an 
+> exception, Position will denote the newly inserted/replaced entry.
+
+The Allow_Replacement parameter is an example of "control coupling."  If you
+want replacement behavior, just call Replace!
+
+> I realize that I advocated avoiding changes to the 
+> specification, but this AI is going to be shot down by WG9 if 
+> it contains safety holes.
+
+There are no safety holes.  The issue we had in Palma was with
+Update_Element for sets (it would be possible to change the order relation
+of the element), and Tucker suggested a change to remove any possible
+erroneous behavior.
+
+There is nothing wrong with Insert, except for the fact that we didn't
+overload Insert to omit the position and status parameters.  Mario gave some
+examples of when that operation would be useful.
+
+****************************************************************
+
+From: Pascal Leroy
+Sent: Friday, July 2, 2004  8:15 AM
+
+> I don't see a safety hole here, just a different style of 
+> doing the same thing. Remember the "Success" parameter does 
+> not reflect some kind of 'total' success of the operation, 
+> just that the element was already there. Other, really 
+> abnormal, conditions raise exceptions as expected.
+
+After calling Insert with some key/element pair, if Success is set to
+False, the key/element pair is not really in the map.  Instead, a pair
+key/some-other-element is in the map.  I see this as a violation of an
+invariant of the map.
+
+> But the solution to this is trivial, just add the 
+> operation variants without the out parameters as 'proxies' 
+
+This is trivial from the perspective of the implementers or of the
+language description.  It is _not_ trivial from the perspective of the
+user of the container.  More operations make the container more
+complicated to use, you have to go back to the documentation to find out
+the meaning of all these operations, and at the end of the day you are
+less likely to use the container.  The string packages are like that at
+the moment: they contain so much stuff that I can never remember what's
+there and what's not, so quite often I end up not using them.
+
+****************************************************************
+
+From: Robert A. Duff
+Sent: Friday, July 2, 2004  8:37 AM
+
+> procedure Insert (Container : in out Map;
+>                   Key       : in     Key_Type;
+>                   New_Item  : in     Element_Type;
+>                   Allow_Replacement : in Boolean;
+>                   Position  :    out Cursor);
+
+The way I did this in my container packages is to have two routines:
+one raises an exception if the key is not there, and the other
+replaces with a new key=>value pair.  You could call them
+Insert and Replace.
+
+I don't see the point of a routine that leaves the key associated with
+the *old* value.
+
+****************************************************************
+
+From: Robert A. Duff
+Sent: Friday, July 2, 2004  8:46 AM
+
+> The way I did this in my container packages is to have two routines:
+> one raises an exception if the key is not there, and the other
+                                        ^^^^^^^^^
+
+Oops!  I meant it raises if the key *is* already there.
+Sorry.
+
+> replaces with a new key=>value pair.  You could call them
+> Insert and Replace.
+
+Roughly the same thing works for mappings and for sets.
+
+> I don't see the point of a routine that leaves the key associated with
+> the *old* value.
+
+****************************************************************
+
+From: Marc Criley
+Sent: Friday, July 2, 2004  9:07 AM
+
+> This is trivial from the perspective of the implementers or of the
+> language description.  It is _not_ trivial from the perspective of the
+> user of the container.  More operations make the container more
+> complicated to use, you have to go back to the documentation to find
+out
+> the meaning of all these operations, and at the end of the day you are
+> less likely to use the container.  The string packages are like that
+at
+> the moment: they contain so much stuff that I can never remember
+what's
+> there and what's not, so quite often I end up not using them.
+
+The abundance of operations has certainly not hindered the adoption of
+the C++ STL or the JDK libraries, whose content and complexity far
+exceed that of the existing and proposed Ada libraries.  And this
+despite those collections often having their functionality supplied not
+just by a single class, but a whole inheritance hierarchy of classes.
+
+Whether it's strings or containers, I expect myself and other
+programmers to have a general familiarity with the services available,
+and then to look at the docs (whether in a separate document or embedded
+as comments associated with the declaration--my preference) for the
+details.  My response to being uncertain about the contents of a library
+is not to forgo its use, but to go scan through it to see what's
+available so I can determine if it's useful to me and then take
+advantage of it if it is!
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Friday, July 2, 2004  9:31 AM
+
+
+> After calling Insert with some key/element pair, if Success is set to
+> False, the key/element pair is not really in the map.  Instead, a pair
+> key/some-other-element is in the map.  I see this as a violation of an
+> invariant of the map.
+
+First of all, it is *not* a violation of any map invariant, and the 
+behavior you describe is often exactly what we want.
+
+I gave an example yesterday, when I re-wrote Mario's example.
+
+A histogram is another example (see the !examples of the AI):
+
+Frequency_Histogram : Word_Count_Histograms.Map;
+...
+procedure Log_Word (Word : in String) is
+    C : Cursor;
+    B : Boolean;
+begin
+    Frequency_Histogram.Insert
+      (Key      => Word,
+       New_Item => 0, --YES
+       Position => C,
+       Success  => B);
+
+    declare
+       procedure Increment (Count : in out Integer) is
+       begin
+          Count := Count + 1;
+       end;
+    begin
+       Update_Element (C, Increment'Access);
+    end;
+end Log_Word;
+
+
+This example illustrates why Pascal is wrong.  In the example, we 
+attempt to insert the key value Word and the element value 0.  This 
+locution is quite deliberate.
+
+If the word is already in the map, then this insertion returns False 
+without touching the word count.  We then increment the existing count, 
+which is exactly what we want.
+
+If the word is not already in the map, then this insertion returns True 
+and the value 0 is associated with that key.  We then increment the 
+count, which gives it the value 1, which is exactly what we want.
+
+Notice that in neither case was it necessary to interrogate the Boolean 
+return value.  It can return True or False, but either value is correct. 
+  The value returned simply reflects the state of the map for this 
+insertion, but this is state information we don't care about.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Friday, July 2, 2004  9:52 AM
+
+> I don't see the point of a routine that leaves the key associated with
+> the *old* value.
+
+See my last post containing the word count histogram for an example of 
+why you'd want to preserve the old value.
+
+The only change we need to make to the API here is to add an overloading 
+for Insert that omits the position and success parameters.
+
+At a minimum this overloading should be added to the sets.  (The map has 
+a Replace operation, so we can probably leave the map alone.)
+
+****************************************************************
+
+From: Nick Roberts
+Sent: Friday, July 2, 2004 11:05 AM
+
+Blimey people, please listen to a guy who has spent a lot of time designing
+these kinds of things.
+
+You /must/ have an insertion operation which returns (in an out parameter) a
+boolean (or some other kind of) flag, where the flag indicates what happened
+(e.g. whether the key already existed or not), but does not raise an
+exception either way. This is because there are lots of well-used algorithms
+that rely (for their efficiency) on being able to quickly tell whether a key
+exists, and to insert a new value (only) if it doesn't (and to know if it
+did). This rules out indicating non-existing by raising an exception (way
+too slow), and doing a separate check in advance means searching the tree or
+hash table twice, which is too inefficient.
+
+In Ada at least, it is certainly /nice/ to have another procedure which has
+no flag, and which simply raises an exception if the key already exists.
+This is because there are many situations and algorithms that expect never
+to insert the same key twice (and if it happens, this indicates a problem
+with code or data). Obviously, this procedure could be written by the user
+in terms of the former procedure, but it is so often used it seems justified
+(to me) to provide it.
+
+You also need a replacement operation that returns a flag and a deletion
+operation that returns a flag, for the same reasons.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Friday, July 2, 2004 12:10 AM
+
+> You /must/ have an insertion operation which returns (in an out parameter) a
+> boolean (or some other kind of) flag, where the flag indicates what happened
+> (e.g. whether the key already existed or not), but does not raise an
+> exception either way. This is because there are lots of well-used algorithms
+> that rely (for their efficiency) on being able to quickly tell whether a key
+> exists, and to insert a new value (only) if it doesn't (and to know if it
+> did). This rules out indicating non-existing by raising an exception (way
+> too slow), and doing a separate check in advance means searching the tree or
+> hash table twice, which is too inefficient.
+
+I agree with all of this.  The API supports all of this behavior.
+
+> In Ada at least, it is certainly /nice/ to have another procedure which has
+> no flag, and which simply raises an exception if the key already exists.
+> This is because there are many situations and algorithms that expect never
+> to insert the same key twice (and if it happens, this indicates a problem
+> with code or data). Obviously, this procedure could be written by the user
+> in terms of the former procedure, but it is so often used it seems justified
+> (to me) to provide it.
+
+The user can handle this very easily using the existing API:
+
+declare
+    C : Cursor;
+    B : Boolean;
+begin
+    Insert (S, E, C, B);
+    pragma Assert (B);
+end;
+
+or for a map:
+
+declare
+    C : Cursor;
+    B : Boolean;
+begin
+    Insert (M, K, E, C, B);
+    pragma Assert (B);
+end;
+
+I will state again that if Insert returns False, whether this is an 
+error depends on the application.  I have given many !examples of why a 
+status of False is *not* an error.
+
+> You also need a replacement operation that returns a flag and a deletion
+> operation that returns a flag, for the same reasons.
+
+You certainly don't need another replacement operation that passes back 
+a flag, since the flag-based insert provides a superset of the 
+functionality of replace.  (Look at the implementation of map Replace, 
+which is simply a convenience function that is implemented in terms of 
+Insert).
+
+Replace is just the same as:
+
+declare
+    C : Cursor;
+    B : Boolean;
+begin
+    Insert (M, K, E, C, B);
+
+    if not B then
+       Replace_Element (C, By => E);
+    end if;
+end;
+
+If you want a flag for replacement, then just use the algorithm above.
+
+Delete is a borderline case.  I probably wouldn't bother passing back a 
+flag since:
+
+(1) in the cursor-based delete, the delete must succeed;
+
+(2) in the key-based delete, you can test the value returned by Length 
+before and after the call to determine whether the key was deleted, so 
+no flag is necessary;
+
+(3) instead of using the key-based delete, you can use Find and the 
+cursor-based delete as follows:
+
+declare
+    C : Cursor := Find (M, K);
+begin
+    if Has_Element (C) then
+       Delete (M, C);
+    end if;
+end;
+
+I will repeat my position on this matter: the only change we need to 
+make here is to add an Insert for sets that omits the position and 
+success parameters, and possibly add a Replace operation for sets.  The 
+map is adequate as is.
+
+****************************************************************
+
+From: Robert A. Duff
+Sent: Friday, July 2, 2004  12:29 PM
+
+Nick Roberts says:
+
+> You /must/ have an insertion operation which returns (in an out parameter) a
+> boolean (or some other kind of) flag, where the flag indicates what happened
+> (e.g. whether the key already existed or not), but does not raise an
+> exception either way. This is because there are lots of well-used algorithms
+> that rely (for their efficiency) on being able to quickly tell whether a key
+> exists, and to insert a new value (only) if it doesn't (and to know if it
+> did). ...
+
+I find that convincing.
+
+****************************************************************
+
+From: Adam Beneschan
+Sent: Friday, July 2, 2004  1:19 PM
+
+
+Marius Amado Alves wrote:
+ 
+> > I realize that I advocated avoiding changes to the specification, but this
+> > AI is going to be shot down by WG9 if it contains safety holes.
+> 
+> I don't see a safety hole here, just a different style of doing the same 
+> thing. Remember the "Success" parameter does not reflect some kind of 
+> 'total' success of the operation, just that the element was already 
+> there. Other, really abnormal, conditions raise exceptions as expected.
+
+and Matthew Heaney wrote:
+ 
+> If I have a set of integers, and I do this:
+> 
+>    Insert (S, 42, C, B);
+>    Insert (S, 42, C, B);
+> 
+> Then in the first call, B returns True, and in the second case, B returns
+> False.  There are no errors.  
+
+I agree that this shouldn't necessarily be considered an error (it
+depends on the application), but doesn't this indicate that the
+"Success" parameter is misnamed?  The opposite of "Success" is
+"Failure", which does (to me) carry the connotation of "something
+going WRONG", i.e. an error.  
+
+And sorry, I don't have a better suggestion.  Something like
+We_Were_Able_To_Do_The_Insertion_Because_It_Wasnt_Already_There would
+be a more descriptive name but suffers from other flaws, such as being
+about three times too long :)
+
+I haven't been following this thread religiously, so my apologies if
+this ground has been covered already......
+
+****************************************************************
+
+From: Marius Amado Alves
+Sent: Friday, July 2, 2004  4:22 PM
+
+> I agree that this shouldn't necessarily be considered an error (it
+> depends on the application), but doesn't this indicate that the
+> "Success" parameter is misnamed?
+
+Yes. I had thought about this before. I almost sent an illustration 
+similar to yours, I think it was
+
+    Insert_If_Not_Already_There_Otherwise_Let_It_Be
+     (... It_Was_Not_There_So_I_Have_Inserted : Boolean)
+
+and in the meanwhile I thought of Proper_Insertion or New_Element 
+instead of Success. And the bloody operation is really Ensure_Inserted, 
+no? And to this day I'm still a big fan of "Put" and "Get" (instead of 
+Insert and Element). But I still don't advise any changes now, for the 
+reasons Pascal gave... and took back :-)
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Friday, July 2, 2004  5:35 PM
+
+> I agree that this shouldn't necessarily be considered an 
+> error (it depends on the application), but doesn't this 
+> indicate that the "Success" parameter is misnamed?  The 
+> opposite of "Success" is "Failure", which does (to me) carry 
+> the connotation of "something going WRONG", i.e. an error.  
+
+The boolean parameter simply conveys information about this insertion.  My
+model is that the call is really an insertion attempt, and depending on the
+current state of the container the attempt can succeed or the attempt can
+fail.  The fact that an insertion attempt "fails" does not imply that
+there's an error.  There would only be an error if the post-condition could
+not be satisfied, in which case an exception would be raised.  But as we
+have seen, the post-condition is satisfied (because the element is already
+in the set), so there is no error and hence no exception either.
+
+This behavior is similar to atomically grabbing a lock, and immediately
+returning if the resource is already locked.  See for example the Win32 API
+function TryEnterCriticalSection.
+
+****************************************************************
+
+From: Nick Roberts
+Sent: Friday, July 2, 2004  1:29 PM
+
+> The user can handle this very easily using the existing API:
+...
+
+
+Yes, but it would be quite a bit neater and easier to be able to write the  
+one line:
+
+    Insert (S, E);
+
+for a set, or:
+
+    Insert (M, K, E);
+
+for a map, and this functionality is quite often required in practice.
+
+>> You also need a replacement operation that returns a flag and a
+>> deletion operation that returns a flag, for the same reasons.
+>
+> You certainly don't need another replacement operation that passes
+> back a flag, since the flag-based insert provides a superset of the  
+> functionality of replace.
+
+This isn't the functionality I was thinking of.
+
+> Replace is just the same as:
+>
+> declare
+>     C : Cursor;
+>     B : Boolean;
+> begin
+>     Insert (M, K, E, C, B);
+>
+>     if not B then
+>        Replace_Element (C, By => E);
+>     end if;
+> end;
+
+The replacement operation that I was thinking of would never insert a new  
+key-value pair, it would either: replace the value for a given key, and  
+return 'true' for a flag 'exists'; do nothing and return 'false' for the  
+flag. The above code is not equivalent to this.
+
+The following code would, I think, be equivalent to what I intended:
+
+    declare
+        C : Cursor := Find (M, K);
+    begin
+        if Has_Element (C) then
+           Replace_Element (C, By => E);
+        end if;
+    end;
+
+However, it would be slightly neater and easier to be able to write  
+something like:
+
+    Replace_When_Exists (M, K, E, B);
+
+> Delete is a borderline case.  I probably wouldn't bother passing
+> back a flag since:
+> ...
+> (2) in the key-based delete, you can test the value returned by
+> Length before and after the call to determine whether the key was
+> deleted, so no flag is necessary;
+
+That's fine, since the Length is then acting as a kind of flag. Maybe not  
+the neastest solution (there seems the danger of somewhat obfuscated code).
+
+> (3) instead of using the key-based delete, you can use Find and
+> the cursor-based delete as follows:
+>
+> declare
+>     C : Cursor := Find (M, K);
+> begin
+>     if Has_Element (C) then
+>        Delete (M, C);
+>     end if;
+> end;
+
+But again it would be slightly neater and easier to write something like:
+
+    Delete_When_Exists (S, E, B);
+
+for a set, or:
+
+    Delete_When_Exists (M, K, B);
+
+for a map.
+
+> I will repeat my position on this matter: the only change we need
+> to make here is to add an Insert for sets that omits the position
+> and success parameters, and possibly add a Replace operation for
+> sets.  The map is adequate as is.
+
+I agree with this statement, but I think there is a marginal argument for  
+the addition of replacement and deletion operations with a flag.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Friday, July 2, 2004  5:22 PM
+
+> Yes, but it would be quite a bit neater and easier to be able 
+> to write the  
+> one line:
+> 
+>     Insert (S, E);
+> for a set, or:
+ 
+Yes, but you want this statement to raise an exception if E is already in
+set S.  This is *not* what I want.
+
+The reason we disagree is because we have different pre- and post-conditions
+for set insertion.  Matt's pre- and post-conditions are:
+
+procedure Insert (S : in out Set; E : in ET);
+--pre: True
+--post: Is_In (S, E)
+
+That's why in Matt's universe there are no exceptions: the precondition is
+as weak as possible, and the post-condition guarantees that the element is
+in the set.  If E is already in S, then the post-condition is satisfied, and
+when the post-condition is satisfied then there's no reason to raise an
+exception.
+
+However, in Nick's universe the pre-condition is:
+
+procedure Insert (S : in out Set; E : in ET);
+--pre: not Is_In (S, E)
+--post: Is_In (S, E)
+
+If the element is already in the set, then the precondition has been
+violated, and so an exception is raised.  However, this behavior doesn't
+make a lot of sense, since the invariants of the set abstraction are
+preserved even if we were to weaken the pre-condition (as in Matt's
+universe). 
+
+A note on exception behavior: In general, if a pre-condition is violated
+(and the operation detects this), then it is appropriate to raise an
+exception, in order to preserve the integrity of the abstraction, and to
+signal the fact that the post-condition cannot be satisfied.  The strange
+thing about Nick's semantics is that the post-condition is satisfied even if
+the pre-condition isn't, so what's the point of having an exception?  The
+effect of the call is the same either way.
+
+However, because we want to be good citizens, we're not supposed to violate
+pre-conditions (the exception is there to remind us to change our bad
+behavior), so insertion into a set would have to written like this:
+
+declare
+   C : Cursor := Find (S, E);
+begin
+   if not Has_Element (C) then
+      Insert (S, E);
+   end;
+end;
+
+But now of course we have doubled the amount of work, since the work done by
+Insert simply duplicates the work of Find, which is precisely what we were
+trying to avoid!
+
+At the end of the day, an insertion operation that omits the cursor and
+boolean parameters should have the same behavior as the insertion operation
+that includes those parameters.  If you want insertion that omits the
+parameters to have a different behavior, then the operation should have a
+different name.  This is precisely why the map operation sans cursor and
+boolean is named "Replace" instead of "Insert".
+
+>     Insert (M, K, E);
+> 
+> for a map, and this functionality is quite often required in practice.
+
+I have *never* needed an insertion operation to raise an exception,
+especially when I have an insertion operation that reports whether the
+insertion succeeded.  I don't find the argument "often required in practice"
+very convincing, especially since we have had many actual examples of code
+from me and others that specifically don't need or want the exception.
+
+Instead of calling Insert as above (and getting an exception), then just
+call Replace:
+
+   Replace (M, K, E);
+
+That does everything that the insertion operation above does, but without
+the exception.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Friday, July 2, 2004  8:56 PM
+
+BTW: The duplication of search overhead could be avoided in the code
+fragment above if the API had an insert with hint:
+
+declare
+   C : Cursor := Ceiling (S, E);
+begin
+   if not Has_Element (C) or else E < C then
+      S.Insert (Hint => C, New_Item => E);
+   end if;
+end;
+
+The hint form of insertion guarantees that insertion is O(1) if the hint is
+useful.  This property is satisfied by the result of the Ceiling function.
+
+****************************************************************
+
+From: Nick Roberts
+Sent: Friday, July 2, 2004  9:28 PM
+
+> ...
+> Yes, but you want this statement to raise an exception if E is
+> already in set S.  This is *not* what I want.
+
+Heh. But it /is/ what I want! Actually, for set insertion, I think both  
+operations -- raise exception if already there, do nothing if already  
+there -- would be nice. I would kinda expect the latter to be named  
+something like 'union', but that's pretty cosmetic.
+
+The reason I would like the insertion that would raise an exception is,  
+for example, if I were reading a list of values from a file (or any serial  
+source), and I wanted to check that there were no duplicates. On the other  
+hand, of course, if I just wanted to build up a set and I didn't care  
+about duplicates, I'd want the other kind of insertion.
+
+>>     Insert (M, K, E);
+>>
+>> for a map, and this functionality is quite often required in
+>> practice.
+>
+> I have *never* needed an insertion operation to raise an
+> exception, especially when I have an insertion operation that
+> reports whether the insertion succeeded.  I don't find the
+> argument "often required in practice" very convincing,
+> especially since we have had many actual examples of code
+> from me and others that specifically don't need or want the
+> exception.
+
+Well, all I can say is that I have been writing real application programs  
+for business, science, and the military, for many, many years, and it is  
+has often been a requirement for me. The typical scenario is that I've got  
+a file (or other serial source) to read into a map (or equivalent), and I  
+must check that there are no duplicates (of key).
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Saturday, July 3, 2004  1:05 AM
+
+> The reason I would like the insertion that would raise an exception is,  
+> for example, if I were reading a list of values from a file (or any serial  
+> source), and I wanted to check that there were no duplicates. 
+
+Fine, then use the Success parameter to check that there are no duplicates.
+
+> Well, all I can say is that I have been writing real application programs  
+> for business, science, and the military, for many, many years, and it is  
+> has often been a requirement for me. The typical scenario is that I've got  
+> a file (or other serial source) to read into a map (or equivalent), and I  
+> must check that there are no duplicates (of key).
+
+Fine, then use the Success parameter to check that there are no duplicates.
+
+****************************************************************
+
+From: Nick Roberts
+Sent: Saturday, July 3, 2004  4:37 AM
+
+> Fine, then use the Success parameter to check that there
+> are no duplicates. [x2]
+
+Hehe. Yes, but that's not the point. The whole point of the original  
+suggestion (an insertion without a flag) was not that it would do  
+something that /cannot/ be done by the version with a flag, but that it  
+would be a bit more convenient in many typical cases.
+
+It's merely the difference between:
+
+    Account: Account_Record;
+    ...
+    while not End_of_File(F) loop
+       Read(F,Account);
+       Insert(M,Account.ID,Account.Balance);
+    end loop;
+
+and:
+
+    Account: Account_Record;
+    Okay: Boolean;
+    ...
+    while not End_of_File(F) loop
+       Read(F,Account);
+       Insert(M,Account.ID,Account.Balance,Okay);
+       raise Duplicate_Account when not Okay;
+    end loop;
+
+so I would have to admit that it's almost a trivial convenience. But this  
+/is/ a scenario that occurs very often in practice, and I think that  
+actually justifies the inclusion of the non-flagged insertion.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Saturday, July 3, 2004 11:41 AM
+
+The point I was trying to make is that the library doesn't know whether the
+statement:
+
+   Insert (M, K, E);
+
+is an error, meaning that it should propagate an exception if key K is
+already in map M.  Only the library user can know whether a duplicate key is
+an error.  (We have seen examples of both interpretations.)
+
+
+> It's merely the difference between:
+[example snipped]
+
+I would have handled a duplicate key by simply ignoring it.  Or I would have
+used Replace.
+
+My argument is that the library should be neutral wrt duplicate key
+behavior.
+
+> so I would have to admit that it's almost a trivial 
+> convenience. But this  
+> /is/ a scenario that occurs very often in practice, and I think that  
+> actually justifies the inclusion of the non-flagged insertion.
+
+It's helpful to differentiate map and sets here.  Everyone seems to agree
+that the set statement:
+
+  Insert (S, E);
+
+makes sense, since if E is already in the map then the post-condition is
+satisfied.
+
+The debate is about how to how to interpret the map statement:
+
+  Insert (M, K, E);
+
+There are two possible interpretations if K is already in M: 
+
+(1) This is an error, and a duplicate key exception is propagated.  
+(2) This is not an error, and there are no exceptions.
+
+You could justify (1) on the grounds that since value E is not entered into
+the map, then the caller should be alerted to this fact.  However, a reason
+to reject interpretation (1) is that you can simply call Replace to get that
+behavior.
+
+That leaves (2).  This has the benefit of symmetry with the corresponding
+insertion operation for sets.  The meaning of these operations is "if the
+key is already in the container, then do nothing."  Another meaning is "this
+is the same as the canonical insertion operation, except that the cursor and
+boolean parameters are omitted."
+
+Obviously I favor interpretation (2).
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Saturday, July 3, 2004  1:12 PM
+
+I think I've got to confess that I didn't expect Replace to have these  
+semantics, and I didn't read the AI carefully enough. Sorry.
+
+I think perhaps, in the light of the lateness in the day, and the fact  
+that these container abstractions were always intended to be quite  
+low-level, upon which users would generally build higher-level  
+abstractions, it's not worth arguing about a few extra convenience  
+procedures too much.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Saturday, July 3, 2004  3:59 PM
+
+...
+> The debate is about how to how to interpret the map statement:
+>
+>   Insert (M, K, E);
+>
+> There are two possible interpretations if K is already in M:
+>
+> (1) This is an error, and a duplicate key exception is propagated.
+> (2) This is not an error, and there are no exceptions.
+>
+> You could justify (1) on the grounds that since value E is not
+> entered into the map, then the caller should be alerted to this fact.
+> However, a reason to reject interpretation (1) is that you can simply
+> call Replace to get that behavior.
+
+Ugh. Something called "Replace" should not have insertion semantics; that
+is, replacing something that doesn't exist is an error in my view. Probably
+the primary cause of confusion in this discussion is that "Replace" might do
+an insert, and "Insert" might not do an insert. Both of these seem goofy to
+me.
+
+But, as Nick said, it's probably more important that these are consistent
+and stable than that they match a particular world view (mine :-).
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Saturday, July 3, 2004  4:47 PM
+
+I realized after I composed my last message that another possibility is to
+interpret the statement:
+
+   Insert (M, K, E);
+
+as having the same behavior as the operation we're calling "Replace."  That would
+allow us to either get rid of exising Replace operation, or keep it but give it
+the (slightly different) semantics Nick described in his earlier post.  (It
+sounds like Randy's leaning that way already.)
+
+****************************************************************
+
+From: Pascal Leroy
+Sent: Monday, July 5, 2004  4:03 AM
+
+Randy wrote:
+
+> Ugh. Something called "Replace" should not have insertion 
+> semantics; that is, replacing something that doesn't exist is 
+> an error in my view. Probably the primary cause of confusion 
+> in this discussion is that "Replace" might do an insert, and 
+> "Insert" might not do an insert. Both of these seem goofy to me.
+
+Agreed.  This is hopelessly confusing.
+
+> But, as Nick said, it's probably more important that these 
+> are consistent and stable than that they match a particular 
+> world view (mine :-).
+
+None of this sound "consistent" or "stable" to me.  At any rate the only
+world view that matters is that of the Heads of Delegations who will vote
+at the next WG9 meeting.  In light of the discussion at the last meeting,
+I see trouble ahead.  But that may only be my inexperience...
+
+****************************************************************
+
+From: Marius Amado Alves
+Sent: Monday, July 5, 2004  9:32 AM
+
+Now you're scaring me! You mean the proposal seriously risks not pass 
+simply because of this?
+
+Would an Note help?
+
+Operations Replace and Insert have a slightly more complex semantics 
+than a direct interpretation of their names. Namely, the effect is 
+conditioned by the prior existence of the specified key:
+
+                         Replace          Insert
+------------------------------------------------------
+Key is already there    replace item     no change
+Key is not there yet    add key, item    add key, item
+------------------------------------------------------
+
+****************************************************************
+
+From: Pascal Leroy
+Sent: Monday, July 5, 2004 10:38 AM
+
+I am saying (repeating, actually) that some countries have expressed
+concerns regarding the safety of the containers library as it stood at the
+time of the last WG9 meeting.  I suspect that these countries will
+ultimately oppose this AI if they think that there are safety issues.
+Whether that will be the majority (which would effectively kill the AI) or
+not is an interesting question.  Whether the said countries would go so
+far as to oppose the entire Amendment is another interesting question.  As
+you can imagine, we can just go forward and count the votes, but the
+outcome may be unpleasant.  It's much better to find a consensus before
+the vote.
+
+In the case at hand I am uncomfortable with the notion that Replace
+sometimes has an insertion semantics and Insert sometimes has a no-op
+semantics.  My opinion doesn't count, however, as I am not voting at WG9.
+Furthermore, I may just be overreacting.  However, I have a feeling that
+this dodgy semantics is going to be hard to swallow in some quarters.
+
+Back to the technical discussion.  As far as I can tell we have identified
+five different behaviors, all of which make sense depending on the
+application needs:
+
+1 - Insert and fail if key is already in the map.
+2 - Insert and replace element if key is already in the map.
+3 - Insert and do nothing if key is already in the map.
+4 - Replace and fail if key is not in the map.
+5 - Replace and insert if key is not in the map.
+
+My advice would be to provide all five behaviors using five subprograms
+with clearly distinct names.  The notion of an out parameter that you can
+drop on the floor is sure to make people nervous.  On the other hand,
+no-one is going to argue that there is a safety problem if you called Foo
+when you really wanted to call Bar.
+
+Just my two cents...
+
+****************************************************************
+
+From: Jeffrey Carter
+Sent: Monday, July 5, 2004 12:02 PM
+
+There's also
+
+6 - Replace and do nothing if key is not in the map.
+
+> My advice would be to provide all five behaviors using five subprograms
+> with clearly distinct names.  The notion of an out parameter that you can
+> drop on the floor is sure to make people nervous.  On the other hand,
+> no-one is going to argue that there is a safety problem if you called Foo
+> when you really wanted to call Bar.
+
+I'm not sure providing 6 different insert and replace operations is a 
+good idea, either. One of each, with behaviors that don't overlap, 
+combined with query operations that allow building the other 4, may be 
+the clearest approach. That would argue for the operations that fail.
+
+****************************************************************
+
+From: Jean-Pierre Rosen
+Sent: Monday, July 5, 2004 12:13 PM
+
+I'm a bit afraid of having to many subprograms...
+Why not follow the example of the "Drop" parameter in Ada.Strings.Fixed,
+i.e. having an enumeration specifying behaviour?
+
+****************************************************************
+
+From: Nick Roberts
+Sent: Monday, July 5, 2004 12:16 PM
+
+I can suggest an emergency alteration to the AI. The changes required  
+don't seem to be drastic. There are four cases covered here (cases 2 and 5  
+that Pascal suggested seem to be the same).
+
+> 3 - Insert and do nothing if key is already in the map.
+
+procedure Insert (Container : in out Map;
+                   Key       : in     Key_Type;
+                   New_Item  : in     Element_Type;
+                   Position  :    out Cursor;
+                   Success   :    out Boolean);
+
+If Length (Container) equals Size (Container), then Insert calls Resize to
+resize Container to some larger value. Insert then uses Hash and Is_Equal_Key
+to check if Key is already present in Container. If a key matches, Success
+returns False and Position designates the element with the matching key.
+Otherwise, Insert allocates a new node, initializes it to Key and New_Item, and
+adds it to Container. Success returns True and Position designates the
+newly-inserted node. Any exceptions raised during allocation are propagated
+and Container is not modified.
+
+[This is exactly as in the current AI.]
+
+> 1 - Insert and fail if key is already in the map.
+
+procedure Insert (Container : in out Map;
+                   Key       : in     Key_Type;
+                   New_Item  : in     Element_Type;
+                   Position  :    out Cursor);
+
+[One possible wording is:]
+
+Insert without a Success parameter is equivalent to Insert with a
+Success parameter with the difference that if Success would have
+been False then this operation propagates the exception
+Insertion_Error.
+
+[or another possible wording is:]
+
+If Length (Container) equals Size (Container), then Insert calls Resize to
+resize Container to some larger value. Insert then uses Hash and  
+Is_Equal_Key
+to check if Key is already present in Container. If a key matches,  
+propagates
+the exception Insertion_Error and Position designates the element with the
+matching key. Otherwise, Insert allocates a new node, initializes it to Key
+and New_Item, and adds it to Container. Position designates the newly-
+inserted node. Any exceptions raised during allocation are propagated and
+Container is not modified.
+
+> 2 - Insert and replace element if key is already in the map.
+> 5 - Replace and insert if key is not in the map.
+
+procedure Insert_or_Replace (Container : in out Map;
+                              Key       : in     Key_Type;
+                              New_Item  : in     Element_Type);
+
+Insert_or_Replace inserts Key and New_Item as per Insert, with the
+difference that if Key is already in the map, then this operation
+assigns New_Item to the element associated with Key. Any exceptions
+raised during assignment are propagated.
+
+[This procedure is named Replace in the current AI.]
+
+> 4 - Replace and fail if key is not in the map.
+
+procedure Replace (Container : in out Map;
+                    Key       : in     Key_Type;
+                    New_Item  : in     Element_Type);
+
+Replace assigns New_Item to the element associated with Key. If Key is
+not already in the map, then this operation propagates the exception
+Replacement_Error, and does not perform any assignment. Any exceptions
+raised during assignment are propagated.
+
+[This procedure has the same profile as Replace in the current AI, but the  
+wording is changed to provide the exception raising semantics.]
+
+Instead of the name 'Insert_or_Replace' I have suggested, a name such as  
+'Emplace' might be considered a little more succinct.
+
+We need to add the two exceptions Insertion_Error and Replacement_Error to  
+the base containers package:
+
+~~~
+
+The library package Containers has the following declaration:
+
+package Ada.Containers is
+    pragma Pure;
+
+    type Hash_Type is mod <Implementation-Defined>;
+
+    type Size_Type is range 0 .. <implementation-defined>;
+
+    Insertion_Error, Replacement_Error: exception;
+
+end Ada.Containers;
+
+Hash_Type represents the range of the result of a hash function. Size_Type
+represents the (potential or actual) size (number of elements) of a  
+container.
+
+Insertion_Error is raised when insertion into a container fails.
+Replacement_Error is raised when replacement of a value in a container  
+fails.
+
+~~~
+
+I actually think we should refrain from trying to add any further  
+operations to the AI now, since there could be a combinatorial explosion  
+due to the other permutations (e.g. supplied value versus default value  
+for insertion, fail silently versus raise exception versus return a flag  
+for deletion). I guess it'll be difficult to make any changes at all.
+
+****************************************************************
+
+From: Nick Roberts
+Sent: Monday, July 5, 2004 12:37 PM
+
+Possibly the following procedure should also be added:
+
+~~~
+
+procedure Replace (Container : in out Map;
+                    Key       : in     Key_Type;
+                    New_Item  : in     Element_Type;
+                    Success   :    out Boolean);
+
+~~~
+
+I'll write a wording later. The idea is that it assigns New_Item if Key  
+exists and sets Success to True, otherwise it sets Success to False. It  
+could be argued that this procedure would not be much better than finding  
+the key into a cursor, and then testing the cursor (and doing a  
+Replace_Element if it is not No_Element).
+
+> I'm not sure providing 6 different insert and replace operations
+> is a good idea, either. One of each, with behaviors that don't
+> overlap, combined with query operations that allow building the
+> other 4, may be the clearest approach. That would argue for the
+> operations that fail.
+
+I think this is basically right, and if we think of adding any operations  
+at all at this stage, it should be as few as possible. I think it's  
+probably okay for the Delete to silently do nothing if the given Key does  
+not exist, although this behaviour might be surprising to some programmers.
+
+****************************************************************
+
+From: Marius Amado Alves
+Sent: Monday, July 5, 2004 12:35 PM
+
+> I'm not sure providing 6 different insert and replace operations is a 
+> good idea, either. One of each, with behaviors that don't overlap, 
+> combined with query operations that allow building the other 4, may be 
+> the clearest approach. That would argue for the operations that fail.
+
+Whatever you do, remember that 'algebraic' behavior is not the only 
+factor in the design, there is also the fact that these operations 
+perform search, combined with the fact that many idioms can profit on 
+this fact for efficiency if that result is made known or used directly 
+by the 'strange' semantics (e.g. Replace doing an insertion), usually to 
+avoid searching twice, as already well exemplified. The current 
+operations represent well a set of primitives that takes this 'unpure' 
+but required factors into consideration. Rename them Extended_Replace 
+and Extended_Insert and provide the 'pure' operations with the 
+'unextended' names perhaps.
+
+****************************************************************
+
+From: Nick Roberts
+Sent: Monday, July 5, 2004 12:56 PM
+
+On Mon, 5 Jul 2004 19:13:00 +0200, Jean-Pierre Rosen <rosen@adalog.fr>  
+wrote:
+
+> I'm a bit afraid of having to many subprograms...
+
+Yes, I think we all are!
+
+> Why not follow the example of the "Drop" parameter in
+> Ada.Strings.Fixed, i.e. having an enumeration specifying
+> behaviour?
+
+I think that's a reasonable idea. We could add:
+
+    type Failure_Action is (Ignore, Error);
+
+to the base package Ada.Containers and then add a parameter such as:
+
+    On_Failure: Failure_Action := Error
+
+to the Insert, Replace, and Delete operations that didn't have a Success  
+parameter. This parameter could be named 'When_Exists' or 'When_Absent' as  
+appropriate.
+
+****************************************************************
+
+From: Marius Amado Alves
+Sent: Monday, July 5, 2004  2:22 PM
+
+Someone had already proposed a 'control coupled' design, and with only 
+Boolean types, which is better than this because it has less special 
+types to manage. (Those special types in the standard String operations 
+are a pain, each time I need them here I go for the RM to find out 
+exactly what package do I have to withen, and then I have to use "use" 
+to keep my sanity writing when the calls.)
+
+And some say control coupling is a bad thing, whatever types you use.
+
+****************************************************************
+
+From: Nick Roberts
+Sent: Monday, July 5, 2004  3:50 PM
+
+I too think control-coupled procedures are often a bad idea, generally  
+because they can make the implementations of those procedures a logical  
+tangle (of deeply nested ifs and cases), which can be bad for correctness  
+and maintenance, and sometimes significantly bad for performance.
+
+On the other hand, a proliferation of procedures, where you have many  
+different variations on a theme, are also a bad idea. Indeed, in this  
+case, I'd say a worse idea.
+
+As for using Booleans, I've tried that myself in the past and gradually  
+come to the conclusion that using enumerated types with (more) meaningful  
+names is usually preferable. The name availability problem can be  
+ameliorated by techniques such as replication within the generic  
+specification. For example, one could add the declarations:
+
+    subtype Failure_Action is Ada.Containers.Failure_Action;
+    Ignore: constant Failure_Action := Ada.Containers.Ignore;
+    Error:  constant Failure_Action := Ada.Containers.Error;
+
+to the specification of Ada.Containers.Hashed_Maps.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Monday, July 5, 2004  9:11 PM
+
+> I am saying (repeating, actually) that some countries have 
+> expressed concerns regarding the safety of the containers 
+> library as it stood at the time of the last WG9 meeting.  
+
+What "safety" issue?  The only one I can think of is the behavior of
+Update_Element for sets.  Tucker suggested a change to remove the erroneous
+behavior and now all is well.  Were there some others?
+
+> In the case at hand I am uncomfortable with the notion that 
+> Replace sometimes has an insertion semantics and Insert 
+> sometimes has a no-op semantics.
+
+Then why not just rename "Replace" to "Insert" instead?  We would then have:
+
+(1) Insert (Container : in out Map;
+            Key       : in     Key_Type;
+            New_Item  : in     Element_Type;
+            Position  :    out Cursor;
+            Success   :    out Boolean);
+
+If the Key is not in the map Container, then insert a new value pair Key and
+New_Item in the map, and set Success to True.  If the Key is already in the
+map, the set Success to False and don't do anything else.
+
+This is what we have right now.  This has the same semantics as the
+similarly-named operation in the STL. 
+
+(2) Insert (Container : in out Map;
+            Key       : in     Key_Type;
+            New_Item  : in     Element_Type);
+
+If Key is not in the map, then insert a new value pair Key and New_Item in
+the map.  If Key is already in the map, then assign New_Item to the element
+associated with Key.
+
+We have this operation in the API already, but it's called "Replace".
+
+We could also add another operation, with behavior not in the current API:
+
+(3) Replace (Container : in out Map;
+             Key       : in     Key_Type;
+             New_Item  : in     Element_Type);
+
+If Key is not in the map, then do nothing.  If Key is already in the map,
+then assign New_Item to the element associated with Key.
+             
+
+> My opinion doesn't count, 
+> however, as I am not voting at WG9. Furthermore, I may just 
+> be overreacting.  However, I have a feeling that this dodgy 
+> semantics is going to be hard to swallow in some quarters.
+
+I don't know which semantics are "dodgy," since these are the same semantics
+(for Insert, anyway) as for the STL, which is already an ISO standard.
+
+ 
+> Back to the technical discussion.  As far as I can tell we 
+> have identified five different behaviors, all of which make 
+> sense depending on the application needs:
+> 
+> 1 - Insert and fail if key is already in the map.
+
+See (1) above.
+
+> 2 - Insert and replace element if key is already in the map.
+
+See (2) above.
+
+> 3 - Insert and do nothing if key is already in the map.
+
+Hmmm.  What's the difference between "Insert and fail" and "Insert and do
+nothing"?  Same as (1) above?
+
+
+> 4 - Replace and fail if key is not in the map.
+
+If by "fail" you mean "do nothing," then see (3) above.
+
+
+> 5 - Replace and insert if key is not in the map.
+
+I don't know what this means.  Sounds like (2) above.
+
+
+> My advice would be to provide all five behaviors using five 
+> subprograms with clearly distinct names.  
+
+The consensus seems to be it's a problem that the operation we're now
+calling "Replace" can insert a new key if it doesn't already exist in the
+map.  That's an easy problem to solve: just name the operation "Insert"
+instead.
+
+
+> The notion of an 
+> out parameter that you can drop on the floor is sure to make 
+> people nervous.  
+
+I can't imagine why.  Nick gave a nice summary of the rationale for such an
+operation, and I have given several examples of why conditional insertion is
+both useful and necessary.
+
+Note again that this is exactly what the STL does.
+
+
+> On the other hand, no-one is going to argue 
+> that there is a safety problem if you called Foo when you 
+> really wanted to call Bar.
+
+As far as I can tell, some people have objected to the fact that the
+operation named "Replace" can insert a new key.  So either rename it
+"Insert," or just get rid of it.  This is a very minor change.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Monday, July 5, 2004  9:20 PM
+
+> I'm a bit afraid of having to many subprograms...
+> Why not follow the example of the "Drop" parameter in 
+> Ada.Strings.Fixed, i.e. having an enumeration specifying behaviour?
+
+
+As others have already pointed out, this is an example of "control
+coupling."  This is my least favorite aspect of the Ada.Strings.* API.
+
+With the Insert we have now (the map operation that has 5 parameters), you
+can build any of the other behaviors.
+
+The operation named "Replace" is merely a convenience function, to either
+insert a new key if it isn't in the map, or replace the current element
+value if the key is already in the map.  The issue seems to be that an
+operation named "Replace" can insert a new key.  All we need to do is rename
+the operation "Insert".
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Monday, July 5, 2004  9:24 PM
+
+> I can suggest an emergency alteration to the AI. The changes 
+> required  
+> don't seem to be drastic. 
+
+Well, adding new exceptions to the API is a very drastic change.  It's also
+completely unnecessary.
+
+All we need to do is change the name of the operation "Replace" to "Insert",
+and all is well.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Monday, July 5, 2004  9:30 PM
+
+> I think this is basically right, and if we think of adding 
+> any operations  
+> at all at this stage, it should be as few as possible. 
+
+We don't need to add any new operations.  Just rename "Replace" to "Insert".
+
+(Note that I would be in favor of creating a new replacement-style operation
+that has the semantics you mentioned in your post a couple of days ago, but
+even that can be easily built from the Find and Replace_Element primitives.)
+
+> I think it's  
+> probably okay for the Delete to silently do nothing if the 
+> given Key does  
+> not exist, although this behaviour might be surprising to 
+> some programmers.
+
+I can't image why.  The post-condition is that the key isn't in the map.  If
+the key isn't in the map before the call, then the post-condition is
+satisfied.  What's surprising about that?  
+
+****************************************************************
+
+From: Pascal Leroy
+Sent: Tuesday, July 6, 2004  2:15 AM
+
+> > I am saying (repeating, actually) that some countries have 
+> expressed 
+> > concerns regarding the safety of the containers library as 
+> it stood at 
+> > the time of the last WG9 meeting.
+> 
+> What "safety" issue?  The only one I can think of is the 
+> behavior of Update_Element for sets.  Tucker suggested a 
+> change to remove the erroneous behavior and now all is well.  
+> Were there some others?
+
+If you don't mind, I am not going to disclose private discussions on a
+public forum.  I was only trying to wave a red flag.
+
+"Safety" is not merely "erroneousness".  Consider two changes that were
+made by the ARG recently: (1) the definition of map equality was changed
+to compare the key/element pairs, instead of only the elements; and (2)
+functions Lower_Bound and Upper_Bound were made symmetrical.  There were
+no erroneousness issues in these cases; still, without these changes the
+AI was sure to be dead-on-arrival, take my word for it.  The reason is
+that semantics that are "surprising" can very easily lead to programming
+errors, so it is best to make the semantics as pure and "natural" as
+possible, given the other constraints.  Of course, what counts as
+"surprising" is in the eye of the beholder to some extent.  But the fact
+that there has been so much discussion on Insert and Replace recently is
+probably an indication that these operations are not exactly WYSIWYG.
+
+> I don't know which semantics are "dodgy," since these are the 
+> same semantics (for Insert, anyway) as for the STL, which is 
+> already an ISO standard.
+
+This is completely bogus.  The fact that STL is an ISO standard is
+irrelevant.  AI-302 will be judged based on how well it preserves and
+extends the "good properties" of Ada: safety, readability, portability,
+etc.  If it can be compatible with STL, so much the better, but if it
+cannot, too bad.  In particular, if the semantics of some operations are
+felt to be inadequate, repeating the mantra "it's the same as STL" won't
+help.
+
+****************************************************************
+
+From: Pascal Leroy
+Sent: Tuesday, July 6, 2004  2:31 AM
+
+Nick wrote:
+
+> I too think control-coupled procedures are often a bad idea, 
+> generally because they can make the implementations of those 
+> procedures a logical tangle (of deeply nested ifs and cases), 
+> which can be bad for correctness and maintenance, and 
+> sometimes significantly bad for performance.
+
+Note that we should really be designing this library for the user, not for
+the implementer.  After all, there will only be a handful implementations
+of these units (the compiler vendors, plus a few Matts here and there).
+These implementations will hopefully be extensively tested by the ACATS.
+So correctness and maintenance of the library itself is only a secondary
+concern.
+
+The real issue is correctness and maintenance of the code on the client
+side.  Here I don't necessarily see control coupling as bad.
+Syntactically, there is very little difference between:
+
+	Insert_And_Replace_If_Present (...);
+
+and:
+
+	Insert (Replace_If_Present => True, ...);
+
+And in fact, judicious use of defaulted parameters can improve the
+readability of the calls (you demonstrated how a defaulted parameter could
+be use to force detection of errors by default).  Furthermore, control
+coupling makes it possible to dynamically/globally switch some options
+(for instance, detect errors based on the value of an environment
+variable), something which is hard to do with multiple entry points.
+
+> On the other hand, a proliferation of procedures, where you 
+> have many different variations on a theme, are also a bad 
+> idea. Indeed, in this case, I'd say a worse idea.
+> 
+> As for using Booleans, I've tried that myself in the past and 
+> gradually come to the conclusion that using enumerated types 
+> with (more) meaningful names is usually preferable.
+
+I agree with Nick here.
+
+****************************************************************
+
+From: Cyrille Comar
+Sent: Tuesday, July 6, 2004  4:42 AM
+
+Pascal Leroy writes:
+ > It's much better to find a consensus before the vote.
+
+I strongly agree. Better have a consensus now and a some official base
+for Ada containers as part of the standard rather than wait for a non
+widely discussed defacto standard to emerge.
+
+****************************************************************
+
+From: Nick Roberts
+Sent: Tuesday, July 6, 2004  6:33 AM
+
+I will play devil's advocate, and make a proposal for changes to
+the AI, based on the idea of having a parameter to control behaviour
+when certain pre-conditions are not met.
+
+Change the base package:
+
+~~~
+
+The library package Containers has the following declaration:
+
+package Ada.Containers is
+    pragma Pure;
+
+    type Hash_Type is mod <Implementation-Defined>;
+
+    type Size_Type is range 0 .. <implementation-defined>;
+
+    type Error_Action is (Ignore, Error);
+
+    Key_Error: exception;
+
+end Ada.Containers;
+
+Hash_Type represents the range of the result of a hash function. Size_Type
+represents the (potential or actual) size (number of elements) of a  
+container.
+
+Key_Error and Error_Action are used in conjunction with certain container
+operations, for handling the situation when a key does or does not exist,
+as described below.
+
+~~~
+
+All of the following changes are for the Ada.Containers.Hashed_Maps
+generic package.
+
+Add the following declarations into the package listing:
+
+~~~
+
+    subtype Error_Action is Ada.Containers.Error_Action;
+
+    Ignore: constant Error_Action := Ada.Containers.Ignore;
+    Error:  constant Error_Action := Ada.Containers.Error;
+
+~~~
+
+Add the following wording after that for the existing Insert:
+
+~~~
+
+procedure Insert (Container  : in out Map;
+                   Key        : in     Key_Type;
+                   New_Item   : in     Element_Type;
+                   Position   :    out Cursor;
+                   Key_Exists : in     Error_Action := Error);
+
+Insert without a Success parameter is equivalent to Insert with a
+Success parameter with the difference that if Success would have been
+False then this operation does: nothing, if Key_Exists is Ignore;
+propagates the exception Key_Error, if Key_Exists is Error.
+
+~~~
+
+Add the specification of this procedure into the package listing.
+
+Rename the procedure 'Replace' as 'Insert_Or_Replace' in the package
+listing and in the wording.
+
+Add the following wording after that for Insert_Or_Replace:
+
+~~~
+
+procedure Replace (Container  : in out Map;
+                    Key        : in     Key_Type;
+                    New_Item   : in     Element_Type;
+                    Key_Absent : in     Error_Action := Error);
+
+Replace assigns New_Item to the element associated with Key. If Key is
+not already in the map, then this operation does not perform any
+assignment and does: nothing, if Key_Absent is Ignore; propagates the
+exception Key_Error, if Key_Absent is Error. Any exceptions raised
+during assignment are propagated.
+
+~~~
+
+Add the specification of this procedure into the package listing.
+
+Replace the current wording for the Delete procedure with Key with:
+
+~~~
+
+procedure Delete (Container  : in out Map;
+                   Key        : in     Key_Type;
+                   Key_Absent : in     Error_Action := Error);
+
+Delete uses Hash and Is_Equal_Key to check if Key is present in
+Container. If Key matches the key of a node, Delete removes the node
+ from the map and then deallocates the node. If Key is not already in the
+map, then this operation does: nothing, if Key_Absent is Ignore;
+propagates the exception Key_Error, if Key_Absent is Error.
+
+AARM Notes: Delete should only compare elements that hash to the same
+bucket in the hash table. Delete with Key_Absent=Ignore should work on
+an empty map; nothing happens in that case.
+
+~~~
+
+Replace the current specification of this procedure in the package
+listing with the specifcation above.
+
+I think this idea raises an issue which needs consideration. Many other
+operations raise Constraint_Error (e.g. if a key does not exists, or a
+cursor is No_Element). One possibility is for Key_Error to be removed
+ from this change, and for Constraint_Error to be raised in its place.
+Another possibility is to raise Key_Error instead of Constraint_Error in
+many further places in the AI; in this case a more generalised name,
+such as Container_Error, might be more appropriate. I feel the latter
+option would probably be helpful to the user for debugging.
+
+I'll happily suggest a set of changes to Ordered_Sets if the above seem
+at all acceptable.
+
+****************************************************************
+
+From: Marius Amado Alves
+Sent: Tuesday, July 6, 2004  8:23 AM
+
+>>As for using Booleans, I've tried that myself in the past and 
+>>gradually come to the conclusion that using enumerated types 
+>>with (more) meaningful names is usually preferable.
+> 
+> I agree with Nick here.
+
+You guys need to take a deep breath or something :-) For the case at
+hand an enumeration with only two values instead of a Boolean is just
+useless baggage.
+
+But I'm against *any* control coupling here. FWIW I agree with Matt's
+set of proposals: simply rename Replace to Insert, maybe rename Success
+to Proper_Insert or something, maybe add the flagless variant, keep the
+rest of the map spec as is, and adjust the sets spec.
+
+****************************************************************
+
+From: Michael Yoder
+Sent: Tuesday, July 6, 2004  11:35 AM
+
+On the semantics of Insert: speaking mathematically, the notion that 
+"Insert might not insert" doesn't bother me.  Insertion of an element 
+ought to be equivalent to finding the union with a singleton set, and 
+yes, that means if the element is already there the set doesn't change. 
+  Still, I can accept that programmers' intuitions might not match those 
+of mathematicians in general or mine in particular.  If I insert an ace 
+of spades into a poker hand already containing one, this is a situation 
+which (expressed delicately) indicates an error condition.  I don't 
+find such analogies appropriate, but others might.
+
+For sets, I suggest adding a procedure Insert_New.  Speaking coarsely, 
+it acts just like Insert, but raises an exception if the inserted 
+element is already present.
+
+For maps, I suggest these names for the five cases enumerated by Pascal:
+
+On Jul 5, 2004, at 11:38 AM, Pascal Leroy wrote:
+
+>
+> Back to the technical discussion.  As far as I can tell we have identified
+> five different behaviors, all of which make sense depending on the
+> application needs:
+>
+> 1 - Insert and fail if key is already in the map.
+Insert_New
+> 2 - Insert and replace element if key is already in the map.
+Insert
+> 3 - Insert and do nothing if key is already in the map.
+Insert_If_New
+> 4 - Replace and fail if key is not in the map.
+Replace_Old
+> 5 - Replace and insert if key is not in the map.
+Replace
+>
+> My advice would be to provide all five behaviors using five subprograms
+> with clearly distinct names.  The notion of an out parameter that you can
+> drop on the floor is sure to make people nervous.  On the other hand,
+> no-one is going to argue that there is a safety problem if you called Foo
+> when you really wanted to call Bar.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Sunday, July 11, 2004  9:03 PM
+
+> There are similar Insert procedures for both Ordered_Sets
+> and Hashed_Maps with highly useful Position and Success 
+> parameters.  Sometimes however, it seems somewhat disturbing 
+> to see declarations of variables for Position and Success 
+> that are not read because it is considered safe to ignore 
+> them.  It might be known that Insert will succeed without 
+> surprises (ceteris paribus).  Examples include adding initial 
+> values to a library level container, like 69 keywords, or 
+> adding known border values to ordered containers.
+
+In the case of a set, the postcondition is satisfied no matter what value is
+returned, so yes there should be convenience operation that omits the cursor
+and boolean parameters, since they only add syntactic noise.
+
+In the case of a map, you already have a convenience function called
+"Replace" that omits the cursor and boolean parameters, and it is defined to
+replace the element associated with the key if the key already exists in the
+map.
+
+I had originally named the three-parameter insertion operation for maps
+"Insert", but was concerned that developers would think that it has the same
+behavior as the five-parameter Insert, but with the cursor and boolean
+parameters omitted.  Since the behavior of the three-parameter operation was
+kind of like Replace_Element (the difference is that it can insert a new
+key), I named the operation "Replace".  
+
+However, others have argued that the fact that it can insert a new key means
+it should be named Insert, which is OK with me.
+
+So ultimately your request is for adding a convenience operation to the set.
+There is already a convenience operation for maps, but it is currently named
+Replace. 
+
+
+> In a 
+> sense, this might also make Ordered_Sets and Hashed_Maps 
+> correspond more closely to Vectors and Doubly_Linkes_List 
+> with regard to Insert procedures.
+
+Yes.  
+
+Here's some history.  My original proposal was quite long, and the ARG asked
+me to cut it down.  As I was re-writing the proposal to make it shorter, I
+looked for operations that were possible candidates for removal, and one of
+the operations I removed was the two-parameter insert for sets.  This
+appears to have been a mistake, but it's no big deal to add it back in.  We
+deliberately deployed a reference implementation to discover API bugs early,
+and this looks like one.  (If you have an Ada 2005 compiler that lets you
+compile children of package Ada, then you can use the a-c*.ad[sb] version of
+the library.  It's at the tigris site.)
+
+
+> (When using maps, I sometimes think of them as sparse
+> arrays. With arrays, I can just write
+> 
+> 	ary(key) := value;
+> 
+> and be done.)
+
+This is exactly how the STL works:
+
+  ary[key] = value;
+
+You can even do stuff like:
+
+  ++ary[key];
+
+and it's guaranteed to work, since the standard says that if key isn't in
+the map then it is inserted, and its element is constructed with its default
+value.  The index operation then returns a reference to the element
+(newly-inserted or not), which the increment operator then works on.
+
+In the Ada case, you have to pass in the default value explicitly (see my
+histogram example), but it works the same as the index operation above (the
+syntax is different, of course):
+
+   Ary.Insert (Key, 0, C, B);
+
+   declare
+      procedure Increment (I : in out Integer) is
+      begin
+         I := I + 1;
+      end;
+   begin
+      Update_Element (C, Increment'Access);
+   end;
+
+This is equivalent to the C++ statement above.  Note that the algorithm
+above works no matter what value is returned for B.  The only thing we
+require is that the insertion be conditional; that is, if the key is already
+in the map, then leave the associated element alone.  It is certainly not an
+"error" if B is false and the existing element value is left unmodified, and
+in fact the algorithm above depends on this behavior.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Wednesday, July 7, 2004  6:52 AM
+
+Randy:
+
+I moved the update_element procedure into the generic_keys nested package
+and declared it this way:
+
+
+   generic
+      with function Key (Element : in Element_Type) 
+        return Key_Type;
+   procedure Generic_Update_Element
+     (Container : in out Set;
+      Position  : in     Cursor;
+      Process   : not null access
+        procedure (Element : in out Element_Type));
+
+I made the Key function a generic formal subprogram for that operation
+directly instead of for the entire nested generic package, since that's the
+only operation that needs a key selector.
+
+The basic algorithm is something like:
+
+   procedure Generic_Update_Element (...) is
+
+      Old_Key : Key_Type renames Key (Position.Element);
+
+   begin
+
+      Process (Position.Element);
+
+      if Old_Key < Position.Element
+        or else Old_Key > Position.Element
+      then
+
+        <remove node from tree>
+        <insert node back into tree>
+
+        if <insertion failed because duplicate key> then
+           <free node>
+           raise Constraint_Error;
+        end if;
+
+      end if;
+
+   end Generic_Update_Element;
+
+Note that you don't need to pass an "=" operator for keys, since you already
+have "<" and ">" for comparing keys to elements.
+
+One question I had was whether update element is allowed to change the key
+(and hence change the relative position of the key's node).  In the code
+fragment above, the node is moved (deleted then immediately re-inserted)
+when there's been a change in the value of the key, and there's an error
+only if there's already a key with the new value.
+
+Another way to have handled this is to not allow the re-insertion at all:
+
+      if Old_Key < Position.Element
+        or else Old_Key > Position.Element
+      then
+
+        <remove node from tree>
+        <free node>
+        raise Constraint_Error;
+
+      end if;
+
+This handles the key-change more pessimistically.  It wasn't clear from your
+notes which behavior was intended.
+
+You can check out the latest packages here:
+
+ordered sets spec:
+<http://charles.tigris.org/source/browse/charles/src/ai302/a-coorse.ads>
+
+ordered sets body:
+<http://charles.tigris.org/source/browse/charles/src/ai302/a-coorse.adb>
+
+I'll have the indefinite ordered sets (a-ciorse.ad[sb]) done in a day or
+two.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Wednesday, July 7, 2004  6:43 PM
+
+...
+> I made the Key function a generic formal subprogram for that operation
+> directly instead of for the entire nested generic package, since that's the
+> only operation that needs a key selector.
+
+I think I prefer it to be on Generic_Keys, simply because that avoids the
+need to use two instantiations.
+
+...
+> Note that you don't need to pass an "=" operator for keys, since you already
+> have "<" and ">" for comparing keys to elements.
+
+Right. I had already noted that in the draft minutes. I don't know if I
+wrote Tucker's proposal down wrong, or if he made that mistake, but it's
+clearly wrong when you read the whole discussion.
+
+> One question I had was whether update element is allowed to change the key
+> (and hence change the relative position of the key's node).  In the code
+> fragment above, the node is moved (deleted then immediately re-inserted)
+> when there's been a change in the value of the key, and there's an error
+> only if there's already a key with the new value.
+
+I don't know; Tucker didn't cover that issue. My gut feeling is that the way
+you have it is better, because dropping elements on the floor (even with an
+exception) is nasty. If there is an alternative, it would be preferred. (Of
+course, doing that could silently cause the routine to be expensive, which
+is also annoying. But it wouldn't be much more expensive than Replace, so it
+probably is OK.)
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Wednesday, July 7, 2004  9:31 AM
+
+> I think I prefer it to be on Generic_Keys, simply because 
+> that avoids the need to use two instantiations.
+
+OK.  I declared the nested package like this:
+
+   generic
+
+      type Key_Type (<>) is limited private;
+
+      with function Key (Element : in Element_Type) 
+        return Key_Type;
+
+      with function "<" (Left : Key_Type; Right : Element_Type)
+          return Boolean is <>;
+
+      with function ">" (Left : Key_Type; Right : Element_Type)
+          return Boolean is <>;
+
+   package Generic_Keys is ...;
+
+
+And I declared the operation like this:
+
+   procedure Update_Element
+     (Container : in out Set;
+      Position  : in     Cursor;
+      Process   : not null access
+        procedure (Element : in out Element_Type));
+
+
+> > One question I had was whether update element is allowed to change the 
+> > key (and hence change the relative position of the key's node).  In 
+> > the code fragment above, the node is moved (deleted then immediately 
+> > re-inserted) when there's been a change in the value of the key, and 
+> > there's an error only if there's already a key with the new value.
+> 
+> I don't know; Tucker didn't cover that issue. My gut feeling 
+> is that the way you have it is better, because dropping 
+> elements on the floor (even with an
+> exception) is nasty. If there is an alternative, it would be 
+> preferred. (Of course, doing that could silently cause the 
+> routine to be expensive, which is also annoying. But it 
+> wouldn't be much more expensive than Replace, so it probably is OK.)
+
+Yes, but it's probably still going to beat any kind of normal insertion,
+since the node isn't destroyed and the element isn't copied.
+
+Another thing I realized is that if we do raise an exception (because the
+new key duplicates an existing key), then the cursor that was passed in
+effectively becomes a dangling reference.
+
+When we delete a key thru a cursor, we set the cursor value to No_Element on
+return.  Another possibility for the declaration of Update_Element, that is
+analogous to the Delete operation, is:
+
+   procedure Update_Element
+     (Container : in out Set;
+      Position  : in out Cursor;  --NOTE MODE
+      Process   : not null access
+        procedure (Element : in out Element_Type));
+
+We could define the semantics as follows: if the key hasn't been modified,
+then Position retains its value.  Otherwise, the node is removed from the
+tree and then re-inserted back into the tree.  If the insertion was
+successful, then Position retains its value.  If the insertion was not
+successful, then the node is deallocated and Position is set to No_Element.
+(Note that there aren't any exceptions.)
+
+It's just an idea, so I figured I'd bring it up.  Since Update_Element now
+has deletion semantics, maybe that should be more obvious.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Wednesday, July 7, 2004  7:13 PM
+
+At the recent ARG meeting we discussed the meaning of Swap for Lists. When
+working on the minutes of the meeting, I noticed this discussion, and I
+think that the resolution of the issue was nonsense (which I failed to
+realize at the time). So I'm bringing it up here for further discussion.
+
+---
+
+Here's the meeting minutes on the topic:
+
+Swap for list: After a swap, do the cursors still designate the same
+elements, or   do they designate the swapped elements? The semantics should
+be similar to that for an array: much like an index designate a “box” in the
+array, a cursor designates a “box” holding an element, so after a swap, the
+elements in the boxes should be changed. So we swap the elements, not the
+nodes.
+
+---
+
+There are a couple of problems with this semantics:
+* This cannot be implemented without an extra level of indirection for
+indefinite containers. While an Ada standard implementation would
+necessarily have such a level of indirection, it is easy to imagine an
+implementation supporting an extension to Ada that would eliminate that
+indirection and the costs thereof. That is, an implementation could support
+a single indefinite component at the end of the node record (with the
+requirement that such a record is initialized on creation); that would get
+rid of extra allocation costs. I don't think we want to prevent such an
+implementation solely for Swap.
+* This completely eliminates any performance advantage for a special swap
+routine for lists. Since the objects will be copied (at least in the
+definite case), it would always be better for the programmer to code their
+own routine that swapped the nodes.
+
+As such, I don't see the point of defining this routine for Lists. Indeed,
+since this routine only provides a performance advantage for indefinite
+vectors (in all other cases the performance is the same or worse than
+something built out of primitives), I have to wonder if it worth having this
+routine at all.
+
+In any case, I think that the thinking about cursors reflected in the
+minutes is flawed. A cursor designates an element - how that is accomplished
+isn't supposed to be visible in the specification of the containers. We
+specifically dropped a lot of wording about "nodes" for this reason - it's
+not necessary to reason about the containers.
+
+That said, it's obvious that the Swap for list should just swap the
+positions of the elements in the list, and cursors should continue to
+designate the same elements. (Logically, what they designate should be
+unspecified, but that seems to be going to far for lists.) The vector one is
+different, simply because cursors are weird -- we have all of the Bounded
+Error rules to explain that they don't necessarily designate the same
+element afterwards. Thus, for the vector one, it should be a Bounded Error
+to use the cursors afterwards, just like for Insert and Delete. (Indexes
+don't have that sort of issue, and usually using indexes would be
+preferred.)
+
+Another alternative is to recognize that these operations are fundamentally
+different, and thus give them different names. But that seems to be rather
+confusing.
+
+All in all, I don't think (and I have *never* thought) that a swap operation
+is worth having for any of the containers, because it is just too
+complicated to define sensibly.
+
+****************************************************************
+
+From: Nick Roberts
+Sent: Wednesday, July 7, 2004  7:31 PM
+
+I have to say, I am annoyed that you didn't follow my suggested model of  
+internal cursors. If you had done so, you simply wouldn't have these  
+problems.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Wednesday, July 7, 2004  8:19 PM
+
+I haven't the foggiest idea what you are talking about; there isn't any
+messages from you in Ada Comment with both "internal" and "cursor" that
+remotely discuss a "model". (If you want to post a reference, *please* just
+give the date of the message, don't quote the whole thing. There is far too
+much quoting going on around here, which makes it redundant for later
+readers of the mail.)
+
+And, in any case, the model of cursors really has nothing to do with this.
+Swap is a stupid operation; it's used mostly in student assignments and
+sub-optimal sorting algorithms. I don't think I've used Swap for anything
+else in my nearly 30 years of programming -- simply because it always
+requires three copies of something, and that's 1/3 too many.
+
+Since the only real use of Swap is in the sorting algorithms, making it
+user-visible is stupid. If it makes some people feel good, fine, as long as
+it doesn't screw up the model. It isn't worth that.
+
+****************************************************************
+
+From: Nick Roberts
+Sent: Thursday, July 8, 2004  7:30 AM
+
+> I haven't the foggiest idea what you are talking about; there isn't
+> any messages from you in Ada Comment with both "internal" and
+> "cursor" that remotely discuss a "model".
+
+It was something that was lengthily discussed in comp.lang.ada, the ASCL  
+mailing list, and other places. I'm surprised you don't remember anything  
+about it, Randy, I thought everyone knew about it. My proposals were  
+posted on the web for a long time. Swing your browser to:
+
+    http://www.adapower.net/ascl/
+
+It's all still there.
+
+> And, in any case, the model of cursors really has nothing to do
+> with this.
+
+I think it does. You were arguing that Swap should be dropped for  
+doubly-linked lists (and maybe also for vectors) because, with the current  
+cursor model, it would be difficult (impossible?) to implement
+the same semantics for both the lists and the vectors. With my model,  
+there would be no such difficulty.
+
+> Swap is a stupid operation; it's used mostly in student
+> assignments and sub-optimal sorting algorithms.
+
+Sub-optimal? Such as Quicksort and Mergesort?
+
+> Since the only real use of Swap is in the sorting algorithms,
+> making it user-visible is stupid.
+
+I don't about 'stupid', but less than vitally important perhaps.
+
+> If it makes some people feel good, fine, as long as
+> it doesn't screw up the model. It isn't worth that.
+
+Well, I agree, at this stage. I just think it's a pity my model wasn't  
+used from the outset.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Thursday, July 8, 2004  9:35 AM
+
+> That said, it's obvious that the Swap for list should just swap the
+> positions of the elements in the list, and cursors should continue to
+> designate the same elements. (Logically, what they designate should be
+> unspecified, but that seems to be going to far for lists.) The vector one is
+> different, simply because cursors are weird -- we have all of the Bounded
+> Error rules to explain that they don't necessarily designate the same
+> element afterwards. Thus, for the vector one, it should be a Bounded Error
+> to use the cursors afterwards, just like for Insert and Delete. (Indexes
+> don't have that sort of issue, and usually using indexes would be
+> preferred.)
+
+So if you were in favor of retaining Swap for lists, then does this mean 
+that you want the original, pre-palma semantics?  (Swap "exchanges 
+nodes," to use Matt's term.)
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, July 8, 2004  1:36 PM
+
+Yes. The Palma semantics don't do anything useful, and certainly are not
+what you would write yourself if you had a need to swap two nodes in a
+hand-programmed list.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Friday, July 2, 2004  2:28 PM
+
+> It was something that was lengthily discussed in comp.lang.ada, the ASCL
+> mailing list, and other places. I'm surprised you don't remember
+> anything about it, Randy, I thought everyone knew about it.
+
+Oh, I didn't realize that you were talking about (ancient) pre-history.
+Since such things are not recorded with the AI (meaning that its impossible
+to go back and look them up), references to them are going to be more
+confusing than enlightening. In this case, I thought that you were referring
+to some specific suggestion for how the wording should be written for *this*
+proposal -- thus the confusion.
+
+In any case, I think virtually everyone here has an idea of how they would
+design this library differently if they were doing it. Whether those ideas
+are better or not is pretty much irrelevant, as we've decided to use Matt's
+basic design - in large part because Matt has done more thinking on this
+topic (including usage issues) than nearly anyone else, *and* he submitted a
+complete proposal as a starting point. I certainly would not have
+implemented cursors as Matt has; but our job at this point is to insure that
+the description of those cursors is correct, and that the operation set is
+complete and described correctly -- not to gripe about some other design
+being better. (We all know that "best is the enemy of good enough", and that
+certainly applies here.)
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Friday, July 9, 2004  9:33 AM
+
+Given Randy's analysis, I think the vector and list swap operations look 
+like this:
+
+For vectors:
+
+procedure Swap (Container : in out Vector;
+                 I, J      : in     Index_Type'Base);
+
+procedure Swap (I, J : in Cursor);
+
+For lists:
+
+procedure Swap (Container : in out List;
+                 I, J      : in     Cursor);
+
+The semantics are as follows.
+
+For the vector swap operations, the elements in the vector are swapped.
+
+One question we need to answer is whether cursors in the cursor-based 
+swap for vectors remain valid.  I know that our working model is that 
+cursors designate elements (rather than positions within the vector), so 
+if the element moves then the cursor is supposed to follow the element.
+
+(In the reference implementation the cursors do remain valid, since 
+internally they're just index values.  But this breaks the model above, 
+since I and J continue to designate the same relative positions as 
+before the swap, and hence I and J deliver different element values 
+following the swap.  Compare this to the list behavior below.)
+
+For the list swap operation, the nodes designated by I and J are 
+relinked.  (I know I'm not supposed to say "nodes" or "relinked," but 
+just bear with me.)  I and J continue to designate the same nodes before 
+and after the swap (and hence, I and J return the same element values as 
+existing prior to the swap).  Following the swap, I designates the node 
+in J's former relative position in the list, and J designates the node 
+in I's former relative position.  (These are just the the pre-Palma 
+semantics.)
+
+Note that the behaviors for vector swap and list swap are different.  I 
+think that's OK, since the reason this operation exists is to allow you 
+to take advantage of the particular representation of the container, in 
+a way that allows swap to be more efficient.
+
+In the case of the definite vector, the implementation will most likely 
+exchange element values by creating at least one temporary.  So in this 
+one case, swap doesn't confer any great advantage besides convenience 
+(and we need it anyway, since the spec must be identical to the 
+indefinite vector).
+
+For the indefinite vector, swap really does confer an advantage, since 
+some form of element indirection is implied, and so the implementor can 
+swap internal pointers instead of elements.  (This was our original 
+motivation for introducing a swap operation.)
+
+The swap for the definite and indefinite lists work the same, by 
+relinking internal nodes.  (In the pre-Palma reference implementation, I 
+implemented swap for lists using Splice.)
+
+Note that each of the three operations declared above has a different 
+signature.  That means there's no possibility that switching from a 
+vector to a list (say) will suddenly introduce different swap semantics 
+(presumably the application was depending on the original semantics), 
+since the signatures are different and hence the change will be caught 
+by the compiler.
+
+(You need to pass the list to the list swap operation, since the list 
+caches pointers to the first and list nodes, and so if you're moving 
+nodes then the cache values might change.  In the vector case, you're 
+moving elements not nodes, so you don't need to pass the vector object.)
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Saturday, July 10, 2004 11:44 AM
+
+Now that container types are publicly tagged, it might make sense to declare
+some container type parameters as class-wide.
+
+For example, the generic_sort and generic_merge for lists are generic
+operations, which means these operations aren't primitive for the list type.
+Should they be declared this way:
+
+generic
+   with function "<" (Left, Right : Element_Type)
+      return Boolean is <>;
+procedure Generic_Sort (Container : in out List'Class);
+
+generic
+   with function "<" (Left, Right : Element_Type)
+      return Boolean is <>;
+procedure Generic_Merge (Target : in out List'Class;
+                         Source : in out List'Class);
+
+If a user does derive from List (say), then he would have to convert back to
+the parent type in order to call an instantiation of generic_sort or
+generic_merge, but that's kind of a pain.
+
+In the case of generic_merge, another possibility is to pass the type as a
+generic formal:
+
+generic
+   type List_Type is new List with private;
+   with function "<" (Left, Right : Element_Type)
+      return Boolean is <>;
+procedure Generic_Merge (Target : in out List_Type;
+                         Source : in out List_Type);
+
+This would force target and source to have the same type.  But of course
+it's more work to instantiate.
+
+For the sets, there are a couple of predicate functions that accept two set
+objects.  The declarations would look like:
+
+function Is_Subset (Item      : Set;
+                    Container : Set'Class)
+   return Boolean;
+
+function Is_Disjoint (Item      : Set;
+                      Container : Set'Class)
+   return Boolean;
+
+(Note that we still haven't decided that the parameter names should be --
+should "Container" come first?)
+
+The sets package also has the nested generic Generic_Keys.  None of its
+operations are primitive for type Set either.  That might be an argument for
+declaring all of the set container parameters as type Set'Class.  (Another
+possibility is to pass in the set type as a generic formal.)
+
+Note that the sets have the union, intersection, etc operations, and the
+lists have the splice operations, but I think those can stay as is.
+
+****************************************************************
+
+From: Nick Roberts
+Sent: Monday, August 2, 2004  4:23 PM
+
+Randy's done a great job, as usual, updating this AI.
+
+For most (maybe all) of the changes, I say "Hooray!" As always, I have
+some comments. Happily, these are all very minor issues. Just dismiss
+any question already answered or issue already dealt with (and accept
+my apologies).
+
+* In line 205, swap two items (to accord with the order of presentation
+of the four container kinds), from:
+
+    The following major non-limited containers are provided:
+       * (Expandable) Vectors of any non-limited type;
+       * Doubly-linked Lists of any non-limited type;
+       * Ordered Sets of any non-limited type;
+       * Hashed Maps keyed by any non-limited type containing any
+    non-limited type.
+
+to:
+
+    The following major non-limited containers are provided:
+       * (Expandable) Vectors of any non-limited type;
+       * Doubly-linked Lists of any non-limited type;
+       * Hashed Maps keyed by any non-limited type containing any
+    non-limited type.
+       * Ordered Sets of any non-limited type;
+
+* Rephrase:
+
+    Separate versions for definite element types are provided, as those
+    can be implemented more efficiently.
+
+as:
+
+    Separate versions for definite and indefinite element types are
+    provided, as those for definite types can be implemented more
+    efficiently.
+
+* Typo in line 253:
+
+    specify precisely where this will happen (it will happen no latter
+    than the
+
+Change 'latter' to 'later'.
+
+* Add a requirement (or Imp Adv) for Hash_Type'Modulus to be a power
+of two? (Line 299.)
+
+* In line 307, clarify what the 'back end' of a vector is :-)
+
+Maybe:
+
+    The language-defined package Containers.Vectors provides a private
+    type Vector and a set of operations. A vector container allows
+    insertion and deletion at any position, but it is specifically
+    optimized for insertion and deletion at the back end of the
+    container (the end with the highest index). A vector container
+    also provides random access to its elements.
+
+* I suggest to rephrase:
+
+    A vector container object manages an unconstrained internal array,
+    which expands as necessary as items are inserted. The *capacity* of
+    a vector corresponds to the total length of the internal array, and
+    the *length* of a vector corresponds to the number of active
+    elements in the internal array.
+
+    A vector container may contain *empty elements*. Empty elements do
+    not have a specified value.
+
+as:
+
+    A vector has a *length*, of the type Containers.Count_Type, which
+    varies dynamically and is the number of elements the vector
+    contains. These elements are the *active elements* of the vector.
+    Their indices are of the subtype Index_Type, and occupy the range
+    f .. f+n-1, where f is Index_Type'First and n is the length of the
+    vector.
+
+    A vector container object manages an internal array, which expands
+    as necessary. The *capacity* of a vector corresponds to the number
+    of elements which can be stored in the internal array, and will
+    always be no less than the length of the vector.
+
+    An active element may be *empty*. An empty element does not have a
+    specified value, and it is an unbounded error to read an empty
+    element.
+
+I know this is a little bit more long-winded, but I think it is a bit
+clearer.
+
+* Maybe the AARM note at line 329:
+
+    The internal array is a virtual structure. There is no requirement
+    for the implementation to be a single contiguous array.
+
+could be better phrased:
+
+    The internal array is a conceptual model for the purposes of
+    defining the semantics of vectors. There is no requirement for an
+    implementation to actually use a single contiguous array.
+
+* Maybe add a AARM note:
+
+       pragma Assert (Index_Type'Base'First < Index_Type'First);
+
+    It is essential that Last_Index is always able to return a valid
+    value, including for an empty vector. It cannot do this if
+    Index_Type'Base'First = Index_Type'First, so it is a requirement
+    that Index_Type'Base'First < Index_Type'First for any instantiation
+    of Containers.Vectors, and this pragma enforces the requirement.
+
+* What is the purpose of Index_Subtype? (This question seems to have
+been raised but not answered.)
+
+* For vectors, lists, maps, and sets the procedures named 'Iteration'
+and 'Reverse_Iteration', which were generic but are now procedures
+taking an access-to-subprogram parameter, would perhaps now be more
+appropriately named 'Iterate' and 'Reverse_Iterate'?  (Or 'Traverse'
+and 'Reverse_Traverse'? :-)
+
+* Should the same thing (change from generic procedure to procedure
+with access-to-subprogram parameter) be done for Generic_Sort? (I
+guess the answer is to do with efficiency.)
+
+* Should procedure 'Assign' be called 'Copy', to emphasise its
+distinction from normal assignment? Should it have start and end
+parameters? (I see idea this already got suggested.)
+
+* The description for Last_Index line 987:
+
+    Returns the position of the last element in Container.
+
+could be better expressed as:
+
+    If the length of Container is 0, Last_Index returns
+    First_Index(Container) - 1, otherwise it returns the index of the
+    last active element in Container.
+
+* Typo in line 1065:
+
+    function Reverse_Find (Container : Vector;
+                           Item      : Element_Type;
+->                        Index     : Index_Type'Base := Index_Type'Las))
+       return Index_Type'Base;
+
+The 't' is missed off 'Last' and there's an extra ')'.
+
+* There may be a call ambiguity problem with Find and Reverse_Find.
+These are provided for both an index and cursor starting point:
+
+    function Find (Container : Vector;
+                   Item      : Element_Type;
+                   Index     : Index_Type'Base := Index_Type'First)
+       return Index_Type'Base;
+
+    function Find (Container : Vector;
+                   Item      : Element_Type;
+                   Position  : Cursor := No_Element)
+       return Cursor;
+
+A call Find(Cont,Item) in a context which could require either an
+index or a cursor will be ambiguous. I'm just pointing this one out
+at the moment; maybe it's too trivial to worry about.
+
+* In the description for Splice, line 1635:
+
+    last node of Container. The length of Target is incremented, and
+    the length of Source is decremented.
+
+'Container' needs to be changed to 'Target'.
+
+* In line 1788:
+
+    AARM Note: The name is "Hashed_Maps" to allow for a secondary
+    standard to include "Sorted_Maps".
+
+Maybe the suggested name should be "Ordered_Maps", by analogy to the
+package "Ordered_Sets"?
+
+* For the map 'Replace' procedure:
+
+    procedure Replace (Container : in out Map;
+                       Key       : in     Key_Type;
+                       New_Item  : in     Element_Type);
+
+    Replace inserts Key and New_Item as per Insert, with the difference that
+    if Key is already in the map, then this operation assigns New_Item to
+    the element associated with Key. Any exceptions raised during assignment
+    are propagated.
+
+I think this procedure should be called 'Replace_or_Insert', to avoid
+potential confusion about its semantics to anyone reading code using
+it. This point has already been argued about, so maybe it should rest
+as is now.
+
+* For the Delete at cursor procedure:
+
+    procedure Delete (Container : in out Map;
+                      Position  : in out Cursor);
+
+    If Position equals No_Element, this operation has no effect.
+    Otherwise, Delete removes the node from the map and deallocates the  
+node.
+    Position is set to No_Element on return.
+
+Is it such a good idea for Position to have mode 'in out'? This
+prevents constructions such as (concocting an example):
+
+    Delete(M,Next(C));
+
+which might be handy sometimes.
+
+* Minor typo in line 2118:
+
+    If Length (Container) > Count, then Constraint_Error is
+    propogated.
+
+Change 'propogated' to 'propagated'. Also, on the following line,
+perhaps the phraseology should be:
+
+    Otherwise, Set_Capacity allocates ...
+
+I'd suggest the same for the wording for the following First and Next
+functions.
+
+* Is it really appropriate for the Key_Type formal parameter of
+generic package Ordered_Sets.Generic_Keys to be limited? I don't think
+it matters a great deal, but it just might assist some implementations
+by making it non-limited (since it would allow them to make internal
+copies). I doubt that a limited type would ever be required in practice:
+if the key is directly extracted from an element, it cannot be limited
+(because the element cannot); if it is indirectly derived, it must be
+via an access value, in which case the access type can be used as the
+key type. That Key_Type is limited doesn't seem to match its conceptual
+abstraction, to my mind.
+
+* In line 2473 and 2788, within package Generic_Keys:
+
+        procedure Update_Element
+->        (Position : in Cursor;
+            Process : not null access procedure (Element : in out  
+Element_Type));
+
+Would it be better to make the mode of Position 'in out', so that if
+re-insertion occurs the cursor 'tracks' the new position?
+
+* In those places where "Index_Type'Succ(X)" is used, couldn't X + 1
+be used instead? Index_Type is an integer type (isn't it?).
+
+* In various places appears a phrase like:
+
+    Any exceptions raised ... are propagated.
+
+I think these should be rephrased in the singular:
+
+    Any exception raised ... is propagated.
+
+since only one exception can be propagated (the first to occur).
+
+* As an example of counting the number of angels dancing on the tip of
+a needle, I wonder if the word 'expansile' should be used instead of
+'expandable'. I think there is a tiny difference of meaning, in that
+the latter suggests something that can be expanded deliberately (like
+a set of modular shelves) whereas the former suggests something that
+inherently tends to expand (as one's bladder, on a visit to the pub).
+
+*** A few side-notes:
+
+The semantics expressed by:
+
+    While Set_Capacity can be used to reduce the capacity of a map, we
+    do not specify whether an implementation actually supports reduction
+    of the capacity. Since the actual capacity can be anything greater
+    than or equal to Count, an implementation never has to reduce the
+    capacity.
+
+is exactly what I wanted. Cool.
+
+Some of the AARM notes are brilliant. E.g. "The implementation needs
+to take care so that aliasing effects do not make the result trash;
+Union (S, S); must work." This is totally cool; it's just the kind
+of gotcha that causes me to have bad nights.
+
+Finally I'd like to express -- and I very much hope this doesn't sound
+trite or ingratiating -- my admiration for Matt and Randy for all the
+perspiration and inspiration (in whichever proportion) they have put
+into this Amendment. I hope it gets passed.
+
+In fact, I just want to add a note that I hope nothing I have posted to
+this mailing list comes across as being deliberately antagonistic or
+offensive (towards Randy or anyone else). Although I may often be blunt
+in the way I put things, and I may often be strident in my criticisms,
+there has never been on my part any element of personal animosity in
+any of my comments. On the contrary, I may disagree vehemently with
+someone on a particular issue, without having any less respect for them.
+
+I feel that it is in the nature of the best technical forums that the
+participants retain a sense of personal respect for the others, however
+passionate their disagreement may be. Nuff said.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Monday, August 9, 2004  4:36 PM
+
+Nick Roberts wrote:
+> 
+> * What is the purpose of Index_Subtype? (This question seems to have
+> been raised but not answered.)
+
+It's there for composability.  You want to be able to write operations
+and declare variables in terms of the index type used to instantiate the
+package.
+
+
+> * For vectors, lists, maps, and sets the procedures named 'Iteration'
+> and 'Reverse_Iteration', which were generic but are now procedures
+> taking an access-to-subprogram parameter, would perhaps now be more
+> appropriately named 'Iterate' and 'Reverse_Iterate'?  (Or 'Traverse'
+> and 'Reverse_Traverse'? :-)
+
+I have made the same comment in my review of the AI.  (The name should
+be the verb phrase "Iterate", not the noun phrase "Iteration".)
+
+
+> * Should the same thing (change from generic procedure to procedure
+> with access-to-subprogram parameter) be done for Generic_Sort? (I
+> guess the answer is to do with efficiency.)
+
+Yes, it has to do with efficiency.  Predefined relational operators for
+a type are intrinsic, so you can't take their address and hence cannot
+pass the operation as the value of an anonymous access parameter.
+
+
+> * Should procedure 'Assign' be called 'Copy', to emphasise its
+> distinction from normal assignment? Should it have start and end
+> parameters? (I see idea this already got suggested.)
+
+No.  It's called Assign because it's an assignment operation.  (In this
+case, more efficient than operator ":=".)
+
+The lexical rule is: Assign takes the Target as the first parameter and
+Source as the second parameter, while Copy takes the Source as the first
+parameter and target as the second parameter, like this:
+
+procedure Assign
+   (Target : in out T;
+    Source : in     T);
+
+procedure Copy
+   (Source : in     T;
+    Target : in out T);
+
+So even if you were to change the name, you'd have to change the
+parameter order too.  But you have have to put the target as the first
+parameter, in order to use distinguished receiver syntax:
+
+    Target.Assign (Source);
+
+Is the same as:
+
+    Target := Source;
+
+but the former is more efficient than the latter (for a vector).
+
+
+> * There may be a call ambiguity problem with Find and Reverse_Find.
+> These are provided for both an index and cursor starting point:
+> 
+>    function Find (Container : Vector;
+>                   Item      : Element_Type;
+>                   Index     : Index_Type'Base := Index_Type'First)
+>       return Index_Type'Base;
+> 
+>    function Find (Container : Vector;
+>                   Item      : Element_Type;
+>                   Position  : Cursor := No_Element)
+>       return Cursor;
+> 
+> A call Find(Cont,Item) in a context which could require either an
+> index or a cursor will be ambiguous. I'm just pointing this one out
+> at the moment; maybe it's too trivial to worry about.
+
+I discussed this with Randy, and he reasoned that ambiguity wouldn't be
+a problem because in the typical case you name the return value anyway.
+
+However, we do have First_Index and Last_Index, and so I would be in
+favor of renaming the first operation Find_Index.
+
+
+> * For the map 'Replace' procedure:
+> 
+>    procedure Replace (Container : in out Map;
+>                       Key       : in     Key_Type;
+>                       New_Item  : in     Element_Type);
+> 
+>    Replace inserts Key and New_Item as per Insert, with the difference that
+>    if Key is already in the map, then this operation assigns New_Item to
+>    the element associated with Key. Any exceptions raised during assignment
+>    are propagated.
+> 
+> I think this procedure should be called 'Replace_or_Insert', to avoid
+> potential confusion about its semantics to anyone reading code using
+> it. This point has already been argued about, so maybe it should rest
+> as is now.
+
+Too much verbosity.  Let's just call it "Insert".
+
+
+
+> * For the Delete at cursor procedure:
+> 
+>    procedure Delete (Container : in out Map;
+>                      Position  : in out Cursor);
+> 
+>    If Position equals No_Element, this operation has no effect.
+>    Otherwise, Delete removes the node from the map and deallocates the  
+> node.
+>    Position is set to No_Element on return.
+> 
+> Is it such a good idea for Position to have mode 'in out'? This
+> prevents constructions such as (concocting an example):
+> 
+>    Delete(M,Next(C));
+> 
+> which might be handy sometimes.
+
+But you're deallocating the node designated by Position, so you have to
+set the cursor to No_Element.
+
+I haven't had a need to do as in your example, but I have had a need to
+iterate through the map and delete each element in turn.  I can do this
+in C++ by saying
+
+    my_map.erase(my_iter++);
+
+but I don't have that option in Ada.  But it's no big deal, just do this:
+
+declare
+    I : Cursor := First (M);
+    J : Cursor;
+begin
+    while Has_Element (I) loop
+       Update_Element (I, Finalize'Access);
+
+       J := I;
+       Next (I);
+
+       M.Delete (J);
+    end loop;
+end;
+
+
+> * Is it really appropriate for the Key_Type formal parameter of
+> generic package Ordered_Sets.Generic_Keys to be limited? I don't think
+> it matters a great deal, but it just might assist some implementations
+> by making it non-limited (since it would allow them to make internal
+> copies). 
+
+But you can make an internal copy (in fact, the reference implementation
+does), you just have to use renames instead of assignment:
+
+declare
+    Copy_Of_Key : Key_Type renames Key (E);
+begin
+
+> I doubt that a limited type would ever be required in practice:
+> if the key is directly extracted from an element, it cannot be limited
+> (because the element cannot); if it is indirectly derived, it must be
+> via an access value, in which case the access type can be used as the
+> key type. That Key_Type is limited doesn't seem to match its conceptual
+> abstraction, to my mind.
+
+But Generic_Keys is written in terms of what Generic_Keys requires.  It
+only needs function Key to implement Update_Element, and it doesn't need
+assignment (since it can use renames).
+
+
+> * In line 2473 and 2788, within package Generic_Keys:
+> 
+>        procedure Update_Element
+> ->        (Position : in Cursor;
+>            Process : not null access procedure (Element : in out  
+> Element_Type));
+> 
+> Would it be better to make the mode of Position 'in out', so that if
+> re-insertion occurs the cursor 'tracks' the new position?
+
+Hmmmm.  Not sure what you mean here, since Position would seem to
+already "track" the new position.  The cursor continues to designate the
+same internal storage node before and after the call (even if the
+relative position of the node changes), and so it doesn't need to be inout.
+
+The more substantive issue in my mind is what happens if the key value
+changes and it matches another key in the set.  In that case we
+deallocate the storage node and then raise Constraint_Error.
+
+I don't really like that, since the cursor is now designating a node
+which has been deallocated.  I'd rather say:
+
+    procedure Update_Element_Or_Delete
+      (Position : in out Cursor;
+       Process  : ...);
+
+and then not raise any exception if there's a match.  Rather, we
+deallocate the node and then set Position to No_Element.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Thursday, July 12, 2004  6:42 PM
+
+One of the things we did in Palma was to move the Update_Element operation
+for ordered sets into its nested package Generic_Keys, to allow it to check
+whether the key was modified.
+
+One of the consequences of moving that operation is that we no longer have
+an operation to pass the set element as a parameter (without also
+instantiating the nested generic).  For example:
+
+procedure Print (S : Set) is
+
+   procedure Print (E : in out ET) is
+   begin
+      -- we only need to query E, not modify it
+   end;
+
+   procedure Process (C : Cursor) is
+   begin
+      Update_Element (C, Print'Access);
+   end;
+
+begin
+
+   S.Iterate (Process'Access);
+
+end Print;
+
+We can do this if only we also instantiate the nested generic.  Of course,
+we could also use the selector function Element for cursors, to return a
+copy of the element, but this isn't very attractive for large elements.
+
+I think what's missing is an operation like Update_Element, but with the
+difference that the access procedure parameter accepts the element with in
+mode.  Something like:
+
+   procedure Query_Element 
+    (Position : in Cursor;
+     Process  : not null access procedure (E : in ET));
+
+This would be declared outside of the Generic_Keys nested package.  In fact,
+I think it makes sense to add this operation for all containers.
+
+This would allow us to write the example above like this:
+
+procedure Print (S : Set) is
+
+   procedure Print (E : in ET) is
+   begin
+      -- we only need to query E, not modify it
+   end;
+
+   procedure Process (C : Cursor) is
+   begin
+      Query_Element (C, Print'Access);
+   end;
+
+begin
+
+   S.Iterate (Process'Access);
+
+end Print;
+
+Also, in Palma we added a Key selector function to the generic formal region
+of Generic_Keys.  Now that we have that, I think it makes sense for
+Generic_Keys to provide the following additional operation:
+
+   function Key (Position : Cursor) return Key_Type;
+
+This allows Generic_Keys to more closely mimic the spec of the (heahed) map.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Friday, July 2, 2004  9:31 AM
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Friday, July 2, 2004  9:31 AM
+
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Wednesday, June 9, 2004  9:31 AM
+Sent: Friday, July 2, 2004  9:31 AM
 
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Wednesday, June 9, 2004  9:31 AM
+Sent: Friday, July 2, 2004  9:31 AM
 
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Wednesday, June 9, 2004  9:31 AM
+Sent: Friday, July 2, 2004  9:31 AM
 
 ****************************************************************

Questions? Ask the ACAA Technical Agent