Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/pyrsistent/_plist.py: 35%

1from collections.abc import Sequence, Hashable 

2from numbers import Integral 

3from functools import reduce 

4 

5 

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') 

12 

13 def __init__(self): 

14 self._head = _EMPTY_PLIST 

15 self._tail = _EMPTY_PLIST 

16 

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 

24 

25 return self._head 

26 

27 def append_elem(self, elem): 

28 return self._append(elem, lambda e: PList(e, _EMPTY_PLIST)) 

29 

30 def append_plist(self, pl): 

31 return self._append(pl, lambda l: l) 

32 

33 def build(self): 

34 return self._head 

35 

36 

37class _PListBase(object): 

38 __slots__ = ('__weakref__',) 

39 

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 

45 

46 def __reduce__(self): 

47 # Pickling support 

48 return plist, (list(self),) 

49 

50 def __len__(self): 

51 """ 

52 Return the length of the list, computed by traversing it. 

53 

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) 

59 

60 def __repr__(self): 

61 return "plist({0})".format(list(self)) 

62 __str__ = __repr__ 

63 

64 def cons(self, elem): 

65 """ 

66 Return a new list with elem inserted as new head. 

67 

68 >>> plist([1, 2]).cons(3) 

69 plist([3, 1, 2]) 

70 """ 

71 return PList(elem, self) 

72 

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)). 

78 

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) 

85 

86 return head 

87 

88 def reverse(self): 

89 """ 

90 Return a reversed version of list. Runs in O(n) where n is the length of the list. 

91 

92 >>> plist([1, 2, 3]).reverse() 

93 plist([3, 2, 1]) 

94 

95 Also supports the standard reversed function. 

96 

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 

105 

106 return result 

107 __reversed__ = reverse 

108 

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). 

113 

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 

124 

125 if not right_list: 

126 # Just a small optimization in the cases where no split occurred 

127 return self, _EMPTY_PLIST 

128 

129 return lb.build(), right_list 

130 

131 def __iter__(self): 

132 li = self 

133 while li: 

134 yield li.first 

135 li = li.rest 

136 

137 def __lt__(self, other): 

138 if not isinstance(other, _PListBase): 

139 return NotImplemented 

140 

141 return tuple(self) < tuple(other) 

142 

143 def __eq__(self, other): 

144 """ 

145 Traverses the lists, checking equality of elements. 

146 

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 

151 

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 

159 

160 return not self_head and not other_head 

161 

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! 

165 

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) 

169 

170 # Take the easy way out for all other slicing cases, not much structural reuse possible anyway 

171 return plist(tuple(self)[index]) 

172 

173 if not isinstance(index, Integral): 

174 raise TypeError("'%s' object cannot be interpreted as an index" % type(index).__name__) 

175 

176 if index < 0: 

177 # NB: O(n)! 

178 index += len(self) 

179 

180 try: 

181 return self._drop(index).first 

182 except AttributeError as e: 

183 raise IndexError("PList index out of range") from e 

184 

185 def _drop(self, count): 

186 if count < 0: 

187 raise IndexError("PList index out of range") 

188 

189 head = self 

190 while count > 0: 

191 head = head.rest 

192 count -= 1 

193 

194 return head 

195 

196 def __hash__(self): 

197 return hash(tuple(self)) 

198 

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. 

203 

204 Raises ValueError if no matching element is found. 

205 

206 >>> plist([1, 2, 1]).remove(1) 

207 plist([2, 1]) 

208 """ 

209 

210 builder = _PListBuilder() 

211 head = self 

212 while head: 

213 if head.first == elem: 

214 return builder.append_plist(head.rest) 

215 

216 builder.append_elem(head.first) 

217 head = head.rest 

218 

219 raise ValueError('{0} not found in PList'.format(elem)) 

220 

221 

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). 

227 

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. 

230 

231 Do not instantiate directly, instead use the factory functions :py:func:`l` or :py:func:`plist` to 

232 create an instance. 

233 

234 Some examples: 

235 

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') 

250 

251 def __new__(cls, first, rest): 

252 instance = super(PList, cls).__new__(cls) 

253 instance.first = first 

254 instance.rest = rest 

255 return instance 

256 

257 def __bool__(self): 

258 return True 

259 __nonzero__ = __bool__ 

260 

261 

262Sequence.register(PList) 

263Hashable.register(PList) 

264 

265 

266class _EmptyPList(_PListBase): 

267 __slots__ = () 

268 

269 def __bool__(self): 

270 return False 

271 __nonzero__ = __bool__ 

272 

273 @property 

274 def first(self): 

275 raise AttributeError("Empty PList has no first") 

276 

277 @property 

278 def rest(self): 

279 return self 

280 

281 

282Sequence.register(_EmptyPList) 

283Hashable.register(_EmptyPList) 

284 

285_EMPTY_PLIST = _EmptyPList() 

286 

287 

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. 

293 

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() 

302 

303 return reduce(lambda pl, elem: pl.cons(elem), iterable, _EMPTY_PLIST) 

304 

305 

306def l(*elements): 

307 """ 

308 Creates a new persistent list containing all arguments. 

309 

310 >>> l(1, 2, 3) 

311 plist([1, 2, 3]) 

312 """ 

313 return plist(elements)