General Tree Implementation

Bu kayıtta size önceden yazdığım General Tree Implementation'ını paylaşacağım. Yakında paylaşacağım, Square Tiling problemininde de bu sınıfı kullanacağım. Belki ileride başka kayıtlarımda da kullanabilirim, o yüzden ayrı bir başlık açmayı uygun gördüm.

Bu implementation'ı Goodrich'in Data Structures & Algorithms kitabındaki AbstractTree sınıfının üzerine yazdım. Aslında anlatılacak pek birşey yok, her node'da bir ArrayList bulunmakta ve bu sayade istendiği kadar child eklenebiliyor.

Position.java

package datastructures;

/**
 * An interface for a position which is an abstraction for the
 * location at which a single element is stored in a positional
 * container.
 */
public interface Position<E> {

 /**
  * Returns the element stored at this position.
  *
  * @return the stored element
  * @throws IllegalStateException if position no longer valid
  */
 E getElement() throws IllegalStateException;
}

Tree.java

package datastructures.trees;

import java.util.Iterator;

import datastructures.Position;

/**
 * An interface for a tree where nodes can have an arbitrary number of children.
 */
public interface Tree<E> extends Iterable<E> {

 /**
  * Returns the root Position of the tree (or null if tree is empty).
  * 
  * @return root Position of the tree (or null if tree is empty)
  */
 Position<E> root();

 /**
  * Returns the Position of p's parent (or null if p is root).
  *
  * @param p
  *            A valid Position within the tree
  * @return Position of p's parent (or null if p is root)
  * @throws IllegalArgumentException
  *             if p is not a valid Position for this tree.
  */
 Position<E> parent(Position<E> p) throws IllegalArgumentException;

 /**
  * Returns an iterable collection of the Positions representing p's
  * children.
  *
  * @param p
  *            A valid Position within the tree
  * @return iterable collection of the Positions of p's children
  * @throws IllegalArgumentException
  *             if p is not a valid Position for this tree.
  */
 Iterable<Position<E>> children(Position<E> p)
   throws IllegalArgumentException;

 /**
  * Returns the number of children of Position p.
  *
  * @param p
  *            A valid Position within the tree
  * @return number of children of Position p
  * @throws IllegalArgumentException
  *             if p is not a valid Position for this tree.
  */
 int numChildren(Position<E> p) throws IllegalArgumentException;

 /**
  * Returns true if Position p has one or more children.
  *
  * @param p
  *            A valid Position within the tree
  * @return true if p has at least one child, false otherwise
  * @throws IllegalArgumentException
  *             if p is not a valid Position for this tree.
  */
 boolean isInternal(Position<E> p) throws IllegalArgumentException;

 /**
  * Returns true if Position p does not have any children.
  *
  * @param p
  *            A valid Position within the tree
  * @return true if p has zero children, false otherwise
  * @throws IllegalArgumentException
  *             if p is not a valid Position for this tree.
  */
 boolean isExternal(Position<E> p) throws IllegalArgumentException;

 /**
  * Returns true if Position p represents the root of the tree.
  *
  * @param p
  *            A valid Position within the tree
  * @return true if p is the root of the tree, false otherwise
  * @throws IllegalArgumentException
  *             if p is not a valid Position for this tree.
  */
 boolean isRoot(Position<E> p) throws IllegalArgumentException;

 /**
  * Returns the number of nodes in the tree.
  * 
  * @return number of nodes in the tree
  */
 int size();

 /**
  * Tests whether the tree is empty.
  * 
  * @return true if the tree is empty, false otherwise
  */
 boolean isEmpty();

 /**
  * Returns an iterator of the elements stored in the tree.
  * 
  * @return iterator of the tree's elements
  */
 Iterator<E> iterator();

 /**
  * Returns an iterable collection of the positions of the tree.
  * 
  * @return iterable collection of the tree's positions
  */
 Iterable<Position<E>> positions();
}

AbstractTree.Java

package datastructures.trees;

import java.util.ArrayList; // for use as snapshot iterator
import java.util.Iterator;
import java.util.List; // for use as snapshot iterator

import datastructures.Position;

/**
 * An abstract base class providing some functionality of the Tree interface.
 *
 * The following three methods remain abstract, and must be implemented by a
 * concrete subclass: root, parent, children. Other methods implemented in this
 * class may be overridden to provide a more direct and efficient
 * implementation.
 */
public abstract class AbstractTree<E> implements Tree<E> {

 @Override
 public boolean isInternal(Position<E> p) {
  return numChildren(p) > 0;
 }

 @Override
 public boolean isExternal(Position<E> p) {
  return numChildren(p) == 0;
 }

 @Override
 public boolean isRoot(Position<E> p) {
  return p == root();
 }

 @Override
 public int numChildren(Position<E> p) {
  int count = 0;
  for (Position<E> child : children(p))
   count++;
  return count;
 }

 @Override
 public int size() {
  int count = 0;
  for (Position<E> p : positions())
   count++;
  return count;
 }

 @Override
 public boolean isEmpty() {
  return size() == 0;
 }

 public int depth(Position<E> p) throws IllegalArgumentException {
  if (isRoot(p))
   return 0;
  else
   return 1 + depth(parent(p));
 }

 public int height(Position<E> p) throws IllegalArgumentException {
  int h = 0; 
  for (Position<E> c : children(p))
   h = Math.max(h, 1 + height(c));
  return h;
 }

 private class ElementIterator implements Iterator<E> {
  Iterator<Position<E>> posIterator = positions().iterator();

  public boolean hasNext() {
   return posIterator.hasNext();
  }

  public E next() {
   return posIterator.next().getElement();
  } 

  public void remove() {
   posIterator.remove();
  }
 }

 @Override
 public Iterator<E> iterator() {
  return new ElementIterator();
 }

 @Override
 public Iterable<Position<E>> positions() {
  return preorder();
 }

 private void preorderSubtree(Position<E> p, List<Position<E>> snapshot) {
  snapshot.add(p);

  for (Position<E> c : children(p))
   preorderSubtree(c, snapshot);
 }

 public Iterable<Position<E>> preorder() {
  List<Position<E>> snapshot = new ArrayList<>();
  if (!isEmpty())
   preorderSubtree(root(), snapshot);
  return snapshot;
 }

 private void postorderSubtree(Position<E> p, List<Position<E>> snapshot) {
  for (Position<E> c : children(p))
   postorderSubtree(c, snapshot);
  snapshot.add(p);
 }

 public Iterable<Position<E>> postorder() {
  List<Position<E>> snapshot = new ArrayList<>();
  if (!isEmpty())
   postorderSubtree(root(), snapshot);
  return snapshot;
 }

}

GeneralTree.java

package datastructures.trees;

import java.util.ArrayList;

import datastructures.Position;

public class GeneralTree<E> extends AbstractTree<E> {

 protected static class Node<E> implements Position<E> {

  private E element;
  private Node<E> parent;
  private ArrayList<Node<E>> children;

  public Node(E element, Node<E> parent) {
   this.element = element;
   this.parent = parent;

   children = new ArrayList<>();
  }

  @Override
  public E getElement() {
   return element;
  }

  public void setElement(E element) {
   this.element = element;
  }

  
  protected Node<E> getChild(int index) {
   if (numChildren() > index)
    return children.get(index);
   else 
    return null;
  }
  
  protected void setChild(int index, E e) {
   children.get(index).setElement(e);
  }
  
  protected void add(Node<E> child) {
   children.add(child);
  }
  
  protected int numChildren() {
   return children.size();
  }
 
  protected Iterable<Position<E>> children() {
   return new ArrayList<Position<E>>(children);
  }
 }

 protected Node<E> root;
 protected int size = 0;

 protected Node<E> validate(Position<E> p) throws IllegalArgumentException {
  if (!(p instanceof Node))
   throw new IllegalArgumentException("Not a valid position type");

  return (Node<E>)p;
 }

 public void addRoot(E e) throws IllegalStateException {
  if (!isEmpty())
   throw new IllegalStateException("Not empty");
  root = new Node<E>(e, null);

  size = 1;
 }

 public void addChild(Position<E> p, E e) throws IllegalStateException {
  Node<E> parent = validate(p);
  Node<E> child = new Node<>(e, parent);

  parent.add(child);

  size++;
 }
 
 public Position<E> getChild(Position<E> p, int i) {
  Node<E> parent = validate(p);
  
  return parent.getChild(i);
 }
 
 public void setChild(Position<E> p, int i, E e) {
  Node<E> parent = validate(p);
  
  parent.setChild(i, e);
 }

 @Override
 public Position<E> root() {
  return root;
 }

 @Override
 public Position<E> parent(Position<E> p) throws IllegalArgumentException {
  Node<E> child = validate(p);

  if (isRoot(child))
   throw new IllegalArgumentException("Root");
  Node<E> parent = child.parent;

  return parent;
 }

 @Override
 public Iterable<Position<E>> children(Position<E> p)
   throws IllegalArgumentException {
  Node<E> parent = validate(p);

  return parent.children();
 }

 @Override
 public int numChildren(Position<E> p) throws IllegalArgumentException {
  Node<E> parent = validate(p);

  return parent.numChildren();
 }

 @Override
 public int size() {
  return size;
 }


}