com.googlecode.concurrenttrees.radix.node.util
Class NodeUtil

java.lang.Object
  com.googlecode.concurrenttrees.radix.node.util.NodeUtil

public class NodeUtil
extends Object

Static utility methods useful when implementing Nodes.

Author:

Niall Gallagher

Method Summary

static int	binarySearchForEdge(AtomicReferenceArray<Node> childNodes, Character edgeFirstCharacter) Returns the index of the node in the given AtomicReferenceArray whose edge starts with the given first character.
static void	ensureNoDuplicateEdges(List<Node> nodes) Throws an exception if any nodes in the given list represent edges having the same first character.

Methods inherited from class java.lang.Object

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

Method Detail

binarySearchForEdge

public static int binarySearchForEdge(AtomicReferenceArray<Node> childNodes,
                                      Character edgeFirstCharacter)

Returns the index of the node in the given AtomicReferenceArray whose edge starts with the given first character.

This method expects that some constraints are enforced on the AtomicReferenceArray:

• The array must already be in ascending sorted order of the first character of the edge for each node
• No entries in the array can be null
• Any existing node in the array cannot be swapped concurrently for another unless the edge associated with the other node also starts with the same first character

If these constraints are enforced as expected, then this method will have deterministic behaviour even in the face of concurrent modification.

Parameters:

childNodes - An AtomicReferenceArray of Node objects, which is used in accordance with the constraints documented in this method

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

Returns:

The index of the node representing the indicated edge, or a value < 0 if no such node exists in the array

ensureNoDuplicateEdges

public static void ensureNoDuplicateEdges(List<Node> nodes)

Throws an exception if any nodes in the given list represent edges having the same first character.

Parameters:

nodes - The list of nodes to validate

Throws:

IllegalStateException - If a duplicate edge is detected