Coverage for pyTooling/LinkedList/__init_

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

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

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

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

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

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

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

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

9# Authors: #

10# Patrick Lehmann #

11# #

12# License: #

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

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"""An object-oriented doubly linked-list data structure for Python."""

33from collections.abc import Sized

34from typing import Generic, TypeVar, Optional as Nullable, Callable, Iterable, Generator, Tuple, List, Any

36try:

37 from pyTooling.Decorators import readonly, export

38 from pyTooling.Exceptions import ToolingException

39 from pyTooling.MetaClasses import ExtendedType

40 from pyTooling.Common import getFullyQualifiedName

41except (ImportError, ModuleNotFoundError): # pragma: no cover

42 print("[pyTooling.LinkedList] Could not import from 'pyTooling.*'!")

44 try:

45 from Decorators import readonly, export

46 from Exceptions import ToolingException

47 from MetaClasses import ExtendedType

48 from Common import getFullyQualifiedName

49 except (ImportError, ModuleNotFoundError) as ex: # pragma: no cover

50 print("[pyTooling.LinkedList] Could not import directly!")

51 raise ex

54_NodeKey = TypeVar("_NodeKey")

55_NodeValue = TypeVar("_NodeValue")

58@export

59class LinkedListException(ToolingException):

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

63@export

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

65 """

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

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

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

70 purposes.

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

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

74 """

76 _linkedList: Nullable["LinkedList[_NodeValue]"] #: Reference to the doubly linked list instance.

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

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

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

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

82 def __init__(

83 self,

84 value: _NodeValue,

85 key: Nullable[_NodeKey] = None,

86 previousNode: Nullable["Node[_NodeKey, _NodeValue]"] = None,

87 nextNode: Nullable["Node[_NodeKey, _NodeValue]"] = None

88 ) -> None:

89 """

90 Initialize a linked list node.

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

93 :param key: Optional sortable key to store in the node.

94 :param previousNode: Optional reference to the previous node.

95 :param nextNode: Optional reference to the next node.

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

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

98 """

99 self._previousNode = previousNode

100 self._nextNode = nextNode

101 self._value = value

102 self._key = value

103

104 # Attache to previous node

105 if previousNode is not None:

106 if not isinstance(previousNode, Node):

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

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

109 raise ex

110

111 # PreviousNode is part of a list

112 if previousNode._linkedList is not None: 112 ↛ 113line 112 didn't jump to line 113 because the condition on line 112 was never true

113 self._linkedList = previousNode._linkedList

114 self._linkedList._count += 1

115

116 # Check if previous was the last node

117 if previousNode._nextNode is None:

118 self._nextNode = None

119 self._linkedList._lastNode = self

120 else:

121 self._nextNode = previousNode._nextNode

122 self._nextNode._previousNode = self

123 else:

124 self._linkedList = None

125

126 previousNode._nextNode = self

127

128 if nextNode is not None: 128 ↛ 129line 128 didn't jump to line 129 because the condition on line 128 was never true

129 if not isinstance(nextNode, Node):

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

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

132 raise ex

133

134 if nextNode._linkedList is not None:

135 if self._linkedList is not None:

136 if self._linkedList is not previousNode._linkedList:

137 raise ValueError()

138

139 previousNode._nextNode = self

140 elif nextNode is not None:

141 if not isinstance(nextNode, Node):

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

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

144 raise ex

145

146 # NextNode is part of a list

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

148 self._linkedList = nextNode._linkedList

149 self._linkedList._count += 1

150

151 # Check if next was the first node

152 if nextNode._previousNode is None:

153 self._previousNode = None

154 self._linkedList._firstNode = self

155 else:

156 self._previousNode = nextNode._previousNode

157 self._previousNode._nextNode = self

158 else:

159 self._linkedList = None

160

161 nextNode._previousNode = self

162 else:

163 self._linkedList = None

164

165 @readonly

166 def List(self) -> Nullable["LinkedList[_NodeValue]"]:

167 """

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

169

170 :return: The linked list, this node is part of, or ``None``.

171 """

172 return self._linkedList

173

174 @readonly

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

176 """

177 Read-only property to access nodes predecessor.

178

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

180

181 :return: The node before the current node or ``None``.

182 """

183 return self._previousNode

184

185 @readonly

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

187 """

188 Read-only property to access nodes successor.

189

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

191

192 :return: The node after the current node or ``None``.

193 """

194 return self._nextNode

195

196 @property

197 def Key(self) -> _NodeKey:

198 """

199 Property to access the node's internal key.

200

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

202

203 :return: The node's key.

204 """

205 return self._key

206

207 @Key.setter

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

209 self._key = key

210

211 @property

212 def Value(self) -> _NodeValue:

213 """

214 Property to access the node's internal data.

215

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

217

218 :return: The node's value.

219 """

220 return self._value

221

222 @Value.setter

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

224 self._value = value

225

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

227 """

228 Insert a node before this node.

229

230 :param node: Node to insert.

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

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

233 :raises LinkedListException: If parameter 'node' is already part of another linked list.

234 """

235 if node is None:

236 raise ValueError(f"Parameter 'node' is None.")

237

238 if not isinstance(node, Node):

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

240 ex.add_note(f"Got type '{getFullyQualifiedName(next)}'.")

241 raise ex

242

243 if node._linkedList is not None:

244 raise LinkedListException(f"Parameter 'node' belongs to another linked list.")

245

246 node._linkedList = self._linkedList

247 node._nextNode = self

248 node._previousNode = self._previousNode

249 if self._previousNode is None:

250 self._linkedList._firstNode = node

251 else:

252 self._previousNode._nextNode = node

253 self._previousNode = node

254 self._linkedList._count += 1

255

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

257 """

258 Insert a node after this node.

259

260 :param node: Node to insert.

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

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

263 :raises LinkedListException: If parameter 'node' is already part of another linked list.

264 """

265 if node is None:

266 raise ValueError(f"Parameter 'node' is None.")

267

268 if not isinstance(node, Node):

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

270 ex.add_note(f"Got type '{getFullyQualifiedName(next)}'.")

271 raise ex

272

273 if node._linkedList is not None:

274 raise LinkedListException(f"Parameter 'node' belongs to another linked list.")

275

276 node._linkedList = self._linkedList

277 node._previousNode = self

278 node._nextNode = self._nextNode

279 if self._nextNode is None:

280 self._linkedList._lastNode = node

281 else:

282 self._nextNode._previousNode = node

283 self._nextNode = node

284 self._linkedList._count += 1

285

286 # move forward

287 # move backward

288 # move by relative pos

289 # move to position

290 # move to begin

291 # move to end

292

293 # insert tuple/list/linkedlist before

294 # insert tuple/list/linkedlist after

295

296 # iterate forward for n

297 # iterate backward for n

298

299 # slice to tuple / list starting from that node

300

301 # swap left by n

302 # swap right by n

303

304 def Remove(self) -> _NodeValue:

305 """

306 Remove this node from the linked list.

307 """

308 if self._previousNode is None:

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

310 self._linkedList._firstNode = self._nextNode

311 self._linkedList._count -= 1

312

313 if self._nextNode is None:

314 self._linkedList._lastNode = None

315

316 self._linkedList = None

317

318 if self._nextNode is not None:

319 self._nextNode._previousNode = None

320

321 self._nextNode = None

322 elif self._nextNode is None:

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

324 self._linkedList._lastNode = self._previousNode

325 self._linkedList._count -= 1

326 self._linkedList = None

327

328 self._previousNode._nextNode = None

329 self._previousNode = None

330 else:

331 self._previousNode._nextNode = self._nextNode

332 self._nextNode._previousNode = self._previousNode

333 self._nextNode = None

334 self._previousNode = None

335

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

337 self._linkedList._count -= 1

338 self._linkedList = None

339

340 return self._value

341

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

343 """

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

345

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

347

348 :param includeSelf: If ``True``, include this node into the sequence, otherwise start at previous node.

349 :return: A sequence of nodes towards the list's first node.

350 """

351 previousNode = self._previousNode

352

353 if includeSelf:

354 yield self

355

356 node = previousNode

357 while node is not None:

358 previousNode = node._previousNode

359 yield node

360 node = previousNode

361

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

363 """

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

365

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

367

368 :param includeSelf: If ``True``, include this node into the sequence, otherwise start at next node.

369 :return: A sequence of nodes towards the list's last node.

370 """

371 nextNode = self._nextNode

372

373 if includeSelf:

374 yield self

375

376 node = nextNode

377 while node is not None:

378 nextNode = node._nextNode

379 yield node

380 node = nextNode

381

382 def __repr__(self) -> str:

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

384

385

386@export

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

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

389

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

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

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

393

394 # allow iterable to initialize the list

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

396 """

397 Initialize an empty linked list.

398

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

400

401 :param nodes: Optional iterable to initialize the linked list.

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

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

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

405 """

406 if nodes is None:

407 self._firstNode = None

408 self._lastNode = None

409 self._count = 0

410 elif not isinstance(nodes, Iterable):

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

412 ex.add_note(f"Got type '{getFullyQualifiedName(next)}'.")

413 raise ex

414 else:

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

416 self._firstNode = None

417 self._lastNode = None

418 self._count = 0

419 return

420

421 try:

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

423 except StopIteration:

424 self._firstNode = None

425 self._lastNode = None

426 self._count = 0

427 return

428

429 if not isinstance(first, Node):

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

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

432 raise ex

433 elif first._linkedList is not None:

434 raise LinkedListException(f"First element in parameter 'nodes' is assigned to different list.")

435

436 position = 1

437 first._linkedList = self

438 first._previousNode = None

439 self._firstNode = previous = node = first

440

441 for node in iterator:

442 if not isinstance(node, Node):

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

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

445 raise ex

446 elif node._linkedList is not None:

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

448

449 node._linkedList = self

450 node._previousNode = previous

451 previous._nextNode = node

452

453 previous = node

454 position += 1

455

456 self._lastNode = node

457 self._count = position

458 node._nextNode = None

459

460 @readonly

461 def IsEmpty(self) -> int:

462 """

463 Read-only property to access the number of .

464

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

466

467 :return: ``True`` if linked list is empty, otherwise ``False``

468 """

469 return self._count == 0

470

471 @readonly

472 def Count(self) -> int:

473 """

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

475

476 :return: Number of nodes.

477 """

478 return self._count

479

480 @readonly

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

482 """

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

484

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

486

487 :return: First node.

488 """

489 return self._firstNode

490

491 @readonly

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

493 """

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

495

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

497

498 :return: Last node.

499 """

500 return self._lastNode

501

502 def Clear(self) -> None:

503 """

504 Clear the linked list.

505 """

506 self._firstNode = None

507 self._lastNode = None

508 self._count = 0

509

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

511 """

512 Insert a node before the first node.

513

514 :param node: Node to insert.

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

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

517 :raises LinkedListException: If parameter 'node' is already part of another linked list.

518 """

519 if node is None:

520 raise ValueError(f"Parameter 'node' is None.")

521

522 if not isinstance(node, Node):

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

524 ex.add_note(f"Got type '{getFullyQualifiedName(next)}'.")

525 raise ex

526

527 if node._linkedList is not None:

528 raise LinkedListException(f"Parameter 'node' belongs to another linked list.")

529

530 node._linkedList = self

531 node._previousNode = None

532 node._nextNode = self._firstNode

533 if self._firstNode is None:

534 self._lastNode = node

535 else:

536 self._firstNode._previousNode = node

537 self._firstNode = node

538 self._count += 1

539

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

541 """

542 Insert a node after the last node.

543

544 :param node: Node to insert.

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

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

547 :raises LinkedListException: If parameter 'node' is already part of another linked list.

548 """

549 if node is None:

550 raise ValueError(f"Parameter 'node' is None.")

551

552 if not isinstance(node, Node):

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

554 ex.add_note(f"Got type '{getFullyQualifiedName(next)}'.")

555 raise ex

556

557 if node._linkedList is not None:

558 raise LinkedListException(f"Parameter 'node' belongs to another linked list.")

559

560 node._linkedList = self

561 node._nextNode = None

562 node._previousNode = self._lastNode

563 if self._lastNode is None:

564 self._firstNode = node

565 else:

566 node._previousNode._nextNode = node

567 self._lastNode = node

568 self._count += 1

569

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

571 """

572 Remove first node from linked list.

573

574 :return: First node.

575 :raises LinkedListException: If linked list is empty.

576 """

577 if self._firstNode is None:

578 raise LinkedListException(f"Linked list is empty.")

579

580 node = self._firstNode

581 self._firstNode = node._nextNode

582 if self._firstNode is None:

583 self._lastNode = None

584 self._count = 0

585 else:

586 self._firstNode._previousNode = None

587 self._count -= 1

588

589 node._linkedList = None

590 node._nextNode = None

591 return node

592

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

594 """

595 Remove last node from linked list.

596

597 :return: Last node.

598 :raises LinkedListException: If linked list is empty.

599 """

600 if self._lastNode is None:

601 raise LinkedListException(f"Linked list is empty.")

602

603 node = self._lastNode

604 self._lastNode = node._previousNode

605 if self._lastNode is None:

606 self._firstNode = None

607 self._count = 0

608 else:

609 self._lastNode._nextNode = None

610 self._count -= 1

611

612 node._linkedList = None

613 node._previousNode = None

614 return node

615

616

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

618 """

619 Access a node in the linked list by position.

620

621 :param index: Node position to access.

622 :return: Node at the given position.

623 :raises ValueError: If parameter 'position' is out of range.

624

625 .. note::

626

627 The algorithm starts iterating nodes from the shorter end.

628 """

629 if index == 0:

630 if self._firstNode is None:

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

632 ex.add_note(f"Linked list is empty.")

633 raise ex

634

635 return self._firstNode

636 elif index == self._count - 1:

637 return self._lastNode

638 elif index >= self._count:

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

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

641 raise ex

642

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

644 pos = 1

645 node = self._firstNode._nextNode

646 while node is not None:

647 if pos == index:

648 return node

649

650 node = node._nextNode

651 pos += 1

652 else: # pragma: no cover

653 raise LinkedListException(f"Node position not found.")

654 else:

655 pos = self._count - 2

656 node = self._lastNode._previousNode

657 while node is not None:

658 if pos == index:

659 return node

660

661 node = node._previousNode

662 pos -= 1

663 else: # pragma: no cover

664 raise LinkedListException(f"Node position not found.")

665

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

667 if self._firstNode is None:

668 raise LinkedListException(f"Linked list is empty.")

669

670 if not reverse:

671 node = self._firstNode

672 while node is not None:

673 if predicate(node):

674 break

675

676 node = node._nextNode

677 else:

678 raise LinkedListException(f"Node not found.")

679 else:

680 node = self._lastNode

681 while node is not None:

682 if predicate(node):

683 break

684

685 node = node._previousNode

686 else:

687 raise LinkedListException(f"Node not found.")

688

689 return node

690

691 def Reverse(self) -> None:

692 """

693 Reverse the order of nodes in the linked list.

694 """

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

696 return

697

698 node = self._lastNode = self._firstNode

699

700 while node is not None:

701 last = node

702 node = last._nextNode

703 last._nextNode = last._previousNode

704

705 last._previousNode = node

706 self._firstNode = last

707

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

709 """

710 Sort the linked list in ascending or descending order.

711

712 The sort operation is **stable**.

713

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

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

716

717 .. note::

718

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

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

721 """

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

723 return

724

725 if key is None:

726 key = lambda node: node._value

727

728 sequence = [n for n in self.IterateFromFirst()]

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

730

731 first = sequence[0]

732

733 position = 1

734 first._previousNode = None

735 self._firstNode = previous = node = first

736

737 for node in sequence[1:]:

738 node._previousNode = previous

739 previous._nextNode = node

740

741 previous = node

742 position += 1

743

744 self._lastNode = node

745 self._count = position

746 node._nextNode = None

747

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

749 """

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

751

752 :return: A sequence of nodes towards the list's last node.

753 """

754 if self._firstNode is None:

755 return

756

757 node = self._firstNode

758 while node is not None:

759 nextNode = node._nextNode

760 yield node

761 node = nextNode

762

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

764 """

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

766

767 :return: A sequence of nodes towards the list's first node.

768 """

769 if self._lastNode is None:

770 return

771

772 node = self._lastNode

773 while node is not None:

774 previousNode = node._previousNode

775 yield node

776 node = previousNode

777

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

779 """

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

781

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

783

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

785 :return: A list (array) of this linked list's values.

786 """

787 if self._count == 0:

788 return []

789 elif reverse:

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

791 else:

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

793

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

795 """

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

797

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

799

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

801 :return: A tuple of this linked list's values.

802 """

803 if self._count == 0:

804 return tuple()

805 elif reverse:

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

807 else:

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

809

810 # Copy

811 # Sort

812

813 # merge lists

814 # append / prepend lists

815 # split list

816

817 # Remove at position (= __delitem__)

818 # Remove by predicate (n times)

819

820 # Insert at position (= __setitem__)

821

822 # insert tuple/list/linkedlist at begin

823 # insert tuple/list/linkedlist at end

824

825 # Find by position (= __getitem__)

826 # Find by predicate from left (n times)

827 # Find by predicate from right (n times)

828

829 # Count by predicate

830

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

832 # slice by start, length from left

833 # Slice by predicate

834

835 # iterate start, length from right

836 # iterate start, length from left

837 # iterate by predicate

838

839 def __len__(self) -> int:

840 """

841 Returns the number of nodes in the linked list.

842

843 :returns: Number of nodes.

844 """

845 return self._count

846

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

848 """

849 Access a node's value by its index.

850

851 :param index: Node index to access.

852 :return: Node's value at the given index.

853 :raises ValueError: If parameter 'index' is out of range.

854

855 .. note::

856

857 The algorithm starts iterating nodes from the shorter end.

858 """

859 return self.GetNodeByIndex(index)._value

860

861 def __setitem__(self, index: int, value: _NodeValue) -> None:

862 """

863 Set the value of node at the given position.

864

865 :param index: Index of the node to modify.

866 :param value: New value for the node's value addressed by index.

867 """

868 self.GetNodeByIndex(index)._value = value

869

870 def __delitem__(self, index: int) -> Node[_NodeKey, _NodeValue]:

871 """

872 Remove a node at the given index.

873

874 :param index: Index of the node to remove.

875 :return: Removed node.

876 """

877 node = self.GetNodeByIndex(index)

878 node.Remove()

879 return node._value

Coverage for pyTooling / LinkedList / init.py: 89%

404 statements