com.trackstudio.tools.tree
Class OrderedTree

java.lang.Object
  com.trackstudio.tools.tree.OrderedTree

public class OrderedTree
extends java.lang.Object

Дерево основано на трех массивах.

Constructor Summary

OrderedTree(java.lang.Comparable o)

Method Summary

void	add(java.lang.Comparable to, java.lang.Comparable o) Добавить объект в дерево
boolean	addAll(java.lang.Comparable to, java.util.List c)
void	addTree(java.lang.Comparable to, OrderedTree t) Вставляет поддерево в дерево.
boolean	contains(java.lang.Comparable o)
java.lang.Comparable	get(java.lang.Comparable o)
java.util.List	getAncestors(java.lang.Comparable o)
java.util.List	getChildren(java.lang.Comparable o) Возвращает список узлов, дочерних к заданному
int	getChildrenCount(java.lang.Comparable o) Возвращает количество непосредственных потомков у узла
int[]	getChildrenPosition(int j)
java.util.List	getCommonNodes(java.lang.Comparable a, java.lang.Comparable b)
java.util.List	getContents() Возвращает список всех элементов дерева
java.util.List	getDescendents(java.lang.Comparable o)
java.util.Iterator	getDescendentsIterator(java.lang.Comparable o)
java.util.List	getDiffNodes(java.lang.Comparable a, java.lang.Comparable b)
int	getElementsPosition(java.lang.Comparable elem) Возвращает позицию объекта в хранилище
java.util.List	getLeaves() Возвращает список листьев- узлов без потомков.
java.lang.Comparable	getParent(java.lang.Comparable o) Возвращаем родительский узел.
java.lang.Comparable	getRoot()
java.util.List	getSiblings(java.lang.Comparable o)
OrderedTree	getSubTree(java.lang.Comparable o)
boolean	hasChildren(java.lang.Comparable o)
boolean	isChildOf(java.lang.Comparable child, java.lang.Comparable parent)
boolean	isParentOf(java.lang.Comparable parent, java.lang.Comparable child)
java.util.Iterator	iterator()
void	moveTree(java.lang.Comparable from, java.lang.Comparable to) 1.
OrderedTree	remove(java.lang.Comparable o)
void	replaceWith(java.lang.Comparable o, java.lang.Comparable with) Замещает один узел другим, при этом никакого перемещения под-деревьев не происходит.
int	search(java.lang.Comparable elem) поиск перебором.
int	size()
boolean	validate()
java.util.ArrayList	validateAncestors()
java.util.ArrayList	validateChildCount()
java.util.ArrayList	validateIndex()

Methods inherited from class java.lang.Object

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

Constructor Detail

OrderedTree

public OrderedTree(java.lang.Comparable o)

Method Detail

search

public int search(java.lang.Comparable elem)

поиск перебором. Нужен на случай, если бинарный поиск не работает (для неComparable элементов).

Parameters:

elem -

getElementsPosition

public int getElementsPosition(java.lang.Comparable elem)

Возвращает позицию объекта в хранилище

Parameters:

elem -

add

public void add(java.lang.Comparable to,
                java.lang.Comparable o)

Добавить объект в дерево

Parameters:

to - узел, к которому добавляется объект

o - объект

getChildrenCount

public int getChildrenCount(java.lang.Comparable o)

Возвращает количество непосредственных потомков у узла

Parameters:

o -

Returns:

количество потомков или -1, если такого узла нет

getChildren

public java.util.List getChildren(java.lang.Comparable o)

Возвращает список узлов, дочерних к заданному

Parameters:

o - заданный узел

Returns:

список узлов или null, если указанного узла не существует

getChildrenPosition

public int[] getChildrenPosition(int j)

getDescendents

public java.util.List getDescendents(java.lang.Comparable o)

getDescendentsIterator

public java.util.Iterator getDescendentsIterator(java.lang.Comparable o)

getParent

public java.lang.Comparable getParent(java.lang.Comparable o)

Возвращаем родительский узел.

Parameters:

o -

Returns:

Родительский узел или null, если элемента нет в хранилище, либо это root (черт, тут вилка получается, надо как-то оговаривать заранее)

getAncestors

public java.util.List getAncestors(java.lang.Comparable o)

getContents

public java.util.List getContents()

Возвращает список всех элементов дерева

addTree

public void addTree(java.lang.Comparable to,
                    OrderedTree t)

Вставляет поддерево в дерево. Жуткий метод

Parameters:

to - куда вставляем

t - что вставляем. Должно быть OrderedTree

contains

public boolean contains(java.lang.Comparable o)

getRoot

public java.lang.Comparable getRoot()

getLeaves

public java.util.List getLeaves()

Возвращает список листьев- узлов без потомков. Делается быстро с помощью childrenCounter

remove

public OrderedTree remove(java.lang.Comparable o)

getSubTree

public OrderedTree getSubTree(java.lang.Comparable o)

size

public int size()

replaceWith

public void replaceWith(java.lang.Comparable o,
                        java.lang.Comparable with)

Замещает один узел другим, при этом никакого перемещения под-деревьев не происходит. Узлы, конечно, должны быть уникальными

Parameters:

o -

with -

get

public java.lang.Comparable get(java.lang.Comparable o)

hasChildren

public boolean hasChildren(java.lang.Comparable o)

moveTree

public void moveTree(java.lang.Comparable from,
                     java.lang.Comparable to)

1. У старого parent сделать childrencounter-- 2. У нового parent сделать childrencounter++ 3. у root сделать parent = to

Parameters:

from -

to -

iterator

public java.util.Iterator iterator()

getCommonNodes

public java.util.List getCommonNodes(java.lang.Comparable a,
                                     java.lang.Comparable b)

getDiffNodes

public java.util.List getDiffNodes(java.lang.Comparable a,
                                   java.lang.Comparable b)

isChildOf

public boolean isChildOf(java.lang.Comparable child,
                         java.lang.Comparable parent)

isParentOf

public boolean isParentOf(java.lang.Comparable parent,
                          java.lang.Comparable child)

addAll

public boolean addAll(java.lang.Comparable to,
                      java.util.List c)

getSiblings

public java.util.List getSiblings(java.lang.Comparable o)

validate

public boolean validate()

validateChildCount

public java.util.ArrayList validateChildCount()

validateAncestors

public java.util.ArrayList validateAncestors()

validateIndex

public java.util.ArrayList validateIndex()