Source Code for Module nltk.containers

  1  # Natural Language Toolkit: Miscellaneous container classes 
  2  # 
  3  # Copyright (C) 2001-2008 NLTK Project 
  4  # Author: Steven Bird <[email protected]> 
  5  # URL: <http://nltk.org> 
  6  # For license information, see LICENSE.TXT 
  7   
  8 -class SortedDict(dict): 
  9      """ 
 10      A very rudamentary sorted dictionary, whose main purpose is to 
 11      allow dictionaries to be displayed in a consistent order in 
 12      regression tests.  keys(), items(), values(), iter*(), and 
 13      __repr__ all sort their return values before returning them. 
 14      (note that the sort order for values() does *not* correspond to 
 15      the sort order for keys().  I.e., zip(d.keys(), d.values()) is not 
 16      necessarily equal to d.items(). 
 17      """ 
 18 -    def keys(self): return sorted(dict.keys(self)) 
 19 -    def items(self): return sorted(dict.items(self)) 
 20 -    def values(self): return sorted(dict.values(self)) 
 21 -    def iterkeys(self): return iter(sorted(dict.keys(self))) 
 22 -    def iteritems(self): return iter(sorted(dict.items(self))) 
 23 -    def itervalues(self): return iter(sorted(dict.values(self))) 
 24 -    def __iter__(self): return iter(sorted(dict.keys(self))) 
 25 -    def repr(self): 
 26          items = ['%s=%s' % t for t in sorted(self.items())] 
 27          return '{%s}' % ', '.join(items) 
 28       
 29  # OrderedDict: Written Doug Winter 
 30  # http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/438823 
 31   
 32 -class OrderedDict(dict): 
 33      """ 
 34      This implementation of a dictionary keeps track of the order 
 35      in which keys were inserted. 
 36      """ 
 37   
 38 -    def __init__(self, d={}): 
 39          self._keys = d.keys() 
 40          dict.__init__(self, d) 
 41   
 42 -    def __delitem__(self, key): 
 43          dict.__delitem__(self, key) 
 44          self._keys.remove(key) 
 45   
 46 -    def __setitem__(self, key, item): 
 47          dict.__setitem__(self, key, item) 
 48          # a peculiar sharp edge from copy.deepcopy 
 49          # we'll have our set item called without __init__ 
 50          if not hasattr(self, '_keys'): 
 51              self._keys = [key,] 
 52          if key not in self._keys: 
 53              self._keys.append(key) 
 54   
 55 -    def clear(self): 
 56          dict.clear(self) 
 57          self._keys = [] 
 58   
 59 -    def items(self): 
 60          for i in self._keys: 
 61              yield i, self[i] 
 62   
 63 -    def keys(self): 
 64          return self._keys 
 65   
 66 -    def popitem(self): 
 67          if len(self._keys) == 0: 
 68              raise KeyError('dictionary is empty') 
 69          else: 
 70              key = self._keys[-1] 
 71              val = self[key] 
 72              del self[key] 
 73              return key, val 
 74   
 75 -    def setdefault(self, key, failobj = None): 
 76          dict.setdefault(self, key, failobj) 
 77          if key not in self._keys: 
 78              self._keys.append(key) 
 79   
 80 -    def update(self, d): 
 81          for key in d.keys(): 
 82              if key not in self: 
 83                  self._keys.append(key) 
 84          dict.update(self, d) 
 85   
 86 -    def values(self): 
 87          for i in self._keys: 
 88              yield self[i] 
 89   
 90 -    def move(self, key, index): 
 91   
 92          """ Move the specified to key to *before* the specified index. """ 
 93   
 94          try: 
 95              cur = self._keys.index(key) 
 96          except ValueError: 
 97              raise KeyError(key) 
 98          self._keys.insert(index, key) 
 99          # this may have shifted the position of cur, if it is after index 
100          if cur >= index: cur = cur + 1 
101          del self._keys[cur] 
102   
103 -    def index(self, key): 
104          if key not in self: 
105              raise KeyError(key) 
106          return self._keys.index(key) 
107   
108   
109  ########################################################################## 
110  # TRIES 
111  ########################################################################## 
112   
113  # Trie structure, by James Tauber and Leonardo Maffi (V. 1.2, July 18 2006) 
114  # Extended by Steven Bird 
115   
116 -class Trie: 
117      """A Trie is like a dictionary in that it maps keys to 
118      values. However, because of the way keys are stored, it allows 
119      look up based on the longest prefix that matches.  Keys must be 
120      strings. 
121      """ 
122   
123 -    def __init__(self, trie=None): 
124          if trie is None: 
125              self._root = [None, {}, 0] 
126          else: 
127              self._root = trie 
128   
129 -    def clear(self): 
130          self._root = [None, {}, 0] 
131   
132 -    def isleaf(self, key): 
133          """Return True if the key is present and it's a leaf of the 
134          Trie, False otherwise.""" 
135   
136          curr_node = self._root 
137          for char in key: 
138              curr_node_1 = curr_node[1] 
139              if char in curr_node_1: 
140                  curr_node = curr_node_1[char] 
141              else: 
142                  return False 
143          return curr_node[0] is not None 
144   
145 -    def find_prefix(self, key): 
146          """Find as much of the key as one can, by using the longest 
147          prefix that has a value.  Return (value, remainder) where 
148          remainder is the rest of the given string.""" 
149   
150          curr_node = self._root 
151          remainder = key 
152          for char in key: 
153              if char in curr_node[1]: 
154                  curr_node = curr_node[1][char] 
155              else: 
156                  return curr_node[0], remainder 
157              remainder = remainder[1:] 
158          return curr_node[0], remainder 
159   
160 -    def subtrie(self, key): 
161          curr_node = self._root 
162          for char in key: 
163              curr_node = curr_node[1][char] 
164          return Trie(trie=curr_node) 
165   
166 -    def __len__(self): 
167          return self._root[2] 
168   
169 -    def __eq__(self, other): 
170          return self._root == other._root 
171   
172 -    def __ne__(self, other): 
173          return not (self == other) 
174   
175 -    def __setitem__(self, key, value): 
176          curr_node = self._root 
177          for char in key: 
178              curr_node[2] += 1 
179              curr_node = curr_node[1].setdefault(char, [None, {}, 0]) 
180          curr_node[0] = value 
181          curr_node[2] += 1 
182   
183 -    def __getitem__(self, key): 
184          """Return the value for the given key if it is present, raises 
185          a KeyError if key not found, and return None if it is present 
186          a key2 that starts with key.""" 
187   
188          curr_node = self._root 
189          for char in key: 
190              curr_node = curr_node[1][char] 
191          return curr_node[0] 
192   
193 -    def __contains__(self, key): 
194          """Return True if the key is present or if it is present a 
195          key2 string that starts with key.""" 
196   
197          curr_node = self._root 
198          for char in key: 
199              curr_node_1 = curr_node[1] 
200              if char in curr_node_1: 
201                  curr_node = curr_node_1[char] 
202              else: 
203                  return False 
204          return True 
205   
206 -    def __str__(self): 
207          return str(self._root) 
208   
209 -    def __repr__(self): 
210          return "Trie(%r)" % self._root 
211