org.jacop.jasat.utils.structures

Class IntTrie<N extends IntTrie.Node<N>>

java.lang.Object

org.jacop.jasat.utils.structures.IntTrie<N>

Type Parameters:

N - the type of the nodes of the Trie

Direct Known Subclasses:

IntSet

public class IntTrie<N extends IntTrie.Node<N>>
extends Object

A class that implements, (hopefully) efficiently, a Trie on integers. It is parametrized by the type of the nodes to carry useful data. implementation based on Trie (or Radix Tree, see http://en.wikipedia.org/wiki/Radix_tree).

It can be used directly as a (simple) set.

Version:

4.9

Author:

Simon Cruanes and Radoslaw Szymanek

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	IntTrie.Node<E> class of nodes of the Trie.
static class	IntTrie.SimpleNode The most simple node possible

Constructor Summary

Constructors

Constructor and Description
IntTrie(N root) initializes the Trie with a root node

Method Summary

Modifier and Type	Method and Description
N	add(int i) add i to the Trie
void	clear() empty the Trie, removing all elements from it
boolean	contains(int i) does the Trie contains i ?
N	getNode(int i) get the node associated with i, or maybe the node that would be associated with i if i was in the Trie (*optional* feature)
N	getRoot()
boolean	isEmpty()
boolean	remove(int i) remove the int i.
int	size()
Set<Integer>	values()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

IntTrie

public IntTrie(N root)

initializes the Trie with a root node

Parameters:

root - the root node.

Method Detail

add

public final N add(int i)

add i to the Trie

Parameters:

i - the int to add to the Trie

Returns:

the node corresponding to i

contains

public final boolean contains(int i)

does the Trie contains i ?

Parameters:

i - the int

Returns:

true if the Trie contains i, false otherwise

getNode

public final N getNode(int i)

get the node associated with i, or maybe the node that would be associated with i if i was in the Trie (*optional* feature)

Parameters:

i - the int

Returns:

the node associated with i if it exists, null otherwise

getRoot

public final N getRoot()

Returns:

the root node

remove

public final boolean remove(int i)

remove the int i.

Parameters:

i - the int to remove from the Trie

Returns:

true if i was in the Trie (and has been removed), false if it was not

clear

public final void clear()

empty the Trie, removing all elements from it

isEmpty

public final boolean isEmpty()

Returns:

true if and only if the trie does not contain anything

size

public final int size()

Returns:

the number of elements in the Trie

values

public Set<Integer> values()

Returns:

the set of values that the Trie contains (quite inefficient)