py_treap module

Provides a treap module - specifically, the class that describes the overall treap, not the nodes.

A treap is a datastructure that’s kind of half way between a heap and a binary search tree

py_treap.center(string, field_use_width, field_avail_width)[source]

Center a string within a given field width.

py_treap.make_used(var)[source]

Persuade linters that ‘var’ is used.

py_treap.pad_to(string, length)[source]

Pad a string to a specified length.

class py_treap.treap[source]

Bases: object

The treap class - or rather, the non-node, treap-proper.

check_heap_invariant()[source]

Check the heap invariant.

check_tree_invariant()[source]

Check the tree invariant.

depth()[source]

Return the depth of the treap (tree).

detailed_inorder_traversal(visit)[source]

Perform an inorder traversal of the treap, passing a little more detail to the visit function at each step.

find(key)

Look up a node in the treap: return the value.

find_max()[source]

Find the highest key in the treap.

find_min()[source]

Find the lowest key in the treap.

find_node(key)[source]

Return the node associated with key, not just its value.

get_key(key)[source]

Look up a _key_ in the treap by key: return the key.

inorder_traversal(visit)[source]

Perform an inorder traversal of the treap.

insert(key, value, priority=None)

Insert a node in the treap.

items()

Produce keys, values and items from almost the same code - a macro since these are very similar.

iterator()

Produce keys, values and items from almost the same code - a macro since these are very similar.

iteritems()[source]

Produce keys, values and items from almost the same code - a macro since these are very similar.

iterkeys()[source]

Produce keys, values and items from almost the same code - a macro since these are very similar.

itervalues()[source]

Produce keys, values and items from almost the same code - a macro since these are very similar.

keys()

Produce keys, values and items from almost the same code - a macro since these are very similar.

predecessor(node)[source]

Find the predecessor of index in the treap.

remove(key)

Remove a node from the treap.

remove_max()[source]

Remove the largest node in the treap.

remove_min()[source]

Remove the lowest node in the treap.

reverse_iterator()[source]

Iterate over the nodes of the treap in reverse order.

class state_class(todo, node)[source]

Bases: object

A state class, used for iterating over the nodes in a treap nonrecursively.

successor(node)[source]

Find the successor of index in the treap.

to_dot(file_=<_io.TextIOWrapper name='<stdout>' mode='w' encoding='utf-8'>)[source]

Output this tree as a dot file.

values()

Produce keys, values and items from almost the same code - a macro since these are very similar.

class py_treap.treap_node[source]

Bases: object

Hold a single node of a treap.

check_heap_invariant()[source]

Check the heap invariant.

check_invariants()[source]

Check the tree and heap invariants.

check_tree_invariant()[source]

Check the tree invariant.

detailed_inorder_traversal(visit, depth=0, from_left=0)[source]

Do an inorder traversal - with lots of parameters.

find_max_node()[source]

Find the highest node in the treap.

find_min_node()[source]

Find the lowest node in the treap.

find_node(key)[source]

Look up a node in the treap: return the containing node.

inorder_traversal(visit)[source]

Do an inorder traversal - without lots of parameters.

insert(node, key, value, priority)[source]

Insert a node - just call the fast version.

key
left
priority
pyx_insert(node, key, value, priority)[source]

Insert a node - this is the fast version.

pyx_remove(node, key)[source]

Remove a node - this is the fast version.

remove(node, key)[source]

Remove a node - just call the fast version.

remove_max(node)[source]

Remove the highest node below us.

remove_min(node)[source]

Remove the lowest node below us.

right
rotate_with_left_child(node)[source]

Rotate left to rebalance - this is a treap thing.

rotate_with_right_child(node)[source]

Rotate right to rebalance - this is a treap thing.

to_dot(initial=True, file_=<_io.TextIOWrapper name='<stdout>' mode='w' encoding='utf-8'>, visited=None)[source]

Generate a dot file describing this tree.

value