Provides general-purpose maps with support to prefix queries.

This module defines the following interfaces:

TernaryTreeMap is an abstract supertype for the following concrete implementations:

A ternary search tree, also known as a lexicographic search tree, is a kind of prefix tree whose nodes contain key elements, rather than complete keys.

The figure below shows a ternary search tree whose keys are sequences of characteres. Each node contain one element (a character) of a key. The keys in this tree are the words “as”, “at”, “bat”, “bats”, “bog”, “boy”, “caste”, “cats”, “day”, “dogs”, “donut”, and “door”. Squares denote terminal nodes. A terminal node contains the last element of a key. It also contains the item (not shown) associated with the key.

Ternary search tree image

For a very short, formal and precise definition of ternary search tree, see pages 674-676 of Sleator and Tarjan's paper “Self-Adjusting Binary Search Trees”, available here, from which the image above was taken. The relevant part is in section 6, “Two Applications of Splaying”, starting at the bottom of page 674 and going up to the first paragraph of page 676. (Sleator and Tarjan do not mention “ternary search trees”, they use the term “lexicographic search tree”.) For a longer discussion, see Bentley and Sedgewick's paper “Fast Algorithms for Sorting and Searching Strings”, or their article “Ternary Search Trees” in Dr. Dobb's.

A ternary splay tree, also known as a lexicographic splay tree, is a self-adjusting form of ternary search tree. Ternary splay trees are an extension of Sleator and Tarjan's plain (binary) splay trees, and were first presented in the same (aforementioned) paper that developed and analyzed splay trees. Both varieties of splay trees use the same restructuring heuristic and have operations with similar amortized time bounds.

By: Francisco Reverbel
Packages
herd.prefixmap

General-purpose maps with support to prefix queries.

Dependencies
ceylon.collection1.2.0

General-purpose maps with support to prefix queries.

By: Francisco Reverbel
Interfaces
PrefixMapshared PrefixMap<KeyElement,out Item>
given KeyElement satisfies Comparable<KeyElement>

A SortedMap whose keys are sequences of Comparable elements. PrefixMap supports the following prefix queries:

  • Does the map contain some Entry whose key has a given prefix?
  • Retrieve all the keys of the map that have a given prefix.
  • Retrieve all the entries in the map whose keys have a given prefix.
TernaryTreeMapshared TernaryTreeMap<KeyElement,Item>
given KeyElement satisfies Comparable<KeyElement>

A mutable PrefixMap backed by a ternary search tree whose keys are sequences of Comparable elements. Map entries are mantained in lexicographic order of keys, from the smallest to the largest key. The lexicographic ordering of keys relies on KeyElement comparisons performed by a formal compare function. The TernaryTreeMap implementations in this package provide a default compare function based on the “natural” comparison of key elements. (The default function merely delegates its task to the KeyElements themselves, which are Comparable). Moreover, these TernaryTreeMap implementations also accept client-defined comparison functions, for example to specify a character ordering that groups together uppercase and lowercase letters.

TernaryTreeMap is an abstract supertype for the concrete ternary tree map implementations TernarySearchTreeMap and TernarySplayTreeMap. In order to satisfy the TernaryTreeMap interface, a concrete class must provide actual implementations for the formal attributes TernaryTreeMap.rootNode and TernaryTreeMap.compare, as well as for the formal methods TernaryTreeMap.search(), put, remove, TernaryTreeMap.createAnotherMap(), clone, equals, and hash.

Classes
TernarySearchTreeMapshared TernarySearchTreeMap<KeyElement,Item>
given KeyElement satisfies Comparable<KeyElement>

A mutable PrefixMap implemented by a ternary search tree whose keys are sequences of Comparable elements. Map entries are mantained in lexicographic order of keys, from the smallest to the largest key. The lexicographic ordering of keys relies on comparisons of KeyElements, performed either by the method compare of the interface Comparable or by a comparator function specified when the map is created.

Ternary search trees are also known as lexicographic search trees. For information on such trees, see the documentation of module herd.prefixmap.

TernarySplayTreeMapshared TernarySplayTreeMap<KeyElement,Item>
given KeyElement satisfies Comparable<KeyElement>

A mutable PrefixMap implemented by a ternary splay tree whose keys are sequences of Comparable elements. Map entries are mantained in lexicographic order of keys, from the smallest to the largest key. The lexicographic ordering of keys relies on comparisons of KeyElements, performed either by the method compare of the interface Comparable or by a comparator function specified when the map is created.

Ternary splay trees are also known as lexicographic splay trees. For information on such trees, see the documentation of module herd.prefixmap.