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 LinkedListError(ToolingException):

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

61@export

62class InternalError(LinkedListError):

63 """

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

66 The exception message states the discovered inconsistency. Please create a `bug report

67 <https://GitHub.com/pyTooling/pyTooling/issues>`__ if this exception is raised.

68 """

71@export

72class NotInAListError(LinkedListError):

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

76@export

77class NotInSameListError(LinkedListError):

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

81@export

82class EmptyListError(LinkedListError):

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

86@export

87class NodeNotFoundError(LinkedListError):

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

91@export

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

93 """

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

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

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

98 purposes.

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

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

102 """

103

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

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

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

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

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

109

110 def __init__(

111 self,

112 value: _NodeValue,

113 key: Nullable[_NodeKey] = None,

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

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

116 ) -> None:

117 """

118 Initialize a linked list node.

119

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

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

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

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

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

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

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

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

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

129 """

130 self._previousNode = previousNode

131 self._nextNode = nextNode

132 self._value = value

133 self._key = key

134

135 # Attache to previous node

136 if previousNode is not None:

137 if not isinstance(previousNode, Node):

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

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

140 raise ex

141

142 # PreviousNode is part of a list

143 if previousNode._linkedList is not None:

144 self._linkedList = previousNode._linkedList

145 self._linkedList._count += 1

146

147 # Check if previous was the last node

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

149 self._nextNode = None

150 self._linkedList._lastNode = self

151 else:

152 self._nextNode = previousNode._nextNode

153 self._nextNode._previousNode = self

154 else:

155 self._linkedList = None

156

157 previousNode._nextNode = self

158

159 if nextNode is not None:

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

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

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

163 raise ex

164

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

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

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

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

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

170 raise ex

171

172 previousNode._nextNode = self

173 elif nextNode is not None:

174 if not isinstance(nextNode, Node):

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

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

177 raise ex

178

179 # NextNode is part of a list

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

181 self._linkedList = nextNode._linkedList

182 self._linkedList._count += 1

183

184 # Check if next was the first node

185 if nextNode._previousNode is None:

186 self._previousNode = None

187 self._linkedList._firstNode = self

188 else:

189 self._previousNode = nextNode._previousNode

190 self._previousNode._nextNode = self

191 else:

192 self._linkedList = None

193

194 nextNode._previousNode = self

195 else:

196 self._linkedList = None

197

198 @readonly

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

200 """

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

202

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

204 """

205 return self._linkedList

206

207 @readonly

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

209 """

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

211

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

213

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

215 """

216 return self._previousNode

217

218 @readonly

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

220 """

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

222

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

224

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

226 """

227 return self._nextNode

228

229 @property

230 def Key(self) -> _NodeKey:

231 """

232 Property to access the node's internal key.

233

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

235

236 :returns: The node's key.

237 """

238 return self._key

239

240 @Key.setter

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

242 self._key = key

243

244 @property

245 def Value(self) -> _NodeValue:

246 """

247 Property to access the node's internal data.

248

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

250

251 :returns: The node's value.

252 """

253 return self._value

254

255 @Value.setter

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

257 self._value = value

258

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

260 """

261 Insert a node before this node.

262

263 :param node: Node to insert.

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

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

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

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

268 """

269 if node is None:

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

271

272 if not isinstance(node, Node):

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

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

275 raise ex

276

277 if node._linkedList is not None:

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

279

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

281 raise NotInAListError("Node is not part of a linked list.")

282

283 node._linkedList = self._linkedList

284 node._nextNode = self

285 node._previousNode = self._previousNode

286 if self._previousNode is None:

287 self._linkedList._firstNode = node

288 else:

289 self._previousNode._nextNode = node

290 self._previousNode = node

291 self._linkedList._count += 1

292

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

294 """

295 Insert a node after this node.

296

297 :param node: Node to insert.

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

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

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

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

302 """

303 if node is None:

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

305

306 if not isinstance(node, Node):

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

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

309 raise ex

310

311 if node._linkedList is not None:

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

313

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

315 raise NotInAListError("Node is not part of a linked list.")

316

317 node._linkedList = self._linkedList

318 node._previousNode = self

319 node._nextNode = self._nextNode

320 if self._nextNode is None:

321 self._linkedList._lastNode = node

322 else:

323 self._nextNode._previousNode = node

324 self._nextNode = node

325 self._linkedList._count += 1

326

327 # move forward

328 # move backward

329 # move by relative pos

330 # move to position

331 # move to begin

332 # move to end

333

334 # insert tuple/list/linkedlist before

335 # insert tuple/list/linkedlist after

336

337 # iterate forward for n

338 # iterate backward for n

339

340 # slice to tuple / list starting from that node

341

342 # swap left by n

343 # swap right by n

344

345 def Remove(self) -> _NodeValue:

346 """

347 Remove this node from the linked list.

348

349 :returns: The value of the removed node.

350 """

351 if self._previousNode is None:

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

353 self._linkedList._firstNode = self._nextNode

354 self._linkedList._count -= 1

355

356 if self._nextNode is None:

357 self._linkedList._lastNode = None

358

359 self._linkedList = None

360

361 if self._nextNode is not None:

362 self._nextNode._previousNode = None

363

364 self._nextNode = None

365 elif self._nextNode is None:

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

367 self._linkedList._lastNode = self._previousNode

368 self._linkedList._count -= 1

369 self._linkedList = None

370

371 self._previousNode._nextNode = None

372 self._previousNode = None

373 else:

374 self._previousNode._nextNode = self._nextNode

375 self._nextNode._previousNode = self._previousNode

376 self._nextNode = None

377 self._previousNode = None

378

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

380 self._linkedList._count -= 1

381 self._linkedList = None

382

383 return self._value

384

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

386 """

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

388

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

390

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

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

393 """

394 previousNode = self._previousNode

395

396 if includeSelf:

397 yield self

398

399 node = previousNode

400 while node is not None:

401 previousNode = node._previousNode

402 yield node

403 node = previousNode

404

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

406 """

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

408

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

410

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

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

413 """

414 nextNode = self._nextNode

415

416 if includeSelf:

417 yield self

418

419 node = nextNode

420 while node is not None:

421 nextNode = node._nextNode

422 yield node

423 node = nextNode

424

425 def __repr__(self) -> str:

426 """

427 Return a detailed string representation of this node.

428

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

430 """

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

432

433

434@export

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

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

437

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

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

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

441

442 # allow iterable to initialize the list

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

444 """

445 Initialize an empty linked list.

446

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

448

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

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

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

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

453 """

454 if nodes is None:

455 self._firstNode = None

456 self._lastNode = None

457 self._count = 0

458 elif not isinstance(nodes, Iterable):

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

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

461 raise ex

462 else:

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

464 self._firstNode = None

465 self._lastNode = None

466 self._count = 0

467 return

468

469 try:

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

471 except StopIteration:

472 self._firstNode = None

473 self._lastNode = None

474 self._count = 0

475 return

476

477 if not isinstance(first, Node):

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

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

480 raise ex

481 elif first._linkedList is not None:

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

483

484 position = 1

485 first._linkedList = self

486 first._previousNode = None

487 self._firstNode = previous = node = first

488

489 for node in iterator:

490 if not isinstance(node, Node):

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

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

493 raise ex

494 elif node._linkedList is not None:

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

496

497 node._linkedList = self

498 node._previousNode = previous

499 previous._nextNode = node

500

501 previous = node

502 position += 1

503

504 self._lastNode = node

505 self._count = position

506 node._nextNode = None

507

508 @readonly

509 def IsEmpty(self) -> int:

510 """

511 Read-only property to return the number of .

512

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

514

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

516 """

517 return self._count == 0

518

519 @readonly

520 def Count(self) -> int:

521 """

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

523

524 :returns: Number of nodes.

525 """

526 return self._count

527

528 @readonly

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

530 """

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

532

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

534

535 :returns: First node.

536 """

537 return self._firstNode

538

539 @readonly

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

541 """

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

543

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

545

546 :returns: Last node.

547 """

548 return self._lastNode

549

550 def Clear(self) -> None:

551 """

552 Clear the linked list.

553 """

554 self._firstNode = None

555 self._lastNode = None

556 self._count = 0

557

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

559 """

560 Insert a node before the first 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 NotInSameListError: If parameter 'node' is already part of another linked list.

566 """

567 if node is None:

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

569

570 if not isinstance(node, Node):

571 ex = TypeError("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 NotInSameListError("Parameter 'node' belongs to another linked list.")

577

578 node._linkedList = self

579 node._previousNode = None

580 node._nextNode = self._firstNode

581 if self._firstNode is None:

582 self._lastNode = node

583 else:

584 self._firstNode._previousNode = node

585 self._firstNode = node

586 self._count += 1

587

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

589 """

590 Insert a node after the last node.

591

592 :param node: Node to insert.

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

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

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

596 """

597 if node is None:

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

599

600 if not isinstance(node, Node):

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

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

603 raise ex

604

605 if node._linkedList is not None:

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

607

608 node._linkedList = self

609 node._nextNode = None

610 node._previousNode = self._lastNode

611 if self._lastNode is None:

612 self._firstNode = node

613 else:

614 self._lastNode._nextNode = node

615 self._lastNode = node

616 self._count += 1

617

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

619 """

620 Remove first node from linked list.

621

622 :returns: First node.

623 :raises EmptyListError: If linked list is empty.

624 """

625 if self._firstNode is None:

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

627

628 node = self._firstNode

629 self._firstNode = node._nextNode

630 if self._firstNode is None:

631 self._lastNode = None

632 self._count = 0

633 else:

634 self._firstNode._previousNode = None

635 self._count -= 1

636

637 node._linkedList = None

638 node._nextNode = None

639 return node

640

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

642 """

643 Remove last node from linked list.

644

645 :returns: Last node.

646 :raises EmptyListError: If linked list is empty.

647 """

648 if self._lastNode is None:

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

650

651 node = self._lastNode

652 self._lastNode = node._previousNode

653 if self._lastNode is None:

654 self._firstNode = None

655 self._count = 0

656 else:

657 self._lastNode._nextNode = None

658 self._count -= 1

659

660 node._linkedList = None

661 node._previousNode = None

662 return node

663

664

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

666 """

667 Access a node in the linked list by position.

668

669 :param index: Node position to access.

670 :returns: Node at the given position.

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

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

673 inconsistent.

674

675 .. note::

676

677 The algorithm starts iterating nodes from the shorter end.

678 """

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

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

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

682 raise ex

683

684 if index == 0:

685 return self._firstNode

686 elif index == self._count - 1:

687 return self._lastNode

688 elif index >= self._count:

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

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

691 raise ex

692

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

694 pos = 1

695 node = self._firstNode._nextNode

696 while node is not None:

697 if pos == index:

698 return node

699

700 node = node._nextNode

701 pos += 1

702 else: # pragma: no cover

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

704 else:

705 pos = self._count - 2

706 node = self._lastNode._previousNode

707 while node is not None:

708 if pos == index:

709 return node

710

711 node = node._previousNode

712 pos -= 1

713 else: # pragma: no cover

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

715

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

717 """

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

719

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

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

722 :returns: The first matching node.

723 :raises EmptyListError: If the list is empty.

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

725 """

726 if self._firstNode is None:

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

728

729 if not reverse:

730 node = self._firstNode

731 while node is not None:

732 if predicate(node):

733 break

734

735 node = node._nextNode

736 else:

737 raise NodeNotFoundError("Node not found.")

738 else:

739 node = self._lastNode

740 while node is not None:

741 if predicate(node):

742 break

743

744 node = node._previousNode

745 else:

746 raise NodeNotFoundError("Node not found.")

747

748 return node

749

750 def Reverse(self) -> None:

751 """

752 Reverse the order of nodes in the linked list.

753 """

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

755 return

756

757 node = self._lastNode = self._firstNode

758

759 while node is not None:

760 last = node

761 node = last._nextNode

762 last._nextNode = last._previousNode

763

764 last._previousNode = node

765 self._firstNode = last

766

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

768 """

769 Sort the linked list in ascending or descending order.

770

771 The sort operation is **stable**.

772

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

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

775

776 .. note::

777

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

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

780 """

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

782 return

783

784 if key is None:

785 key = lambda node: node._value

786

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

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

789

790 first = sequence[0]

791

792 position = 1

793 first._previousNode = None

794 self._firstNode = previous = node = first

795

796 for node in sequence[1:]:

797 node._previousNode = previous

798 previous._nextNode = node

799

800 previous = node

801 position += 1

802

803 self._lastNode = node

804 self._count = position

805 node._nextNode = None

806

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

808 """

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

810

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

812 """

813 if self._firstNode is None:

814 return

815

816 node = self._firstNode

817 while node is not None:

818 nextNode = node._nextNode

819 yield node

820 node = nextNode

821

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

823 """

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

825

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

827 """

828 if self._lastNode is None:

829 return

830

831 node = self._lastNode

832 while node is not None:

833 previousNode = node._previousNode

834 yield node

835 node = previousNode

836

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

838 """

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

840

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

842

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

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

845 """

846 if self._count == 0:

847 return []

848 elif reverse:

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

850 else:

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

852

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

854 """

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

856

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

858

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

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

861 """

862 if self._count == 0:

863 return tuple()

864 elif reverse:

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

866 else:

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

868

869 # Copy

870 # Sort

871

872 # merge lists

873 # append / prepend lists

874 # split list

875

876 # Remove at position (= __delitem__)

877 # Remove by predicate (n times)

878

879 # Insert at position (= __setitem__)

880

881 # insert tuple/list/linkedlist at begin

882 # insert tuple/list/linkedlist at end

883

884 # Find by position (= __getitem__)

885 # Find by predicate from left (n times)

886 # Find by predicate from right (n times)

887

888 # Count by predicate

889

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

891 # slice by start, length from left

892 # Slice by predicate

893

894 # iterate start, length from right

895 # iterate start, length from left

896 # iterate by predicate

897

898 def __len__(self) -> int:

899 """

900 Returns the number of nodes in the linked list.

901

902 :returns: Number of nodes.

903 """

904 return self._count

905

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

907 """

908 Access a node's value by its index.

909

910 :param index: Node index to access.

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

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

913

914 .. note::

915

916 The algorithm starts iterating nodes from the shorter end.

917 """

918 return self.GetNodeByIndex(index)._value

919

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

921 """

922 Set the value of node at the given position.

923

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

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

926 """

927 self.GetNodeByIndex(index)._value = value

928

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

930 """

931 Remove a node at the given index.

932

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

934 :returns: Removed node.

935 """

936 node = self.GetNodeByIndex(index)

937 node.Remove()

938 return node._value

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

418 statements