Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/pyrsistent/_plist.py: 35%
143 statements
« prev ^ index » next coverage.py v7.2.2, created at 2023-03-26 06:12 +0000
« prev ^ index » next coverage.py v7.2.2, created at 2023-03-26 06:12 +0000
1from collections.abc import Sequence, Hashable
2from numbers import Integral
3from functools import reduce
6class _PListBuilder(object):
7 """
8 Helper class to allow construction of a list without
9 having to reverse it in the end.
10 """
11 __slots__ = ('_head', '_tail')
13 def __init__(self):
14 self._head = _EMPTY_PLIST
15 self._tail = _EMPTY_PLIST
17 def _append(self, elem, constructor):
18 if not self._tail:
19 self._head = constructor(elem)
20 self._tail = self._head
21 else:
22 self._tail.rest = constructor(elem)
23 self._tail = self._tail.rest
25 return self._head
27 def append_elem(self, elem):
28 return self._append(elem, lambda e: PList(e, _EMPTY_PLIST))
30 def append_plist(self, pl):
31 return self._append(pl, lambda l: l)
33 def build(self):
34 return self._head
37class _PListBase(object):
38 __slots__ = ('__weakref__',)
40 # Selected implementations can be taken straight from the Sequence
41 # class, other are less suitable. Especially those that work with
42 # index lookups.
43 count = Sequence.count
44 index = Sequence.index
46 def __reduce__(self):
47 # Pickling support
48 return plist, (list(self),)
50 def __len__(self):
51 """
52 Return the length of the list, computed by traversing it.
54 This is obviously O(n) but with the current implementation
55 where a list is also a node the overhead of storing the length
56 in every node would be quite significant.
57 """
58 return sum(1 for _ in self)
60 def __repr__(self):
61 return "plist({0})".format(list(self))
62 __str__ = __repr__
64 def cons(self, elem):
65 """
66 Return a new list with elem inserted as new head.
68 >>> plist([1, 2]).cons(3)
69 plist([3, 1, 2])
70 """
71 return PList(elem, self)
73 def mcons(self, iterable):
74 """
75 Return a new list with all elements of iterable repeatedly cons:ed to the current list.
76 NB! The elements will be inserted in the reverse order of the iterable.
77 Runs in O(len(iterable)).
79 >>> plist([1, 2]).mcons([3, 4])
80 plist([4, 3, 1, 2])
81 """
82 head = self
83 for elem in iterable:
84 head = head.cons(elem)
86 return head
88 def reverse(self):
89 """
90 Return a reversed version of list. Runs in O(n) where n is the length of the list.
92 >>> plist([1, 2, 3]).reverse()
93 plist([3, 2, 1])
95 Also supports the standard reversed function.
97 >>> reversed(plist([1, 2, 3]))
98 plist([3, 2, 1])
99 """
100 result = plist()
101 head = self
102 while head:
103 result = result.cons(head.first)
104 head = head.rest
106 return result
107 __reversed__ = reverse
109 def split(self, index):
110 """
111 Spilt the list at position specified by index. Returns a tuple containing the
112 list up until index and the list after the index. Runs in O(index).
114 >>> plist([1, 2, 3, 4]).split(2)
115 (plist([1, 2]), plist([3, 4]))
116 """
117 lb = _PListBuilder()
118 right_list = self
119 i = 0
120 while right_list and i < index:
121 lb.append_elem(right_list.first)
122 right_list = right_list.rest
123 i += 1
125 if not right_list:
126 # Just a small optimization in the cases where no split occurred
127 return self, _EMPTY_PLIST
129 return lb.build(), right_list
131 def __iter__(self):
132 li = self
133 while li:
134 yield li.first
135 li = li.rest
137 def __lt__(self, other):
138 if not isinstance(other, _PListBase):
139 return NotImplemented
141 return tuple(self) < tuple(other)
143 def __eq__(self, other):
144 """
145 Traverses the lists, checking equality of elements.
147 This is an O(n) operation, but preserves the standard semantics of list equality.
148 """
149 if not isinstance(other, _PListBase):
150 return NotImplemented
152 self_head = self
153 other_head = other
154 while self_head and other_head:
155 if not self_head.first == other_head.first:
156 return False
157 self_head = self_head.rest
158 other_head = other_head.rest
160 return not self_head and not other_head
162 def __getitem__(self, index):
163 # Don't use this this data structure if you plan to do a lot of indexing, it is
164 # very inefficient! Use a PVector instead!
166 if isinstance(index, slice):
167 if index.start is not None and index.stop is None and (index.step is None or index.step == 1):
168 return self._drop(index.start)
170 # Take the easy way out for all other slicing cases, not much structural reuse possible anyway
171 return plist(tuple(self)[index])
173 if not isinstance(index, Integral):
174 raise TypeError("'%s' object cannot be interpreted as an index" % type(index).__name__)
176 if index < 0:
177 # NB: O(n)!
178 index += len(self)
180 try:
181 return self._drop(index).first
182 except AttributeError as e:
183 raise IndexError("PList index out of range") from e
185 def _drop(self, count):
186 if count < 0:
187 raise IndexError("PList index out of range")
189 head = self
190 while count > 0:
191 head = head.rest
192 count -= 1
194 return head
196 def __hash__(self):
197 return hash(tuple(self))
199 def remove(self, elem):
200 """
201 Return new list with first element equal to elem removed. O(k) where k is the position
202 of the element that is removed.
204 Raises ValueError if no matching element is found.
206 >>> plist([1, 2, 1]).remove(1)
207 plist([2, 1])
208 """
210 builder = _PListBuilder()
211 head = self
212 while head:
213 if head.first == elem:
214 return builder.append_plist(head.rest)
216 builder.append_elem(head.first)
217 head = head.rest
219 raise ValueError('{0} not found in PList'.format(elem))
222class PList(_PListBase):
223 """
224 Classical Lisp style singly linked list. Adding elements to the head using cons is O(1).
225 Element access is O(k) where k is the position of the element in the list. Taking the
226 length of the list is O(n).
228 Fully supports the Sequence and Hashable protocols including indexing and slicing but
229 if you need fast random access go for the PVector instead.
231 Do not instantiate directly, instead use the factory functions :py:func:`l` or :py:func:`plist` to
232 create an instance.
234 Some examples:
236 >>> x = plist([1, 2])
237 >>> y = x.cons(3)
238 >>> x
239 plist([1, 2])
240 >>> y
241 plist([3, 1, 2])
242 >>> y.first
243 3
244 >>> y.rest == x
245 True
246 >>> y[:2]
247 plist([3, 1])
248 """
249 __slots__ = ('first', 'rest')
251 def __new__(cls, first, rest):
252 instance = super(PList, cls).__new__(cls)
253 instance.first = first
254 instance.rest = rest
255 return instance
257 def __bool__(self):
258 return True
259 __nonzero__ = __bool__
262Sequence.register(PList)
263Hashable.register(PList)
266class _EmptyPList(_PListBase):
267 __slots__ = ()
269 def __bool__(self):
270 return False
271 __nonzero__ = __bool__
273 @property
274 def first(self):
275 raise AttributeError("Empty PList has no first")
277 @property
278 def rest(self):
279 return self
282Sequence.register(_EmptyPList)
283Hashable.register(_EmptyPList)
285_EMPTY_PLIST = _EmptyPList()
288def plist(iterable=(), reverse=False):
289 """
290 Creates a new persistent list containing all elements of iterable.
291 Optional parameter reverse specifies if the elements should be inserted in
292 reverse order or not.
294 >>> plist([1, 2, 3])
295 plist([1, 2, 3])
296 >>> plist([1, 2, 3], reverse=True)
297 plist([3, 2, 1])
298 """
299 if not reverse:
300 iterable = list(iterable)
301 iterable.reverse()
303 return reduce(lambda pl, elem: pl.cons(elem), iterable, _EMPTY_PLIST)
306def l(*elements):
307 """
308 Creates a new persistent list containing all arguments.
310 >>> l(1, 2, 3)
311 plist([1, 2, 3])
312 """
313 return plist(elements)