sortedlist¶

class blist.sortedlist(iterable=(), key=None)¶

A sortedlist provides most of the same methods as a blist (and, hence, a list), but keeps the items in sorted order. Methods that would insert an item at a particular location are not included (e.g., append, insert). To add an element to the sortedlist, use add. To add several elements, use update. To remove an element, use discard, remove, or del L[i].

An optional iterable provides an initial series of items to populate the sortedlist.

key specifies a function of one argument that is used to extract a comparison key from each list element: key=str.lower. The default value is None (compare the elements directly). The key function must always return the same key for an item or the results are unpredictable.

A sortedlist can be used as an order statistic tree (Cormen et al., Introduction to Algorithms, ch. 14) that allows duplicate keys.

x in L

Returns True if and only if x is an element in the list.

Requires $\Theta\left(\log^2 n\right)$ total operations or $\Theta\left(\log n\right)$ comparisons.

Return type:	`bool`

del L[i]

Removes the element located at index i from the list.

Requires $\Theta\left(\log n\right)$ operations and no comparisons.

del L[i:j]

Removes the elements from i to j from the list.

Requires $\Theta\left(\log n\right)$ operations and no comparisons.

L == L2, L != L2, L < L2, L <= L2, L > L2, L >= L2

Compares two lists. For full details see Comparisons in the Python language reference.

In the worst case, requires $\Theta\left(n\right)$ operations and $\Theta\left(n\right)$ comparisons.

Return type:	`bool`

L[i]

Returns the element at position i.

Requires $\Theta\left(\log n\right)$ operations in the worst case but only $\Theta\left(1\right)$ operations if the list’s size has not been changed recently. Requires no comparisons in any case.

(Cormen et al. call this operation “SELECT”.)

Return type:	item

L[i:j]

Returns a new sortedlist containing the elements from i to j.

Requires $\Theta\left(\log n\right)$ operations and no comparisons.

Return type:	`sortedlist`

L *= k

Increase the length of the list by a factor of k, by inserting k-1 additional shallow copies of each item in the list.

Requires $\Theta\left(n \log\left(k + n\right)\right)$ operations and no comparisons.

iter(L)¶

Creates an iterator over the list.

Requires $\Theta\left(\log n\right)$ operations to create the iterator. Each element from the iterator requires $\Theta\left(1\right)$ operations to retrieve, or $\Theta\left(n\right)$ operations to iterate over the entire list.

Return type:	iterator

len(L)¶

Returns the number of elements in the list.

Requires $\Theta\left(1\right)$ operations.

Return type:	`int`

L * k or k * L

Returns a new sorted list containing k shallow copies of each item in L.

Requires $\Theta\left(n \log\left(k + n\right)\right)$ operations and no comparisons.

Return type:	`sortedlist`

reversed(L)¶

Creates an iterator to traverse the list in reverse.

Requires $\Theta\left(\log n\right)$ operations to create the iterator. Each element from the iterator requires $\Theta\left(1\right)$ operations to retrieve, or $\Theta\left(n\right)$ operations to iterate over the entire list. Requires no comparisons in any case.

Return type:	iterator

L[i] = x

Replace the item at position i of L with x.

Requires $\Theta\left(\log n\right)$ operations in the worst case but only $\Theta\left(1\right)$ operations if the list’s size has not been changed recently. Requires no comparisons in any case.

L[i:j] = iterable

Replace the items at positions i through j with the contents of iterable.

Requires $\Theta\left(j - i + \log n\right)$ operations and no comparisons.

L.add(value)¶

Add the element value to the list.

Requires $\Theta\left(\log^2 n\right)$ total operations or $\Theta\left(\log n\right)$ comparisons.

L.bisect_left(value)¶

Similarly to the bisect module in the standard library, this returns an appropriate index to insert value in L. If value is already present in L, the insertion point will be before (to the left of) any existing entries.

Requires $\Theta\left(\log^2 n\right)$ total operations or $\Theta\left(\log n\right)$ comparisons.

L.bisect(value)¶: Same as bisect_left.

L.bisect_right(value)¶: Same thing as bisect_left, but if value is already present in L, the insertion point will be after (to the right of) any existing entries.

L.count(value)¶

Returns the number of occurrences of value in the list.

Requires $\Theta\left(n\right)$ operations and $\Theta\left(n\right)$ comparisons in the worst case.

Return type:	`int`

L.discard(value)¶

Removes the first occurrence of value. If value is not a member, does nothing.

In the worst case, requires $\Theta\left(\log^2 n\right)$ operations and $\Theta\left(\log n\right)$ comparisons.

L.index(value[, start[, stop]])¶

Returns the smallest k such that $L[k] == x$ and $i <= k < j$ . Raises ValueError if value is not present. stop defaults to the end of the list. start defaults to the beginning. Negative indexes are supported, as for slice indices.

In the worst case, requires $\Theta\left(\log^2 m\right)$ operations and $\Theta\left(\log m\right)$ comparisons, where m is stop - start.

(Cormen et al. call this operation “RANK”.)

Return type:	`int`

L.pop([index])¶

Removes and return item at index (default last). Raises IndexError if list is empty or index is out of range. Negative indexes are supported, as for slice indices.

Requires $\Theta\left(\log n\right)$ operations and no comparisons.

Return type:	item

L.remove(value)¶

Remove first occurrence of value. Raises ValueError if value is not present.

In the worst case, requires $\Theta\left(\log^2 n\right)$ operations and $\Theta\left(\log n\right)$ comparisons.

L.update(iterable)¶

Grow the list by inserting all elements from the iterable.

Requires $\Theta\left(m \log^2 \left(n + m\right)\right)$ operations and $\Theta\left(m \log\left(n + m\right)\right)$ comparisons, where m is the size of the iterable and n is the size of the list initially.

sortedlist¶

Table of contents

blist

heapdict

winreg_unicode

ion-sampler

Navigation

sortedlist¶

Table of contents

blist

heapdict

winreg_unicode

ion-sampler

Quick search

Navigation