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 sys import version_info

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

37try:

38 from pyTooling.Decorators import readonly, export

39 from pyTooling.Exceptions import ToolingException

40 from pyTooling.MetaClasses import ExtendedType

41 from pyTooling.Common import getFullyQualifiedName

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

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

45 try:

46 from Decorators import readonly, export

47 from Exceptions import ToolingException

48 from MetaClasses import ExtendedType

49 from Common import getFullyQualifiedName

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

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

52 raise ex

55_NodeKey = TypeVar("_NodeKey")

56_NodeValue = TypeVar("_NodeValue")

59@export

60class LinkedListException(ToolingException):

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

64@export

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

66 """

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

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

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

71 purposes.

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

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

75 """

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

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

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

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

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

83 def __init__(

84 self,

85 value: _NodeValue,

86 key: Nullable[_NodeKey] = None,

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

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

89 ) -> None:

90 """

91 Initialize a linked list node.

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

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

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

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

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

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

99 """

100 self._previousNode = previousNode

101 self._nextNode = nextNode

102 self._value = value

103 self._key = value

104

105 # Attache to previous node

106 if previousNode is not None:

107 if not isinstance(previousNode, Node):

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

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

110 raise ex

111

112 # PreviousNode is part of a list

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

114 self._linkedList = previousNode._linkedList

115 self._linkedList._count += 1

116

117 # Check if previous was the last node

118 if previousNode._nextNode is None:

119 self._nextNode = None

120 self._linkedList._lastNode = self

121 else:

122 self._nextNode = previousNode._nextNode

123 self._nextNode._previousNode = self

124 else:

125 self._linkedList = None

126

127 previousNode._nextNode = self

128

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

130 if not isinstance(nextNode, Node):

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

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

133 raise ex

134

135 if nextNode._linkedList is not None:

136 if self._linkedList is not None:

137 if self._linkedList is not previousNode._linkedList:

138 raise ValueError()

139

140 previousNode._nextNode = self

141 elif nextNode is not None:

142 if not isinstance(nextNode, Node):

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

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

145 raise ex

146

147 # NextNode is part of a list

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

149 self._linkedList = nextNode._linkedList

150 self._linkedList._count += 1

151

152 # Check if next was the first node

153 if nextNode._previousNode is None:

154 self._previousNode = None

155 self._linkedList._firstNode = self

156 else:

157 self._previousNode = nextNode._previousNode

158 self._previousNode._nextNode = self

159 else:

160 self._linkedList = None

161

162 nextNode._previousNode = self

163 else:

164 self._linkedList = None

165

166 @readonly

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

168 """

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

170

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

172 """

173 return self._linkedList

174

175 @readonly

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

177 """

178 Read-only property to access nodes predecessor.

179

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

181

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

183 """

184 return self._previousNode

185

186 @readonly

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

188 """

189 Read-only property to access nodes successor.

190

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

192

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

194 """

195 return self._nextNode

196

197 @property

198 def Key(self) -> _NodeKey:

199 """

200 Property to access the node's internal key.

201

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

203

204 :return: The node's key.

205 """

206 return self._key

207

208 @Key.setter

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

210 self._key = key

211

212 @property

213 def Value(self) -> _NodeValue:

214 """

215 Property to access the node's internal data.

216

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

218

219 :return: The node's value.

220 """

221 return self._value

222

223 @Value.setter

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

225 self._value = value

226

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

228 """

229 Insert a node before this node.

230

231 :param node: Node to insert.

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

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

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

235 """

236 if node is None:

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

238

239 if not isinstance(node, Node):

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

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

242 raise ex

243

244 if node._linkedList is not None:

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

246

247 node._linkedList = self._linkedList

248 node._nextNode = self

249 node._previousNode = self._previousNode

250 if self._previousNode is None:

251 self._linkedList._firstNode = node

252 else:

253 self._previousNode._nextNode = node

254 self._previousNode = node

255 self._linkedList._count += 1

256

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

258 """

259 Insert a node after this node.

260

261 :param node: Node to insert.

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

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

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

265 """

266 if node is None:

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

268

269 if not isinstance(node, Node):

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

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

272 raise ex

273

274 if node._linkedList is not None:

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

276

277 node._linkedList = self._linkedList

278 node._previousNode = self

279 node._nextNode = self._nextNode

280 if self._nextNode is None:

281 self._linkedList._lastNode = node

282 else:

283 self._nextNode._previousNode = node

284 self._nextNode = node

285 self._linkedList._count += 1

286

287 # move forward

288 # move backward

289 # move by relative pos

290 # move to position

291 # move to begin

292 # move to end

293

294 # insert tuple/list/linkedlist before

295 # insert tuple/list/linkedlist after

296

297 # iterate forward for n

298 # iterate backward for n

299

300 # slice to tuple / list starting from that node

301

302 # swap left by n

303 # swap right by n

304

305 def Remove(self) -> _NodeValue:

306 """

307 Remove this node from the linked list.

308 """

309 if self._previousNode is None:

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

311 self._linkedList._firstNode = self._nextNode

312 self._linkedList._count -= 1

313

314 if self._nextNode is None:

315 self._linkedList._lastNode = None

316

317 self._linkedList = None

318

319 if self._nextNode is not None:

320 self._nextNode._previousNode = None

321

322 self._nextNode = None

323 elif self._nextNode is None:

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

325 self._linkedList._lastNode = self._previousNode

326 self._linkedList._count -= 1

327 self._linkedList = None

328

329 self._previousNode._nextNode = None

330 self._previousNode = None

331 else:

332 self._previousNode._nextNode = self._nextNode

333 self._nextNode._previousNode = self._previousNode

334 self._nextNode = None

335 self._previousNode = None

336

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

338 self._linkedList._count -= 1

339 self._linkedList = None

340

341 return self._value

342

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

344 """

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

346

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

348

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

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

351 """

352 previousNode = self._previousNode

353

354 if includeSelf:

355 yield self

356

357 node = previousNode

358 while node is not None:

359 previousNode = node._previousNode

360 yield node

361 node = previousNode

362

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

364 """

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

366

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

368

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

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

371 """

372 nextNode = self._nextNode

373

374 if includeSelf:

375 yield self

376

377 node = nextNode

378 while node is not None:

379 nextNode = node._nextNode

380 yield node

381 node = nextNode

382

383 def __repr__(self) -> str:

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

385

386

387@export

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

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

390

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

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

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

394

395 # allow iterable to initialize the list

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

397 """

398 Initialize an empty linked list.

399

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

401

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

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

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

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

406 """

407 if nodes is None:

408 self._firstNode = None

409 self._lastNode = None

410 self._count = 0

411 elif not isinstance(nodes, Iterable):

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

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

414 raise ex

415 else:

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

417 self._firstNode = None

418 self._lastNode = None

419 self._count = 0

420 return

421

422 try:

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

424 except StopIteration:

425 self._firstNode = None

426 self._lastNode = None

427 self._count = 0

428 return

429

430 if not isinstance(first, Node):

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

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

433 raise ex

434 elif first._linkedList is not None:

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

436

437 position = 1

438 first._linkedList = self

439 first._previousNode = None

440 self._firstNode = previous = node = first

441

442 for node in iterator:

443 if not isinstance(node, Node):

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

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

446 raise ex

447 elif node._linkedList is not None:

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

449

450 node._linkedList = self

451 node._previousNode = previous

452 previous._nextNode = node

453

454 previous = node

455 position += 1

456

457 self._lastNode = node

458 self._count = position

459 node._nextNode = None

460

461 @readonly

462 def IsEmpty(self) -> int:

463 """

464 Read-only property to access the number of .

465

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

467

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

469 """

470 return self._count == 0

471

472 @readonly

473 def Count(self) -> int:

474 """

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

476

477 :return: Number of nodes.

478 """

479 return self._count

480

481 @readonly

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

483 """

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

485

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

487

488 :return: First node.

489 """

490 return self._firstNode

491

492 @readonly

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

494 """

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

496

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

498

499 :return: Last node.

500 """

501 return self._lastNode

502

503 def Clear(self) -> None:

504 """

505 Clear the linked list.

506 """

507 self._firstNode = None

508 self._lastNode = None

509 self._count = 0

510

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

512 """

513 Insert a node before the first node.

514

515 :param node: Node to insert.

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

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

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

519 """

520 if node is None:

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

522

523 if not isinstance(node, Node):

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

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

526 raise ex

527

528 if node._linkedList is not None:

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

530

531 node._linkedList = self

532 node._previousNode = None

533 node._nextNode = self._firstNode

534 if self._firstNode is None:

535 self._lastNode = node

536 else:

537 self._firstNode._previousNode = node

538 self._firstNode = node

539 self._count += 1

540

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

542 """

543 Insert a node after the last node.

544

545 :param node: Node to insert.

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

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

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

549 """

550 if node is None:

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

552

553 if not isinstance(node, Node):

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

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

556 raise ex

557

558 if node._linkedList is not None:

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

560

561 node._linkedList = self

562 node._nextNode = None

563 node._previousNode = self._lastNode

564 if self._lastNode is None:

565 self._firstNode = node

566 else:

567 node._previousNode._nextNode = node

568 self._lastNode = node

569 self._count += 1

570

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

572 """

573 Remove first node from linked list.

574

575 :return: First node.

576 :raises LinkedListException: If linked list is empty.

577 """

578 if self._firstNode is None:

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

580

581 node = self._firstNode

582 self._firstNode = node._nextNode

583 if self._firstNode is None:

584 self._lastNode = None

585 self._count = 0

586 else:

587 self._firstNode._previousNode = None

588 self._count -= 1

589

590 node._linkedList = None

591 node._nextNode = None

592 return node

593

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

595 """

596 Remove last node from linked list.

597

598 :return: Last node.

599 :raises LinkedListException: If linked list is empty.

600 """

601 if self._lastNode is None:

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

603

604 node = self._lastNode

605 self._lastNode = node._previousNode

606 if self._lastNode is None:

607 self._firstNode = None

608 self._count = 0

609 else:

610 self._lastNode._nextNode = None

611 self._count -= 1

612

613 node._linkedList = None

614 node._previousNode = None

615 return node

616

617

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

619 """

620 Access a node in the linked list by position.

621

622 :param index: Node position to access.

623 :return: Node at the given position.

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

625

626 .. note::

627

628 The algorithm starts iterating nodes from the shorter end.

629 """

630 if index == 0:

631 if self._firstNode is None:

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

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

634 raise ex

635

636 return self._firstNode

637 elif index == self._count - 1:

638 return self._lastNode

639 elif index >= self._count:

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

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

642 raise ex

643

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

645 pos = 1

646 node = self._firstNode._nextNode

647 while node is not None:

648 if pos == index:

649 return node

650

651 node = node._nextNode

652 pos += 1

653 else: # pragma: no cover

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

655 else:

656 pos = self._count - 2

657 node = self._lastNode._previousNode

658 while node is not None:

659 if pos == index:

660 return node

661

662 node = node._previousNode

663 pos -= 1

664 else: # pragma: no cover

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

666

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

668 if self._firstNode is None:

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

670

671 if not reverse:

672 node = self._firstNode

673 while node is not None:

674 if predicate(node):

675 break

676

677 node = node._nextNode

678 else:

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

680 else:

681 node = self._lastNode

682 while node is not None:

683 if predicate(node):

684 break

685

686 node = node._previousNode

687 else:

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

689

690 return node

691

692 def Reverse(self) -> None:

693 """

694 Reverse the order of nodes in the linked list.

695 """

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

697 return

698

699 node = self._lastNode = self._firstNode

700

701 while node is not None:

702 last = node

703 node = last._nextNode

704 last._nextNode = last._previousNode

705

706 last._previousNode = node

707 self._firstNode = last

708

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

710 """

711 Sort the linked list in ascending or descending order.

712

713 The sort operation is **stable**.

714

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

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

717

718 .. note::

719

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

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

722 """

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

724 return

725

726 if key is None:

727 key = lambda node: node._value

728

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

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

731

732 first = sequence[0]

733

734 position = 1

735 first._previousNode = None

736 self._firstNode = previous = node = first

737

738 for node in sequence[1:]:

739 node._previousNode = previous

740 previous._nextNode = node

741

742 previous = node

743 position += 1

744

745 self._lastNode = node

746 self._count = position

747 node._nextNode = None

748

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

750 """

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

752

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

754 """

755 if self._firstNode is None:

756 return

757

758 node = self._firstNode

759 while node is not None:

760 nextNode = node._nextNode

761 yield node

762 node = nextNode

763

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

765 """

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

767

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

769 """

770 if self._lastNode is None:

771 return

772

773 node = self._lastNode

774 while node is not None:

775 previousNode = node._previousNode

776 yield node

777 node = previousNode

778

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

780 """

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

782

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

784

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

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

787 """

788 if self._count == 0:

789 return []

790 elif reverse:

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

792 else:

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

794

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

796 """

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

798

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

800

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

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

803 """

804 if self._count == 0:

805 return tuple()

806 elif reverse:

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

808 else:

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

810

811 # Copy

812 # Sort

813

814 # merge lists

815 # append / prepend lists

816 # split list

817

818 # Remove at position (= __delitem__)

819 # Remove by predicate (n times)

820

821 # Insert at position (= __setitem__)

822

823 # insert tuple/list/linkedlist at begin

824 # insert tuple/list/linkedlist at end

825

826 # Find by position (= __getitem__)

827 # Find by predicate from left (n times)

828 # Find by predicate from right (n times)

829

830 # Count by predicate

831

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

833 # slice by start, length from left

834 # Slice by predicate

835

836 # iterate start, length from right

837 # iterate start, length from left

838 # iterate by predicate

839

840 def __len__(self) -> int:

841 """

842 Returns the number of nodes in the linked list.

843

844 :returns: Number of nodes.

845 """

846 return self._count

847

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

849 """

850 Access a node's value by its index.

851

852 :param index: Node index to access.

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

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

855

856 .. note::

857

858 The algorithm starts iterating nodes from the shorter end.

859 """

860 return self.GetNodeByIndex(index)._value

861

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

863 """

864 Set the value of node at the given position.

865

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

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

868 """

869 self.GetNodeByIndex(index)._value = value

870

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

872 """

873 Remove a node at the given index.

874

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

876 :return: Removed node.

877 """

878 node = self.GetNodeByIndex(index)

879 node.Remove()

880 return node._value

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

405 statements