Interface Node
-
- All Superinterfaces:
NodeCharacterProvider
,java.io.Serializable
- 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, java.io.Serializable
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)
- 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 ofCharSequence
, the only requirement is that they provide aCharSequence
view onto the character data. Character data can optionally be stored outside of the tree.CharSequence
s 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.CharSequence
s are free to store character data within the tree but in a size-reduced encoding such as UTF-8
-
-
Method Summary
All Methods Instance Methods Abstract Methods Modifier and Type Method Description java.lang.CharSequence
getIncomingEdge()
Returns all characters of the "edge" encoded in this node, belonging to the connection from a parent node to this node.java.lang.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(java.lang.Character edgeFirstCharacter)
Returns the child of this node whose edge starts with the given first character.java.util.List<Node>
getOutgoingEdges()
Returns a read-only list of the child nodes to which this node has outgoing edges, i.e.java.lang.Object
getValue()
Returns a value object which has been associated with a key and which is stored in this node, or returnsnull
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
java.lang.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 interfaceNodeCharacterProvider
- Returns:
- The first character of the "edge" encoded in this node
-
getIncomingEdge
java.lang.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
java.lang.Object getValue()
Returns a value object which has been associated with a key and which is stored in this node, or returnsnull
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(java.lang.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 viaupdateOutgoingEdge(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 viagetOutgoingEdge(Character)
.- Parameters:
childNode
- The new child node to associated with this edge
-
getOutgoingEdges
java.util.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
-
-