Coverage for pyTooling/LinkedList/__init__.py: 93%

1# ==================================================================================================================== # 

2# _____ _ _ _ _ _ _ _ _ _ # 

3# _ __ _ |_ _|__ ___ | (_)_ __ __ _ | | (_)_ __ | | _____ __| | | (_)___| |_ # 

4# | '_ \| | | || |/ _ \ / _ \| | | '_ \ / _` | | | | | '_ \| |/ / _ \/ _` | | | / __| __| # 

5# | |_) | |_| || | (_) | (_) | | | | | | (_| |_| |___| | | | | < __/ (_| | |___| \__ \ |_ # 

6# | .__/ \__, ||_|\___/ \___/|_|_|_| |_|\__, (_)_____|_|_| |_|_|\_\___|\__,_|_____|_|___/\__| # 

7# |_| |___/ |___/ # 

8# ==================================================================================================================== # 

9# Authors: # 

10# Patrick Lehmann # 

11# # 

12# License: # 

13# ==================================================================================================================== # 

14# Copyright 2025-2026 Patrick Lehmann - Bötzingen, Germany # 

15# # 

16# Licensed under the Apache License, Version 2.0 (the "License"); # 

17# you may not use this file except in compliance with the License. # 

18# You may obtain a copy of the License at # 

19# # 

20# http://www.apache.org/licenses/LICENSE-2.0 # 

21# # 

22# Unless required by applicable law or agreed to in writing, software # 

23# distributed under the License is distributed on an "AS IS" BASIS, # 

24# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # 

25# See the License for the specific language governing permissions and # 

26# limitations under the License. # 

27# # 

28# SPDX-License-Identifier: Apache-2.0 # 

29# ==================================================================================================================== # 

30# 

31""" 

32An object-oriented doubly linked-list data structure for Python. 

33 

34.. seealso:: 

35 

36 :mod:`pyTooling.Tree` 

37 |rarr| A tree data structure. 

38 :mod:`pyTooling.Graph` 

39 |rarr| A graph data structure. 

40""" 

41from __future__ import annotations 

42 

43from collections.abc import Sized 

44from typing import Generic, TypeVar, Optional as Nullable, Callable, Iterable, Generator, Any 

45 

46from pyTooling.Decorators import readonly, export 

47from pyTooling.Exceptions import NotInSameHierarchyError, ToolingException 

48from pyTooling.MetaClasses import ExtendedType 

49from pyTooling.Common import getFullyQualifiedName 

50from pyTooling.DataModel import Predicate 

51 

52 

53_NodeKey = TypeVar("_NodeKey") 

54_NodeValue = TypeVar("_NodeValue") 

55 

56 

57@export 

58class LinkedListError(ToolingException): 

59 """Base-exception of all exceptions raised by :mod:`pyTooling.LinkedList`.""" 

60 

61 

62@export 

63class InternalError(LinkedListError): 

64 """ 

65 The exception is raised when the linked list's internal state became inconsistent. 

66 

67 The exception message states the discovered inconsistency. Please create a 

68 :gh:`bug report <pyTooling/pyTooling/issues>` if this exception is raised. 

69 """ 

70 

71 

72@export 

73class NotInAListError(LinkedListError): 

74 """The exception is raised when a node is not assigned to any linked list.""" 

75 

76 _unlinkedNode: Nullable[Node] #: Node that isn't part of a linked list. 

77 

78 def __init__(self, message: str, /, *, unlinkedNode: Nullable[Node] = None) -> None: 

79 """ 

80 Initializes the exception with the node that isn't part of a linked list. 

81 

82 :param message: The exception's message. 

83 :param unlinkedNode: Optional, the node that isn't part of a linked list. 

84 """ 

85 super().__init__(message) 

86 self._unlinkedNode = unlinkedNode 

87 

88 @readonly 

89 def UnlinkedNode(self) -> Nullable[Node]: 

90 """ 

91 Read-only property to access the node that isn't part of a linked list (:attr:`_unlinkedNode`). 

92 

93 :returns: The node, or ``None`` if it wasn't recorded. 

94 """ 

95 return self._unlinkedNode 

96 

97 

98@export 

99class NotInSameListError(LinkedListError, NotInSameHierarchyError): 

100 """The exception is raised when a node is assigned to a different linked list than expected.""" 

101 

102 

103@export 

104class EmptyListError(LinkedListError): 

105 """The exception is raised when an operation needs at least one element, but the linked list is empty.""" 

106 

107 

108@export 

109class NodeNotFoundError(LinkedListError): 

110 """The exception is raised when no node matching the search criterion was found.""" 

111 

112 

113@export 

114class Node(Generic[_NodeKey, _NodeValue], metaclass=ExtendedType, slots=True): 

115 """ 

116 The node in an object-oriented doubly linked-list. 

117 

118 It contains a reference to the doubly linked list (:attr:`_list`), the previous node (:attr:`_previous`), the next 

119 node (:attr:`_next`) and the data (:attr:`_value`). Optionally, a key (:attr:`_key`) can be stored for sorting 

120 purposes. 

121 

122 The :attr:`_previous` field of the **first node** in a doubly linked list is ``None``. Similarly, the :attr:`_next` 

123 field of the **last node** is ``None``. ``None`` represents the end of the linked list when iterating it node-by-node. 

124 """ 

125 

126 _linkedList: Nullable[LinkedList[_NodeKey, _NodeValue]] #: Reference to the doubly linked list instance. 

127 _previousNode: Nullable[Node[_NodeKey, _NodeValue]] #: Reference to the previous node. 

128 _nextNode: Nullable[Node[_NodeKey, _NodeValue]] #: Reference to the next node. 

129 _key: Nullable[_NodeKey] #: The sortable key of the node. 

130 _value: _NodeValue #: The value of the node. 

131 

132 def __init__( 

133 self, 

134 value: _NodeValue, 

135 key: Nullable[_NodeKey] = None, 

136 previousNode: Nullable[Node[_NodeKey, _NodeValue]] = None, 

137 nextNode: Nullable[Node[_NodeKey, _NodeValue]] = None 

138 ) -> None: 

139 """ 

140 Initialize a linked list node. 

141 

142 :param value: Value to store in the node. 

143 :param key: Optional, sortable key to store in the node. 

144 :param previousNode: Optional, reference to the previous node. 

145 :param nextNode: Optional, reference to the next node. 

146 :raises TypeError: If parameter 'previous' is not of type :class:`Node`. 

147 :raises TypeError: If parameter 'next' is not of type :class:`Node`. 

148 :raises ValueError: If parameter 'value' is None. 

149 :raises ValueError: If ``previous`` and ``next`` belong to different linked lists. |br| 

150 A node can only be inserted between two neighbours of the same linked list. 

151 """ 

152 self._previousNode = previousNode 

153 self._nextNode = nextNode 

154 self._value = value 

155 self._key = key 

156 

157 # Attache to previous node 

158 if previousNode is not None: 

159 if not isinstance(previousNode, Node): 

160 ex = TypeError("Parameter 'previous' is not of type Node.") 

161 ex.add_note(f"Got type '{getFullyQualifiedName(previousNode)}'.") 

162 raise ex 

163 

164 # PreviousNode is part of a list 

165 if previousNode._linkedList is not None: 

166 self._linkedList = previousNode._linkedList 

167 self._linkedList._count += 1 

168 

169 # Check if previous was the last node 

170 if previousNode._nextNode is None: 170 ↛ 171line 170 didn't jump to line 171 because the condition on line 170 was never true

171 self._nextNode = None 

172 self._linkedList._lastNode = self 

173 else: 

174 self._nextNode = previousNode._nextNode 

175 self._nextNode._previousNode = self 

176 else: 

177 self._linkedList = None 

178 

179 previousNode._nextNode = self 

180 

181 if nextNode is not None: 

182 if not isinstance(nextNode, Node): 182 ↛ 183line 182 didn't jump to line 183 because the condition on line 182 was never true

183 ex = TypeError("Parameter 'next' is not of type Node.") 

184 ex.add_note(f"Got type '{getFullyQualifiedName(nextNode)}'.") 

185 raise ex 

186 

187 # 'self._linkedList' was just taken from 'previousNode', so comparing it against 'previousNode' again 

188 # could never differ - the two neighbours are what has to agree. 

189 if nextNode._linkedList is not previousNode._linkedList: 189 ↛ 194line 189 didn't jump to line 194 because the condition on line 189 was always true

190 ex = ValueError("Parameters 'previous' and 'next' belong to different linked lists.") 

191 ex.add_note("A node can only be inserted between two neighbours of the same linked list.") 

192 raise ex 

193 

194 previousNode._nextNode = self 

195 elif nextNode is not None: 

196 if not isinstance(nextNode, Node): 

197 ex = TypeError("Parameter 'next' is not of type Node.") 

198 ex.add_note(f"Got type '{getFullyQualifiedName(nextNode)}'.") 

199 raise ex 

200 

201 # NextNode is part of a list 

202 if nextNode._linkedList is not None: 202 ↛ 203line 202 didn't jump to line 203 because the condition on line 202 was never true

203 self._linkedList = nextNode._linkedList 

204 self._linkedList._count += 1 

205 

206 # Check if next was the first node 

207 if nextNode._previousNode is None: 

208 self._previousNode = None 

209 self._linkedList._firstNode = self 

210 else: 

211 self._previousNode = nextNode._previousNode 

212 self._previousNode._nextNode = self 

213 else: 

214 self._linkedList = None 

215 

216 nextNode._previousNode = self 

217 else: 

218 self._linkedList = None 

219 

220 @readonly 

221 def List(self) -> Nullable[LinkedList[_NodeKey, _NodeValue]]: 

222 """ 

223 Read-only property to access the linked list, this node belongs to. 

224 

225 :returns: The linked list, this node is part of, or ``None``. 

226 """ 

227 return self._linkedList 

228 

229 @readonly 

230 def PreviousNode(self) -> Nullable[Node[_NodeKey, _NodeValue]]: 

231 """ 

232 Read-only property to access node's predecessor. 

233 

234 This reference is ``None`` if the node is the first node in the doubly linked list. 

235 

236 :returns: The node before the current node or ``None``. 

237 """ 

238 return self._previousNode 

239 

240 @readonly 

241 def NextNode(self) -> Nullable[Node[_NodeKey, _NodeValue]]: 

242 """ 

243 Read-only property to access node's successor. 

244 

245 This reference is ``None`` if the node is the last node in the doubly linked list. 

246 

247 :returns: The node after the current node or ``None``. 

248 """ 

249 return self._nextNode 

250 

251 @property 

252 def Key(self) -> _NodeKey: 

253 """ 

254 Property to access the node's internal key. 

255 

256 The key can be a scalar or a reference to an object. 

257 

258 :returns: The node's key. 

259 """ 

260 return self._key 

261 

262 @Key.setter 

263 def Key(self, key: _NodeKey) -> None: 

264 self._key = key 

265 

266 @property 

267 def Value(self) -> _NodeValue: 

268 """ 

269 Property to access the node's internal data. 

270 

271 The data can be a scalar or a reference to an object. 

272 

273 :returns: The node's value. 

274 """ 

275 return self._value 

276 

277 @Value.setter 

278 def Value(self, value: _NodeValue) -> None: 

279 self._value = value 

280 

281 def InsertNodeBefore(self, node: Node[_NodeKey, _NodeValue]) -> None: 

282 """ 

283 Insert a node before this node. 

284 

285 :param node: Node to insert. 

286 :raises ValueError: If parameter 'node' is ``None``. 

287 :raises TypeError: If parameter 'node' is not of type :class:`Node`. 

288 :raises NotInSameListError: If parameter 'node' is already part of another linked list. 

289 :raises NotInAListError: If this node is not part of a linked list. 

290 """ 

291 if node is None: 

292 raise ValueError("Parameter 'node' is None.") 

293 

294 if not isinstance(node, Node): 

295 ex = TypeError("Parameter 'node' is not of type Node.") 

296 ex.add_note(f"Got type '{getFullyQualifiedName(node)}'.") 

297 raise ex 

298 

299 if node._linkedList is not None: 

300 raise NotInSameListError("Parameter 'node' belongs to another linked list.") 

301 

302 if self._linkedList is None: 

303 raise NotInAListError("Node is not part of a linked list.", unlinkedNode=self) 

304 

305 node._linkedList = self._linkedList 

306 node._nextNode = self 

307 node._previousNode = self._previousNode 

308 if self._previousNode is None: 

309 self._linkedList._firstNode = node 

310 else: 

311 self._previousNode._nextNode = node 

312 self._previousNode = node 

313 self._linkedList._count += 1 

314 

315 def InsertNodeAfter(self, node: Node[_NodeKey, _NodeValue]) -> None: 

316 """ 

317 Insert a node after this node. 

318 

319 :param node: Node to insert. 

320 :raises ValueError: If parameter 'node' is ``None``. 

321 :raises TypeError: If parameter 'node' is not of type :class:`Node`. 

322 :raises NotInSameListError: If parameter 'node' is already part of another linked list. 

323 :raises NotInAListError: If this node is not part of a linked list. 

324 """ 

325 if node is None: 

326 raise ValueError("Parameter 'node' is None.") 

327 

328 if not isinstance(node, Node): 

329 ex = TypeError("Parameter 'node' is not of type Node.") 

330 ex.add_note(f"Got type '{getFullyQualifiedName(node)}'.") 

331 raise ex 

332 

333 if node._linkedList is not None: 

334 raise NotInSameListError("Parameter 'node' belongs to another linked list.") 

335 

336 if self._linkedList is None: 

337 raise NotInAListError("Node is not part of a linked list.", unlinkedNode=self) 

338 

339 node._linkedList = self._linkedList 

340 node._previousNode = self 

341 node._nextNode = self._nextNode 

342 if self._nextNode is None: 

343 self._linkedList._lastNode = node 

344 else: 

345 self._nextNode._previousNode = node 

346 self._nextNode = node 

347 self._linkedList._count += 1 

348 

349 # move forward 

350 # move backward 

351 # move by relative pos 

352 # move to position 

353 # move to begin 

354 # move to end 

355 

356 # insert tuple/list/linkedlist before 

357 # insert tuple/list/linkedlist after 

358 

359 # iterate forward for n 

360 # iterate backward for n 

361 

362 # slice to tuple / list starting from that node 

363 

364 # swap left by n 

365 # swap right by n 

366 

367 def Remove(self) -> _NodeValue: 

368 """ 

369 Remove this node from the linked list. 

370 

371 :returns: The value of the removed node. 

372 """ 

373 if self._previousNode is None: 

374 if self._linkedList is not None: 374 ↛ 383line 374 didn't jump to line 383 because the condition on line 374 was always true

375 self._linkedList._firstNode = self._nextNode 

376 self._linkedList._count -= 1 

377 

378 if self._nextNode is None: 

379 self._linkedList._lastNode = None 

380 

381 self._linkedList = None 

382 

383 if self._nextNode is not None: 

384 self._nextNode._previousNode = None 

385 

386 self._nextNode = None 

387 elif self._nextNode is None: 

388 if self._linkedList is not None: 388 ↛ 393line 388 didn't jump to line 393 because the condition on line 388 was always true

389 self._linkedList._lastNode = self._previousNode 

390 self._linkedList._count -= 1 

391 self._linkedList = None 

392 

393 self._previousNode._nextNode = None 

394 self._previousNode = None 

395 else: 

396 self._previousNode._nextNode = self._nextNode 

397 self._nextNode._previousNode = self._previousNode 

398 self._nextNode = None 

399 self._previousNode = None 

400 

401 if self._linkedList is not None: 401 ↛ 405line 401 didn't jump to line 405 because the condition on line 401 was always true

402 self._linkedList._count -= 1 

403 self._linkedList = None 

404 

405 return self._value 

406 

407 def IterateToFirst(self, includeSelf: bool = False) -> Generator[Node[_NodeKey, _NodeValue], None, None]: 

408 """ 

409 Return a generator iterating backward from this node to the list's first node. 

410 

411 Optionally, this node can be included into the generated sequence. 

412 

413 :param includeSelf: Optional, if ``True``, include this node into the sequence, otherwise start at previous node. 

414 :returns: A sequence of nodes towards the list's first node. 

415 """ 

416 previousNode = self._previousNode 

417 

418 if includeSelf: 

419 yield self 

420 

421 node = previousNode 

422 while node is not None: 

423 previousNode = node._previousNode 

424 yield node 

425 node = previousNode 

426 

427 def IterateToLast(self, includeSelf: bool = False) -> Generator[Node[_NodeKey, _NodeValue], None, None]: 

428 """ 

429 Return a generator iterating forward from this node to the list's last node. 

430 

431 Optionally, this node can be included into the generated sequence by setting. 

432 

433 :param includeSelf: Optional, if ``True``, include this node into the sequence, otherwise start at next node. 

434 :returns: A sequence of nodes towards the list's last node. 

435 """ 

436 nextNode = self._nextNode 

437 

438 if includeSelf: 

439 yield self 

440 

441 node = nextNode 

442 while node is not None: 

443 nextNode = node._nextNode 

444 yield node 

445 node = nextNode 

446 

447 def __repr__(self) -> str: 

448 """ 

449 Return a detailed string representation of this node. 

450 

451 :returns: The node's value, prefixed by its kind. 

452 """ 

453 return f"Node: {self._value}" 

454 

455 

456@export 

457class LinkedList(Generic[_NodeKey, _NodeValue], metaclass=ExtendedType, slots=True): 

458 """An object-oriented doubly linked-list.""" 

459 

460 _firstNode: Nullable[Node[_NodeKey, _NodeValue]] #: Reference to the first node of the linked list. 

461 _lastNode: Nullable[Node[_NodeKey, _NodeValue]] #: Reference to the last node of the linked list. 

462 _count: int #: Number of nodes in the linked list. 

463 

464 # allow iterable to initialize the list 

465 def __init__(self, nodes: Nullable[Iterable[Node[_NodeKey, _NodeValue]]] = None) -> None: 

466 """ 

467 Initialize an empty linked list. 

468 

469 Optionally, an iterable can be given to initialize the linked list. The order is preserved. 

470 

471 :param nodes: Optional, iterable to initialize the linked list. 

472 :raises TypeError: If parameter 'nodes' is not an :class:`iterable <typing.Iterable>`. 

473 :raises TypeError: If parameter 'nodes' items are not of type :class:`Node`. 

474 :raises NotInSameListError: If parameter 'nodes' contains items which are already part of another linked list. 

475 """ 

476 if nodes is None: 

477 self._firstNode = None 

478 self._lastNode = None 

479 self._count = 0 

480 elif not isinstance(nodes, Iterable): 

481 ex = TypeError("Parameter 'nodes' is not an iterable.") 

482 ex.add_note(f"Got type '{getFullyQualifiedName(nodes)}'.") 

483 raise ex 

484 else: 

485 if isinstance(nodes, Sized) and len(nodes) == 0: 

486 self._firstNode = None 

487 self._lastNode = None 

488 self._count = 0 

489 return 

490 

491 try: 

492 first = next(iterator := iter(nodes)) 

493 except StopIteration: 

494 self._firstNode = None 

495 self._lastNode = None 

496 self._count = 0 

497 return 

498 

499 if not isinstance(first, Node): 

500 ex = TypeError("First element in parameter 'nodes' is not of type Node.") 

501 ex.add_note(f"Got type '{getFullyQualifiedName(first)}'.") 

502 raise ex 

503 elif first._linkedList is not None: 

504 raise NotInSameListError("First element in parameter 'nodes' is assigned to different list.") 

505 

506 position = 1 

507 first._linkedList = self 

508 first._previousNode = None 

509 self._firstNode = previous = node = first 

510 

511 for node in iterator: 

512 if not isinstance(node, Node): 

513 ex = TypeError(f"{position}. element in parameter 'nodes' is not of type Node.") 

514 ex.add_note(f"Got type '{getFullyQualifiedName(node)}'.") 

515 raise ex 

516 elif node._linkedList is not None: 

517 raise NotInSameListError(f"{position}. element in parameter 'nodes' is assigned to different list.") 

518 

519 node._linkedList = self 

520 node._previousNode = previous 

521 previous._nextNode = node 

522 

523 previous = node 

524 position += 1 

525 

526 self._lastNode = node 

527 self._count = position 

528 node._nextNode = None 

529 

530 @readonly 

531 def IsEmpty(self) -> int: 

532 """ 

533 Read-only property to return the number of . 

534 

535 This reference is ``None`` if the node is the last node in the doubly linked list. 

536 

537 :returns: ``True`` if linked list is empty, otherwise ``False`` 

538 """ 

539 return self._count == 0 

540 

541 @readonly 

542 def Count(self) -> int: 

543 """ 

544 Read-only property to access the number of nodes in the linked list. 

545 

546 :returns: Number of nodes. 

547 """ 

548 return self._count 

549 

550 @readonly 

551 def FirstNode(self) -> Nullable[Node[_NodeKey, _NodeValue]]: 

552 """ 

553 Read-only property to access the first node in the linked list. 

554 

555 In case the list is empty, ``None`` is returned. 

556 

557 :returns: First node. 

558 """ 

559 return self._firstNode 

560 

561 @readonly 

562 def LastNode(self) -> Nullable[Node[_NodeKey, _NodeValue]]: 

563 """ 

564 Read-only property to access the last node in the linked list. 

565 

566 In case the list is empty, ``None`` is returned. 

567 

568 :returns: Last node. 

569 """ 

570 return self._lastNode 

571 

572 def Clear(self) -> None: 

573 """ 

574 Clear the linked list. 

575 

576 Every node is removed: afterwards, it belongs to no linked list and has neither a previous nor a next node, so it 

577 can be inserted into a linked list again. 

578 """ 

579 node = self._firstNode 

580 while node is not None: 

581 nextNode = node._nextNode 

582 node._linkedList = None 

583 node._previousNode = None 

584 node._nextNode = None 

585 node = nextNode 

586 

587 self._firstNode = None 

588 self._lastNode = None 

589 self._count = 0 

590 

591 def InsertBeforeFirst(self, node: Node[_NodeKey, _NodeValue]) -> None: 

592 """ 

593 Insert a node before the first node. 

594 

595 :param node: Node to insert. 

596 :raises ValueError: If parameter 'node' is ``None``. 

597 :raises TypeError: If parameter 'node' is not of type :class:`Node`. 

598 :raises NotInSameListError: If parameter 'node' is already part of another linked list. 

599 """ 

600 if node is None: 

601 raise ValueError("Parameter 'node' is None.") 

602 

603 if not isinstance(node, Node): 

604 ex = TypeError("Parameter 'node' is not of type Node.") 

605 ex.add_note(f"Got type '{getFullyQualifiedName(node)}'.") 

606 raise ex 

607 

608 if node._linkedList is not None: 

609 raise NotInSameListError("Parameter 'node' belongs to another linked list.") 

610 

611 node._linkedList = self 

612 node._previousNode = None 

613 node._nextNode = self._firstNode 

614 if self._firstNode is None: 

615 self._lastNode = node 

616 else: 

617 self._firstNode._previousNode = node 

618 self._firstNode = node 

619 self._count += 1 

620 

621 def InsertAfterLast(self, node: Node[_NodeKey, _NodeValue]) -> None: 

622 """ 

623 Insert a node after the last node. 

624 

625 :param node: Node to insert. 

626 :raises ValueError: If parameter 'node' is ``None``. 

627 :raises TypeError: If parameter 'node' is not of type :class:`Node`. 

628 :raises NotInSameListError: If parameter 'node' is already part of another linked list. 

629 """ 

630 if node is None: 

631 raise ValueError("Parameter 'node' is None.") 

632 

633 if not isinstance(node, Node): 

634 ex = TypeError("Parameter 'node' is not of type Node.") 

635 ex.add_note(f"Got type '{getFullyQualifiedName(node)}'.") 

636 raise ex 

637 

638 if node._linkedList is not None: 

639 raise NotInSameListError("Parameter 'node' belongs to another linked list.") 

640 

641 node._linkedList = self 

642 node._nextNode = None 

643 node._previousNode = self._lastNode 

644 if self._lastNode is None: 

645 self._firstNode = node 

646 else: 

647 self._lastNode._nextNode = node 

648 self._lastNode = node 

649 self._count += 1 

650 

651 def RemoveFirst(self) -> Node[_NodeKey, _NodeValue]: 

652 """ 

653 Remove first node from linked list. 

654 

655 :returns: First node. 

656 :raises EmptyListError: If linked list is empty. 

657 """ 

658 if self._firstNode is None: 

659 raise EmptyListError("Linked list is empty.") 

660 

661 node = self._firstNode 

662 self._firstNode = node._nextNode 

663 if self._firstNode is None: 

664 self._lastNode = None 

665 self._count = 0 

666 else: 

667 self._firstNode._previousNode = None 

668 self._count -= 1 

669 

670 node._linkedList = None 

671 node._nextNode = None 

672 return node 

673 

674 def RemoveLast(self) -> Node[_NodeKey, _NodeValue]: 

675 """ 

676 Remove last node from linked list. 

677 

678 :returns: Last node. 

679 :raises EmptyListError: If linked list is empty. 

680 """ 

681 if self._lastNode is None: 

682 raise EmptyListError("Linked list is empty.") 

683 

684 node = self._lastNode 

685 self._lastNode = node._previousNode 

686 if self._lastNode is None: 

687 self._firstNode = None 

688 self._count = 0 

689 else: 

690 self._lastNode._nextNode = None 

691 self._count -= 1 

692 

693 node._linkedList = None 

694 node._previousNode = None 

695 return node 

696 

697 

698 def GetNodeByIndex(self, index: int) -> Node[_NodeKey, _NodeValue]: 

699 """ 

700 Access a node in the linked list by position. 

701 

702 :param index: Node position to access. 

703 :returns: Node at the given position. 

704 :raises ValueError: If parameter 'position' is out of range, which includes an empty list. 

705 :raises InternalError: If the node at that position could not be reached, so the list's internal state is 

706 inconsistent. 

707 

708 .. note:: 

709 

710 The algorithm starts iterating nodes from the shorter end. 

711 """ 

712 if self._firstNode is None or self._lastNode is None: 

713 ex = ValueError("Parameter 'position' is out of range.") 

714 ex.add_note("Linked list is empty.") 

715 raise ex 

716 

717 if index == 0: 

718 return self._firstNode 

719 elif index == self._count - 1: 

720 return self._lastNode 

721 elif index >= self._count: 

722 ex = ValueError("Parameter 'position' is out of range.") 

723 ex.add_note(f"Linked list has {self._count} elements. Requested index: {index}.") 

724 raise ex 

725 

726 if index < self._count / 2: 726 ↛ 738line 726 didn't jump to line 738 because the condition on line 726 was always true

727 pos = 1 

728 node = self._firstNode._nextNode 

729 while node is not None: 

730 if pos == index: 

731 return node 

732 

733 node = node._nextNode 

734 pos += 1 

735 else: # pragma: no cover 

736 raise InternalError("Node position not found.") 

737 else: 

738 pos = self._count - 2 

739 node = self._lastNode._previousNode 

740 while node is not None: 

741 if pos == index: 

742 return node 

743 

744 node = node._previousNode 

745 pos -= 1 

746 else: # pragma: no cover 

747 raise InternalError("Node position not found.") 

748 

749 def Search(self, predicate: Predicate[Node], reverse: bool = False) -> Node[_NodeKey, _NodeValue]: 

750 """ 

751 Search the list for the first node matching a predicate. 

752 

753 :param predicate: Filter function accepting a node and returning a boolean. 

754 :param reverse: Optional, if ``True``, search from the last node towards the first. 

755 :returns: The first matching node. 

756 :raises EmptyListError: If the list is empty. 

757 :raises NodeNotFoundError: If no node matches the predicate. 

758 """ 

759 if self._firstNode is None: 

760 raise EmptyListError("Linked list is empty.") 

761 

762 if not reverse: 

763 node = self._firstNode 

764 while node is not None: 

765 if predicate(node): 

766 break 

767 

768 node = node._nextNode 

769 else: 

770 raise NodeNotFoundError("Node not found.") 

771 else: 

772 node = self._lastNode 

773 while node is not None: 

774 if predicate(node): 

775 break 

776 

777 node = node._previousNode 

778 else: 

779 raise NodeNotFoundError("Node not found.") 

780 

781 return node 

782 

783 def Reverse(self) -> None: 

784 """ 

785 Reverse the order of nodes in the linked list. 

786 """ 

787 if self._firstNode is None or self._firstNode is self._lastNode: 

788 return 

789 

790 node = self._lastNode = self._firstNode 

791 

792 while node is not None: 

793 last = node 

794 node = last._nextNode 

795 last._nextNode = last._previousNode 

796 

797 last._previousNode = node 

798 self._firstNode = last 

799 

800 def Sort(self, key: Nullable[Callable[[Node[_NodeKey, _NodeValue]], Any]] = None, reverse: bool = False) -> None: 

801 """ 

802 Sort the linked list in ascending or descending order. 

803 

804 The sort operation is **stable**. 

805 

806 :param key: Optional, function to access a user-defined key for sorting. 

807 :param reverse: Optional, parameter, if ``True`` sort in descending order, otherwise in ascending order. 

808 

809 .. note:: 

810 

811 The linked list is converted to an array, which is sorted by quicksort using the builtin :meth:`~list.sort`. 

812 Afterward, the sorted array is used to reconstruct the linked list in requested order. 

813 """ 

814 if (self._firstNode is None) or (self._firstNode is self._lastNode): 

815 return 

816 

817 if key is None: 

818 key = lambda node: node._value 

819 

820 sequence = list(self.IterateFromFirst()) 

821 sequence.sort(key=key, reverse=reverse) 

822 

823 first = sequence[0] 

824 

825 position = 1 

826 first._previousNode = None 

827 self._firstNode = previous = node = first 

828 

829 for node in sequence[1:]: 

830 node._previousNode = previous 

831 previous._nextNode = node 

832 

833 previous = node 

834 position += 1 

835 

836 self._lastNode = node 

837 self._count = position 

838 node._nextNode = None 

839 

840 def IterateFromFirst(self) -> Generator[Node[_NodeKey, _NodeValue], None, None]: 

841 """ 

842 Return a generator iterating forward from list's first node to list's last node. 

843 

844 :returns: A sequence of nodes towards the list's last node. 

845 """ 

846 if self._firstNode is None: 

847 return 

848 

849 node = self._firstNode 

850 while node is not None: 

851 nextNode = node._nextNode 

852 yield node 

853 node = nextNode 

854 

855 def IterateFromLast(self) -> Generator[Node[_NodeKey, _NodeValue], None, None]: 

856 """ 

857 Return a generator iterating backward from list's last node to list's first node. 

858 

859 :returns: A sequence of nodes towards the list's first node. 

860 """ 

861 if self._lastNode is None: 

862 return 

863 

864 node = self._lastNode 

865 while node is not None: 

866 previousNode = node._previousNode 

867 yield node 

868 node = previousNode 

869 

870 def ToList(self, reverse: bool = False) -> list[Node[_NodeKey, _NodeValue]]: 

871 """ 

872 Convert the linked list to a :class:`list`. 

873 

874 Optionally, the resulting list can be constructed in reverse order. 

875 

876 :param reverse: Optional, parameter, if ``True`` return in reversed order, otherwise in normal order. 

877 :returns: A list (array) of this linked list's values. 

878 """ 

879 if self._count == 0: 

880 return [] 

881 elif reverse: 

882 return [n._value for n in self.IterateFromLast()] 

883 else: 

884 return [n._value for n in self.IterateFromFirst()] 

885 

886 def ToTuple(self, reverse: bool = False) -> tuple[Node[_NodeKey, _NodeValue], ...]: 

887 """ 

888 Convert the linked list to a :class:`tuple`. 

889 

890 Optionally, the resulting tuple can be constructed in reverse order. 

891 

892 :param reverse: Optional, parameter, if ``True`` return in reversed order, otherwise in normal order. 

893 :returns: A tuple of this linked list's values. 

894 """ 

895 if self._count == 0: 

896 return tuple() 

897 elif reverse: 

898 return tuple(n._value for n in self.IterateFromLast()) 

899 else: 

900 return tuple(n._value for n in self.IterateFromFirst()) 

901 

902 # Copy 

903 # Sort 

904 

905 # merge lists 

906 # append / prepend lists 

907 # split list 

908 

909 # Remove at position (= __delitem__) 

910 # Remove by predicate (n times) 

911 

912 # Insert at position (= __setitem__) 

913 

914 # insert tuple/list/linkedlist at begin 

915 # insert tuple/list/linkedlist at end 

916 

917 # Find by position (= __getitem__) 

918 # Find by predicate from left (n times) 

919 # Find by predicate from right (n times) 

920 

921 # Count by predicate 

922 

923 # slice by start, length from right -> new list 

924 # slice by start, length from left 

925 # Slice by predicate 

926 

927 # iterate start, length from right 

928 # iterate start, length from left 

929 # iterate by predicate 

930 

931 def __len__(self) -> int: 

932 """ 

933 Returns the number of nodes in the linked list. 

934 

935 :returns: Number of nodes. 

936 """ 

937 return self._count 

938 

939 def __getitem__(self, index: int) -> _NodeValue: 

940 """