Package it.unimi.dsi.util

Interface PrefixMap<S extends CharSequence>

All Superinterfaces:
Function<CharSequence,Long>, Function<CharSequence,Long>, Object2LongFunction<CharSequence>, Serializable, StringMap<S>, ToLongFunction<CharSequence>
All Known Implementing Classes:
AbstractPrefixMap, ImmutableExternalPrefixMap, StringMaps.SynchronizedPrefixMap, TernaryIntervalSearchTree
public interface PrefixMap<S extends CharSequence> extends StringMap<S>
A map from prefixes to string intervals (and possibly vice versa).

Instances of this class provide the services of a StringMap, but by assuming the strings are lexicographically ordered, they can provide further information by exposing a function from string prefixes to intervals and a function from intervals to string prefixes.

In the first case, given a prefix, we can ask for the range of strings starting with that prefix, expressed as an Interval. This information is very useful to satisfy prefix queries (e.g., monitor*) with a brute-force approach.

Optionally, a prefix map may provide the opposite service: given an interval of terms, it may provide the maximum common prefix. This feature can be checked for by calling prefixMap().

Since:
0.9.2
Author:
Sebastiano Vigna

  • Method Details

    • rangeMap

      Object2ObjectFunction<CharSequence,Interval> rangeMap()
      Returns a function mapping prefixes to ranges of strings.
      Returns:
      a function mapping prefixes to ranges of strings.

    • prefixMap

      Object2ObjectFunction<Interval,S> prefixMap()
      Returns a function mapping ranges of strings to common prefixes (optional operation).
      Returns:
      a function mapping ranges of strings to common prefixes, or null if this map does not support prefixes.