[Python-checkins] r70100 - peps/trunk/pep-0372.txt

[raymond.hettinger]

Author: raymond.hettinger
Date: Mon Mar  2 21:40:36 2009
New Revision: 70100

Log:
Mark the PEP as Accepted.
Replace the odict references with OrderedDict.
Specify the __repr__() format.
Update the __eq__() specification as discussed on python-dev.



Modified:
   peps/trunk/pep-0372.txt

Modified: peps/trunk/pep-0372.txt
==============================================================================
--- peps/trunk/pep-0372.txt	(original)
+++ peps/trunk/pep-0372.txt	Mon Mar  2 21:40:36 2009
@@ -4,7 +4,7 @@
 Last-Modified: $Date$
 Author: Armin Ronacher <armin.ronacher at active-4.com>
         Raymond Hettinger <python at rcn.com>
-Status: Draft
+Status: Accepted
 Type: Standards Track
 Content-Type: text/x-rst
 Created: 15-Jun-2008
@@ -16,7 +16,7 @@
 ========
 
 This PEP proposes an ordered dictionary as a new data structure for
-the ``collections`` module, called "odict" in this PEP for short.  The
+the ``collections`` module, called "OrderedDict" in this PEP.  The
 proposed API incorporates the experiences gained from working with
 similar implementations that exist in various real-world applications
 and other programming languages.
@@ -44,13 +44,13 @@
 
 The following example shows the behavior for simple assignments:
 
-    >>> d = odict()
+    >>> d = OrderedDict()
     >>> d['parrot'] = 'dead'
     >>> d['penguin'] = 'exploded'
     >>> d.items()
     [('parrot', 'dead'), ('penguin', 'exploded')]
 
-That the ordering is preserved makes an odict useful for a couple of
+That the ordering is preserved makes an OrderedDict useful for a couple of
 situations:
 
 - XML/HTML processing libraries currently drop the ordering of
@@ -97,10 +97,10 @@
 well as mappings like a dict does.  Unlike a regular dictionary,
 the insertion order is preserved.
 
-    >>> d = odict([('a', 'b'), ('c', 'd')])
+    >>> d = OrderedDict([('a', 'b'), ('c', 'd')])
     >>> d.update({'foo': 'bar'})
     >>> d
-    collections.odict([('a', 'b'), ('c', 'd'), ('foo', 'bar')])
+    collections.OrderedDict([('a', 'b'), ('c', 'd'), ('foo', 'bar')])
 
 If ordered dicts are updated from regular dicts, the ordering of new
 keys is of course undefined.
@@ -119,7 +119,7 @@
 
 New methods not available on dict:
 
-``odict.__reversed__()``
+``OrderedDict.__reversed__()``
     Supports reverse iteration by key.
 
 
@@ -138,8 +138,8 @@
     former.  This has the side-effect that the position of the first
     key is used because only the value is actually overwritten::
 
-        >>> odict([('a', 1), ('b', 2), ('a', 3)])
-        collections.odict([('a', 3), ('b', 2)])
+        >>> OrderedDict([('a', 1), ('b', 2), ('a', 3)])
+        collections.OrderedDict([('a', 3), ('b', 2)])
 
     This behavior is consistent with existing implementations in
     Python, the PHP array and the hashmap in Ruby 1.9.
@@ -155,10 +155,10 @@
 Do any limitations arise from subclassing dict?
 
     Yes.  Since the API for dicts is different in Py2.x and Py3.x, the
-    odict API must also be different.  So, the Py2.7 version will need
+    OrderedDict API must also be different.  So, the Py2.7 version will need
     to override iterkeys, itervalues, and iteritems.
 
-Does ``odict.popitem()`` return a particular key/value pair?
+Does ``OrderedDict.popitem()`` return a particular key/value pair?
 
     Yes.  It pops-off the most recently inserted new key and its
     corresponding value.  This corresponds to the usual LIFO behavior
@@ -167,23 +167,26 @@
     The actual implementation is more efficient and pops directly
     from a sorted list of keys.
     
-Does odict support indexing, slicing, and whatnot?
+Does OrderedDict support indexing, slicing, and whatnot?
 
-    As a matter of fact, ``odict`` does not implement the ``Sequence``
+    As a matter of fact, ``OrderedDict`` does not implement the ``Sequence``
     interface.  Rather, it is a ``MutableMapping`` that remembers
     the order of key insertion.  The only sequence-like addition is
     support for ``reversed``.
 
-Does odict support alternate sort orders such as alphabetical?
+    An further advantage of not allowing indexing is that it leaves open
+    the possibility of a fast C implementation using linked lists.
+
+Does OrderedDict support alternate sort orders such as alphabetical?
 
    No.  Those wanting different sort orders really need to be using another
-   technique.  The odict is all about recording insertion order.   If any
+   technique.  The OrderedDict is all about recording insertion order.   If any
    other order is of interest, then another structure (like an in-memory
    dbm) is likely a better fit.
 
-How well does odict work with the json module, PyYAML, and ConfigParser?
+How well does OrderedDict work with the json module, PyYAML, and ConfigParser?
 
-   For json, the good news is that json's encoder respects odict's iteration order::
+   For json, the good news is that json's encoder respects OrderedDict's iteration order::
 
         >>> items = [('one', 1), ('two', 2), ('three',3), ('four',4), ('five',5)]
         >>> json.dumps(OrderedDict(items))
@@ -221,20 +224,18 @@
         >>> config.remove_option('Log', 'error')
         >>> config.write(open('myconfig.ini', 'w'))
 
-How does odict handle equality testing?
+How does OrderedDict handle equality testing?
+
+    Comparing two ordered dictionaries implies that the test will be
+    order-sensitive so that list ``(od1.items())==list(od2.items())``.
 
-   Being a dict, one might expect equality tests to not care about order.  For
-   an odict-to-dict comparison, this would be a necessity and it's probably
-   not wise to silently switch comparison modes based on the input types.
-   Also, some third-party tools that expect dict inputs may also expect the
-   comparison to not care about order.  Accordingly, we decided to punt and
-   let the usual dict equality testing run without reference to internal
-   ordering.  This should be documented clearly since different people will
-   have different expectations.  If a use case does arise, it's not hard for
-   a user explicitly craft an order based comparison::
+    When ordered dicts are compared with other Mappings, their order
+    insensitive comparison is used.  This allows ordered dictionaries
+    to be substituted anywhere regular dictionaries are used.
 
-       # Explict order-sensitive comparison
-       >>> list(od1.items())==list(od2.items())
+How __repr__ format will maintain order during an repr/eval round-trip?
+
+    OrderedDict([('a', 1), ('b', 2)])
 
 What are the trade-offs of the possible underlying data structures?
 
@@ -255,6 +256,7 @@
      would keep the same big-oh performance as regular dictionaries.  It is
      the fastest and most space efficient.
 
+
 Reference Implementation
 ========================