niemads package

NiemaDS is a Python library that implements useful non-standard data structures.

Module contents

class niemads.DisjointSet(initial=None)

Bases: object

DisjointSet class, implemented using the Up-Tree data structure for amortized O(1) find and union operations

add(x)

Add a new element x to this DisjointSet as a sentinel node

Args:

x: The element to insert

find(x)

Return the sentinel node of the element x. Implements path compression along the search

Args:

x: The element to find

Returns:

The sentinel node of x

remove(x)

Remove the element x from this DisjointSet

Args:

x: The element to remove

sets()

Return the sets of this DisjointSet

Returns:

list of set: The sets of this DisjointSet

union(x, y)

Union the sets containing x and y. Implements Union-By-Size

Args:

x: One of the two elements whose sets will be unioned y: One of the two elements whose sets will be unioned

class niemads.MultiwayTrie(initial=None)

Bases: object

MultiwayTrie class, implemented using TreeSwift

add(x)

Add a new element x to this MultiwayTrie

Args:

x: The element to insert

extend(xs)

Add each element of xs to this MultiwayTrie

Args:

xs: The elements to insert

iter_ascending()

Iterate over the elements of this MultiwayTrie in ascending order

iter_descending()

Iterate over the elements of this MultiwayTrie in descending order

static read_tree_newick(newick)

Read a tree from a Newick string or file

Args:

newick (str): Either a Newick string or the path to a Newick file (plain-text or gzipped)

Returns:

MultiwayTrie: The Multiway Trie represented by newick. If the Newick file has multiple trees (one per line), a list of Tree objects will be returned

remove(x)

Remove the element x from this MultiwayTrie

Args:

x: The element to remove

class niemads.RandomSet(initial=None)

Bases: object

RandomSet class, which is a set with random (rather than arbitrary) pop

add(x)

Add a new element x to this RandomSet

Args:

x: The element to insert

pop_random()

Randomly remove and return an element from this RandomSet

Returns:

A random element from this RandomSet

remove(x)

Remove the element x from this RandomSet

Args:

x: The element to remove

top_random()

Randomly return an element from this RandomSet

Returns:

A random element from this RandomSet