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"""

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

34.. seealso::

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

43from collections.abc import Sized

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

46from pyTooling.Decorators import readonly, export

47from pyTooling.Exceptions import ToolingException

48from pyTooling.MetaClasses import ExtendedType

49from pyTooling.Common import getFullyQualifiedName

52_NodeKey = TypeVar("_NodeKey")

53_NodeValue = TypeVar("_NodeValue")

56@export

57class LinkedListException(ToolingException):

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

61@export

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

63 """

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

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

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

68 purposes.

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

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

72 """

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

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

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

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

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

80 def __init__(

81 self,

82 value: _NodeValue,

83 key: Nullable[_NodeKey] = None,

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

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

86 ) -> None:

87 """

88 Initialize a linked list node.

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

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

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

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

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

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

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

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

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

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:

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: 118 ↛ 119line 118 didn't jump to line 119 because the condition on line 118 was never true

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:

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

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 # 'self._linkedList' was just taken from 'previousNode', so comparing it against 'previousNode' again

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

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

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

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

140 raise ex

141

142 previousNode._nextNode = self

143 elif nextNode is not None:

144 if not isinstance(nextNode, Node):

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

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

147 raise ex

148

149 # NextNode is part of a list

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

151 self._linkedList = nextNode._linkedList

152 self._linkedList._count += 1

153

154 # Check if next was the first node

155 if nextNode._previousNode is None:

156 self._previousNode = None

157 self._linkedList._firstNode = self

158 else:

159 self._previousNode = nextNode._previousNode

160 self._previousNode._nextNode = self

161 else:

162 self._linkedList = None

163

164 nextNode._previousNode = self

165 else:

166 self._linkedList = None

167

168 @readonly

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

170 """

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

172

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

174 """

175 return self._linkedList

176

177 @readonly

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

179 """

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

181

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

183

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

185 """

186 return self._previousNode

187

188 @readonly

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

190 """

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

192

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

194

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

196 """

197 return self._nextNode

198

199 @property

200 def Key(self) -> _NodeKey:

201 """

202 Property to access the node's internal key.

203

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

205

206 :returns: The node's key.

207 """

208 return self._key

209

210 @Key.setter

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

212 self._key = key

213

214 @property

215 def Value(self) -> _NodeValue:

216 """

217 Property to access the node's internal data.

218

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

220

221 :returns: The node's value.

222 """

223 return self._value

224

225 @Value.setter

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

227 self._value = value

228

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

230 """

231 Insert a node before this node.

232

233 :param node: Node to insert.

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

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

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

237 :raises LinkedListException: If this node is not part of a linked list.

238 """

239 if node is None:

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

241

242 if not isinstance(node, Node):

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

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

245 raise ex

246

247 if node._linkedList is not None:

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

249

250 if self._linkedList is None: 250 ↛ 251line 250 didn't jump to line 251 because the condition on line 250 was never true

251 raise LinkedListException(f"Node is not part of a linked list.")

252

253 node._linkedList = self._linkedList

254 node._nextNode = self

255 node._previousNode = self._previousNode

256 if self._previousNode is None:

257 self._linkedList._firstNode = node

258 else:

259 self._previousNode._nextNode = node

260 self._previousNode = node

261 self._linkedList._count += 1

262

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

264 """

265 Insert a node after this node.

266

267 :param node: Node to insert.

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

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

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

271 :raises LinkedListException: If this node is not part of a linked list.

272 """

273 if node is None:

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

275

276 if not isinstance(node, Node):

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

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

279 raise ex

280

281 if node._linkedList is not None:

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

283

284 if self._linkedList is None: 284 ↛ 285line 284 didn't jump to line 285 because the condition on line 284 was never true

285 raise LinkedListException(f"Node is not part of a linked list.")

286

287 node._linkedList = self._linkedList

288 node._previousNode = self

289 node._nextNode = self._nextNode

290 if self._nextNode is None:

291 self._linkedList._lastNode = node

292 else:

293 self._nextNode._previousNode = node

294 self._nextNode = node

295 self._linkedList._count += 1

296

297 # move forward

298 # move backward

299 # move by relative pos

300 # move to position

301 # move to begin

302 # move to end

303

304 # insert tuple/list/linkedlist before

305 # insert tuple/list/linkedlist after

306

307 # iterate forward for n

308 # iterate backward for n

309

310 # slice to tuple / list starting from that node

311

312 # swap left by n

313 # swap right by n

314

315 def Remove(self) -> _NodeValue:

316 """

317 Remove this node from the linked list.

318

319 :returns: The value of the removed node.

320 """

321 if self._previousNode is None:

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

323 self._linkedList._firstNode = self._nextNode

324 self._linkedList._count -= 1

325

326 if self._nextNode is None:

327 self._linkedList._lastNode = None

328

329 self._linkedList = None

330

331 if self._nextNode is not None:

332 self._nextNode._previousNode = None

333

334 self._nextNode = None

335 elif self._nextNode is None:

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

337 self._linkedList._lastNode = self._previousNode

338 self._linkedList._count -= 1

339 self._linkedList = None

340

341 self._previousNode._nextNode = None

342 self._previousNode = None

343 else:

344 self._previousNode._nextNode = self._nextNode

345 self._nextNode._previousNode = self._previousNode

346 self._nextNode = None

347 self._previousNode = None

348

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

350 self._linkedList._count -= 1

351 self._linkedList = None

352

353 return self._value

354

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

356 """

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

358

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

360

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

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

363 """

364 previousNode = self._previousNode

365

366 if includeSelf:

367 yield self

368

369 node = previousNode

370 while node is not None:

371 previousNode = node._previousNode

372 yield node

373 node = previousNode

374

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

376 """

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

378

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

380

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

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

383 """

384 nextNode = self._nextNode

385

386 if includeSelf:

387 yield self

388

389 node = nextNode

390 while node is not None:

391 nextNode = node._nextNode

392 yield node

393 node = nextNode

394

395 def __repr__(self) -> str:

396 """

397 Return a detailed string representation of this node.

398

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

400 """

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

402

403

404@export

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

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

407

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

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

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

411

412 # allow iterable to initialize the list

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

414 """

415 Initialize an empty linked list.

416

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

418

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

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

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

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

423 """

424 if nodes is None:

425 self._firstNode = None

426 self._lastNode = None

427 self._count = 0

428 elif not isinstance(nodes, Iterable):

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

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

431 raise ex

432 else:

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

434 self._firstNode = None

435 self._lastNode = None

436 self._count = 0

437 return

438

439 try:

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

441 except StopIteration:

442 self._firstNode = None

443 self._lastNode = None

444 self._count = 0

445 return

446

447 if not isinstance(first, Node):

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

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

450 raise ex

451 elif first._linkedList is not None:

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

453

454 position = 1

455 first._linkedList = self

456 first._previousNode = None

457 self._firstNode = previous = node = first

458

459 for node in iterator:

460 if not isinstance(node, Node):

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

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

463 raise ex

464 elif node._linkedList is not None:

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

466

467 node._linkedList = self

468 node._previousNode = previous

469 previous._nextNode = node

470

471 previous = node

472 position += 1

473

474 self._lastNode = node

475 self._count = position

476 node._nextNode = None

477

478 @readonly

479 def IsEmpty(self) -> int:

480 """

481 Read-only property to return the number of .

482

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

484

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

486 """

487 return self._count == 0

488

489 @readonly

490 def Count(self) -> int:

491 """

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

493

494 :returns: Number of nodes.

495 """

496 return self._count

497

498 @readonly

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

500 """

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

502

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

504

505 :returns: First node.

506 """

507 return self._firstNode

508

509 @readonly

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

511 """

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

513

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

515

516 :returns: Last node.

517 """

518 return self._lastNode

519

520 def Clear(self) -> None:

521 """

522 Clear the linked list.

523 """

524 self._firstNode = None

525 self._lastNode = None

526 self._count = 0

527

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

529 """

530 Insert a node before the first node.

531

532 :param node: Node to insert.

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

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

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

536 """

537 if node is None:

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

539

540 if not isinstance(node, Node):

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

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

543 raise ex

544

545 if node._linkedList is not None:

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

547

548 node._linkedList = self

549 node._previousNode = None

550 node._nextNode = self._firstNode

551 if self._firstNode is None:

552 self._lastNode = node

553 else:

554 self._firstNode._previousNode = node

555 self._firstNode = node

556 self._count += 1

557

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

559 """

560 Insert a node after the last node.

561

562 :param node: Node to insert.

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

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

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

566 """

567 if node is None:

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

569

570 if not isinstance(node, Node):

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

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

573 raise ex

574

575 if node._linkedList is not None:

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

577

578 node._linkedList = self

579 node._nextNode = None

580 node._previousNode = self._lastNode

581 if self._lastNode is None:

582 self._firstNode = node

583 else:

584 self._lastNode._nextNode = node

585 self._lastNode = node

586 self._count += 1

587

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

589 """

590 Remove first node from linked list.

591

592 :returns: First node.

593 :raises LinkedListException: If linked list is empty.

594 """

595 if self._firstNode is None:

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

597

598 node = self._firstNode

599 self._firstNode = node._nextNode

600 if self._firstNode is None:

601 self._lastNode = None

602 self._count = 0

603 else:

604 self._firstNode._previousNode = None

605 self._count -= 1

606

607 node._linkedList = None

608 node._nextNode = None

609 return node

610

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

612 """

613 Remove last node from linked list.

614

615 :returns: Last node.

616 :raises LinkedListException: If linked list is empty.

617 """

618 if self._lastNode is None:

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

620

621 node = self._lastNode

622 self._lastNode = node._previousNode

623 if self._lastNode is None:

624 self._firstNode = None

625 self._count = 0

626 else:

627 self._lastNode._nextNode = None

628 self._count -= 1

629

630 node._linkedList = None

631 node._previousNode = None

632 return node

633

634

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

636 """

637 Access a node in the linked list by position.

638

639 :param index: Node position to access.

640 :returns: Node at the given position.

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

642 :raises LinkedListException: If the list is empty, or the index is out of range.

643

644 .. note::

645

646 The algorithm starts iterating nodes from the shorter end.

647 """

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

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

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

651 raise ex

652

653 if index == 0:

654 return self._firstNode

655 elif index == self._count - 1:

656 return self._lastNode

657 elif index >= self._count:

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

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

660 raise ex

661

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

663 pos = 1

664 node = self._firstNode._nextNode

665 while node is not None:

666 if pos == index:

667 return node

668

669 node = node._nextNode

670 pos += 1

671 else: # pragma: no cover

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

673 else:

674 pos = self._count - 2

675 node = self._lastNode._previousNode

676 while node is not None:

677 if pos == index:

678 return node

679

680 node = node._previousNode

681 pos -= 1

682 else: # pragma: no cover

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

684

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

686 """

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

688

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

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

691 :returns: The first matching node.

692 :raises LinkedListException: If the list is empty, or no node matches.

693 """

694 if self._firstNode is None:

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

696

697 if not reverse:

698 node = self._firstNode

699 while node is not None:

700 if predicate(node):

701 break

702

703 node = node._nextNode

704 else:

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

706 else:

707 node = self._lastNode

708 while node is not None:

709 if predicate(node):

710 break

711

712 node = node._previousNode

713 else:

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

715

716 return node

717

718 def Reverse(self) -> None:

719 """

720 Reverse the order of nodes in the linked list.

721 """

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

723 return

724

725 node = self._lastNode = self._firstNode

726

727 while node is not None:

728 last = node

729 node = last._nextNode

730 last._nextNode = last._previousNode

731

732 last._previousNode = node

733 self._firstNode = last

734

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

736 """

737 Sort the linked list in ascending or descending order.

738

739 The sort operation is **stable**.

740

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

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

743

744 .. note::

745

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

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

748 """

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

750 return

751

752 if key is None:

753 key = lambda node: node._value

754

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

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

757

758 first = sequence[0]

759

760 position = 1

761 first._previousNode = None

762 self._firstNode = previous = node = first

763

764 for node in sequence[1:]:

765 node._previousNode = previous

766 previous._nextNode = node

767

768 previous = node

769 position += 1

770

771 self._lastNode = node

772 self._count = position

773 node._nextNode = None

774

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

776 """

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

778

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

780 """

781 if self._firstNode is None:

782 return

783

784 node = self._firstNode

785 while node is not None:

786 nextNode = node._nextNode

787 yield node

788 node = nextNode

789

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

791 """

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

793

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

795 """

796 if self._lastNode is None:

797 return

798

799 node = self._lastNode

800 while node is not None:

801 previousNode = node._previousNode

802 yield node

803 node = previousNode

804

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

806 """

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

808

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

810

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

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

813 """

814 if self._count == 0:

815 return []

816 elif reverse:

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

818 else:

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

820

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

822 """

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

824

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

826

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

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

829 """

830 if self._count == 0:

831 return tuple()

832 elif reverse:

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

834 else:

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

836

837 # Copy

838 # Sort

839

840 # merge lists

841 # append / prepend lists

842 # split list

843

844 # Remove at position (= __delitem__)

845 # Remove by predicate (n times)

846

847 # Insert at position (= __setitem__)

848

849 # insert tuple/list/linkedlist at begin

850 # insert tuple/list/linkedlist at end

851

852 # Find by position (= __getitem__)

853 # Find by predicate from left (n times)

854 # Find by predicate from right (n times)

855

856 # Count by predicate

857

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

859 # slice by start, length from left

860 # Slice by predicate

861

862 # iterate start, length from right

863 # iterate start, length from left

864 # iterate by predicate

865

866 def __len__(self) -> int:

867 """

868 Returns the number of nodes in the linked list.

869

870 :returns: Number of nodes.

871 """

872 return self._count

873

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

875 """

876 Access a node's value by its index.

877

878 :param index: Node index to access.

879 :returns: Node's value at the given index.

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

881

882 .. note::

883

884 The algorithm starts iterating nodes from the shorter end.

885 """

886 return self.GetNodeByIndex(index)._value

887

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

889 """

890 Set the value of node at the given position.

891

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

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

894 """

895 self.GetNodeByIndex(index)._value = value

896

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

898 """

899 Remove a node at the given index.

900

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

902 :returns: Removed node.

903 """

904 node = self.GetNodeByIndex(index)

905 node.Remove()

906 return node._value

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

408 statements