gst.py (plain text)

"""The gst module contains functions implementing the immutable general search
tree (GST) data abstraction for CS61A at UC Berkeley.

GSTs are (immutable) general search trees, an example of a tree structure
that is used for storing sorted data in a way to allow for quick searching
later.

One might notice that none of the doctests for either ADT actually "show" an
GST. This is because this ADT is meant to be treated as a black box: the
tests do not assume any specific implementation for GST.
"""


from itree import *


# General Search Trees Abstraction


empty_gst = None


def make_gst(keys, children=()):
    """Create a GST with data and children.

    It should be noted that nothing in the constructor or selectors actually
    force the GST to be a proper search tree, so in reality this makes just a
    simple tree with tuples as data.

    >>> g1 = make_gst((0, 2),
    ...               (empty_gst, make_gst((1,)), make_gst((4, 5, 6))))
    """
    return make_itree(keys, children)


def gst_keys(g):
    """Return the datum of GST g.

    >>> g1 = make_gst((0, 2),
    ...               (empty_gst, make_gst((1,)), make_gst((4, 5, 6))))
    >>> gst_keys(g1)
    (0, 2)
    """
    return itree_datum(g)


def gst_children(g):
    """Return the children of GST g.

    >>> g1 = make_gst((0, 2),
    ...               (empty_gst, make_gst((1,)), make_gst((4, 5, 6))))
    >>> gst_keys(gst_children(g1)[2])
    (4, 5, 6)
    """
    return itree_children(g)