tree.java

这是一个matlab的java实现。里面有许多内容。请大家慢慢捉摸。

/* Copyright (C) 2003 Univ. of Massachusetts Amherst, Computer Science Dept.
   This file is part of "MALLET" (MAchine Learning for LanguagE Toolkit).
   http://www.cs.umass.edu/~mccallum/mallet
   This software is provided under the terms of the Common Public License,
   version 1.0, as published by http://www.opensource.org.  For further
   information, see the file `LICENSE' included with this distribution. */

package edu.umass.cs.mallet.grmm;

import salvo.jesus.graph.Vertex;
import salvo.jesus.graph.Edge;
import edu.umass.cs.mallet.base.types.Alphabet;
import salvo.jesus.graph.listener.NullGraphListener;
import java.util.Collections;
import java.util.ArrayList;
import java.util.List;
import salvo.jesus.graph.GraphAddVertexEvent;
import java.util.Iterator;


/**
 *  Class for arbitrary trees, based on implementation in OpenJGraph.
 *  The OpenJGraph tree implementation is a bit minimal wrt
 *   convenience functions, so we add a few here.
 *
 * Created: Wed Oct  1 14:51:47 2003
 *
 * @author <a href="mailto:[e-mail]">Charles Sutton</a>
 * @version $Id: Tree.java,v 1.1 2004/07/15 17:53:31 casutton Exp $
 */
public class Tree {

	private Alphabet vertices = new Alphabet ();
	private ArrayList parents = new ArrayList ();
	private ArrayList children = new ArrayList ();

	private Vertex root = null;

	public Tree() {} // Tree constructor

	// Efficient indexing of parents, children

	protected int lookupIndex (Vertex v) 
	{
		return vertices.lookupIndex (v, false);
	}

	protected Vertex lookupVertex (int idx)
	{
		return (Vertex) vertices.lookupObject (idx);
	}

	int maybeAddVertex (Vertex v)
	{
		int foo = vertices.lookupIndex (v, false);
		if (foo == -1) {
			foo = vertices.lookupIndex (v);
			parents.add (null);
			children.add (new ArrayList ());
		}
		return foo;
	}

	public void add (Vertex rt)
	{
		if (root == null) {
			maybeAddVertex (rt);
			root = rt;
		} else {
			throw new UnsupportedOperationException
				("This tree already has a root.");
		}
	}


	public void addNode (Vertex parent, Vertex child)
	{
		int id1;
		if (root == null) {
			root = parent;
			id1 = maybeAddVertex (parent);
		} else if ((id1 = lookupIndex (parent)) == -1)
			throw new UnsupportedOperationException
				("This tree already has a root.");
	
		int id2 = maybeAddVertex (child);

    Object oldParent = parents.get (id2);
    if ((oldParent != null) && (oldParent != parent))
      throw new UnsupportedOperationException
              ("Trying to change parent of vertex "+child+" from "
               +oldParent+" to "+parent);

		parents.set (id2, parent);
		ArrayList childList = (ArrayList) children.get (id1);
		childList.add (child);
	}

	
	public Vertex getParent (Vertex child) 
	{
		return (Vertex) parents.get (vertices.lookupIndex (child));
	}

	public List getChildren (Vertex parent)
	{
		int id = vertices.lookupIndex (parent);
		return Collections.unmodifiableList ((List) children.get (id));
	}

	// Convenience functions

	public boolean isRoot (Vertex var) 
	{
		int idx = lookupIndex (var);
		return (parents.get(idx) == null);
	}


	public boolean containsVertex (Vertex v) 
	{
		return (vertices.lookupIndex (v, false) >= 0);
	}

	public boolean isLeaf (Vertex v)
	{
		int idx = lookupIndex (v);
		return ((List)children.get(idx)).size() == 0;
	}

	public Iterator getVerticesIterator () 
	{
		return vertices.iterator();
	}

	public Vertex getRoot () { return root; }

} // Tree