CVS difference for ais/ai-10302.txt

Differences between 1.2 and version 1.3
Log of other versions for file ais/ai-10302.txt

--- ais/ai-10302.txt	2003/09/30 02:01:14	1.2
+++ ais/ai-10302.txt	2003/10/29 22:54:15	1.3
@@ -841,7 +841,7 @@
 by Iterator.  If Iterator equals Null_Iterator, then Constraint_Error is
 propagated.
 
-!comment
+AARM Note
 The successor of Last is Back, and the successor of Back is First.  If
 the list is empty, First, Last, and Back all designate the same node.
 
@@ -851,7 +851,7 @@
 designated by Iterator.  If Iterator equals Null_Iterator, then
 Constraint_Error is propagated.
 
-!comment
+AARM Note
 The predecessor of Back is Last, and the predecessor of First is Back.
 
 The procedure Increment is equivalent to Iterator := Succ (Iterator).
@@ -1383,7 +1383,7 @@
    (Left, Right : Wide_String) return Boolean;
 pragma Pure (Ada.Containers.Less_Wide_String_Case_Insensitive);
 
-!comment
+DESIGN NOTE:
 I think we should have hash functions for all predefined types, such
 Integer, Long_Integer, etc.
 
@@ -1757,7 +1757,7 @@
 If Iterator equals Null_Iterator, then Constraint_Error is propagated.
 Otherwise it returns the successor of the node designated by Iterator.
 
-!comment
+AARM NOTE
 The successor of Last is Back, and the successor of Back is First.  If
 the container is empty, then First, Last, and Back all designate the
 sentinel node.
@@ -1768,7 +1768,7 @@
 If Iterator equals Null_Iterator, then Constraint_Error is propagated.
 Otherwise it returns the predecessor of the node designated by Iterator.
 
-!comment
+AARM NOTE
 The predecessor of First is Back, and the predecessor of Back is Last.
 
 
@@ -6012,8 +6012,7 @@
 
     Elements_Per_Node : in Positive := 8;
 
-!comment
-
+NOTE:
 I have passed the number of elements per node as a generic formal
 constant, but I again I don't know whether this is exposing too many
 implementation details, or whether this will constrain implementor
@@ -6593,7 +6592,7 @@
 raised during internal allocation are propagated, and Target is not
 modified.
 
-!comment
+AARM NOTE
 The sentinel doesn't count as an element, so it is never copied.  The
 sentinel is not affected by Assign, and so following Assign the Target
 has the same sentinel as it did prior to Assign.
@@ -6615,7 +6614,7 @@
 Returns the number of elements in Container.  The time complexity of
 this operation is O(1).
 
-!comment
+AARM NOTE
 The time complexity of Length differs from the corresponding size()
 operation in C++, which allows size() for a list to have O(n) time
 complexity.
@@ -6631,7 +6630,7 @@
 Deletes all the nodes that belong to Container, and sets the length of
 to 0.  Any exceptions raised during deallocation are propagated.
 
-!comment
+AARM NOTE
 
 Here and elsewhere, when an operation propagates an exception, the
 container is never left in an inconsistent state.  This standard might
@@ -6658,7 +6657,7 @@
 accurately reflect the fact that there are that many nodes remaining in
 the container.
 
-!end comment
+END AARM NOTE
 
 
 procedure Swap (Left, Right : in out Container_Type);
@@ -6667,7 +6666,7 @@
 the Left container are now in the Right container, and vice versa.  The
 time complexity of Swap is O(1).
 
-!comment
+AARM NOTE
 The Back sentinel node follows the rest of the nodes to their new home
 in the other container.
 
@@ -6916,7 +6915,7 @@
 (towards the back) the node designated by Iterator.  If Iterator equals
 Null_Iterator, the operation fails and Constraint_Error is raised.
 
-!comment
+AARM NOTE
 The successor of Last is Back, and the successor of Back is First.  If
 the list is empty, First, Last, and Back all designate the same node.
 
@@ -6928,7 +6927,7 @@
 (towards the front) the node designated by Iterator.  If Iterator equals
 Null_Iterator, the operation fails and Constraint_Error is raised.
 
-!comment
+AARM NOTE
 The predecessor of Back is Last, and the predecessor of First is Back.
 
 
@@ -8463,7 +8462,7 @@
 alias of Target, the operation does nothing.  Any exceptions raised
 during internal allocation or deallocation are propagated.
 
-!comment
+AARM NOTE
 
 Here and elsewhere we might decide to impose the req'mt that if there's
 an exception during Assign, then Target is not modified.  We can make
@@ -8499,7 +8498,7 @@
 Sets the length of the container to 0.  The size of the container is not
 affected.  Any exceptions raised during deallocation are propagated.
 
-!comment
+AARM NOTE
 This doesn't delete the buckets array -- it just deletes the nodes
 hanging off the buckets array.  If you want to delete the buckets array
 too (thus setting the map's size to 0), then you can Swap with a
@@ -8579,7 +8578,7 @@
 resize prior to the insertion proper.  If the container size is 0 the
 operation fails and Constraint_Error is propagated.
 
-!comment
+AARM NOTE
 
 This allows a developer to resize the container at the time most
 suitable for his application, independently of the time of insertion.
@@ -8656,7 +8655,7 @@
 exceptions raised by Is_Equal_Key or during the deallocation are
 propagated.
 
-!comment
+AARM NOTE
 
 Here and elsewhere, even if deallocation fails, Container must remain
 consistent.  Here its state must reflect the fact that the node was
@@ -8786,7 +8785,7 @@
 is propagated.  Otherwise, returns the value of the expression Hash
 (Key) mod Size (Container).
 
-!comment
+AARM NOTE
 We could relax the precondition, and simply return 1 if size is 0.
 
 
@@ -8915,7 +8914,7 @@
 that designates a variable view of the key component on the node
 designated by Iterator.
 
-!comment
+AARM NOTE
 
 It would be easy to break a map abstraction if keys were modified,
 especially if it were easy to do so, when the modification might be
@@ -9957,7 +9956,7 @@
 equals Null_Iterator, the operation fails and Constraint_Error is
 propagated.
 
-!comment
+AARM NOTE
 
 A sorted map has wrap-around semantics similar to an unbounded
 doubly-linked list.  Therefore the successor of Last is Back, and the
@@ -9971,7 +9970,7 @@
 equals Null_Iterator, the operation fails and Constraint_Error is
 propagated.
 
-!comment
+AARM NOTE
 
 Pred is symmetric to Succ.  Therefore the predecessor of Back is Last,
 and the predecessor of First is Back.
@@ -11451,9 +11450,8 @@
 function Ada.Containers.Less_Wide_String_Case_Insensitive
    (Left, Right : Wide_String) return Boolean;
 pragma Pure (Ada.Containers.Less_Wide_String_Case_Insensitive);
-
-!comment
 
+DESIGN NOTE:
 I think we should have hash functions for all predefined types, such
 Integer, Long_Integer, etc.
 
@@ -12409,9 +12407,8 @@
 
 In the absence of any explicit initialization, objects of type
 Iterator_Type are default-initialized to the value Null_Iterator.
-
-!comment
 
+AARM NOTE
 When a sorted set container object elaborates, a sentinel node belonging
 to the container is allocated automatically.  Its element is
 uninitialized, except for any controlled initialization or
@@ -12427,8 +12424,7 @@
 Target, the operation does nothing.  Any exceptions raised during
 internal allocation or deallocation are propagated.
 
-!comment
-
+AARM NOTE
 The sentinel is not affected by Assign, and its element is never copied.
 The sentinel Target had before the Assign is the same sentinel has after
 the Assign.
@@ -15245,6 +15241,13 @@
 
 *************************************************************
 
+From: Simon Wright
+Sent: Tuesday, September 30, 2003  8:09 AM
+
+This is what I meant to say, sorry it wasn't clear.
+
+*************************************************************
+
 From: Martin Dowie
 Sent: Monday, September 29, 2003  2:42 AM
 
@@ -15668,6 +15671,17 @@
 
 *************************************************************
 
+From: Martin Krischik
+Sent: Tuesday, September 30, 2003  4:55 AM
+
+> Perhaps more desirable is to have these be children of Ada.Containers:
+> Ada.Containers.Indefinite_Elements and Ada.Containers.Persistent_Elements.
+
+But symetry would then demand Ada.Containers.Definite_Elements wich was my 
+original point.
+
+*************************************************************
+
 From: Marius Amado Alves
 Sent: Monday, September 29, 2003  9:38 AM
 
@@ -15760,7 +15774,7 @@
 
 *************************************************************
 
-From: Marius Amado Alves
+From: Mario Amado Alves
 Sent: Monday, September 29, 2003  4:31 PM
 
 Hmm... it's not exactly recursive because the elements of the second
@@ -15778,4 +15792,275 @@
 What Matthew proposes is the first step in this infinite ladder of types.
 
 *************************************************************
+
+From: Mario Amado Alves
+Sent: Tuesday, September 30, 2003  3:39 AM
+
+I don't see this set theory here. Ada types allows recursion (via
+pointers to an incomplete type). My solutions to the problem provide
+recursion. Both Ada and my solutions provide *exact* recursion, meaning
+the type refers to itself, really itself (although indirectly).
+Matthew's solution does not provide this.
+
+
+*************************************************************
+
+From: Ed Schonberg
+Sent: Tuesday, September 30, 2003  4:31 PM
+
+If you have reference semantics, then of course a conventional
+tree is all you need.
+
+If all you have is containers without any atomic components, you do
+have pure set theory and you can represent 0 with {}, n+1 with {n}, and
+so on, but that is probably NOT the purpose of these containers :-)!
+ 
+If you want value semantics, atomic components at the bottom, and
+homogeneous containers I don't see how you can avoid programming each
+level by hand.
+
+*************************************************************
+
+From: Nick Roberts
+Sent: Tuesday, September 30, 2003  3:43 PM
+
+[Regarding recursive container containment]
+
+Mário,
+
+As far as I'm concerned, the most likely way to do this is to declare:
+   (1) an incomplete type T1;
+   (2) an access type A1 for which T1 is the designated type;
+   (3) a record type T2 which includes a component of type A1;
+   (4) a container type T3 with T2 as its element type;
+   (5) a completion of T1 as a derivation of T3.
+
+For example:
+
+   type Contact_List; -- (1)
+   type Contact_List_Ref is access Contact_List; -- (2)
+
+   type Contact_Descriptor is
+      record
+         ...
+         Friends: Contact_List_Ref;
+         ...
+      end record; -- (3)
+
+   package Contact_Lists is
+new Ada.Containers.Lists.Double.Unbounded(Contact_Descriptor); -- (4)
+   use Contact_Lists; -- to see non-operation and iterator-only declarations
+
+   type Contact_List is new Contact_Lists.Container_Type; -- (5)
+
+I'm not certain that this works perfectly, and I'm not sure it's the best
+possible way.
+
+Would we have difficulty instantiating Generic_Sort and Generic_Merge?
+
+*************************************************************
+
+From: Mario Amado Alves
+Sent: Monday, September 29, 2003  4:31 PM
+
+Hmm... it's not exactly recursive because the elements of the second
+container type R do not refer exactly to R containers--they refer to the
+first container type instead.
+
+*************************************************************
+
+From: Mario Amado Alves
+Sent: Thursday, October  2, 2003  1:06 PM
+
+"If you have reference semantics, then of course a conventional tree is all you need." (Ed)
+
+That is indeed the case. AI-302 containers are by-reference types.
+
+*************************************************************
+
+From: Mario Amado Alves
+Sent: Thursday, October  2, 2003  1:08 PM
+
+> As far as I'm concerned, the most likely way to do this is to declare:
+>    (1) an incomplete type T1;
+>    (2) an access type A1 for which T1 is the designated type;
+>    (3) a record type T2 which includes a component of type A1;
+>    (4) a container type T3 with T2 as its element type;
+>    (5) a completion of T1 as a derivation of T3.
+> 
+> I'm not certain that this works perfectly, and I'm not sure it's the 
+> best possible way.
+
+It's a nice way. The Ada way. Access types. Thanks. I'll rewrite what I
+have this way and see if I find any problems. (The only 'problem' I see
+already is merely of style: because containers are already by-reference,
+access types to containers bring two levels of indirection--which is ugly
+to us pointerless programming types.)
+
+*************************************************************
+
+From: Tucker Taft
+Sent: Monday, September 29, 2003  10:34 PM
+
+I wonder about the complexity vs. value of multimaps
+and multisets.  It seems easy enough to use maps and sets,
+and make the associated value itself be a container
+(e.g. a linked list).  I realize there might be some
+small additional cost, but in my experience, the
+typical number of uses of multisets/multimaps is an order
+of magnitude smaller than the number of uses of sets/maps,
+while the implementation complexity of multisets/multimaps
+if you are trying to do them without the level of indirection
+implied by a set of lists is significant (and rarely
+worth the trouble).
+
+*************************************************************
+
+From: Matthew Heaney
+Sent: Tuesday, September 30, 2003  9:47 AM
+
+In the multimap case, it is indeed true you could implement it as a map
+whose element subtype is a linked list.  With that in mind, my latest
+proposal has 5 containers:
+
+vector
+linked list
+hashed map with string-key forms too
+sorted set
+sorted multiset
+
+There are only unbounded forms.  If we take away the (sorted) multiset,
+that would reduce it to 4 containers:
+
+vector
+linked list
+hashed map et al
+sorted set
+
+The case for implementing a multiset as a set with a linked-list element
+is harder to argue, because set elements are in general nonmutable.  To
+modify a set element, the API provides the Unchecked_Modification
+operation, which was named that way to put the fear of god into anyone
+who tried to use it.  
+
+If we intend to use a sorted set as a multiset, then we're saying that
+set element modification is normal.  In that case we should probably
+move the Unchecked_Modification operation back up into the parent, and
+give the operation a less scary name.  Alternatively, we could provide a
+sorted map.
+
+> I realize there might be some
+> small additional cost, but in my experience, the
+> typical number of uses of multisets/multimaps is an order
+> of magnitude smaller than the number of uses of sets/maps, 
+> while the implementation complexity of multisets/multimaps if 
+> you are trying to do them without the level of indirection 
+> implied by a set of lists is significant (and rarely worth 
+> the trouble).
+
+In the case of Charles, all the sorted maps, multimaps, sets, and
+multisets use the same red-black tree type.  There are only minor
+differences between the unique-key and multiple-key forms.  (Actually,
+that's true for the hashed forms as well.)  
+
+The only salient difference between a single-key container and a
+multi-key container is the behavior of insert.  In the former case
+insertion is conditional, and in latter case insertion is unconditional.
+The low-level tree type has both kinds of insertion operations, which
+are called as appropriate by the high-level container abstraction.
+
+*************************************************************
+
+From: Nick Roberts
+Sent: Tuesday, September 30, 2003  4:01 PM
+
+> I wonder about the complexity vs. value of multimaps
+> and multisets.  It seems easy enough to use maps and sets,
+> and make the associated value itself be a container
+> (e.g. a linked list).  ...
+
+I think I'd agree that the multimaps and multisets could be done without,
+but I'm alarmed about the idea of reducing the number of containers or
+operations too much. Surely we should not set some arbitrary limit (e.g. 20
+or 25 pages) which could cause some really useful feature to be discarded.
+Please, oh please, if Matt ends up with 26 or 27 pages the result should be
+reviewed and possibly considered acceptable!
+
+Incidentally, on reading through AI-302 (02), I'm coming to like the
+proposal. My concerns about this design (Charles) were always relatively
+minor, and I'd much rather that some container library were adopted, rather
+than none at all. I think it's size is mitigated by its orthogonality, and I
+think that the size of the perceived interface is more important than the
+amount of code or the size of an implementation.
+
+As for the composition problems, couldn't the container types be made
+visibly controlled? I don't much like this idea, but it might be the lesser
+of two evils.
+
+Also, should I toss in a proposal for some trivial utility generic
+procedures and functions (Sort_Array, Reverse_Array, that sort of thing)?
+
+*************************************************************
+
+From: Mario Amado Alves
+Sent: Tuesday, September 30, 2003  4:15 AM
+
+I have found (uni? mono?)elementary containers (containers of only one
+element) useful in many situations.
+
+generic
+  type Element (<>) is private;
+package Ada.Containers.Elementary is
+  type Container is private;
+  procedure Put (C : in out Container; E : in Element);
+  function Get (C : Container) return Element;
+end;
+
+It is an incredibily simple (and short :-) abstraction but very useful.
+It provides pointerless programming. With Annex <PC>, it provides a
+simple way to save/load one-of-a-kind objects. I have implemented the IE
+and PC extensions to AI-302-02 using elementary containers to much
+advantage (see below; more details on request). I propose elementary
+containers be added to AI-302, right on clause A.16. Alternatively, on
+Annex <IE>.
+
+The spec above might be too short. Here's how a real signature looks
+like:
+
+  generic
+    type Element (<>) is private;
+    type Element_Ptr is access all Element;
+    type Container is private;
+    with procedure Put (C : in out Container; E : Element) is <>;
+    with function Put (E : Element) return Container is <>;
+    with function Get (C : Container) return Element is <>;
+    with procedure Delete (C : in out Container) is <>;
+    with function Access_Of (C : Container) return Element_Ptr is <>;
+    with function "=" (L, R : Container) return Boolean is <>;
+    with procedure Overwrite (C : Container; E : Element) is <>;
+    with function Img (C : Container) return String is <>;
+  package Signature is end;
+
+This is from an adaptation of SCOPE to Charles used to make
+proof-of-concept implementations for Annexes <IE> and <PC>. It is long,
+but: Element_Ptr, Access_Of and "=" were specifically added for Charles;
+Img was added for instrumentation; Overwrite is also kind of
+implementation-oriented, and can be dropped in the right context; Delete
+can also be excused, if we're happy with the container doing that on
+finalization.
+
+So a more realistic spec might be
+
+generic
+  type Element (<>) is private;
+package Ada.Containers.Elementary is
+  type Container is private;
+  procedure Put (C : in out Container; E : in Element);
+  function Put (E : Element) return Container;
+  function Get (C : Container) return Element;
+  procedure Delete (C : Container);
+end;
+
+*************************************************************
+
 

Questions? Ask the ACAA Technical Agent