Package com.pnfsoftware.jeb.util.collect

Class CFBytesTrie<T>

java.lang.Object
com.pnfsoftware.jeb.util.collect.CFBytesTrie<T>
Type Parameters:
T - value type
@Ser public class CFBytesTrie<T> extends Object
A trie map specialized to handle context-free (CF) binary strings. Context-free here means that the binary strings stored as keys cannot be such that, given a binary string A, there exists a longer binary string B whose prefix is A.

Characteristics/limitations:
- Support for insertion and retrieval only (no removal).
- The null key and the empty key are illegal.
- Null values are illegal.

This class is not thread-safe. This class does not override equals/hashCode/toString.

Implementation notes: this class is serializable (provided that the stored objects T are also serializable). In order to serialize this class efficiently, both in terms of space and time, a key extractor should be set.

  • Constructor Details

    • CFBytesTrie

      public CFBytesTrie()
      Create an empty trie.

  • Method Details

    • setKeyExtractor

      public void setKeyExtractor(CFBytesTrie.IKeyExtractor<T> keyExtractor)
      Set the key extractor used by put(Object) and optimized serialization.
      Parameters:
      keyExtractor - key extractor

    • getKeyExtractor

      public CFBytesTrie.IKeyExtractor<T> getKeyExtractor()
      Returns:
      configured key extractor, or null

    • clear

      public void clear()
      Remove all entries.

    • size

      public int size()
      Returns:
      number of entries

    • isEmpty

      public boolean isEmpty()
      Returns:
      true if the trie is empty

    • put

      public void put(T object)
      Add a new entry to the trie. This method throws an IllegalStateException on prefix collision.
      Parameters:
      object - value (the value's key is derived using the key extractor)

    • put

      public void put(byte[] key, T object)
      Add a new entry to the trie. This method throws an IllegalStateException on prefix collision.
      Parameters:
      key - key
      object - value

    • put

      public T put(byte[] keyarray, int start, int end, T object)
      Add a new entry to the trie. This method throws an IllegalStateException on prefix collision.
      Parameters:
      keyarray - key array
      start - key start position in the array
      end - key end position (exclusive)
      object - value
      Returns:
      the previous entry at key, null if none

    • putSafe

      public boolean putSafe(byte[] keyarray, int start, int end, T object, T[] aprev)
      Add a new entry to the trie. This method does not throw if a prefix collision is detected; instead, false is returned.
      Parameters:
      keyarray - key array
      start - key start position in the array
      end - key end position (exclusive)
      object - value
      aprev - if non-null, a one-element array that will receive the previous entry at key, or null if none
      Returns:
      success indicator (false if a prefix collision occurred)

    • get

      public T get(byte[] key, boolean exactKey)
      Retrieve a value in the trie.
      Parameters:
      key - key
      exactKey - true to require an exact key match
      Returns:
      object value, null if none

    • get

      public T get(byte[] keyarray, int start, int max, boolean exactKey)
      Retrieve a value in the trie.
      Parameters:
      keyarray - key array
      start - key start index
      max - key end index (exclusive)
      exactKey - if false, more potential key bytes may be provided, and the object whose key matches the beginning of the sequence of bytes will be returned
      Returns:
      object value, null if none

    • formatInternalState

      public String formatInternalState()
      Format internal trie statistics.
      Returns:
      formatted state string

    • getValues

      public List<T> getValues()
      Generate a list of all values stored in this trie. This method is potentially expensive.
      Returns:
      list of stored values

    • getItems

      public List<Couple<byte[],T>> getItems()
      Generate the list of items (key, value) stored in this trie. This method is potentially expensive.
      Returns:
      list of stored key-value pairs