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 rootNode and compare, as well as for the formal methods search(), put, remove, createAnotherMap(), clone, equals, and hash.

By: Francisco Reverbel
See also PrefixMap, Map, Entry, Comparable, TreeNode, TernarySearchTreeMap, TernarySplayTreeMap

no type hierarchy

  • 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
Attributes
compareshared formal Comparison(KeyElement, KeyElement) compare

A comparator function used to sort the key elements.

emptyshared actual default Boolean empty

Determines if this map is empty, that is, if it has no entries.

Refines Collection.empty (empty) ultimately refines Iterable.empty (empty)
firstshared actual <PrefixMap.Key->Item>? first

The first element returned by the iterator, if any, or null if this stream is empty. For a stream with an unstable iteration order, a different value might be produced each time first is evaluated.

Refines Iterable.first (first)
lastshared actual <PrefixMap.Key->Item>? last

The last element returned by the iterator, if any, or null if this stream is empty. In the case of an infinite stream, this operation never terminates; furthermore, this default implementation iterates all elements, which might be very expensive.

Refines Iterable.last (last)
rootNodeshared formal 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 empty instead.

sizeshared actual Integer size

The number of elements returned by the iterator of this stream, if the iterator terminates. In the case of an infinite stream, this operation never terminates.

Refines Iterable.size (size)
Inherited Attributes
Attributes inherited from: Object
hash, string
Attributes inherited from: Collection<Element>
empty, permutations, string
Attributes inherited from: Correspondence<Key,Item>
keys
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
Methods
ascendingEntriesshared actual {<PrefixMap.Key->Item>*} ascendingEntries(PrefixMap.Key from, PrefixMap.Key to)

The entries with keys larger than or equal to the first given value (from), and smaller than or equal to the second given value (to), sorted in ascending order.

This is a lazy operation, returning a view of the underlying sorted map.

Refines SortedMap.ascendingEntries (ascendingEntries)
compareKeysshared Comparison compareKeys(PrefixMap.Key key1, PrefixMap.Key key2)

Lexicographically compares two keys. Returns smaller if key1 < key2, equal if key1 == key2, and larger if key1 > key2.

createAnotherMapshared formal TernaryTreeMap<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.

Parameters:
  • entries = {}

    The initial entries in the new 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.

definesshared actual Boolean defines(Object key)

Determines if there is a value defined for the given key.

Refines Map.defines (defines) ultimately refines Correspondence.defines (defines)
descendingEntriesshared actual {<PrefixMap.Key->Item>*} descendingEntries(PrefixMap.Key from, PrefixMap.Key to)

The entries with keys smaller than or equal to the first given value (from), and larger than or equal to the second given value (to), sorted in descending order.

This is a lazy operation, returning a view of the underlying sorted map.

Refines SortedMap.descendingEntries (descendingEntries)
eagerIteratorshared Iterator<PrefixMap.Key->Item> eagerIterator()

An eager iterator for the entries in this ternary tree.

entriesWithPrefixshared actual {<PrefixMap.Key->Item>*} entriesWithPrefix(Object prefix)

Returns a stream with all the entries in this map whose keys have the given prefix.

getshared actual Item? get(Object key)

Returns the value defined for the given key, or null if there is no value defined for the given key.

Refines Map.get (get) ultimately refines Correspondence.get (get)
hasKeyWithPrefixshared actual Boolean hasKeyWithPrefix(Object prefix)

Returns true if this map has a key with the given prefix, or false otherwise.

higherEntriesshared actual {<PrefixMap.Key->Item>*} higherEntries(PrefixMap.Key key)

The entries with keys larger than or equal to the given key, sorted by key in ascending order.

This is a lazy operation, returning a view of the underlying sorted map.

Refines SortedMap.higherEntries (higherEntries)
iteratorshared actual Iterator<PrefixMap.Key->Item> iterator()

An iterator for the elements belonging to this stream.

Refines Iterable.iterator (iterator)
keysWithPrefixshared actual {PrefixMap.Key*} keysWithPrefix(Object prefix)

Returns a stream containing all the keys with the given prefix that are present in this map.

lowerEntriesshared actual {<PrefixMap.Key->Item>*} lowerEntries(PrefixMap.Key key)

The entries with keys smaller than or equal to the given key, sorted by key in descending order.

This is a lazy operation, returning a view of the underlying sorted map.

Refines SortedMap.lowerEntries (lowerEntries)
measureshared actual TernaryTreeMap<KeyElement,Item> measure(PrefixMap.Key from, Integer length)

Obtain a measure containing the mapped values starting from the given starting index (from), with the given length. If length<=0, the resulting measure is empty.

The measure should contain the given number (length) of elements of this stream, starting from the element at the given starting index (from), in the same order as they are produced by the iterator of the stream. In the case where the iterator would be exhausted before length elements are produced, the resulting measure contains only those elements which were produced before the iterator was exhausted, and the length of the measure is less then the given length.

When the given index does not belong to this ranged object, the behavior is implementation dependent.

Refines Ranged.measure (measure)
printNodesshared void printNodes(Integer paddedElementLength = 1, Integer paddedItemLength = ...)

Prints a series of lines to the standart output of the virtual machine process, with one line per node of this tree. Each line has the format

Node@<nnnnnnnn>: <element>, <item>, <left child>, <middle child>, <right child>, T

or the format

Node@<nnnnnnnn>: <element>, <item>, <left child>, <middle child>, <right child>
  • The field <nnnnnnnn> is the hash of the node, left padded with '_' characters to a minimum lenght of 10 characteres.
  • The field <element> is the string representation of the KeyElement in the node.
  • The field <item> is the string representation of the Item in the node, or <null> if there is no Item in the node.
  • The fields <left child>, <middle child>, and <right child> identify the corresponding child nodes. Each of these fields has the format Node@<nnnnnnnn> if the corresponding child node exists, otherwise it contains the text no left child (in the case of a missing left child), or the text no middle child (in the case of a missing middle child), or the text no right child (in the case of a missing right child).
  • Lines with the first format (with an ending 'T') represent terminal nodes, lines with the second format represent nonterminal nodes.

The example below shows a section of the output produced by a call to printNodes on a TernaryTreeMap<Character, Integer>.

Node@_596706728: b, <null>, Node@2106900153, Node@1070501849, Node@1298146757  
Node@2106900153: a, <null>,   no left child, Node@1443055846,  no right child  
Node@1443055846: t,      2, Node@_502838712, no middle child,  no right child, T
Node@_502838712: s,      2,   no left child, no middle child,  no right child, T     

This method is intended mainly for debugging purposes.

Parameters:
  • paddedElementLength = 1

    Minimum length (in Characters) of an Element, in the output generated by printNodes().

  • paddedItemLength = 6

    Minimum length (in Characters) of an Item, in the output generated by printNodes().

shared formal 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 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.

spanshared actual TernaryTreeMap<KeyElement,Item> span(PrefixMap.Key from, PrefixMap.Key to)

Obtain a span containing the elements between the two given indices.

The span should contain elements of this stream, starting from the element at the given starting index (from), and ending with the element at the given ending index (to), in the same order as they are produced by the iterator of the stream, except when the ending index occurs earlier than the starting index, in which case they occur in the opposite order.

When one or both of the given indices does not belong to this ranged stream, the behavior is implementation dependent.

Refines Ranged.span (span)
spanFromshared actual TernaryTreeMap<KeyElement,Item> spanFrom(PrefixMap.Key from)

Obtain a span containing the elements between the given starting index (from) and the last index of this ranged object.

The span should contain elements of this stream, starting from the element at the given starting index (from), in the same order as they are produced by the iterator of the stream.

When the given index does not belong to this ranged stream, the behavior is implementation dependent.

Refines Ranged.spanFrom (spanFrom)
spanToshared actual TernaryTreeMap<KeyElement,Item> spanTo(PrefixMap.Key to)

Obtain a span containing the elements between the first index of this ranged stream and given end index (to).

The span should contain elements of this stream, up to the element at the given ending index (to), in the same order as they are produced by the iterator of the stream.

When the given index does not belong to this ranged stream, the behavior is implementation dependent.

Refines Ranged.spanTo (spanTo)
Inherited Methods
Methods inherited from: Object
equals
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