From: David ‘Bombe’ Roden <bombe@pterodactylus.net>
Date: Mon, 26 May 2008 17:50:13 +0000 (+0200)
Subject: add tree data structure
X-Git-Url: https://git.pterodactylus.net/?p=jSite2.git;a=commitdiff_plain;h=415d6680a02bfbd85ad3f154a7c7f2aee5453549

add tree data structure
---

diff --git a/src/net/pterodactylus/util/data/Node.java b/src/net/pterodactylus/util/data/Node.java
new file mode 100644
index 0000000..7737d50
--- /dev/null
+++ b/src/net/pterodactylus/util/data/Node.java
@@ -0,0 +1,87 @@
+
+package net.pterodactylus.util.data;
+
+import java.util.Iterator;
+
+/**
+ * A node that can be stored in a {@link Tree}. A node has exactly one parent
+ * (which is <code>null</code> if the node is the {@link Tree#getRootNode()}
+ * of the tree) and an arbitrary amount of child nodes.
+ * 
+ * @author David ‘Bombe’ Roden &lt;bombe@freenetproject.org&gt;
+ * @param <E>
+ *            The type of the element to store
+ */
+public interface Node<E> extends Iterable<Node<E>> {
+
+	/**
+	 * Returns the parent node of the node.
+	 * 
+	 * @return The parent node
+	 */
+	public Node<E> getParent();
+
+	/**
+	 * Returns the element that is stored in the node.
+	 * 
+	 * @return The node’s element
+	 */
+	public E getElement();
+
+	/**
+	 * Adds an element as a child to this node and returns the created node.
+	 * 
+	 * @param child
+	 *            The child node’s element
+	 * @return The created child node
+	 */
+	public Node<E> addChild(E child);
+
+	/**
+	 * Returns the number of children this node has.
+	 * 
+	 * @return The number of children
+	 */
+	public int size();
+
+	/**
+	 * Returns the child at the given index.
+	 * 
+	 * @param index
+	 *            The index of the child
+	 * @return The child at the given index
+	 */
+	public Node<E> getChild(int index);
+
+	/**
+	 * Remove the given child node from this node. If the given node is not a
+	 * child of this node, nothing happens.
+	 * 
+	 * @param childNode
+	 *            The child node to remove
+	 */
+	public void removeChild(Node<E> childNode);
+
+	/**
+	 * Removes the child node that contains the given element. The element in
+	 * the node is checked using {@link Object#equals(Object)}.
+	 * 
+	 * @param child
+	 *            The child element to remove
+	 */
+	public void removeChild(E child);
+
+	/**
+	 * Removes the child at the given index.
+	 * 
+	 * @param childIndex
+	 *            The index of the child to remove
+	 */
+	public void removeChild(int childIndex);
+
+	/**
+	 * {@inheritDoc}
+	 */
+	public Iterator<Node<E>> iterator();
+
+}
\ No newline at end of file
diff --git a/src/net/pterodactylus/util/data/NodeImpl.java b/src/net/pterodactylus/util/data/NodeImpl.java
new file mode 100644
index 0000000..a30f76e
--- /dev/null
+++ b/src/net/pterodactylus/util/data/NodeImpl.java
@@ -0,0 +1,120 @@
+
+package net.pterodactylus.util.data;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+/**
+ * Implementation of the {@link Node} interface.
+ * 
+ * @author David ‘Bombe’ Roden &lt;bombe@freenetproject.org&gt;
+ * @param <E>
+ *            The type of the element to store
+ */
+class NodeImpl<E> implements Node<E> {
+
+	/** The parent node of this node. */
+	private final Node<E> parentNode;
+
+	/** The element contained in this node. */
+	private final E element;
+
+	/** The child nodes of this node. */
+	private final List<Node<E>> children = new ArrayList<Node<E>>();
+
+	/**
+	 * Creates a new root node.
+	 */
+	NodeImpl() {
+		this.parentNode = null;
+		this.element = null;
+	}
+
+	/**
+	 * Creates a new node with the given parent and element.
+	 * 
+	 * @param parentNode
+	 *            The parent of this node
+	 * @param element
+	 *            The element of this node
+	 */
+	NodeImpl(Node<E> parentNode, E element) {
+		if ((parentNode == null) || (element == null)) {
+			throw new NullPointerException("null is not allowed as parent or element");
+		}
+		this.parentNode = parentNode;
+		this.element = element;
+	}
+
+	/**
+	 * {@inheritDoc}
+	 */
+	public Node<E> getParent() {
+		return parentNode;
+	}
+
+	/**
+	 * {@inheritDoc}
+	 */
+	public E getElement() {
+		return element;
+	}
+
+	/**
+	 * {@inheritDoc}
+	 */
+	public Node<E> addChild(E child) {
+		Node<E> childNode = new NodeImpl<E>(this, child);
+		children.add(childNode);
+		return childNode;
+	}
+
+	/**
+	 * {@inheritDoc}
+	 */
+	public int size() {
+		return children.size();
+	}
+
+	/**
+	 * {@inheritDoc}
+	 */
+	public Node<E> getChild(int childIndex) {
+		return children.get(childIndex);
+	}
+
+	/**
+	 * {@inheritDoc}
+	 */
+	public void removeChild(Node<E> childNode) {
+		children.remove(childNode);
+	}
+
+	/**
+	 * {@inheritDoc}
+	 */
+	public void removeChild(E child) {
+		for (Node<E> childNode: children) {
+			if (child.equals(childNode.getElement())) {
+				children.remove(childNode);
+				break;
+			}
+		}
+	}
+
+	/**
+	 * {@inheritDoc}
+	 */
+	public void removeChild(int childIndex) {
+		children.remove(childIndex);
+	}
+
+	/**
+	 * {@inheritDoc}
+	 */
+	public Iterator<Node<E>> iterator() {
+		return children.iterator();
+	}
+
+}
\ No newline at end of file
diff --git a/src/net/pterodactylus/util/data/Tree.java b/src/net/pterodactylus/util/data/Tree.java
new file mode 100644
index 0000000..5cbb990
--- /dev/null
+++ b/src/net/pterodactylus/util/data/Tree.java
@@ -0,0 +1,44 @@
+/*
+ * jSite2 - Tree.java -
+ * Copyright © 2008 David Roden
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ */
+
+package net.pterodactylus.util.data;
+
+/**
+ * A tree structure in which every node can have an arbitrary amount of
+ * children.
+ * 
+ * @author David ‘Bombe’ Roden &lt;bombe@freenetproject.org&gt;
+ * @param <E>
+ *            The type of the element to store
+ */
+public class Tree<E> {
+
+	/** The root node of the tree. */
+	private final Node<E> rootNode = new NodeImpl<E>();
+
+	/**
+	 * Returns the root node of the tree.
+	 * 
+	 * @return The root node of the tree
+	 */
+	public Node<E> getRootNode() {
+		return rootNode;
+	}
+
+}