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)

Center a string within a given field width

py_treap.make_used(var)

Persuade linters that ‘var’ is used.

py_treap.pad_to(string, length)

Pad a string to a specified length

class py_treap.treap

Bases: object

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

check_heap_invariant()

Check the heap invariant

check_tree_invariant()

Check the tree invariant

depth()

Return the depth of the treap (tree)

detailed_inorder_traversal(visit)

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

Find the highest key in the treap

find_min()

Find the lowest key in the treap

find_node(key)

Return the node associated with key, not just its value

get_key(key)

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

inorder_traversal(visit)

Perform an inorder traversal of the treap

insert(key, value, priority=None)

Insert a node in the treap

items()

A macro for iterators - produces keys, values and items from almost the same code

iterator()

A macro for iterators - produces keys, values and items from almost the same code

iteritems()

A macro for iterators - produces keys, values and items from almost the same code

iterkeys()

A macro for iterators - produces keys, values and items from almost the same code

itervalues()

A macro for iterators - produces keys, values and items from almost the same code

keys()

A macro for iterators - produces keys, values and items from almost the same code

predecessor(node)

Find the predecessor of index in the treap

remove(key)

Remove a node from the treap

remove_max()

Remove the largest node in the treap

remove_min()

Remove the lowest node in the treap

reverse_iterator()

Iterate over the nodes of the treap in reverse order

class state_class(todo, node)

Bases: object

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

successor(node)

Find the successor of index in the treap

to_dot(file_=<_io.TextIOWrapper name='<stdout>' mode='w' encoding='ANSI_X3.4-1968'>)

Output this tree as a dot file

values()

A macro for iterators - produces keys, values and items from almost the same code

class py_treap.treap_node

Bases: object

Hold a single node of a treap

check_heap_invariant()

Check the heap invariant

check_invariants()

Check the tree and heap invariants

check_tree_invariant()

Check the tree invariant

detailed_inorder_traversal(visit, depth=0, from_left=0)

Do an inorder traversal - with lots of parameters

find_max_node()

Find the highest node in the treap

find_min_node()

Find the lowest node in the treap

find_node(key)

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

inorder_traversal(visit)

Do an inorder traversal - without lots of parameters

insert(node, key, value, priority)

Insert a node - just call the fast version

key

left

priority

pyx_insert(node, key, value, priority)

Insert a node - this is the fast version

pyx_remove(node, key)

Remove a node - this is the fast version

remove(node, key)

Remove a node - just call the fast version

remove_max(node)

Remove the highest node below us

remove_min(node)

Remove the lowest node below us

right

rotate_with_left_child(node)

This is a treap thing - rotate to rebalance

rotate_with_right_child(node)

This is a treap thing - rotate to rebalance

to_dot(initial=True, file_=<_io.TextIOWrapper name='<stdout>' mode='w' encoding='ANSI_X3.4-1968'>, visited=None)

Generate a dot file describing this tree

value