Note

This is an old version of the documentation. See http://docs.astropy.org/en/stable for the latest version.

BST¶

class astropy.table.BST(data, row_index, unique=False)[source] [edit on github]

Bases: object

A basic binary search tree in pure Python, used as an engine for indexing.

Parameters: data : Table Sorted columns of the original table row_index : Column object Row numbers corresponding to data columns unique : bool (defaults to False) Whether the values of the index must be unique

Attributes Summary

 height Return the BST height.

Methods Summary

 add(key[, data]) Add a key, data pair. find(key) Return all data values corresponding to a given key. find_node(key) Find the node associated with the given key. is_valid() Returns whether this is a valid BST. items() Return BST items in order as (key, data) pairs. range(lower, upper[, bounds]) Return all nodes with keys in the given range. range_nodes(lower, upper[, bounds]) Return nodes in the given range. remove(key[, data]) Remove data corresponding to the given key. replace_rows(row_map) Replace all rows with the values they map to in the given dictionary. same_prefix(val) Assuming the given value has smaller length than keys, return nodes whose keys have this value as a prefix. shift_left(row) Decrement all rows larger than the given row. shift_right(row) Increment all rows greater than or equal to the given row. sort() Make row order align with key order. sorted_data() Return BST rows sorted by key values. traverse([order]) Return nodes of the BST in the given order.

Attributes Documentation

height

Return the BST height.

Methods Documentation

add(key, data=None)[source] [edit on github]

find(key)[source] [edit on github]

Return all data values corresponding to a given key.

Parameters: key : tuple Input key data_vals : list List of rows corresponding to the input key
find_node(key)[source] [edit on github]

Find the node associated with the given key.

is_valid()[source] [edit on github]

Returns whether this is a valid BST.

items()[source] [edit on github]

Return BST items in order as (key, data) pairs.

range(lower, upper, bounds=(True, True))[source] [edit on github]

Return all nodes with keys in the given range.

Parameters: lower : tuple Lower bound upper : tuple Upper bound bounds : tuple (x, y) of bools Indicates whether the search should be inclusive or exclusive with respect to the endpoints. The first argument x corresponds to an inclusive lower bound, and the second argument y to an inclusive upper bound.
range_nodes(lower, upper, bounds=(True, True))[source] [edit on github]

Return nodes in the given range.

remove(key, data=None)[source] [edit on github]

Remove data corresponding to the given key.

Parameters: key : tuple The key to remove data : int or None If None, remove the node corresponding to the given key. If not None, remove only the given data value from the node. successful : bool True if removal was successful, false otherwise
replace_rows(row_map)[source] [edit on github]

Replace all rows with the values they map to in the given dictionary. Any rows not present as keys in the dictionary will have their nodes deleted.

Parameters: row_map : dict Mapping of row numbers to new row numbers
same_prefix(val)[source] [edit on github]

Assuming the given value has smaller length than keys, return nodes whose keys have this value as a prefix.

shift_left(row)[source] [edit on github]

Decrement all rows larger than the given row.

shift_right(row)[source] [edit on github]

Increment all rows greater than or equal to the given row.

sort()[source] [edit on github]

Make row order align with key order.

sorted_data()[source] [edit on github]

Return BST rows sorted by key values.

traverse(order=u'inorder')[source] [edit on github]

Return nodes of the BST in the given order.

Parameters: order : str The order in which to recursively search the BST. Possible values are: “preorder”: current node, left subtree, right subtree “inorder”: left subtree, current node, right subtree “postorder”: left subtree, right subtree, current node