cs_survival_kit ¶

Hand-written data structures and algorithms, plus a benchmarking toolkit.

The companion library to the CS Survival Guide, which renders this package's docstrings and source as its API reference.

The package namespace holds the defaults: List is the list to use when any list will do. The individual implementations live in cs_survival_kit.data_structures, and the algorithms in cs_survival_kit.algorithms.

List ¶

List(items: Iterable[T] = (), *, capacity: int = 4, growth: GrowthPolicy = doubling)

Bases: DynamicArray[T]

The default list: a DynamicArray under a name that says "just a list".

List adds nothing to DynamicArray; it is the name. Every operation and every cost is DynamicArray's, and the full table is in its docstring. The name exists so that code can say which it means: a DynamicArray because it wants an array, or a List because it wants the default. If a better general-purpose list is ever added to the kit, this is the name that will point at it.

Complexity

The same as DynamicArray. The operations that make it the default:

Operation	Time
`a[i]`, `a[i] = x`	O(1)
`append`	O(1) amortized, O(n) worst
`pop_back`	O(1)
`len(a)`	O(1)
iteration	O(n)

And the ones that are not its strength: prepend, pop_front and insert or pop away from the end are O(n), because the elements after the position shift. Constructing from items is O(n).

Parameters:

Name	Type	Description	Default
`items`	`Iterable[T]`	Elements to add to the new list, in order. Defaults to empty.	`()`
`capacity`	`int`	The number of slots to allocate up front, as for `DynamicArray`.	`4`
`growth`	`GrowthPolicy`	The growth policy, as for `DynamicArray`. Doubling by default.	`doubling`

Examples:

>>> from cs_survival_kit import List
>>> a = List([3, 1, 2])
>>> a
List([3, 1, 2])
>>> a.append(4)
>>> a[0], a[3], len(a)
(3, 4, 4)
>>> a.pop_back()
4

It is a DynamicArray, so anything written for one accepts it:

>>> from cs_survival_kit.data_structures import AbstractList, DynamicArray
>>> isinstance(a, DynamicArray), isinstance(a, AbstractList)
(True, True)

And it satisfies the sorting contract, like every list in the kit:

>>> from cs_survival_kit.algorithms.sorting import Sortable
>>> isinstance(a, Sortable)
True

Source code in cs_survival_kit/data_structures/dynamic_array.py · View on GitHub

def __init__(
    self,
    items: Iterable[T] = (),
    *,
    capacity: int = 4,
    growth: GrowthPolicy = doubling,
) -> None:
    if capacity <= 0:
        raise ValueError("capacity must be greater than 0")

    self._items: list[T | None] = [None] * capacity
    self._capacity: int = capacity
    self._size: int = 0
    self._growth: GrowthPolicy = growth

    for item in items:
        self.append(item)