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.

By: Francisco Reverbel
See also PrefixMap, Map, Entry, Comparable, TernaryTreeMap
  • TernarySearchTreeMap
    • Basic
      • Identifiable
      • Object
        • Anything
    • TernaryTreeMap
      • MutableMap
        • Map
          • Collection
            • Iterable
              • Category
          • Correspondence
        • MapMutator
          • Map
            • Collection
              • Iterable
                • Category
            • Correspondence
      • PrefixMap
        • Ranged
          • Iterable
            • Category
        • SortedMap
          • Map
            • Collection
              • Iterable
                • Category
            • Correspondence
          • Ranged
            • Iterable
              • Category

no subtypes hierarchy

TernarySearchTreeMapshared TernarySearchTreeMap({<PrefixMap.Key->Item>*} entries = ..., Comparison(KeyElement, KeyElement) compare = ...)

Create a new TernarySearchTreeMap with the given entries and the comparator function specified by the parameter compare.

  • entries = {}

    The initial entries in the map. If entries is absent, an empty map will be created.

  • compare = (KeyElement x, KeyElement y) => x.compare(y)

    A function used to compare key elements. If compare is absent, the comparator method of interface Comparable will be used to compare KeyElements.

copyshared copy(TernarySearchTreeMap<KeyElement,Item> sourceMap)

Create a new TernarySearchTreeMap with the same entries and comparator function as the given TernarySearchTreeMap.

compareshared actual Comparison(KeyElement, KeyElement) compare

A comparator function used to sort the entries.

hashshared actual Integer hash

The hash value of the value, which allows the value to be an element of a hash-based set or key of a hash-based map. Implementations must respect the constraint that:

  • if x==y then x.hash==y.hash.

Therefore, a class which refines equals must also refine hash.

Because the Integer type is platform-dependent a compiler for a given platform is permitted to further manipulate the calculated hash for an object, and the resulting hash may differ between platforms.

Refines Identifiable.hash (hash) ultimately refines Object.hash (hash)
rootNodeshared actual Object? rootNode

An object that is the root node of the tree, or null in the case of an empty tree. This attribute is not intended for use by client code. Its purpose is merely to serve as a “hook” through which methods actually defined by interface TernaryTreeMap have access to the root object provided by a concrete TernaryTreeMap implementation.

In order to check if this map is empty, client code should use the attribute TernaryTreeMap.empty instead.

Inherited Attributes
Attributes inherited from: Object
hash, string
Attributes inherited from: Collection<Element>
empty, permutations, string
Attributes inherited from: Correspondence<Key,Item>
Attributes inherited from: Iterable<Element,Absent>
coalesced, cycled, distinct, empty, exceptLast, first, indexed, last, paired, rest, size, string
Attributes inherited from: Map<Key,Item>
coalescedMap, distinct, hash, items, keys
Attributes inherited from: TernaryTreeMap<KeyElement,Item>
clearshared actual void clear()

Remove every entry from this map, leaving an empty map with no entries.

Refines MapMutator.clear (clear)
cloneshared actual TernarySearchTreeMap<KeyElement,Item> clone()

A shallow copy of this collection, that is, a collection with identical elements which does not change if this collection changes. If this collection is immutable, it is acceptable to return a reference to this collection. If this collection is mutable, a newly instantiated collection must be returned.

Refines MutableMap.clone (clone) ultimately refines Collection.clone (clone)
createAnotherMapshared actual TernarySearchTreeMap<KeyElement,Item> createAnotherMap({<PrefixMap.Key->Item>*} entries, Comparison(KeyElement, KeyElement) compare)

Factory method that creates another TernaryTreeMap with the given entries and the comparator function specified by the parameter compare.

equalsshared actual Boolean equals(Object that)

Determine if two values are equal. Implementations should respect the constraints that:

  • if x===y then x==y (reflexivity),
  • if x==y then y==x (symmetry),
  • if x==y and y==z then x==z (transitivity).

Furthermore it is recommended that implementations ensure that if x==y then x and y have the same concrete class.

A class which explicitly refines equals() is said to support value equality, and the equality operator == is considered much more meaningful for such classes than for a class which simply inherits the default implementation of identity equality from Identifiable.

Refines Identifiable.equals (equals) ultimately refines Object.equals (equals)
putshared actual Item? put(PrefixMap.Key key, Item item)

Add an entry to this map, overwriting any existing entry for the given key, and returning the previous value associated with the given key, if any, or null if no existing entry was overwritten.

Refines MutableMap.put (put) ultimately refines MapMutator.put (put)
removeshared actual Item? remove(PrefixMap.Key key)

Remove the entry associated with the given key, if any, from this map, returning the value no longer associated with the given key, if any, or null if there was no entry associated with the given key.

Refines MutableMap.remove (remove) ultimately refines MapMutator.remove (remove)
shared actual Object? search(PrefixMap.Key key)

Searches for a key in this ternary tree. This method is not intended for use by client code. Its purpose is merely to serve as a “hook” through which methods actually defined by interface TernaryTreeMap have access to search functionality provided by a concrete TernaryTreeMap implementation.

A call to TernaryTreeMap.search() returns either the last node of a middle path with the sequence of elements of the given key, or null if there is no such middle path. A node returned by search is not necessarily terminal. If tree.search(key) returns a terminal node, then key is actually present in the tree, and the returned node contains the item associated with key. If tree.search(key) returns a non-terminal node, key appears only as a prefix of some key in the tree, and there is no item associated with key.

In order to search for a key in this map, client code should use the method lookup instead.

Inherited Methods
Methods inherited from: Object
Methods inherited from: Category<Element>
contains, containsAny, containsEvery
Methods inherited from: Collection<Element>
clone, contains
Methods inherited from: Correspondence<Key,Item>
defines, definesAny, definesEvery, get, getAll
Methods inherited from: Iterable<Element,Absent>
any, by, chain, collect, contains, count, defaultNullElements, each, every, filter, find, findLast, flatMap, fold, follow, frequencies, getFromFirst, group, indexes, interpose, iterator, locate, locateLast, locations, longerThan, map, max, narrow, partition, product, reduce, repeat, scan, select, sequence, shorterThan, skip, skipWhile, sort, spread, summarize, tabulate, take, takeWhile
Methods inherited from: Map<Key,Item>
clone, contains, defaultNullElements, defaultNullItems, defines, equals, filterKeys, get, getOrDefault, inverse, mapItems, patch
Methods inherited from: MapMutator<Key,Item>
clear, put, putAll, remove, removeAll, removeEntry, replaceEntry
Methods inherited from: MutableMap<Key,Item>
clone, put, remove
Methods inherited from: PrefixMap<KeyElement,Item>
Methods inherited from: Ranged<Index,Element,Subrange>
measure, span, spanFrom, spanTo
Methods inherited from: SortedMap<Key,Item>
ascendingEntries, descendingEntries, higherEntries, lowerEntries
Methods inherited from: TernaryTreeMap<KeyElement,Item>