Module Functional
[show private]
[frames] | no frames]

Source Code for Module Functional

  1  #!/usr/bin/python2.5 
  2  """ 
  3  Functional data structures.  These include `LList`, an immutable linked-list 
  4  with constant-time addition to the head, tail slices, length and hash methods. 
  5  """ 
  6  __docformat__ = "restructuredtext" 
  7   
  8  #----------------------------------------------------------------------- 
  9  # Linked list data structure 
 10  #----------------------------------------------------------------------- 
 11   
 12  NULL = None # we'll override this in a second. 
 13  """An empty `LList`. 
 14   
 15  :: 
 16   
 17   len(NULL) = 0 
 18   hash(NULL) = 0 
 19   NULL.toList() = [] 
 20  """ 
 21   
22 -class LList(object):
23 """ 24 Immutable linked-list datatype. 25 26 Unlike python lists, allows constant-time addition to the head and 27 fast tail slices. Length and hash methods are also constant-time. 28 """ 29 __slots__ = [ 'head','tail','hash','len' ]
30 - def __init__(self, head, tail):
31 """Create a list consisting of `head` appended to the list 32 given by `tail`.""" 33 self.head = head 34 """The item at the start of this list.""" 35 self.tail = tail 36 """The list of items following the head.""" 37 self.hash = None 38 """Hashcode for this list.""" 39 self.len = self.tail.len+1 if self.tail is not None else 0 40 """Length of this list."""
41
42 - def __iter__(self):
43 """Iterate over the elements of this list.""" 44 l = self 45 while l: 46 yield l.head 47 l = l.tail
48 - def __repr__(self):
49 """Return a string which could be 'eval'ed to yield this `LList`.""" 50 return "LList("+repr(self.head)+","+repr(self.tail)+")"
51 - def __str__ (self):
52 """Return a string representation of this list.""" 53 return '['+(', '.join(map(str,self)))+']'
54 - def __eq__ (self, other):
55 """Return `True` iff the `LList` objects have the same contents 56 and order.""" 57 if self is other: 58 return True 59 if self.len != other.len or hash(self) != hash(other): 60 return False 61 return self.head == other.head and self.tail == other.tail
62 - def __ne__ (self, other):
63 return not (self == other)
64 - def __cmp__ (self, other):
65 """Compare two `LList` objects in lexicographic order: a list prefix 66 is "less than" the full list.""" 67 if self is other: # very important optimization. 68 return 0 69 if not self: 70 return -1 if other else 0 # eol less than everything else 71 c = cmp(self.head, other.head) 72 return c if c != 0 else cmp(self.tail, other.tail)
73 - def __hash__ (self):
74 """Return a hash of the contents of this list. 75 76 The hashcode for a LList is:: 77 78 hash(self.head) + (17 * hash(self.tail)) 79 80 """ 81 if self.hash is None: 82 self.hash = hash(self.head) + (17 * hash(self.tail)) 83 return self.hash
84 - def __len__ (self):
85 """Return the length of this list.""" 86 return self.len
87 - def __nonzero__ (self):
88 """Return `True` iff the list has at least one item in it.""" 89 return self is not NULL
90 - def __getitem__ (self, key):
91 """Returns an element or slice of this `LList`.""" 92 if isinstance(key, slice): 93 start, stop, stride = key.indices(self.len) 94 if start != 0: 95 return self.tail[(start-1):(stop-1):stride] 96 if start == 0 and stop == self.len and stride == 1: 97 return self 98 # bail. This will be slow! 99 return LList.fromList(self.toList()[start:stop:stride]) 100 if not self: 101 raise IndexError 102 return self.head if key == 0 else self.tail[key-1]
103
104 - def fromList(lst):
105 """Create an `LList` from a python list.""" 106 r = NULL 107 for x in reversed(lst): 108 r = LList(x, r) 109 return r
110 fromList = staticmethod(fromList) 111
112 - def toList(self):
113 """Create a python list from this `LList`.""" 114 return list(self)
115 116 NULL = LList(None, None) # this is the true null value. 117 NULL.hash = 0 118