Mega Code Archive
This class is designed to provide a generic tree that allows duplicates
<![CDATA[
/*
* @(#)Tree.java 1.0 Apr 26, 2008
*
* The MIT License
*
* Copyright (c) 2008 Malachi de AElfweald <malachid@gmail.com>
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
* THE SOFTWARE.
*/
//package org.eoti.util;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.RandomAccess;
import java.util.concurrent.CopyOnWriteArrayList;
/**
* TreeSet and TreeMap are both Balanced Trees that don't allow duplicate keys.
* This class is designed to provide a generic tree that allows duplicates.
*/
public class Tree<T extends Tree<T>> implements Collection<T>, RandomAccess,
Iterable<T> {
protected CopyOnWriteArrayList<T> subtrees;
public Tree() {
subtrees = new CopyOnWriteArrayList<T>();
}
public int totalSize() {
int totalSize = size();
for (T tree : subtrees)
totalSize += tree.totalSize();
return totalSize;
}
// START OVERRIDES OF Object
public String toString() {
return String.format("[Tree [%s]]", subtrees.toString());
}
// END OVERRIDES OF Object
// START OVERRIDES OF Collection
public int size() {
return subtrees.size();
}
public boolean isEmpty() {
return subtrees.isEmpty();
}
public boolean contains(Object o) {
return subtrees.contains(o);
}
public Iterator<T> iterator() {
return subtrees.iterator();
}
public Object[] toArray() {
return subtrees.toArray();
}
public <T> T[] toArray(T[] ts) {
return subtrees.toArray(ts);
}
public boolean add(T subTree) {
return subtrees.add(subTree);
}
public boolean remove(Object o) {
return subtrees.remove(o);
}
public boolean containsAll(Collection<?> c) {
return subtrees.containsAll(c);
}
public boolean addAll(Collection<? extends T> ts) {
return subtrees.addAll(ts);
}
public boolean removeAll(Collection<?> c) {
return subtrees.removeAll(c);
}
public boolean retainAll(Collection<?> c) {
return subtrees.retainAll(c);
}
public void clear() {
subtrees.clear();
}
public int hashCode() {
return subtrees.hashCode();
}
public boolean equals(Object obj) {
if (!(obj instanceof Tree))
return false;
return subtrees.equals(((Tree) obj).subtrees);
}
// END OVERRIDES OF Collection
// START WRAPPERS OF CopyOnWriteArrayList
public void add(int index, T subTree) {
subtrees.add(index, subTree);
}
public T get(int index) {
return subtrees.get(index);
}
public int indexOf(T subTree, int index) {
return subtrees.indexOf(subTree, index);
}
public int indexOf(Object obj) {
return subtrees.indexOf(obj);
}
public int lastIndexOf(T subTree, int index) {
return subtrees.lastIndexOf(subTree, index);
}
public int lastIndexOf(Object obj) {
return subtrees.lastIndexOf(obj);
}
public ListIterator<T> listIterator() {
return subtrees.listIterator();
}
public ListIterator<T> listIterator(int index) {
return subtrees.listIterator(index);
}
public T remove(int index) {
return subtrees.remove(index);
}
public T set(int index, T subTree) {
return subtrees.set(index, subTree);
}
public List<T> subList(int fromIndex, int toIndex) {
return subtrees.subList(fromIndex, toIndex);
}
// END WRAPPERS OF CopyOnWriteArrayList
/**
* Creates a deep copy of the specified Tree. Changes to one do not change
* the other.
*/
@SuppressWarnings("unchecked")
public Tree<T> copy() {
Tree<T> t = newInstance();
for (T subtree : subtrees)
t.add((T) subtree.copy());
return t;
}
/**
* Creates a Symbolic Link to the this Tree. Changes to one are changed in
* the other.
*/
public Tree<T> symlink() {
Tree<T> t = newInstance();
t.subtrees = subtrees;
return t;
}
public Tree<T> newInstance() {
return new Tree<T>();
}
}
]]>