game/util/stablelist.py

   1 # ###################################################
   2 # Copyright (C) 2008 The OpenAnno Team
   3 # team@openanno.org
   4 # This file is part of OpenAnno.
   5 #
   6 # OpenAnno is free software; you can redistribute it and/or modify
   7 # it under the terms of the GNU General Public License as published by
   8 # the Free Software Foundation; either version 2 of the License, or
   9 # (at your option) any later version.
  10 #
  11 # This program is distributed in the hope that it will be useful,
  12 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 # GNU General Public License for more details.
  15 #
  16 # You should have received a copy of the GNU General Public License
  17 # along with this program; if not, write to the
  18 # Free Software Foundation, Inc.,
  19 # 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20 # ###################################################
  21
  22 class stablelist(object):
  23         def __init__(self, *values):
  24                 self.clear()
  25                 for v in values:
  26                         self.append(v)
  27
  28         def _getFreeKey(self):
  29                 if len(self._free) > 0:
  30                         return self._free.pop()
  31                 else:
  32                         self._last += 1
  33                         return self._last
  34
  35         def append(self, value):
  36                 key = self._getFreeKey()
  37                 self._values[key] = value
  38                 return key
  39
  40         def clear(self):
  41                 self._last = -1
  42                 self._free = []
  43                 self._values = {}
  44
  45         def count(self):
  46                 return len(self._values)
  47
  48         def extend(self, *values):
  49                 for v in values:
  50                         self.append(v)
  51
  52         def get(self, key, otherwise = None):
  53                 assert(isinstance(key, int) and key >= 0)
  54                 return self[key] if key in self else otherwise
  55
  56         def has_key(self, key):
  57                 assert(isinstance(key, int) and key >= 0)
  58                 return key in self._values
  59
  60         def index(self, value):
  61                 for k, v in self._values.items():
  62                         if v == value:
  63                                 return k
  64                 else:
  65                         raise ValueError()
  66
  67         def items(self):
  68                 return self._values.items()
  69
  70         def iteritems(self):
  71                 return self._values.iteritems()
  72
  73         def iterkeys(self):
  74                 return self._values.iterkeys()
  75
  76         def itervalues(self):
  77                 return self._values.itervalues()
  78
  79         def keys(self):
  80                 return self._values.keys()
  81
  82         def pop(self, index = None):
  83                 if index is None:
  84                         index = self._last
  85                 else:
  86                         assert(isinstance(key, int) and key >= 0)
  87                 #index can be 0 if no item exists... -> error
  88                 ret = self[index]
  89                 del self[index]
  90                 return ret
  91
  92         def popitem(self):
  93                 return (self._last, self.pop(self._last))
  94
  95         def remove(self, value):
  96                 del self[self.index(value)]
  97
  98         def setdefault(self, key, value):
  99                 assert(isinstance(key, int) and key >= 0)
 100                 if key not in self._values:
 101                         self[key] = value
 102                 return self[key]
 103
 104         def values(self):
 105                 return self._values.values()
 106
 107         def __add__(self, other):
 108                 assert(self.__class__ == other.__class__)
 109                 ret = stablelist(self)
 110                 for v in other:
 111                         ret.append(self)
 112                 return ret
 113
 114         def __contains__(self, value):
 115                 try:
 116                         return self.index(value) >= 0
 117                 except:
 118                         return False
 119
 120         def __delitem__(self, key):
 121                 assert(isinstance(key, int) and key >= 0)
 122                 del self._values[key]
 123                 if key == self._last:
 124                         for i in xrange(key - 1, -1, -1):
 125                                 if i in self._values:
 126                                         self._last = i
 127                                         return
 128                                 else:
 129                                         self._free.remove(i)
 130                         else:
 131                                 self._last = -1
 132                 else:
 133                         self._free.append(key)
 134
 135         def __eq__(self, other):
 136                 assert(self.__class__ == other.__class__)
 137                 return self._values == other._values
 138
 139         def __getitem__(self, key):
 140                 assert(isinstance(key, int) and key >= 0)
 141                 return self._values[key]
 142
 143         def __hash__(self):
 144                 return hash(self._values)
 145
 146         def __iadd__(self, other):
 147                 assert(self.__class__ == other.__class__)
 148                 ret = []
 149                 for v in other:
 150                         ret = ret + [self.append(v)]
 151                 return ret
 152
 153         def __iter__(self):
 154                 return self._values.itervalues()
 155
 156         def __len__(self):
 157                 return len(self._values)
 158
 159         def __ne__(self, other):
 160                 return not (self == other)
 161
 162         def __repr__(self):
 163                 return repr(self._values)
 164
 165         def __str__(self):
 166                 return str(self._values)
 167
 168         def __setitem__(self, key, value):
 169                 assert(isinstance(key, int) and key >= 0)
 170                 if key not in self._values:
 171                         if key in self._free:
 172                                 self._free.remove(key)
 173                         else:
 174                                 for i in xrange(self._last + 1, key):
 175                                         self._free.append(i)
 176                                 self._last = key
 177                 self._values[key] = value