public class

CFBytesTrie

extends Object
java.lang.Object
   ↳ com.pnfsoftware.jeb.util.collect.CFBytesTrie<T>

Class Overview

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.

Summary

Nested Classes
interface CFBytesTrie.IKeyExtractor<T> The key extractor provides the bytes (to be used in the trie) for an element to be stored in the trie. 
class CFBytesTrie.Node A node in the trie. 
Public Constructors
CFBytesTrie()
Public Methods
void clear()
String formatInternalState()
T get(byte[] key, boolean exactKey)
Retrieve a value in the trie.
T get(byte[] keyarray, int start, int max, boolean exactKey)
Retrieve a value in the trie.
List<Couple<byte[], T>> getItems()
Generate the list of items (key, value) stored in this trie.
IKeyExtractor<T> getKeyExtractor()
List<T> getValues()
Generate a list of all values stored in this trie.
boolean isEmpty()
T put(byte[] keyarray, int start, int end, T object)
Add a new entry to the trie.
void put(T object)
Add a new entry to the trie.
void put(byte[] key, T object)
Add a new entry to the trie.
boolean putSafe(byte[] keyarray, int start, int end, T object, T[] aprev)
Add a new entry to the trie.
void setKeyExtractor(IKeyExtractor<T> keyExtractor)
int size()
[Expand]
Inherited Methods
From class java.lang.Object

Public Constructors

public CFBytesTrie ()

Public Methods

public void clear ()

public String formatInternalState ()

public T get (byte[] key, boolean exactKey)

Retrieve a value in the trie.

Parameters
key key
Returns
  • object value, null if none

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

public List<Couple<byte[], T>> getItems ()

Generate the list of items (key, value) stored in this trie. This method is potentially expensive.

public IKeyExtractor<T> getKeyExtractor ()

public List<T> getValues ()

Generate a list of all values stored in this trie. This method is potentially expensive.

public boolean isEmpty ()

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

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)

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

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)

public void setKeyExtractor (IKeyExtractor<T> keyExtractor)

public int size ()