From 415d6680a02bfbd85ad3f154a7c7f2aee5453549 Mon Sep 17 00:00:00 2001 From: =?utf8?q?David=20=E2=80=98Bombe=E2=80=99=20Roden?= Date: Mon, 26 May 2008 19:50:13 +0200 Subject: [PATCH] add tree data structure --- src/net/pterodactylus/util/data/Node.java | 87 +++++++++++++++++++ src/net/pterodactylus/util/data/NodeImpl.java | 120 ++++++++++++++++++++++++++ src/net/pterodactylus/util/data/Tree.java | 44 ++++++++++ 3 files changed, 251 insertions(+) create mode 100644 src/net/pterodactylus/util/data/Node.java create mode 100644 src/net/pterodactylus/util/data/NodeImpl.java create mode 100644 src/net/pterodactylus/util/data/Tree.java 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 null if the node is the {@link Tree#getRootNode()} + * of the tree) and an arbitrary amount of child nodes. + * + * @author David ‘Bombe’ Roden <bombe@freenetproject.org> + * @param + * The type of the element to store + */ +public interface Node extends Iterable> { + + /** + * Returns the parent node of the node. + * + * @return The parent node + */ + public Node 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 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 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 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> 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 <bombe@freenetproject.org> + * @param + * The type of the element to store + */ +class NodeImpl implements Node { + + /** The parent node of this node. */ + private final Node parentNode; + + /** The element contained in this node. */ + private final E element; + + /** The child nodes of this node. */ + private final List> children = new ArrayList>(); + + /** + * 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 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 getParent() { + return parentNode; + } + + /** + * {@inheritDoc} + */ + public E getElement() { + return element; + } + + /** + * {@inheritDoc} + */ + public Node addChild(E child) { + Node childNode = new NodeImpl(this, child); + children.add(childNode); + return childNode; + } + + /** + * {@inheritDoc} + */ + public int size() { + return children.size(); + } + + /** + * {@inheritDoc} + */ + public Node getChild(int childIndex) { + return children.get(childIndex); + } + + /** + * {@inheritDoc} + */ + public void removeChild(Node childNode) { + children.remove(childNode); + } + + /** + * {@inheritDoc} + */ + public void removeChild(E child) { + for (Node childNode: children) { + if (child.equals(childNode.getElement())) { + children.remove(childNode); + break; + } + } + } + + /** + * {@inheritDoc} + */ + public void removeChild(int childIndex) { + children.remove(childIndex); + } + + /** + * {@inheritDoc} + */ + public Iterator> 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 <bombe@freenetproject.org> + * @param + * The type of the element to store + */ +public class Tree { + + /** The root node of the tree. */ + private final Node rootNode = new NodeImpl(); + + /** + * Returns the root node of the tree. + * + * @return The root node of the tree + */ + public Node getRootNode() { + return rootNode; + } + +} -- 2.7.4