Tree, Dictionary and Set Concepts

« 15-210 C++ Library Documentation

Usage: #include "bst.h"

The library provides binary search trees, sorted dictionaries and sorted sets, in two layers. A binary search tree is the tree from lecture: you take it apart at its root using expose and build new trees using join_mid. A dictionary or set is built on a tree, but you use it through operations on keys and values, such as find, insert and set_union.

Each layer is specified by concepts, the C++ way of specifying an abstract data type, as the sequence concept is for sequences. Code written against a concept, rather than a particular type, is generic: it works with any type that satisfies the concept. The library's types are treaps, and the treap page describes each of their operations with its cost. This page describes the concepts and how to write generic code with them.

The library defines five concepts:

Binary Search Trees

A tree holds key-value pairs. Its keys are distinct and increase from left to right, in the order given by <. A type Tree satisfies the par::bst concept if it names its key and value types as Tree::key_type and Tree::value_type, its keys are totally ordered, comparable with ==, !=, <, <=, > and >=, and it has the four operations from lecture. With K and V for the key and value types: 

auto size() const -> std::size_t;                                      // the number of elements
auto expose(const Tree& t) -> std::optional<par::node_view<Tree>>;     // view a tree's root

static auto empty() -> Tree;                                           // the empty tree
auto join_mid(Tree L, const K& k, const V& v, Tree R) -> Tree;         // create a new tree

par::key_t<Tree> and par::value_t<Tree> also name the key and value types. The treap page describes empty, size, expose and join_mid in detail.

expose is the primary mechanism for writing generic code over BSTs. It returns a view of the root element: an empty optional for the empty tree, and otherwise a node_view of the root's key, value and subtrees: 

template<typename Tree>
struct node_view {
  const Tree& left;
  const par::key_t<Tree>& key;
  const par::value_t<Tree>& value;
  const Tree& right;
};

The view refers into the tree instead of copying it, so exposing a tree costs nothing, but the view is only valid while the tree is.

join_mid(L, k, v, R) works the other way, building one tree from a left subtree, a key-value pair and a right subtree. It requires every key of L to be less than k, and k to be less than every key of R. This is where a balanced tree does its balancing, so the result holds exactly those pairs but need not have k at its root.

Every other tree algorithm, from searching to splitting to taking a union, can be written with these four operations. The library provides two of them generically for every tree, as free functions: split and join. 

template<par::bst Tree>
auto join(const Tree& L, const Tree& R) -> Tree

template<par::bst Tree>
auto split(const Tree& t, const par::key_t<Tree>& k) -> std::tuple<Tree, std::optional<par::value_t<Tree>>, Tree>

Generic Tree Code

We will typically write generic tree code as a function or class template whose type parameter must satisfy par::bst: 

template<par::bst Tree>
auto find(const Tree& t, const par::key_t<Tree>& k) -> std::optional<par::value_t<Tree>>;

A constrained template is very similar to constrained auto that we used frequently when writing sequence algorithms (recall f(const sequence auto& S) as a function parameter). So, the above code is (almost) equivalent to writing 

auto find(const par::bst auto& t, const auto& k);

except that we give an explicit name, Tree, to the type parameter. This is useful when writing generic tree code so that we can write Tree::empty(), par::key_t<Tree>, and par::value_t<Tree> which require us to have a name to refer to.

Technically, if you really prefer constrained auto, you could also write 

auto find(const par::bst auto& t, const par::key_t<decltype(t)>& k) -> std::optional<par::value_t<decltype(t)>>;

making use of the decltype keyword, which gives the type of its argument, but this is far less nice to write, hence why we prefer using an explicit constrained template.

A function or class template written against par::bst should use only the four operations promised by the concept and the generic split and join, so that it works with any tree implementation. The usual shape is a recursion that exposes the tree, handles the empty and non-empty cases, and then recurs on the left or right subtree, or both. 

// The value at k in t, or nothing if k is not in t
template<par::bst Tree>
auto find(const Tree& t, const par::key_t<Tree>& k) -> std::optional<par::value_t<Tree>> {
  if (auto e = expose(t)) {
    auto [left, key, value, right] = e.value();
    if (k < key) return find(left, k);
    if (key < k) return find(right, k);
    return value;
  }
  return std::nullopt;
}

// t with k mapped to v, replacing any value k already had
template<par::bst Tree>
auto insert(const Tree& t, const par::key_t<Tree>& k, const par::value_t<Tree>& v) -> Tree {
  if (auto e = expose(t)) {
    auto [left, key, value, right] = e.value();
    if (k < key) return join_mid(insert(left, k, v), key, value, right);
    if (key < k) return join_mid(left, key, value, insert(right, k, v));
    return join_mid(left, k, v, right);
  }
  return join_mid(Tree::empty(), k, v, Tree::empty());
}

find only reads the tree, following one path down from the root. insert follows the same path, then rebuilds it with join_mid on the way back up. The new key always goes into the subtree where it belongs, so every join_mid gets the ordering it requires, and each one gives the tree a chance to rebalance. Both work on the library's tree, par::treap: 

using tree = par::treap<int, std::string>;

auto leaf = [](int k, std::string v) { return join_mid(tree::empty(), k, v, tree::empty()); };
tree t = join_mid(leaf(1, "a"), 2, "b", leaf(3, "c"));

tree t2 = insert(t, 4, "d");
auto four = find(t2, 4);    // an optional holding "d"

Dictionaries and Sets

A dictionary maps keys to values, and a set is a collection of keys. Their keys are sorted by <, which gives meaning to operations such as first, next, split and get_range. Like everything in the library, dictionaries and sets are persistent: an operation such as insert returns a new dictionary and leaves its argument unchanged.

A type Dict satisfies the par::sorted_dict concept if it names its key and value types as Dict::key_type and Dict::value_type, its keys are totally ordered as a tree's are, and it has these operations. An operation on one dictionary is a member function, one on two dictionaries is a free function, and the operations that make a dictionary from scratch are static: 

// Making a dictionary
static auto empty() -> Dict;
static auto singleton(K k, V v) -> Dict;
static auto from_sequence(const sequence auto& pairs) -> Dict;

auto size() const -> std::size_t;

// Converting into a sequence
auto to_sequence() const -> par::array_sequence<std::pair<K, V>>;

// Searching
auto find(const K& k) const -> std::optional<V>;
auto first() const -> std::optional<std::pair<const K&, const V&>>;
auto last() const -> std::optional<std::pair<const K&, const V&>>;
auto prev(const K& k) const -> std::optional<std::pair<const K&, const V&>>;
auto next(const K& k) const -> std::optional<std::pair<const K&, const V&>>;

// Persistent updates
auto insert(K k, V v) const -> Dict;
auto remove(const K& k) const -> Dict;
auto filter(std::predicate<K, V> auto&& p) const -> Dict;

// Order statistics operations
auto rank(const K& k) const -> std::size_t;
auto select(std::size_t i) const -> std::optional<std::pair<const K&, const V&>>;

// Splitting and joining
auto split(const K& k) const -> std::tuple<Dict, std::optional<V>, Dict>;
auto get_range(const K& k1, const K& k2) const -> Dict;
auto join(const Dict& a, const Dict& b) -> Dict;

// Set-theoretic operations
auto set_union(const Dict& a, const Dict& b) -> Dict;
auto set_intersection(const Dict& a, const Dict& b) -> Dict;
auto set_difference(const Dict& a, const Dict& b) -> Dict;

The treap page describes each operation, from making a dictionary to combining two. A few rules hold for every dictionary: in set_union and set_intersection, a key in both keeps the left argument's value; from_sequence keeps the first value of a repeated key; get_range(k1, k2) includes k1 but not k2; and ranks start at zero.

A set, which satisfies par::sorted_set, has the same operations without values. It has contains in place of find, its keys come back as copies rather than references, and its split reports whether the key was present. With Set for the set's type: 

// Making a set
static auto empty() -> Set;
static auto singleton(K k) -> Set;
static auto from_sequence(const sequence<K> auto& keys) -> Set;

auto size() const -> std::size_t;

// Converting into a sequence
auto to_sequence() const -> par::array_sequence<K>;

// Searching
auto contains(const K& k) const -> bool;
auto first() const -> std::optional<K>;
auto last() const -> std::optional<K>;
auto prev(const K& k) const -> std::optional<K>;
auto next(const K& k) const -> std::optional<K>;

// Persistent updates
auto insert(K k) const -> Set;
auto remove(const K& k) const -> Set;
auto filter(std::predicate<K> auto&& p) const -> Set;

// Order statistics operations
auto rank(const K& k) const -> std::size_t;
auto select(std::size_t i) const -> std::optional<K>;

// Splitting and joining
auto split(const K& k) const -> std::tuple<Set, bool, Set>;
auto get_range(const K& k1, const K& k2) const -> Set;
auto join(const Set& a, const Set& b) -> Set;

// Set-theoretic operations
auto set_union(const Set& a, const Set& b) -> Set;
auto set_intersection(const Set& a, const Set& b) -> Set;
auto set_difference(const Set& a, const Set& b) -> Set;

Generic Dictionary and Set Code

Generic dictionary code is written the same way, as a template whose type parameter must satisfy par::sorted_dict. It can use the concept's operations and nothing else, so it works with whichever dictionary it is given.

For example, a histogram counts how many times each key has occurred. It can be represented as a dictionary that maps each key to its count. The class template below takes the dictionary type as its parameter, as an SML functor takes a structure, and its static members are the histogram's three operations: empty makes a histogram in which nothing has occurred, add records one more occurrence of a key, and count returns how many times a key has occurred, which is 0 if it never has: 

// A persistent histogram type
// - add returns a new histogram with the updated count
template<par::sorted_dict Dict>
class histogram {
  Dict hist{};
  
  histogram(Dict h) : hist(std::move(h)) { }
  
 public:
  histogram() = default;
 
  // add one more occurrence of k
  auto add(const par::key_t<Dict>& k) const -> histogram {
    if (auto freq = hist.find(k)) return {hist.insert(k, freq.value() + 1)};
    return {hist.insert(k, 1)};
  }

  // Return the number of times k has occurred
  auto count(const par::key_t<Dict>& k) const -> int {
    if (auto freq = hist.find(k)) return freq.value();
    return 0;
  }
};

Since insert replaces the value of a key that is already present, add looks up the old count first and then inserts one more. Given a dictionary from strings to counts, the histogram counts words: 

using word_histogram = histogram<par::treap_dict<std::string, int>>;
word_histogram empty{};

auto h1 = empty.add("pear");
auto h2 = h1.add("apple");
auto h3 = h2.add("pear");

int pears = h3.count("pear");      // 2
int earlier = h1.count("pear");    // 1, since the type is persistent

Generic set code takes a type that satisfies par::sorted_set instead. These two tests, whether one set is a subset of another and whether two sets have no keys in common, work with any set: 

// Whether every key of a is also in b
template<par::sorted_set Set>
auto is_subset(const Set& a, const Set& b) -> bool {
  return set_difference(a, b).size() == 0;
}

// Whether a and b have no keys in common
template<par::sorted_set Set>
auto is_disjoint(const Set& a, const Set& b) -> bool {
  return set_intersection(a, b).size() == 0;
}

Augmented Trees and Dictionaries

An augmented tree or dictionary also keeps all of its values combined into one. It satisfies par::aug_bst or par::aug_sorted_dict, which require everything par::bst or par::sorted_dict does, plus one additional function: 

// Returns the reduction of every value in the structure with respect to
// the associative binary function Combine with the given identity value
auto reduced_val() const -> augmented_value_type;

Given a par::aug_bst<K,V,Combine,Identity> or par::aug_sorted_dict<K,V,Combine,Identity>, the reduced_val function returns the values combined with Combine in increasing order of their keys, or Identity if there are none. Its result has type augmented_value_type, which is usually the value type itself. It takes constant time, so together with get_range it gives the combined value of any range of keys in logarithmic time. The treap page's augmentation section shows how to make augmented trees and dictionaries, with examples of three different ways to combine values.

The Concepts' Code

Optional: If you're curious, you can see the code for the concepts below, but you are not required to understand it.
Click to view the bst, sorted_dict and sorted_set concepts 
template<typename T, typename K = void, typename V = void>
concept bst =
  requires { typename T::key_type; typename T::value_type; } &&
  std::totally_ordered<key_t<T>> &&
  (std::same_as<K, void> || std::same_as<key_t<T>, K>) &&
  (std::same_as<V, void> || std::same_as<value_t<T>, V>) &&
  requires(const T& t, const key_t<T>& k, const value_t<T>& v) {
    { T::empty() }           -> std::same_as<T>;
    { t.size() }             -> std::convertible_to<std::size_t>;
    { expose(t) }            -> std::same_as<std::optional<node_view<T>>>;
    { join_mid(t, k, v, t) } -> std::same_as<T>;   // a balanced tree of L, (k, v), R; keys of L < k < keys of R
  };

template<typename D, typename K = void, typename V = void>
concept sorted_dict =
  requires { typename D::key_type; typename D::value_type; } &&
  std::totally_ordered<key_t<D>> &&
  (std::same_as<K, void> || std::same_as<key_t<D>, K>) &&
  (std::same_as<V, void> || std::same_as<value_t<D>, V>) &&
  // construction and bulk conversion
  requires(const D& d, const key_t<D>& k, value_t<D> v, const array_sequence<std::pair<key_t<D>, value_t<D>>>& pairs) {
    { D::empty() }              -> std::same_as<D>;
    { D::singleton(k, v) }      -> std::same_as<D>;
    { D::from_sequence(pairs) } -> std::same_as<D>;
    { d.to_sequence() }         -> std::same_as<array_sequence<std::pair<key_t<D>, value_t<D>>>>;
  } &&
  // one key
  requires(const D& d, const key_t<D>& k, value_t<D> v) {
    { d.size() }       -> std::convertible_to<std::size_t>;
    { d.find(k) }      -> std::same_as<std::optional<value_t<D>>>;
    { d.insert(k, v) } -> std::same_as<D>;
    { d.remove(k) }    -> std::same_as<D>;
  } &&
  // two dictionaries
  requires(const D& a, const D& b) {
    { set_union(a, b) }        -> std::same_as<D>;
    { set_intersection(a, b) } -> std::same_as<D>;
    { set_difference(a, b) }   -> std::same_as<D>;
    { join(a, b) }             -> std::same_as<D>;
  } &&
  // filtering
  requires(const D& d, bool (&p)(const key_t<D>&, const value_t<D>&)) {
    { d.filter(p) } -> std::same_as<D>;
  } &&
  // order
  requires(const D& d, const key_t<D>& k) {
    { d.first() }         -> std::same_as<std::optional<std::pair<const key_t<D>&, const value_t<D>&>>>;
    { d.last() }          -> std::same_as<std::optional<std::pair<const key_t<D>&, const value_t<D>&>>>;
    { d.prev(k) }         -> std::same_as<std::optional<std::pair<const key_t<D>&, const value_t<D>&>>>;
    { d.next(k) }         -> std::same_as<std::optional<std::pair<const key_t<D>&, const value_t<D>&>>>;
    { d.split(k) }        -> std::same_as<std::tuple<D, std::optional<value_t<D>>, D>>;
    { d.get_range(k, k) } -> std::same_as<D>;
  } &&
  // ranks
  requires(const D& d, const key_t<D>& k, std::size_t i) {
    { d.rank(k) }   -> std::same_as<std::size_t>;
    { d.select(i) } -> std::same_as<std::optional<std::pair<const key_t<D>&, const value_t<D>&>>>;
  };

template<typename S, typename K = void>
concept sorted_set =
  requires { typename S::key_type; } &&
  std::totally_ordered<key_t<S>> &&
  (std::same_as<K, void> || std::same_as<key_t<S>, K>) &&
  // construction and bulk conversion
  requires(const S& s, const key_t<S>& k, const array_sequence<key_t<S>>& keys) {
    { S::empty() }             -> std::same_as<S>;
    { S::singleton(k) }        -> std::same_as<S>;
    { S::from_sequence(keys) } -> std::same_as<S>;
    { s.to_sequence() }        -> std::same_as<array_sequence<key_t<S>>>;
  } &&
  // one key
  requires(const S& s, const key_t<S>& k) {
    { s.size() }      -> std::convertible_to<std::size_t>;
    { s.contains(k) } -> std::same_as<bool>;
    { s.insert(k) }   -> std::same_as<S>;
    { s.remove(k) }   -> std::same_as<S>;
  } &&
  // two sets
  requires(const S& a, const S& b) {
    { set_union(a, b) }        -> std::same_as<S>;
    { set_intersection(a, b) } -> std::same_as<S>;
    { set_difference(a, b) }   -> std::same_as<S>;
    { join(a, b) }             -> std::same_as<S>;
  } &&
  // filtering
  requires(const S& s, bool (&p)(const key_t<S>&)) {
    { s.filter(p) } -> std::same_as<S>;
  } &&
  // order
  requires(const S& s, const key_t<S>& k) {
    { s.first() }         -> std::same_as<std::optional<key_t<S>>>;
    { s.last() }          -> std::same_as<std::optional<key_t<S>>>;
    { s.prev(k) }         -> std::same_as<std::optional<key_t<S>>>;
    { s.next(k) }         -> std::same_as<std::optional<key_t<S>>>;
    { s.split(k) }        -> std::same_as<std::tuple<S, bool, S>>;
    { s.get_range(k, k) } -> std::same_as<S>;
  } &&
  // ranks
  requires(const S& s, const key_t<S>& k, std::size_t i) {
    { s.rank(k) }   -> std::same_as<std::size_t>;
    { s.select(i) } -> std::same_as<std::optional<key_t<S>>>;
  };
Click to view the augmented concepts, aug_bst and aug_sorted_dict

They refine par::bst and par::sorted_dict with the requirements in detail::augmented. 

namespace detail {

struct unspecified {};

// An augmentation, identified by its three policies.
template<auto Combine, auto Identity, auto Lift> struct augmentation {};

// T's values form a monoid under combine and identity, mapped into augmented_value_type by lift,
// and reduced_val is the reduction of the whole of T. Given policies pin the augmentation.
template<typename T, auto Combine, auto Identity, auto Lift>
concept augmented =
  requires { typename T::augmented_value_type; } &&
  requires(const T& t, const typename T::augmented_value_type& a, const value_t<T>& v) {
    { t.reduced_val() }   -> std::same_as<typename T::augmented_value_type>;
    { T::combine(a, a) } -> std::convertible_to<typename T::augmented_value_type>;
    { T::identity }      -> std::convertible_to<typename T::augmented_value_type>;
    { T::lift(v) }       -> std::convertible_to<typename T::augmented_value_type>;
  } &&
  (std::same_as<decltype(Combine), unspecified> ||
   std::same_as<augmentation<T::combine, T::identity, T::lift>, augmentation<Combine, Identity, Lift>>);

}  // namespace detail

template<typename T, typename K = void, typename V = void,
         auto Combine = detail::unspecified{}, auto Identity = detail::unspecified{}, auto Lift = std::identity{}>
concept aug_bst = bst<T, K, V> && detail::augmented<T, Combine, Identity, Lift>;

template<typename D, typename K = void, typename V = void,
         auto Combine = detail::unspecified{}, auto Identity = detail::unspecified{}, auto Lift = std::identity{}>
concept aug_sorted_dict = sorted_dict<D, K, V> && detail::augmented<D, Combine, Identity, Lift>;