gran.tools.tree
Class OrderedTree

java.lang.Object
  gran.tools.tree.AbstractTree
      gran.tools.tree.OrderedTree

All Implemented Interfaces:

Tree

public class OrderedTree

extends AbstractTree

implements Tree

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

Constructor Summary

OrderedTree(java.lang.Object o)

Method Summary

void	add(java.lang.Object to, java.lang.Object o) Добавить объект в дерево
void	addTree(java.lang.Object to, Tree t) Вставляет поддерево в дерево.
boolean	contains(java.lang.Object o) Проверяет, содержит ли дерево заданный узел
java.lang.Object[]	elements() возвращает массиы элементов
java.lang.Object	get(java.lang.Object o)
java.util.List	getAncestors(java.lang.Object o) Возвращает список узлов, стоящих по дереву выше заданного, вплоть до корня дерева.
java.util.List	getChildren(java.lang.Object o) Возвращает список узлов, дочерних к заданному
int	getChildrenCount(java.lang.Object o) Возвращает количество непосредственных потомков у узла
int[]	getChildrenPosition(int j) Возвращает список узлов, дочерних к заданному
java.util.List	getContents() Возвращает список всех элементов дерева
java.util.List	getDescendents(java.lang.Object o) Возвращает список всех узлов, располагающихся ниже заданного (рекурсивно)
int	getElementsPosition(java.lang.Object elem) Возвращает позицию объекта в хранилище
java.util.List	getLeaves() Возвращает список листьев- узлов без потомков.
java.lang.Object	getParent(java.lang.Object o) Возвращаем родительский узел.
java.lang.Object	getRoot() Возвращает корневой узел
Tree	getSubTree(java.lang.Object o) Возвращает под-дерево с корнем в заданном узле
boolean	hasChildren(java.lang.Object o) Проверяет, есть ли у данного узла дочерние элементы
static void	main(java.lang.String[] s)
void	moveTree(java.lang.Object from, java.lang.Object to) 1.
Tree	remove(java.lang.Object o) Удаляет элемент из дерева.
void	replaceWith(java.lang.Object o, java.lang.Object with) Замещает один узел другим, при этом никакого перемещения под-деревьев не происходит.
void	retainAll(OrderedTree t)
int	search(java.lang.Object elem) поиск перебором.
int	size() Возврашает размер дерева

Methods inherited from class gran.tools.tree.AbstractTree

addAll, getCommonNodes, getDiffNodes, getSiblings, isChildOf, isParentOf, iterator

Methods inherited from class java.lang.Object

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

Methods inherited from interface gran.tools.tree.Tree

addAll, getCommonNodes, getDiffNodes, getSiblings, isChildOf, isParentOf, iterator

Constructor Detail

OrderedTree

public OrderedTree(java.lang.Object o)

Method Detail

search

public int search(java.lang.Object elem)

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

Parameters:

elem -

getElementsPosition

public int getElementsPosition(java.lang.Object elem)

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

Parameters:

elem -

add

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

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

Specified by:

add in interface Tree

Parameters:

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

o - объект

Returns:

true, если объект был добавлен; false, если, например, to не существует

getChildrenCount

public int getChildrenCount(java.lang.Object o)

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

Parameters:

o -

Returns:

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

getChildren

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

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

Specified by:

getChildren in interface Tree

Parameters:

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

Returns:

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

getChildrenPosition

public int[] getChildrenPosition(int j)

Description copied from interface: Tree

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

Specified by:

getChildrenPosition in interface Tree

Returns:

список узлов

getDescendents

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

Description copied from interface: Tree

Возвращает список всех узлов, располагающихся ниже заданного (рекурсивно)

Specified by:

getDescendents in interface Tree

Parameters:

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

Returns:

список узлов

getParent

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

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

Specified by:

getParent in interface Tree

Parameters:

o -

Returns:

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

getAncestors

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

Description copied from interface: Tree

Возвращает список узлов, стоящих по дереву выше заданного, вплоть до корня дерева.

Specified by:

getAncestors in interface Tree

Parameters:

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

Returns:

список узлов

getContents

public java.util.List getContents()

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

Specified by:

getContents in interface Tree

Returns:

список всех елементов дерева

addTree

public void addTree(java.lang.Object to,
                    Tree t)

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

Specified by:

addTree in interface Tree

Parameters:

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

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

contains

public boolean contains(java.lang.Object o)

Description copied from interface: Tree

Проверяет, содержит ли дерево заданный узел

Specified by:

contains in interface Tree

Parameters:

o -

Returns:

true, если содержит. Иначе false

getRoot

public java.lang.Object getRoot()

Description copied from interface: Tree

Возвращает корневой узел

Specified by:

getRoot in interface Tree

Returns:

корневой узел

getLeaves

public java.util.List getLeaves()

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

Specified by:

getLeaves in interface Tree

Returns:

список всех листьев

remove

public Tree remove(java.lang.Object o)

Description copied from interface: Tree

Удаляет элемент из дерева. При этом удаляются и все его дочерние узлы

Specified by:

remove in interface Tree

Parameters:

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

Returns:

Под-дерево, корнем которого является удаленный узел

getSubTree

public Tree getSubTree(java.lang.Object o)

Description copied from interface: Tree

Возвращает под-дерево с корнем в заданном узле

Specified by:

getSubTree in interface Tree

Parameters:

o -

Returns:

поддевево

elements

public java.lang.Object[] elements()

возвращает массиы элементов

size

public int size()

Description copied from interface: Tree

Возврашает размер дерева

Specified by:

size in interface Tree

Returns:

количество элементов

replaceWith

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

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

Specified by:

replaceWith in interface Tree

Parameters:

o -

with -

Returns:

true

get

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

Specified by:

get in interface Tree

hasChildren

public boolean hasChildren(java.lang.Object o)

Description copied from interface: Tree

Проверяет, есть ли у данного узла дочерние элементы

Specified by:

hasChildren in interface Tree

Parameters:

o -

Returns:

true, если есть дочерние элементы

moveTree

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

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

Specified by:

moveTree in interface Tree

Overrides:

moveTree in class AbstractTree

Parameters:

from -

to -

retainAll

public void retainAll(OrderedTree t)

main

public static void main(java.lang.String[] s)