1
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
10
11
12 NULL = None
13 """An empty `LList`.
14
15 ::
16
17 len(NULL) = 0
18 hash(NULL) = 0
19 NULL.toList() = []
20 """
21
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' ]
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
43 """Iterate over the elements of this list."""
44 l = self
45 while l:
46 yield l.head
47 l = l.tail
49 """Return a string which could be 'eval'ed to yield this `LList`."""
50 return "LList("+repr(self.head)+","+repr(self.tail)+")"
52 """Return a string representation of this list."""
53 return '['+(', '.join(map(str,self)))+']'
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
63 return not (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:
68 return 0
69 if not self:
70 return -1 if other else 0
71 c = cmp(self.head, other.head)
72 return c if c != 0 else cmp(self.tail, other.tail)
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
85 """Return the length of this list."""
86 return self.len
88 """Return `True` iff the list has at least one item in it."""
89 return self is not NULL
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
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
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
113 """Create a python list from this `LList`."""
114 return list(self)
115
116 NULL = LList(None, None)
117 NULL.hash = 0
118