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 if version_info >= (3, 11): # pragma: no cover

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

111 raise ex

112

113 # PreviousNode is part of a list

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

115 self._linkedList = previousNode._linkedList

116 self._linkedList._count += 1

117

118 # Check if previous was the last node

119 if previousNode._nextNode is None:

120 self._nextNode = None

121 self._linkedList._lastNode = self

122 else:

123 self._nextNode = previousNode._nextNode

124 self._nextNode._previousNode = self

125 else:

126 self._linkedList = None

127

128 previousNode._nextNode = self

129

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

131 if not isinstance(nextNode, Node):

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

133 if version_info >= (3, 11): # pragma: no cover

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

135 raise ex

136

137 if nextNode._linkedList is not None:

138 if self._linkedList is not None:

139 if self._linkedList is not previousNode._linkedList:

140 raise ValueError()

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 if version_info >= (3, 11): # pragma: no cover

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

148 raise ex

149

150 # NextNode is part of a list

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

152 self._linkedList = nextNode._linkedList

153 self._linkedList._count += 1

154

155 # Check if next was the first node

156 if nextNode._previousNode is None:

157 self._previousNode = None

158 self._linkedList._firstNode = self

159 else:

160 self._previousNode = nextNode._previousNode

161 self._previousNode._nextNode = self

162 else:

163 self._linkedList = None

164

165 nextNode._previousNode = self

166 else:

167 self._linkedList = None

168

169 @readonly

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

171 """

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

173

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

175 """

176 return self._linkedList

177

178 @readonly

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

180 """

181 Read-only property to access nodes predecessor.

182

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

184

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

186 """

187 return self._previousNode

188

189 @readonly

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

191 """

192 Read-only property to access nodes successor.

193

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

195

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

197 """

198 return self._nextNode

199

200 @property

201 def Key(self) -> _NodeKey:

202 """

203 Property to access the node's internal key.

204

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

206

207 :return: The node's key.

208 """

209 return self._key

210

211 @Key.setter

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

213 self._key = key

214

215 @property

216 def Value(self) -> _NodeValue:

217 """

218 Property to access the node's internal data.

219

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

221

222 :return: The node's value.

223 """

224 return self._value

225

226 @Value.setter

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

228 self._value = value

229

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

231 """

232 Insert a node before this node.

233

234 :param node: Node to insert.

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

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

237 :raises LinkedListException: If parameter 'node' is already part of another 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 if version_info >= (3, 11): # pragma: no cover

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

246 raise ex

247

248 if node._linkedList is not None:

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

250

251 node._linkedList = self._linkedList

252 node._nextNode = self

253 node._previousNode = self._previousNode

254 if self._previousNode is None:

255 self._linkedList._firstNode = node

256 else:

257 self._previousNode._nextNode = node

258 self._previousNode = node

259 self._linkedList._count += 1

260

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

262 """

263 Insert a node after this node.

264

265 :param node: Node to insert.

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

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

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

269 """

270 if node is None:

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

272

273 if not isinstance(node, Node):

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

275 if version_info >= (3, 11): # pragma: no cover

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

277 raise ex

278

279 if node._linkedList is not None:

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

281

282 node._linkedList = self._linkedList

283 node._previousNode = self

284 node._nextNode = self._nextNode

285 if self._nextNode is None:

286 self._linkedList._lastNode = node

287 else:

288 self._nextNode._previousNode = node

289 self._nextNode = node

290 self._linkedList._count += 1

291

292 # move forward

293 # move backward

294 # move by relative pos

295 # move to position

296 # move to begin

297 # move to end

298

299 # insert tuple/list/linkedlist before

300 # insert tuple/list/linkedlist after

301

302 # iterate forward for n

303 # iterate backward for n

304

305 # slice to tuple / list starting from that node

306

307 # swap left by n

308 # swap right by n

309

310 def Remove(self) -> _NodeValue:

311 """

312 Remove this node from the linked list.

313 """

314 if self._previousNode is None:

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

316 self._linkedList._firstNode = self._nextNode

317 self._linkedList._count -= 1

318

319 if self._nextNode is None:

320 self._linkedList._lastNode = None

321

322 self._linkedList = None

323

324 if self._nextNode is not None:

325 self._nextNode._previousNode = None

326

327 self._nextNode = None

328 elif self._nextNode is None:

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

330 self._linkedList._lastNode = self._previousNode

331 self._linkedList._count -= 1

332 self._linkedList = None

333

334 self._previousNode._nextNode = None

335 self._previousNode = None

336 else:

337 self._previousNode._nextNode = self._nextNode

338 self._nextNode._previousNode = self._previousNode

339 self._nextNode = None

340 self._previousNode = None

341

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

343 self._linkedList._count -= 1

344 self._linkedList = None

345

346 return self._value

347

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

349 """

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

351

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

353

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

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

356 """

357 previousNode = self._previousNode

358

359 if includeSelf:

360 yield self

361

362 node = previousNode

363 while node is not None:

364 previousNode = node._previousNode

365 yield node

366 node = previousNode

367

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

369 """

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

371

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

373

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

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

376 """

377 nextNode = self._nextNode

378

379 if includeSelf:

380 yield self

381

382 node = nextNode

383 while node is not None:

384 nextNode = node._nextNode

385 yield node

386 node = nextNode

387

388 def __repr__(self) -> str:

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

390

391

392@export

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

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

395

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

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

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

399

400 # allow iterable to initialize the list

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

402 """

403 Initialize an empty linked list.

404

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

406

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

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

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

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

411 """

412 if nodes is None:

413 self._firstNode = None

414 self._lastNode = None

415 self._count = 0

416 elif not isinstance(nodes, Iterable):

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

418 if version_info >= (3, 11): # pragma: no cover

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

420 raise ex

421 else:

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

423 self._firstNode = None

424 self._lastNode = None

425 self._count = 0

426 return

427

428 try:

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

430 except StopIteration:

431 self._firstNode = None

432 self._lastNode = None

433 self._count = 0

434 return

435

436 if not isinstance(first, Node):

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

438 if version_info >= (3, 11): # pragma: no cover

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

440 raise ex

441 elif first._linkedList is not None:

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

443

444 position = 1

445 first._linkedList = self

446 first._previousNode = None

447 self._firstNode = previous = node = first

448

449 for node in iterator:

450 if not isinstance(node, Node):

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

452 if version_info >= (3, 11): # pragma: no cover

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

454 raise ex

455 elif node._linkedList is not None:

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

457

458 node._linkedList = self

459 node._previousNode = previous

460 previous._nextNode = node

461

462 previous = node

463 position += 1

464

465 self._lastNode = node

466 self._count = position

467 node._nextNode = None

468

469 @readonly

470 def IsEmpty(self) -> int:

471 """

472 Read-only property to access the number of .

473

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

475

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

477 """

478 return self._count == 0

479

480 @readonly

481 def Count(self) -> int:

482 """

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

484

485 :return: Number of nodes.

486 """

487 return self._count

488

489 @readonly

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

491 """

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

493

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

495

496 :return: First node.

497 """

498 return self._firstNode

499

500 @readonly

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

502 """

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

504

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

506

507 :return: Last node.

508 """

509 return self._lastNode

510

511 def Clear(self) -> None:

512 """

513 Clear the linked list.

514 """

515 self._firstNode = None

516 self._lastNode = None

517 self._count = 0

518

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

520 """

521 Insert a node before the first node.

522

523 :param node: Node to insert.

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

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

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

527 """

528 if node is None:

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

530

531 if not isinstance(node, Node):

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

533 if version_info >= (3, 11): # pragma: no cover

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

535 raise ex

536

537 if node._linkedList is not None:

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

539

540 node._linkedList = self

541 node._previousNode = None

542 node._nextNode = self._firstNode

543 if self._firstNode is None:

544 self._lastNode = node

545 else:

546 self._firstNode._previousNode = node

547 self._firstNode = node

548 self._count += 1

549

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

551 """

552 Insert a node after the last node.

553

554 :param node: Node to insert.

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

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

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

558 """

559 if node is None:

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

561

562 if not isinstance(node, Node):

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

564 if version_info >= (3, 11): # pragma: no cover

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

566 raise ex

567

568 if node._linkedList is not None:

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

570

571 node._linkedList = self

572 node._nextNode = None

573 node._previousNode = self._lastNode

574 if self._lastNode is None:

575 self._firstNode = node

576 else:

577 node._previousNode._nextNode = node

578 self._lastNode = node

579 self._count += 1

580

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

582 """

583 Remove first node from linked list.

584

585 :return: First node.

586 :raises LinkedListException: If linked list is empty.

587 """

588 if self._firstNode is None:

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

590

591 node = self._firstNode

592 self._firstNode = node._nextNode

593 if self._firstNode is None:

594 self._lastNode = None

595 self._count = 0

596 else:

597 self._firstNode._previousNode = None

598 self._count -= 1

599

600 node._linkedList = None

601 node._nextNode = None

602 return node

603

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

605 """

606 Remove last node from linked list.

607

608 :return: Last node.

609 :raises LinkedListException: If linked list is empty.

610 """

611 if self._lastNode is None:

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

613

614 node = self._lastNode

615 self._lastNode = node._previousNode

616 if self._lastNode is None:

617 self._firstNode = None

618 self._count = 0

619 else:

620 self._lastNode._nextNode = None

621 self._count -= 1

622

623 node._linkedList = None

624 node._previousNode = None

625 return node

626

627

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

629 """

630 Access a node in the linked list by position.

631

632 :param index: Node position to access.

633 :return: Node at the given position.

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

635

636 .. note::

637

638 The algorithm starts iterating nodes from the shorter end.

639 """

640 if index == 0:

641 if self._firstNode is None:

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

643 if version_info >= (3, 11): # pragma: no cover

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

645 raise ex

646

647 return self._firstNode

648 elif index == self._count - 1:

649 return self._lastNode

650 elif index >= self._count:

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

652 if version_info >= (3, 11): # pragma: no cover

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

654 raise ex

655

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

657 pos = 1

658 node = self._firstNode._nextNode

659 while node is not None:

660 if pos == index:

661 return node

662

663 node = node._nextNode

664 pos += 1

665 else: # pragma: no cover

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

667 else:

668 pos = self._count - 2

669 node = self._lastNode._previousNode

670 while node is not None:

671 if pos == index:

672 return node

673

674 node = node._previousNode

675 pos -= 1

676 else: # pragma: no cover

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

678

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

680 if self._firstNode is None:

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

682

683 if not reverse:

684 node = self._firstNode

685 while node is not None:

686 if predicate(node):

687 break

688

689 node = node._nextNode

690 else:

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

692 else:

693 node = self._lastNode

694 while node is not None:

695 if predicate(node):

696 break

697

698 node = node._previousNode

699 else:

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

701

702 return node

703

704 def Reverse(self) -> None:

705 """

706 Reverse the order of nodes in the linked list.

707 """

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

709 return

710

711 node = self._lastNode = self._firstNode

712

713 while node is not None:

714 last = node

715 node = last._nextNode

716 last._nextNode = last._previousNode

717

718 last._previousNode = node

719 self._firstNode = last

720

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

722 """

723 Sort the linked list in ascending or descending order.

724

725 The sort operation is **stable**.

726

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

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

729

730 .. note::

731

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

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

734 """

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

736 return

737

738 if key is None:

739 key = lambda node: node._value

740

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

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

743

744 first = sequence[0]

745

746 position = 1

747 first._previousNode = None

748 self._firstNode = previous = node = first

749

750 for node in sequence[1:]:

751 node._previousNode = previous

752 previous._nextNode = node

753

754 previous = node

755 position += 1

756

757 self._lastNode = node

758 self._count = position

759 node._nextNode = None

760

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

762 """

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

764

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

766 """

767 if self._firstNode is None:

768 return

769

770 node = self._firstNode

771 while node is not None:

772 nextNode = node._nextNode

773 yield node

774 node = nextNode

775

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

777 """

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

779

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

781 """

782 if self._lastNode is None:

783 return

784

785 node = self._lastNode

786 while node is not None:

787 previousNode = node._previousNode

788 yield node

789 node = previousNode

790

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

792 """

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

794

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

796

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

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

799 """

800 if self._count == 0:

801 return []

802 elif reverse:

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

804 else:

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

806

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

808 """

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

810

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

812

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

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

815 """

816 if self._count == 0:

817 return tuple()

818 elif reverse:

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

820 else:

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

822

823 # Copy

824 # Sort

825

826 # merge lists

827 # append / prepend lists

828 # split list

829

830 # Remove at position (= __delitem__)

831 # Remove by predicate (n times)

832

833 # Insert at position (= __setitem__)

834

835 # insert tuple/list/linkedlist at begin

836 # insert tuple/list/linkedlist at end

837

838 # Find by position (= __getitem__)

839 # Find by predicate from left (n times)

840 # Find by predicate from right (n times)

841

842 # Count by predicate

843

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

845 # slice by start, length from left

846 # Slice by predicate

847

848 # iterate start, length from right

849 # iterate start, length from left

850 # iterate by predicate

851

852 def __len__(self) -> int:

853 """

854 Returns the number of nodes in the linked list.

855

856 :returns: Number of nodes.

857 """

858 return self._count

859

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

861 """

862 Access a node's value by its index.

863

864 :param index: Node index to access.

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

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

867

868 .. note::

869

870 The algorithm starts iterating nodes from the shorter end.

871 """

872 return self.GetNodeByIndex(index)._value

873

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

875 """

876 Set the value of node at the given position.

877

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

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

880 """

881 self.GetNodeByIndex(index)._value = value

882

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

884 """

885 Remove a node at the given index.

886

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

888 :return: Removed node.

889 """

890 node = self.GetNodeByIndex(index)

891 node.Remove()

892 return node._value

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

393 statements