org.apache.jackrabbit.commons.flat
Class BTreeManager

java.lang.Object
  org.apache.jackrabbit.commons.flat.BTreeManager

All Implemented Interfaces:

TreeManager

public class BTreeManager
extends Object
implements TreeManager

This TreeManager implementation provides B+-tree like behavior. That is items of a sequence (i.e. NodeSequence or PropertySequence) are mapped to a sub-tree in JCR in a way such that only leave nodes carry actual values, the sub-tree is always balanced and ordered. This implementation does in contrast to a full B+-tree implementation not join nodes after deletions. This does not affect the order of items and also leaves the tree balanced wrt. its depths. It might however result in a sparse tree. That is, the tree might get unbalanced wrt. its weights.

The nodes in the JCR sub tree are arranged such that any node named x only contains child nodes with names greater or equal to x. The implementation keeps the child nodes in the sub tree ordered if the respective node type supports ordering of child nodes. Ordering is always wrt. to a Comparator on the respective keys. For lexical order this arrangement corresponds to how words are arranged in a multi volume encyclopedia.

Example usage:

 // Create a new TreeManager instance rooted at node. Splitting of nodes takes place
 // when the number of children of a node exceeds 40 and is done such that each new
 // node has at least 40 child nodes. The keys are ordered according to the natural
 // order of java.lang.String.
 TreeManager treeManager = new BTreeManager(node, 20, 40, Rank.<String>comparableComparator(), true);

 // Create a new NodeSequence with that tree manager
 NodeSequence nodes = ItemSequence.createNodeSequence(treeManager);

 // Add nodes with key "jcr" and "day"
 nodes.addNode("jcr", NodeType.NT_UNSTRUCTURED);
 nodes.addNode("day", NodeType.NT_UNSTRUCTURED);

 // Iterate over the node in the sequence.
 // Prints "day jcr "
 for (Node n : nodes) {
     System.out.print(n.getName() + " ");
 }

 // Retrieve node with key "jcr"
 Node n = nodes.getItem("jcr");

 // Remove node with key "day"
 nodes.removeNode("day");
 

Constructor Summary

BTreeManager(Node root, int minChildren, int maxChildren, Comparator<String> order, boolean autoSave)
Create a new BTreeManager rooted at Node root.

Method Summary

protected Node	createIntermediateNode(Node parent, String name) Creates and return an intermediate node for the given name as child node of parent.
boolean	getAutoSave() Whether to automatically save changes of the current session occurring from adding/removing nodes and properties.
Set<String>	getIgnoredProperties() Properties to ignore.
protected SizedIterator<Node>	getNodes(Node node) Returns a SizedIterator of the child nodes of node.
Comparator<String>	getOrder() Comparator used for establishing the order of the keys in the sequence.
protected SizedIterator<Property>	getProperties(Node node) Returns a SizedIterator of the properties of node which excludes the jcr.primaryType property.
Node	getRoot()
protected <T> SizedIterator<T>	getSizedIterator(Iterator<T> iterator, long size) Wraps iterator into a SizedIterator given a size.
boolean	isLeaf(Node node) Returns !
boolean	isRoot(Node node) Determined whether the given node is the root node of the JCR sub-tree.
void	join(ItemSequence itemSequence, Node node, Node cause) This implementation does not actually join any nodes.
void	join(ItemSequence itemSequence, Node node, Property cause) This implementation does not actually join any nodes.
protected void	move(Node node, Node parent) Move node to the new parent.
protected void	move(Property property, Node parent) Move property to the new parent.
void	split(ItemSequence itemSequence, Node node, Node cause) This implementations splits node when its number of child nodes exceeds the maximum number specified in the constructor.
void	split(ItemSequence itemSequence, Node node, Property cause) This implementations splits node when its number of properties exceeds the maximum number specified in the constructor.

Methods inherited from class java.lang.Object

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

Constructor Detail

BTreeManager

public BTreeManager(Node root,
                    int minChildren,
                    int maxChildren,
                    Comparator<String> order,
                    boolean autoSave)
             throws RepositoryException

Create a new BTreeManager rooted at Node root.

Parameters:

root - the root of the JCR sub-tree where the items of the sequence are stored.

minChildren - minimal number of children for a node after splitting.

maxChildren - maximal number of children for a node after which splitting occurs.

order - order according to which the keys are stored

autoSave - determines whether the current session is saved after add/delete operations.

Throws:

RepositoryException

Method Detail

getIgnoredProperties

public Set<String> getIgnoredProperties()

Properties to ignore. The default set contains JcrConstants.JCR_PRIMARYTYPE and JcrConstants.JCR_MIXINTYPES.

Specified by:

getIgnoredProperties in interface TreeManager

Returns:

split

public void split(ItemSequence itemSequence,
                  Node node,
                  Node cause)
           throws RepositoryException

This implementations splits node when its number of child nodes exceeds the maximum number specified in the constructor. Splitting is done such that after the split each of the new child nodes contains at least as many nodes as specified in the constructor.

Specified by:

split in interface TreeManager

Parameters:

itemSequence - the ItemSequence where the new node cause has been inserted.

node - the parent node of the newly inserted node

cause - the newly inserted node or null if not known.

Throws:

RepositoryException

See Also:

TreeManager.split(org.apache.jackrabbit.commons.flat.ItemSequence, javax.jcr.Node, javax.jcr.Node)

split

public void split(ItemSequence itemSequence,
                  Node node,
                  Property cause)
           throws RepositoryException

This implementations splits node when its number of properties exceeds the maximum number specified in the constructor. Splitting is done such that after the split each of the new child nodes contains at least as many nodes as specified in the constructor.

Specified by:

split in interface TreeManager

Parameters:

itemSequence - the ItemSequence where the new property cause has been inserted.

node - the parent node of the newly inserted property

cause - the newly inserted property or null if not known.

Throws:

RepositoryException

See Also:

TreeManager.split(org.apache.jackrabbit.commons.flat.ItemSequence, javax.jcr.Node, javax.jcr.Property)

join

public void join(ItemSequence itemSequence,
                 Node node,
                 Node cause)
          throws RepositoryException

This implementation does not actually join any nodes. It does however delete node if getNodes(Node) returns an empty iterator. It does further recursively delete any parent of node which does not have any child node.

Specified by:

join in interface TreeManager

Parameters:

itemSequence - the ItemSequence where the node cause has been deleted from.

node - the parent node from which cause has been deleted.

cause - the deleted node or null if not known. Note: cause might be stale.

Throws:

RepositoryException

See Also:

TreeManager.join(org.apache.jackrabbit.commons.flat.ItemSequence, javax.jcr.Node, javax.jcr.Node)

join

public void join(ItemSequence itemSequence,
                 Node node,
                 Property cause)
          throws RepositoryException

This implementation does not actually join any nodes. It does however delete node if getProperties(Node) returns an empty iterator. It does further recursively delete any parent of node which does not have any child node.

Specified by:

join in interface TreeManager

Parameters:

itemSequence - the ItemSequence where the property cause has been deleted from.

node - the parent node from which cause has been deleted.

cause - the deleted property or null if not known. Note: cause might be stale.

Throws:

RepositoryException

See Also:

TreeManager.join(org.apache.jackrabbit.commons.flat.ItemSequence, javax.jcr.Node, javax.jcr.Property)

getRoot

public Node getRoot()

Specified by:

getRoot in interface TreeManager

Returns:

the root node of the JCR sub-tree where the items of the sequence are be mapped to.

isRoot

public boolean isRoot(Node node)
               throws RepositoryException

Description copied from interface: TreeManager

Determined whether the given node is the root node of the JCR sub-tree.

Specified by:

isRoot in interface TreeManager

Parameters:

node - Node to test for root

Returns:

getRoot().isSame(node).

Throws:

RepositoryException

isLeaf

public boolean isLeaf(Node node)
               throws RepositoryException

Returns !node.hasNodes()

Specified by:

isLeaf in interface TreeManager

Parameters:

node - Node to test for leaf

Returns:

true if node is a leaf node, false otherwise.

Throws:

RepositoryException

See Also:

TreeManager.isLeaf(javax.jcr.Node)

getOrder

public Comparator<String> getOrder()

Description copied from interface: TreeManager

Comparator used for establishing the order of the keys in the sequence.

Specified by:

getOrder in interface TreeManager

Returns:

a Comparator<String> instance

getAutoSave

public boolean getAutoSave()

Description copied from interface: TreeManager

Whether to automatically save changes of the current session occurring from adding/removing nodes and properties.

Specified by:

getAutoSave in interface TreeManager

Returns:

true if changes should be automatically saved, false otherwiese.

getNodes

protected SizedIterator<Node> getNodes(Node node)
                                throws RepositoryException

Returns a SizedIterator of the child nodes of node.

Throws:

RepositoryException

getProperties

protected SizedIterator<Property> getProperties(Node node)
                                         throws RepositoryException

Returns a SizedIterator of the properties of node which excludes the jcr.primaryType property.

Throws:

RepositoryException

createIntermediateNode

protected Node createIntermediateNode(Node parent,
                                      String name)
                               throws RepositoryException

Creates and return an intermediate node for the given name as child node of parent.

Throws:

RepositoryException

move

protected void move(Node node,
                    Node parent)
             throws RepositoryException

Move node to the new parent.

Throws:

RepositoryException

move

protected void move(Property property,
                    Node parent)
             throws RepositoryException

Move property to the new parent.

Throws:

RepositoryException

getSizedIterator

protected final <T> SizedIterator<T> getSizedIterator(Iterator<T> iterator,
                                                      long size)

Wraps iterator into a SizedIterator given a size. The value of the size parameter must correctly reflect the number of items in iterator.