SortedCollection

digraph InheritanceGraph { graph [bgcolor=transparent, color=lightsteelblue2, fontname=Arial, fontsize=10, outputorder=edgesfirst, overlap=prism, penwidth=2, rankdir=LR, splines=spline, style="dashed, rounded", truecolor=true]; node [colorscheme=pastel19, fontname=Arial, fontsize=10, height=0, penwidth=2, shape=box, style="filled, rounded", width=0]; edge [color=lightslategrey, penwidth=1]; subgraph "cluster_abjad.utilities" { graph [label="abjad.utilities"]; node [color=1]; "abjad.utilities.SortedCollection.SortedCollection" [URL="../api/abjad/utilities/SortedCollection.html#abjad.utilities.SortedCollection.SortedCollection", color=black, fontcolor=white, label="Sorted\nCollection", target=_top]; } subgraph cluster_builtins { graph [label=builtins]; node [color=2]; "builtins.object" [URL="https://docs.python.org/3.6/library/functions.html#object", label=object, target=_top]; } "builtins.object" -> "abjad.utilities.SortedCollection.SortedCollection"; }

class abjad.utilities.SortedCollection.SortedCollection(iterable=(), key=None)

Sorted collection.

Sequence sorted by a key function.

SortedCollection() is much easier to work with than using bisect() directly. It supports key functions like those use in sorted(), min(), and max(). The result of the key function call is saved so that keys can be searched efficiently.

Instead of returning an insertion-point which can be hard to interpret, the five find-methods return a specific item in the sequence. They can scan for exact matches, the last item less-than-or-equal to a key, or the first item greater-than-or-equal to a key.

Once found, an item’s ordinal position can be located with the index() method. New items can be added with the insert() and insert_right() methods. Old items can be deleted with the remove() method.

The usual sequence methods are provided to support indexing, slicing, length lookup, clearing, copying, forward and reverse iteration, contains checking, item counts, item removal, and a nice looking repr.

Finding and indexing are O(log n) operations while iteration and insertion are O(n). The initial sort is O(n log n).

The key function is stored in the ‘key’ attibute for easy introspection or so that you can assign a new key function (triggering an automatic re-sort).

In short, the class was designed to handle all of the common use cases for bisect but with a simpler API and support for key functions.

>>> from pprint import pprint
>>> from operator import itemgetter
>>> s = abjad.SortedCollection(key=itemgetter(2))
>>> for record in [
...         ('roger', 'young', 30),
...         ('angela', 'jones', 28),
...         ('bill', 'smith', 22),
...         ('david', 'thomas', 32)]:
...     s.insert(record)
... 
>>> pprint(list(s))         # show records sorted by age
[
('bill', 'smith', 22)
,
 
('angela', 'jones', 28)
,
 
('roger', 'young', 30)
,
 
('david', 'thomas', 32)
]
>>> s.find_le(29)           # find oldest person aged 29 or younger
('angela', 'jones', 28)
>>> s.find_lt(28)           # find oldest person under 28
('bill', 'smith', 22)
>>> s.find_gt(28)           # find youngest person over 28
('roger', 'young', 30)
>>> r = s.find_ge(32)       # find youngest person aged 32 or older
>>> s.index(r)              # get the index of their record
3
>>> s[3]                    # fetch the record at that index
('david', 'thomas', 32)
>>> s.key = itemgetter(0)   # now sort by first name
>>> pprint(list(s))
[
('angela', 'jones', 28)
,
 
('bill', 'smith', 22)
,
 
('david', 'thomas', 32)
,
 
('roger', 'young', 30)
]

Attributes Summary

__contains__ Is true when sorted collection contains item.
__getitem__ Gets item or slice identifier by argument.
__iter__ Iterates sorted collection.
__len__ Length of sorted collection.
__repr__ Interpreter reprsentation of sorted collection.
__reversed__ Reverses sorted collection.
clear Clears sorted collection.
copy Copies sorted collection.
count Returns number of occurrences of item.
find Returns first item with a key == k.
find_ge Returns first item with a key >= equal to k.
find_gt Returns first item with a key > k.
find_le Returns last item with a key <= k.
find_lt Returns last item with a key < k.
index Find the position of an item.
insert Inserts a new item.
insert_right Insert a new item.
key key function
remove Remove first occurence of item.

Special methods

__contains__(item)

Is true when sorted collection contains item.

Returns true or false.

__getitem__(argument)

Gets item or slice identifier by argument.

Returns item.

__iter__()

Iterates sorted collection.

Yields items.

__len__()

Length of sorted collection.

Defined equal to number of items in collection.

Returns nonnegatie integer.

__repr__()

Interpreter reprsentation of sorted collection.

Returns string.

__reversed__()

Reverses sorted collection.

Yields items.


Methods

clear()

Clears sorted collection.

Returns none.

copy()

Copies sorted collection.

Returns new sorted collection.

count(item)

Returns number of occurrences of item.

find(k)

Returns first item with a key == k.

Raises ValueError if not found.

find_ge(k)

Returns first item with a key >= equal to k.

Raises ValueError if not found.

find_gt(k)

Returns first item with a key > k.

Raises ValueError if not found.

find_le(k)

Returns last item with a key <= k.

Raises ValueError if not found.

find_lt(k)

Returns last item with a key < k.

Raises ValueError if not found.

index(item)

Find the position of an item.

Raises ValueError if not found.

insert(item)

Inserts a new item.

If equal keys are found, adds to the left.

insert_right(item)

Insert a new item.

If equal keys are found, add to the right.

remove(item)

Remove first occurence of item.

Raises ValueError if not found.


Read/write properties

key

key function