Segment List Recipe

class sortedcollections.SegmentList(iterable=None, key=<function identity>)[source]

List that supports fast random insertion and deletion of elements.

SegmentList is a special case of a SortedList initialized with a key function that always returns 0. As such, several SortedList methods are not implemented for SegmentList.

__init__(iterable=())[source]

Initialize sorted-key list instance.

Optional iterable argument provides an initial iterable of values to initialize the sorted-key list.

Optional key argument defines a callable that, like the key argument to Python’s sorted function, extracts a comparison key from each value. The default is the identity function.

Runtime complexity: O(n*log(n))

>>> from operator import neg
>>> skl = SortedKeyList(key=neg)
>>> skl
SortedKeyList([], key=<built-in function neg>)
>>> skl = SortedKeyList([3, 1, 2], key=neg)
>>> skl
SortedKeyList([3, 2, 1], key=<built-in function neg>)
Parameters
  • iterable – initial values (optional)

  • key – function used to extract comparison key (optional)

__setitem__(index, value)[source]

Raise not-implemented error.

sl.__setitem__(index, value) <==> sl[index] = value

Raises

NotImplementedError – use del sl[index] and sl.add(value) instead

add(*args, **kwargs)

Not implemented.

append(value)[source]

Raise not-implemented error.

Implemented to override MutableSequence.append which provides an erroneous default implementation.

Raises

NotImplementedError – use sl.add(value) instead

bisect(*args, **kwargs)

Not implemented.

bisect_key(*args, **kwargs)

Not implemented.

bisect_key_left(*args, **kwargs)

Not implemented.

bisect_key_right(*args, **kwargs)

Not implemented.

bisect_left(*args, **kwargs)

Not implemented.

bisect_right(*args, **kwargs)

Not implemented.

extend(values)[source]

Raise not-implemented error.

Implemented to override MutableSequence.extend which provides an erroneous default implementation.

Raises

NotImplementedError – use sl.update(values) instead

insert(index, value)[source]

Raise not-implemented error.

Raises

NotImplementedError – use sl.add(value) instead

irange(*args, **kwargs)

Not implemented.

irange_key(*args, **kwargs)

Not implemented.

reverse()[source]

Raise not-implemented error.

Sorted list maintains values in ascending sort order. Values may not be reversed in-place.

Use reversed(sl) for an iterator over values in descending sort order.

Implemented to override MutableSequence.reverse which provides an erroneous default implementation.

Raises

NotImplementedError – use reversed(sl) instead

sort(key=None, reverse=False)[source]

Stable sort in place.

update(*args, **kwargs)

Not implemented.

static zero(_)[source]

Return 0.