com.googlecode.concurrenttrees.radix.node
Interface Node

All Superinterfaces:

NodeCharacterProvider

All Known Implementing Classes:

ByteArrayNodeDefault, ByteArrayNodeLeafNullValue, ByteArrayNodeLeafVoidValue, ByteArrayNodeLeafWithValue, ByteArrayNodeNonLeafNullValue, ByteArrayNodeNonLeafVoidValue, CharArrayNodeDefault, CharArrayNodeLeafNullValue, CharArrayNodeLeafVoidValue, CharArrayNodeLeafWithValue, CharArrayNodeNonLeafNullValue, CharArrayNodeNonLeafVoidValue, CharSequenceNodeDefault, CharSequenceNodeLeafNullValue, CharSequenceNodeLeafVoidValue, CharSequenceNodeLeafWithValue, CharSequenceNodeNonLeafNullValue, CharSequenceNodeNonLeafVoidValue

public interface Node
extends NodeCharacterProvider

Specifies the methods that nodes must implement.

The main function of a node is to represent an "edge" in the tree. An edge is a connection from a parent node to a child node which represents a sequence of characters. For practical reasons we store these characters in the child node, to avoid needing separate Edge objects. All nodes except the root encode at least one character for an edge.

Nodes contain several fields, but not all nodes will actually need to store values in every field. Therefore some specialized implementations of this interface are possible, optimized for storing various combinations of data items in reduced numbers of fields, to reduce memory overhead.

Nodes are partially immutable:

• The characters of an "edge" encoded in within a node are immutable (these characters belong to the edge arriving at the current node from a parent node)
• The number of outgoing edges from a node (references to child nodes), and the first characters of those edges are immutable
• The references to child nodes for existing edges (as identified by their first characters) are mutable with constraints; the reference to a child node for an existing edge may be updated to point to a different child node as long as the new edge starts with the same first character
• If a node stores a value, the reference to the value is immutable (values can be changed but it requires recreating the node with the new value - this is to account for specialized node implementations omitting a field for the value when not required)

These constraints exist allow concurrent traversal and modifications to the tree. Nodes are required to implement some operations atomically, see documentation on each method in this interface for details.

Hints for specialized implementations of this Node interface:

• Leaf nodes do not need to store references to child nodes; a specialized node implementation could eliminate a field and associated data structure for child node references
• All leaf nodes store values
• Some non-leaf nodes store values, some do not
• Edge character data can be encoded using implementation-specific methods.

  Nodes are not required to store a CharSequence object verbatim, or use a particular implementation of CharSequence, the only requirement is that they provide a CharSequence view onto the character data.

  Character data can optionally be stored outside of the tree. CharSequences can encode a start and end offset (or length) as a view onto a larger string (possibly a view onto the original key inserted). Furthermore end offset could be stored as length, relative to the start offset with variable length encoding to avoid storing 4 bytes for the length. This option would have consequences for garbage collection of large string keys however, therefore would mostly suit immutable data sets.

  Character data can be compressed. CharSequences are free to store character data within the tree but in a size-reduced encoding such as UTF-8

Author:

Niall Gallagher

Method Summary

CharSequence	getIncomingEdge() Returns all characters of the "edge" encoded in this node, belonging to the connection from a parent node to this node.
Character	getIncomingEdgeFirstCharacter() Returns the first character of the "edge" encoded in this node, belonging to the connection from a parent node to this node.
Node	getOutgoingEdge(Character edgeFirstCharacter) Returns the child of this node whose edge starts with the given first character.
List<Node>	getOutgoingEdges() Returns a read-only list of the child nodes to which this node has outgoing edges, i.e.
Object	getValue() Returns a value object which has been associated with a key and which is stored in this node, or returns null if no value is stored in this node.
void	updateOutgoingEdge(Node childNode) Updates the child node reference for a given edge (identified by its first character) to point to a different child node.

Method Detail

getIncomingEdgeFirstCharacter

Character getIncomingEdgeFirstCharacter()

Returns the first character of the "edge" encoded in this node, belonging to the connection from a parent node to this node.

Specified by:

getIncomingEdgeFirstCharacter in interface NodeCharacterProvider

Returns:

The first character of the "edge" encoded in this node

getIncomingEdge

CharSequence getIncomingEdge()

Returns all characters of the "edge" encoded in this node, belonging to the connection from a parent node to this node.

Returns:

All characters of the "edge" encoded in this node

getValue

Object getValue()

Returns a value object which has been associated with a key and which is stored in this node, or returns null if no value is stored in this node.

Returns:

A value object which has been associated with a key and which is stored in this node, or returns null if no value is stored in this node

getOutgoingEdge

Node getOutgoingEdge(Character edgeFirstCharacter)

Returns the child of this node whose edge starts with the given first character.

This read must be performed atomically, in relation to writes made via updateOutgoingEdge(Node).

Parameters:

edgeFirstCharacter - The first character of the edge for which the associated child node is required

Returns:

The child of this node whose edge starts with the given first character, or null if this node has no such outgoing edge

updateOutgoingEdge

void updateOutgoingEdge(Node childNode)

Updates the child node reference for a given edge (identified by its first character) to point to a different child node.

The first character of the given child node's edge must match the first character of an existing outgoing edge from this node.

This write must be performed atomically, in relation to reads made via getOutgoingEdge(Character).

Parameters:

childNode - The new child node to associated with this edge

getOutgoingEdges

List<Node> getOutgoingEdges()

Returns a read-only list of the child nodes to which this node has outgoing edges, i.e. child nodes which have incoming edges from this node.

It is intended that this method will be used for copying/cloning nodes.

Returns:

A read-only list of the child nodes to which this node has outgoing edges