Revision b4368e33 kamaki/clients/commissioning/utils/ordereddict.py

b/kamaki/clients/commissioning/utils/ordereddict.py
1 
# Backport of OrderedDict() class that runs on Python 2.4, 2.5, 2.6, 2.7 and pypy.
2 
# Passes Python2.7's test suite and incorporates all the latest updates.
1 
#!/usr/bin/env python
2 

  		





  
  3
  
    
# Copyright 2012 GRNET S.A. All rights reserved.


  		





  
  4
  
    
#


  		





  
  5
  
    
# Redistribution and use in source and binary forms, with or


  		





  
  6
  
    
# without modification, are permitted provided that the following


  		





  
  7
  
    
# conditions are met:


  		





  
  8
  
    
#


  		





  
  9
  
    
#   1. Redistributions of source code must retain the above


  		





  
  10
  
    
#      copyright notice, this list of conditions and the following


  		





  
  11
  
    
#      disclaimer.


  		





  
  12
  
    
#


  		





  
  13
  
    
#   2. Redistributions in binary form must reproduce the above


  		





  
  14
  
    
#      copyright notice, this list of conditions and the following


  		





  
  15
  
    
#      disclaimer in the documentation and/or other materials


  		





  
  16
  
    
#      provided with the distribution.


  		





  
  17
  
    
#


  		





  
  18
  
    
# THIS SOFTWARE IS PROVIDED BY GRNET S.A. ``AS IS'' AND ANY EXPRESS


  		





  
  19
  
    
# OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED


  		





  
  20
  
    
# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR


  		





  
  21
  
    
# PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GRNET S.A OR


  		





  
  22
  
    
# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,


  		





  
  23
  
    
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT


  		





  
  24
  
    
# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF


  		





  
  25
  
    
# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED


  		





  
  26
  
    
# AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT


  		





  
  27
  
    
# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN


  		





  
  28
  
    
# ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE


  		





  
  29
  
    
# POSSIBILITY OF SUCH DAMAGE.


  		





  
  30
  
    
#


  		





  
  31
  
    
# The views and conclusions contained in the software and


  		





  
  32
  
    
# documentation are those of the authors and should not be


  		





  
  33
  
    
# interpreted as representing official policies, either expressed


  		





  
  34
  
    
# or implied, of GRNET S.A.


  		





  
  35
  
    

  		





  
  36
  
    
# Backport of OrderedDict() class that runs on Python 2.4, 2.5, 2.6, 2.7 and


  		





  
  37
  
    
# pypy. Passes Python2.7's test suite and incorporates all the latest updates.


  		





  3
  38
  
    

  		





  4
  39
  
    
try:


  		





  5
  40
  
    
    from thread import get_ident as _get_ident


  		





  ......




  17
  52
  
    
    # An inherited dict maps keys to values.


  		





  18
  53
  
    
    # The inherited dict provides __getitem__, __len__, __contains__, and get.


  		





  19
  54
  
    
    # The remaining methods are order-aware.


  		





  20
  
  
    
    # Big-O running times for all methods are the same as for regular dictionaries.


  		





  
  55
  
    
    # Big-O running times for all methods are the same as for regular


  		





  
  56
  
    
    # dictionaries.


  		





  21
  57
  
    

  		





  22
  
  
    
    # The internal self.__map dictionary maps keys to links in a doubly linked list.


  		





  
  58
  
    
    # The internal self.__map dictionary maps keys to links in a doubly linked 


  		





  
  59
  
    
    # list.


  		





  23
  60
  
    
    # The circular doubly linked list starts and ends with a sentinel element.


  		





  24
  61
  
    
    # The sentinel element never gets deleted (this simplifies the algorithm).


  		





  25
  62
  
    
    # Each link is stored as a list of length three:  [PREV, NEXT, KEY].


  		





  ......




  42
  79
  
    

  		





  43
  80
  
    
    def __setitem__(self, key, value, dict_setitem=dict.__setitem__):


  		





  44
  81
  
    
        'od.__setitem__(i, y) <==> od[i]=y'


  		





  45
  
  
    
        # Setting a new item creates a new link which goes at the end of the linked


  		





  46
  
  
    
        # list, and the inherited dictionary is updated with the new key/value pair.


  		





  
  82
  
    
        # Setting a new item creates a new link which goes at the end of the


  		





  
  83
  
    
        # linked


  		





  
  84
  
    
        # list, and the inherited dictionary is updated with the new key/value


  		





  
  85
  
    
        # pair.


  		





  47
  86
  
    
        if key not in self:


  		





  48
  87
  
    
            root = self.__root


  		





  49
  88
  
    
            last = root[0]


  		





  ......




  53
  92
  
    
    def __delitem__(self, key, dict_delitem=dict.__delitem__):


  		





  54
  93
  
    
        'od.__delitem__(y) <==> del od[y]'


  		





  55
  94
  
    
        # Deleting an existing item uses self.__map to find the link which is


  		





  56
  
  
    
        # then removed by updating the links in the predecessor and successor nodes.


  		





  
  95
  
    
        # then removed by updating the links in the predecessor and successor


  		





  
  96
  
    
        # nodes.


  		





  57
  97
  
    
        dict_delitem(self, key)


  		





  58
  98
  
    
        link_prev, link_next, key = self.__map.pop(key)


  		





  59
  99
  
    
        link_prev[1] = link_next


  		





  ......




  142
  182
  
    
        '''od.update(E, **F) -> None.  Update od from dict/iterable E and F.


  		





  143
  183
  
    

  		





  144
  184
  
    
        If E is a dict instance, does:           for k in E: od[k] = E[k]


  		





  145
  
  
    
        If E has a .keys() method, does:         for k in E.keys(): od[k] = E[k]


  		





  
  185
  
    
        If E has a .keys() method, does:         for k in E.keys(): od[k]=E[k]


  		





  146
  186
  
    
        Or if E is an iterable of items, does:   for k, v in E: od[k] = v


  		





  147
  
  
    
        In either case, this is followed by:     for k, v in F.items(): od[k] = v


  		





  
  187
  
    
        In either case, this is followed by:     for k, v in F.items(): od[k]=v


  		





  148
  188
  
    

  		





  149
  189
  
    
        '''


  		





  150
  190
  
    
        if len(args) > 2:


  		












Also available in:
  Unified diff