com.jivesoftware.forum.renderer.filter.wiki.list
Class WikiList

java.lang.Object
  com.jivesoftware.forum.renderer.filter.wiki.list.WikiList

public class WikiList
extends java.lang.Object

A simple tree structure for lists.

The tree holds a maximum of 65534 nodes. It is not intended to be thread-safe. Based on algorithm found in the book "Introduction To Algorithms" by Cormen et all, MIT Press, 1997.

Field Summary

protected ListItem[]	keys
protected char[]	leftChildren
protected char	nextIndex
protected char[]	rightSiblings
protected ListItem	rootItem

Constructor Summary

WikiList()
Creates a new wiki list tree.

Method Summary

void	addChild(ListItem parent, ListItem newChild) Adds a child list item to the tree.
protected int	fillDepthKeys(char startIndex, ListItem[] depthKeys, int cursor) Recursive method that fills the depthKeys array with all the child keys in the tree in depth first order.
protected char	findDepth(ListItem item, char startIndex, int[] depth) Identical to the findKey method, but it also keeps track of the depth.
protected char	findKey(ListItem item, char startIndex) Returns the index of the specified value, or 0 if the item could not be found.
ListItem	getChild(ListItem parent, int index) Returns a child of parent at index index.
int	getChildCount(ListItem parent) Returns the number of children of parent.
ListItem[]	getChildren(ListItem parent) Returns an array of the children of the parent, or an empty array if there are no children or the parent is not in the tree.
int	getDepth(ListItem item) Returns the depth in the tree that the element can be found at or -1 if the element is not in the tree.
int	getIndexOfChild(ListItem parent, ListItem child) Returns the index of child in parent or -1 if child is not a child of parent.
protected char	getLeftSiblingIndex(char index) Returs the left sibling index of index.
ListItem	getParent(ListItem child) Returns a parent of child, or null if there is no parent.
ListItem[]	getRecursiveChildren(ListItem parent) Returns the list items in the in the tree in depth-first order.
ListItem[]	getRecursiveKeys() Returns the list items in the in the tree in depth-first order.
ListItem	getRootItem() Returns the dummy root item that is used to create the tree (since the tree is required to have a single root node).
boolean	isLeaf(ListItem item) Returns true if the tree node is a leaf.
ListItem[]	keys() Returns the list items in the tree.
protected void	resizeTree()
void	toString(java.lang.StringBuffer buffer, RenderContext renderContext) Returns the list rendered out to html

Methods inherited from class java.lang.Object

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

Field Detail

keys

protected ListItem[] keys

leftChildren

protected char[] leftChildren

rightSiblings

protected char[] rightSiblings

nextIndex

protected char nextIndex

rootItem

protected ListItem rootItem

Constructor Detail

WikiList

public WikiList()

Creates a new wiki list tree.

Method Detail

getRootItem

public ListItem getRootItem()

Returns the dummy root item that is used to create the tree (since the tree is required to have a single root node).

Returns:

the dummy root item that is used to create the tree

addChild

public void addChild(ListItem parent,
                     ListItem newChild)

Adds a child list item to the tree.

Parameters:

parent - the parent to add the new value to.

newChild - new child to add to the tree.

getParent

public ListItem getParent(ListItem child)

Returns a parent of child, or null if there is no parent.

Parameters:

child - the child item to return the parent for

Returns:

a parent of child, or null if there is no parent.

getChild

public ListItem getChild(ListItem parent,
                         int index)

Returns a child of parent at index index.

Parameters:

parent - the parent item

index - the child's index in the parent's children

Returns:

a child of parent at index index.

getChildCount

public int getChildCount(ListItem parent)

Returns the number of children of parent.

Parameters:

parent - the parent item

Returns:

the number of children of parent.

getChildren

public ListItem[] getChildren(ListItem parent)

Returns an array of the children of the parent, or an empty array if there are no children or the parent is not in the tree.

Parameters:

parent - the parent to get the children of.

Returns:

the children of the parent item

getIndexOfChild

public int getIndexOfChild(ListItem parent,
                           ListItem child)

Returns the index of child in parent or -1 if child is not a child of parent.

Parameters:

parent - the parent item

child - the child item

Returns:

the index of child in parent or -1 if child is not a child of parent.

getDepth

public int getDepth(ListItem item)

Returns the depth in the tree that the element can be found at or -1 if the element is not in the tree. For example, the root element is depth 0, direct children of the root element are depth 1, etc.

Parameters:

item - the item to find the depth for.

Returns:

the depth of key in the tree hiearchy.

getRecursiveKeys

public ListItem[] getRecursiveKeys()

Returns the list items in the in the tree in depth-first order. For example, give the tree:

   1
   |-- 3
   |-- |-- 4
   |-- |-- |-- 7
   |-- |-- 6
   |-- 5
 

Then this method would return the sequence: 1, 3, 4, 7, 6, 5.

Returns:

the list items of the tree in depth-first order.

getRecursiveChildren

public ListItem[] getRecursiveChildren(ListItem parent)

Returns the list items in the in the tree in depth-first order. For example, give the tree:

   1
   |-- 3
   |-- |-- 4
   |-- |-- |-- 7
   |-- |-- 6
   |-- 5
 

Then this method would return the sequence: 1, 3, 4, 7, 6, 5.

Parameters:

parent - the parent to get children of.

Returns:

the list items of the tree in depth-first order.

isLeaf

public boolean isLeaf(ListItem item)

Returns true if the tree node is a leaf.

Parameters:

item - the item to check

Returns:

true if item has no children.

keys

public ListItem[] keys()

Returns the list items in the tree.

Returns:

the list items in the tree.

findKey

protected char findKey(ListItem item,
                       char startIndex)

Returns the index of the specified value, or 0 if the item could not be found. Tail recursion was removed, but not the other recursive step. Using a stack instead often isn't even faster under Java.

Parameters:

item - the item to search for.

startIndex - the index in the tree to start searching at. Pass in the root index to search the entire tree.

Returns:

the index of the specified value, or 0 if the item could not be found

findDepth

protected char findDepth(ListItem item,
                         char startIndex,
                         int[] depth)

Identical to the findKey method, but it also keeps track of the depth.

Parameters:

item - the item to search for.

startIndex - the index in the tree to start searching at. Pass in the root index to search the entire tree.

depth - an array - only the first element is used to designate the depth of the item

Returns:

the index of the specified value, or 0 if the item could not be found

fillDepthKeys

protected int fillDepthKeys(char startIndex,
                            ListItem[] depthKeys,
                            int cursor)

Recursive method that fills the depthKeys array with all the child keys in the tree in depth first order.

Parameters:

startIndex - the starting index for the current recursive iteration.

depthKeys - the array of depth-first keys that is being filled.

cursor - the current index in the depthKeys array.

Returns:

the new cursor value after a recursive run.

getLeftSiblingIndex

protected char getLeftSiblingIndex(char index)

Returs the left sibling index of index. There is no easy way to find a left sibling. Therefore, we are forced to linearly scan the rightSiblings array until we encounter a reference to index. We'll make the assumption that entries are added in order since that assumption can yield big performance gain if it's true (and no real performance hit otherwise).

Parameters:

index - the item's index

Returns:

the left sibling index of index.

resizeTree

protected void resizeTree()

toString

public void toString(java.lang.StringBuffer buffer,
                     RenderContext renderContext)

Returns the list rendered out to html

Parameters:

buffer - the buffer to write the rendered html to

renderContext - the render context