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

1from collections.abc import Sequence, Hashable 

2from numbers import Integral 

3from functools import reduce 

4from typing import Generic, TypeVar 

5 

6T_co = TypeVar('T_co', covariant=True) 

7 

8 

9class _PListBuilder(object): 

10 """ 

11 Helper class to allow construction of a list without 

12 having to reverse it in the end. 

13 """ 

14 __slots__ = ('_head', '_tail') 

15 

16 def __init__(self): 

17 self._head = _EMPTY_PLIST 

18 self._tail = _EMPTY_PLIST 

19 

20 def _append(self, elem, constructor): 

21 if not self._tail: 

22 self._head = constructor(elem) 

23 self._tail = self._head 

24 else: 

25 self._tail.rest = constructor(elem) 

26 self._tail = self._tail.rest 

27 

28 return self._head 

29 

30 def append_elem(self, elem): 

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

32 

33 def append_plist(self, pl): 

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

35 

36 def build(self): 

37 return self._head 

38 

39 

40class _PListBase(object): 

41 __slots__ = ('__weakref__',) 

42 

43 # Selected implementations can be taken straight from the Sequence 

44 # class, other are less suitable. Especially those that work with 

45 # index lookups. 

46 count = Sequence.count 

47 index = Sequence.index 

48 

49 def __reduce__(self): 

50 # Pickling support 

51 return plist, (list(self),) 

52 

53 def __len__(self): 

54 """ 

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

56 

57 This is obviously O(n) but with the current implementation 

58 where a list is also a node the overhead of storing the length 

59 in every node would be quite significant. 

60 """ 

61 return sum(1 for _ in self) 

62 

63 def __repr__(self): 

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

65 __str__ = __repr__ 

66 

67 def cons(self, elem): 

68 """ 

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

70 

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

72 plist([3, 1, 2]) 

73 """ 

74 return PList(elem, self) 

75 

76 def mcons(self, iterable): 

77 """ 

78 Return a new list with all elements of iterable repeatedly cons:ed to the current list. 

79 NB! The elements will be inserted in the reverse order of the iterable. 

80 Runs in O(len(iterable)). 

81 

82 >>> plist([1, 2]).mcons([3, 4]) 

83 plist([4, 3, 1, 2]) 

84 """ 

85 head = self 

86 for elem in iterable: 

87 head = head.cons(elem) 

88 

89 return head 

90 

91 def reverse(self): 

92 """ 

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

94 

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

96 plist([3, 2, 1]) 

97 

98 Also supports the standard reversed function. 

99 

100 >>> reversed(plist([1, 2, 3])) 

101 plist([3, 2, 1]) 

102 """ 

103 result = plist() 

104 head = self 

105 while head: 

106 result = result.cons(head.first) 

107 head = head.rest 

108 

109 return result 

110 __reversed__ = reverse 

111 

112 def split(self, index): 

113 """ 

114 Spilt the list at position specified by index. Returns a tuple containing the 

115 list up until index and the list after the index. Runs in O(index). 

116 

117 >>> plist([1, 2, 3, 4]).split(2) 

118 (plist([1, 2]), plist([3, 4])) 

119 """ 

120 lb = _PListBuilder() 

121 right_list = self 

122 i = 0 

123 while right_list and i < index: 

124 lb.append_elem(right_list.first) 

125 right_list = right_list.rest 

126 i += 1 

127 

128 if not right_list: 

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

130 return self, _EMPTY_PLIST 

131 

132 return lb.build(), right_list 

133 

134 def __iter__(self): 

135 li = self 

136 while li: 

137 yield li.first 

138 li = li.rest 

139 

140 def __lt__(self, other): 

141 if not isinstance(other, _PListBase): 

142 return NotImplemented 

143 

144 return tuple(self) < tuple(other) 

145 

146 def __eq__(self, other): 

147 """ 

148 Traverses the lists, checking equality of elements. 

149 

150 This is an O(n) operation, but preserves the standard semantics of list equality. 

151 """ 

152 if not isinstance(other, _PListBase): 

153 return NotImplemented 

154 

155 self_head = self 

156 other_head = other 

157 while self_head and other_head: 

158 if not self_head.first == other_head.first: 

159 return False 

160 self_head = self_head.rest 

161 other_head = other_head.rest 

162 

163 return not self_head and not other_head 

164 

165 def __getitem__(self, index): 

166 # Don't use this this data structure if you plan to do a lot of indexing, it is 

167 # very inefficient! Use a PVector instead! 

168 

169 if isinstance(index, slice): 

170 if index.start is not None and index.stop is None and (index.step is None or index.step == 1): 

171 return self._drop(index.start) 

172 

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

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

175 

176 if not isinstance(index, Integral): 

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

178 

179 if index < 0: 

180 # NB: O(n)! 

181 index += len(self) 

182 

183 try: 

184 return self._drop(index).first 

185 except AttributeError as e: 

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

187 

188 def _drop(self, count): 

189 if count < 0: 

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

191 

192 head = self 

193 while count > 0: 

194 head = head.rest 

195 count -= 1 

196 

197 return head 

198 

199 def __hash__(self): 

200 return hash(tuple(self)) 

201 

202 def remove(self, elem): 

203 """ 

204 Return new list with first element equal to elem removed. O(k) where k is the position 

205 of the element that is removed. 

206 

207 Raises ValueError if no matching element is found. 

208 

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

210 plist([2, 1]) 

211 """ 

212 

213 builder = _PListBuilder() 

214 head = self 

215 while head: 

216 if head.first == elem: 

217 return builder.append_plist(head.rest) 

218 

219 builder.append_elem(head.first) 

220 head = head.rest 

221 

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

223 

224 

225class PList(Generic[T_co], _PListBase): 

226 """ 

227 Classical Lisp style singly linked list. Adding elements to the head using cons is O(1). 

228 Element access is O(k) where k is the position of the element in the list. Taking the 

229 length of the list is O(n). 

230 

231 Fully supports the Sequence and Hashable protocols including indexing and slicing but 

232 if you need fast random access go for the PVector instead. 

233 

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

235 create an instance. 

236 

237 Some examples: 

238 

239 >>> x = plist([1, 2]) 

240 >>> y = x.cons(3) 

241 >>> x 

242 plist([1, 2]) 

243 >>> y 

244 plist([3, 1, 2]) 

245 >>> y.first 

246 3 

247 >>> y.rest == x 

248 True 

249 >>> y[:2] 

250 plist([3, 1]) 

251 """ 

252 __slots__ = ('first', 'rest') 

253 

254 def __new__(cls, first, rest): 

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

256 instance.first = first 

257 instance.rest = rest 

258 return instance 

259 

260 def __bool__(self): 

261 return True 

262 __nonzero__ = __bool__ 

263 

264 

265Sequence.register(PList) 

266Hashable.register(PList) 

267 

268 

269class _EmptyPList(_PListBase): 

270 __slots__ = () 

271 

272 def __bool__(self): 

273 return False 

274 __nonzero__ = __bool__ 

275 

276 @property 

277 def first(self): 

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

279 

280 @property 

281 def rest(self): 

282 return self 

283 

284 

285Sequence.register(_EmptyPList) 

286Hashable.register(_EmptyPList) 

287 

288_EMPTY_PLIST = _EmptyPList() 

289 

290 

291def plist(iterable=(), reverse=False): 

292 """ 

293 Creates a new persistent list containing all elements of iterable. 

294 Optional parameter reverse specifies if the elements should be inserted in 

295 reverse order or not. 

296 

297 >>> plist([1, 2, 3]) 

298 plist([1, 2, 3]) 

299 >>> plist([1, 2, 3], reverse=True) 

300 plist([3, 2, 1]) 

301 """ 

302 if not reverse: 

303 iterable = list(iterable) 

304 iterable.reverse() 

305 

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

307 

308 

309def l(*elements): 

310 """ 

311 Creates a new persistent list containing all arguments. 

312 

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

314 plist([1, 2, 3]) 

315 """ 

316 return plist(elements)