Package com.pnfsoftware.jeb.util.collect

Class CFBytesTrie<T>

java.lang.Object
com.pnfsoftware.jeb.util.collect.CFBytesTrie<T>
Type Parameters:
T -
@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: the is serializable (at the condition 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()

  • Method Details

    • setKeyExtractor

      public void setKeyExtractor(CFBytesTrie.IKeyExtractor<T> keyExtractor)

    • getKeyExtractor

      public CFBytesTrie.IKeyExtractor<T> getKeyExtractor()

    • clear

      public void clear()

    • size

      public int size()

    • isEmpty

      public boolean isEmpty()

    • 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 -
      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()

    • getValues

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

    • getItems

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