Jive Forums API (5.5.20.2-oracle) Developer Javadocs

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

java.lang.Object
  extended by 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

Jive Forums Project Page

Copyright © 1999-2006 Jive Software.