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

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

        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 interface NodeCharacterProvider
        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 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​(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 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

        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