Package com.googlecode.concurrenttrees.radix.node.concrete.charsequence

Class CharSequenceNodeDefault

  • All Implemented Interfaces:
    Node, NodeCharacterProvider, java.io.Serializable
    public class CharSequenceNodeDefault
extends java.lang.Object
implements Node
    A implementation of the Node interface which stores the incoming edge as a CharSequence (a view onto the original key) rather than copying the edge into a character array. Stores all variables and supports all behaviours required by the tree, but still could be more memory efficient.

    See NodeFactory for documentation on how alternative node implementations can be created to reduce memory overhead. See the Node interface for details on how to write memory-efficient nodes.

    This implementation stores references to child nodes in an AtomicReferenceArray, in ascending sorted order of the first character of the edges which child nodes define.

    The getOutgoingEdge(Character) method uses binary search to locate a requested node, given the first character of an edge indicated. The node is then read and returned atomically from the AtomicReferenceArray.

    The updateOutgoingEdge(com.googlecode.concurrenttrees.radix.node.Node) method ensures that any attempt to update a reference to a child node preserves the constraints defined in the Node interface. New child nodes are written atomically to the AtomicReferenceArray.

    The constraints defined in the Node interface ensure that the AtomicReferenceArray always remains in ascending sorted order regardless of modifications performed concurrently, as long as the modifications comply with the constraints. This node enforces those constraints.

    See Also:
    Serialized Form

    • Constructor Summary

      Constructors 
      Constructor Description
      CharSequenceNodeDefault​(java.lang.CharSequence edgeCharSequence, java.lang.Object value, java.util.List<Node> outgoingEdges)  

    • Method Summary

      All Methods Instance Methods Concrete 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.
      java.lang.String toString()  
      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.

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • incomingEdgeCharSequence

        private final java.lang.CharSequence incomingEdgeCharSequence

      • outgoingEdges

        private final java.util.concurrent.atomic.AtomicReferenceArray<Node> outgoingEdges

      • outgoingEdgesAsList

        private final java.util.List<Node> outgoingEdgesAsList

      • value

        private final java.lang.Object value

    • Constructor Detail

      • CharSequenceNodeDefault

        public CharSequenceNodeDefault​(java.lang.CharSequence edgeCharSequence,
                               java.lang.Object value,
                               java.util.List<Node> outgoingEdges)

    • Method Detail

      • getIncomingEdge

        public java.lang.CharSequence getIncomingEdge()
        Description copied from interface: Node
        Returns all characters of the "edge" encoded in this node, belonging to the connection from a parent node to this node.
        Specified by:
        getIncomingEdge in interface Node
        Returns:
        All characters of the "edge" encoded in this node

      • getIncomingEdgeFirstCharacter

        public java.lang.Character getIncomingEdgeFirstCharacter()
        Description copied from interface: Node
        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 Node
        Specified by:
        getIncomingEdgeFirstCharacter in interface NodeCharacterProvider
        Returns:
        The first character of the "edge" encoded in this node

      • getValue

        public java.lang.Object getValue()
        Description copied from interface: 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.
        Specified by:
        getValue in interface 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

        public Node getOutgoingEdge​(java.lang.Character edgeFirstCharacter)
        Description copied from interface: Node
        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 Node.updateOutgoingEdge(Node).

        Specified by:
        getOutgoingEdge in interface 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

        public void updateOutgoingEdge​(Node childNode)
        Description copied from interface: Node
        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 Node.getOutgoingEdge(Character).

        Specified by:
        updateOutgoingEdge in interface Node
        Parameters:
        childNode - The new child node to associated with this edge

      • getOutgoingEdges

        public java.util.List<Node> getOutgoingEdges()
        Description copied from interface: Node
        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.

        Specified by:
        getOutgoingEdges in interface Node
        Returns:
        A read-only list of the child nodes to which this node has outgoing edges

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object