Segment List Recipe

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

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=())

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)

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)

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)

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)

Raise not-implemented error.

Raises

NotImplementedError – use sl.add(value) instead

irange(*args, **kwargs)

Not implemented.

irange_key(*args, **kwargs)

Not implemented.

reverse()

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)

Stable sort in place.

update(*args, **kwargs)

Not implemented.

static zero(_)

Return 0.