Conversion¶

Overview¶

This module converts between a Python list and any linear structure of sds.linear. Its main use is to sort the content of a structure with the list-based functions of sds.algorithms.sorting and get a structure back.

Both functions are generic: they rely only on __iter__ and add(), which every LinearCollection implements with its own semantics. No class-specific code is involved.

        graph LR
    A["Linear structure"] -->|"to_list()"| B["list"]
    B -->|"sorted() / quick_sort()"| C["sorted list"]
    C -->|"from_list(cls, ...)"| D["Linear structure"]

    style A fill:#3498db,color:#fff
    style D fill:#2ecc71,color:#fff

Round-trip behaviour¶

to_list(from_list(cls, items)) returns items unchanged only for the structures that iterate in insertion order.

Structure	Round trip	Why
`LinkedList`, `DoublyLinkedList`, `CircularLinkedList`	Identity	`add()` appends; iteration goes head to tail
`Queue`	Identity	`add()` enqueues; iteration goes front to rear
`Deque`	Identity	`add()` adds at the rear; iteration goes front to rear
`Stack`	Reversed	`add()` pushes; iteration goes top to bottom
`PriorityQueue`	Sorted by priority	`add()` inserts at the item’s priority

Example¶

from sds.linear import Queue, Stack, from_list, to_list

queue = from_list(Queue, [3, 1, 2])
ordered = from_list(Queue, sorted(to_list(queue)))
print(to_list(ordered))                     # [1, 2, 3]

print(to_list(from_list(Stack, [1, 2, 3]))) # [3, 2, 1] - LIFO

# Constructor arguments are forwarded
from sds.linear import PriorityQueue
pq = from_list(PriorityQueue, ["pear", "fig", "banana"], key=len)
print(to_list(pq))                          # ['fig', 'pear', 'banana']

Complexity¶

Function	Time	Notes
`to_list(structure)`	O(n)	One pass over the structure
`from_list(cls, items)`	n × cost of `cls.add()`	O(n) for `DoublyLinkedList`, `CircularLinkedList`, `Stack`, `Deque`; O(n²) for `LinkedList`, `Queue`, `PriorityQueue`

Detailed Documentation¶

sds.linear.convert.to_list(structure)[source]¶

Return the items of a linear structure as a new list.

Items come out in the structure’s own iteration order, so the result of a Stack starts with its top element and the result of a PriorityQueue starts with its highest-priority element.

Parameters:: structure (LinearCollection) – Any linear structure. It is left unchanged.
Returns:: A new list; mutating it does not affect structure.
Return type:: list
Raises:: StructureTypeError – If structure is not a LinearCollection.

Examples

>>> from sds.linear import Deque, to_list
>>> d = Deque()
>>> d.add_rear(1)
>>> d.add_front(0)
>>> to_list(d)
[0, 1]

Notes

Time complexity: O(n). Space complexity: O(n).

sds.linear.convert.from_list(cls, items, **kwargs)[source]¶

Build a linear structure of type cls from items.

A fresh cls(**kwargs) is created, then each item is passed, in order, to its add() method. What “adding” means is up to the structure: appended to a linked list, pushed on a stack, inserted at its priority in a priority queue.

Parameters:

cls (type) – A concrete LinearCollection subclass.
items (iterable) – Items to add, in order. Any iterable is accepted, including another linear structure.
**kwargs (Any) – Forwarded to the constructor, e.g. key and reverse for PriorityQueue.

Returns:

A new instance of cls.

Return type:

LinearCollection

Raises:

StructureTypeError – If cls is not a LinearCollection subclass, or if kwargs does not match its constructor.

Examples

>>> from sds.linear import PriorityQueue, from_list, to_list
>>> pq = from_list(PriorityQueue, ["ccc", "a", "bb"], key=len, reverse=True)
>>> to_list(pq)
['ccc', 'bb', 'a']

Notes

Time complexity: n times the cost of cls.add(). That is O(n) for DoublyLinkedList, CircularLinkedList, Stack and Deque, but O(n²) for LinkedList and Queue (appending walks the chain, no tail pointer) and for PriorityQueue (sorted insertion).