defaultgraphmodel.java

用JGraph编的软件

/*
 * @(#)DefaultGraphModel.java	1.0 1/1/02
 * 
 * Copyright (c) 2001-2004, Gaudenz Alder 
 * All rights reserved. 
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * - Redistributions of source code must retain the above copyright notice,
 *   this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright notice,
 *   this list of conditions and the following disclaimer in the documentation 
 *   and/or other materials provided with the distribution.
 * - Neither the name of JGraph nor the names of its contributors may be used
 *   to endorse or promote products derived from this software without specific
 *   prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *
 */

package org.jgraph.graph;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import javax.swing.event.EventListenerList;
import javax.swing.tree.DefaultMutableTreeNode;
import javax.swing.tree.MutableTreeNode;
import javax.swing.tree.TreeNode;
import javax.swing.undo.CannotRedoException;
import javax.swing.undo.CannotUndoException;
import javax.swing.undo.CompoundEdit;
import javax.swing.undo.UndoableEdit;
import javax.swing.undo.UndoableEditSupport;

import org.jgraph.event.GraphModelEvent;
import org.jgraph.event.GraphModelListener;

/**
 * A simple implementation of a graph model.
 *
 * @version 1.0 1/1/02
 * @author Gaudenz Alder
 */

public class DefaultGraphModel
	extends UndoableEditSupport
	implements Serializable, GraphModel {

	/** The list of listeners that listen to the model. */
	protected transient EventListenerList listenerList =
		new EventListenerList();

	/** Default instance of an empty iterator. */
	protected transient Iterator emptyIterator = new EmptyIterator();

	/** Set that contains all root cells of this model. */
	protected List roots = new ArrayList();

	/** Indicates whether isLeaf is based on a node's allowsChildren value. */
	protected boolean asksAllowsChildren = false;

	/**
	 * Constructs a model that is not an attribute store.
	 */
	public DefaultGraphModel() {
	}

	//
	// Graph Model
	//

	/**
	 * Returns the number of roots in the model.  Returns 0 if the
	 * model is empty.
	 *
	 * @return  the number of roots in the model
	 */
	public int getRootCount() {
		return roots.size();
	}

	/**
	 * Returns the root at index <I>index</I> in the model.
	 * This should not return null if <i>index</i> is a valid
	 * index for the model (that is <i>index</i> >= 0 &&
	 * <i>index</i> < getRootCount()).
	 *
	 * @return  the root of at index <I>index</I>
	 */
	public Object getRootAt(int index) {
		return roots.get(index);
	}

	/**
	 * Returns the index of <code>root</code> in the model.
	 * If root is <code>null</code>, returns -1.
	 * @param parent a root in the model, obtained from this data source
	 * @return the index of the root in the model, or -1
	 *    if the parent is <code>null</code>
	 */
	public int getIndexOfRoot(Object root) {
		return roots.indexOf(root);
	}

	/**
	 * Returns <code>true</code> if <code>node</code> or one of its
	 * ancestors is in the model.
	 *
	 * @return <code>true</code> if  <code>node</code> is in the model
	 */
	public boolean contains(Object node) {
		Object parentNode = null;
		while ((parentNode = getParent(node))
			!= null)
			node = parentNode;
		return roots.contains(node);
	}

	/**
	 * Returns a <code>Map</code> that represents the attributes for
	 * the specified cell. This attributes have precedence over each
	 * view's attributes, regardless of isAttributeStore.
	 *
	 * @return attributes of <code>node</code> as a <code>Map</code>
	 */
	public Map getAttributes(Object node) {
		if (node instanceof GraphCell)
			return ((GraphCell) node).getAttributes();
		return null;
	}

	//
	// Graph Structure
	//

	/**
	 * Returns the source of <code>edge</code>. <I>edge</I> must be an object
	 * previously obtained from this data source.
	 *
	 * @return <code>Object</code> that represents the source of <i>edge</i>
	 */
	public Object getSource(Object edge) {
		if (edge instanceof Edge)
			return ((Edge) edge).getSource();
		return null;
	}

	/**
	 * Returns the target of <code>edge</code>. <I>edge</I> must be an object
	 * previously obtained from this data source.
	 *
	 * @return <code>Object</code> that represents the target of <i>edge</i>
	 */
	public Object getTarget(Object edge) {
		if (edge instanceof Edge)
			return ((Edge) edge).getTarget();
		return null;
	}

	/**
	 * Returns <code>true</code> if <code>port</code> is a valid source
	 * for <code>edge</code>. <I>edge</I> and <I>port</I> must be
	 * objects previously obtained from this data source.
	 *
	 * @return <code>true</code> if <code>port</code> is a valid source
	 *                           for <code>edge</code>.
	 */
	public boolean acceptsSource(Object edge, Object port) {
		return true;
	}

	/**
	 * Returns <code>true</code> if <code>port</code> is a valid target
	 * for <code>edge</code>. <I>edge</I> and <I>port</I> must be
	 * objects previously obtained from this data source.
	 *
	 * @return <code>true</code> if <code>port</code> is a valid target
	 *                           for <code>edge</code>.
	 */
	public boolean acceptsTarget(Object edge, Object port) {
		return true;
	}

	/**
	 * Returns an iterator of the edges connected to <code>port</code>.
	 * <I>port</I> must be a object previously obtained from
	 * this data source. This method never returns null.
	 *
	 * @param   port  a port in the graph, obtained from this data source
	 * @return  <code>Iterator</code> that represents the connected edges
	 */
	public Iterator edges(Object port) {
		if (port instanceof Port)
			return ((Port) port).edges();
		return emptyIterator;
	}

	/**
	 * Returns <code>true</code> if <code>edge</code> is a valid edge.
	 *
	 * @return <code>true</code> if <code>edge</code> is a valid edge.
	 */
	public boolean isEdge(Object edge) {
		return edge instanceof Edge;
	}

	/**
	 * Returns <code>true</code> if <code>port</code> is a valid
	 * port, possibly supporting edge connection.
	 *
	 * @return <code>true</code> if <code>port</code> is a valid port.
	 */
	public boolean isPort(Object port) {
		return port instanceof Port;
	}

	//
	// Group Structure
	//

 	/**
	 * Returns a map of (cell, clone)-pairs for all <code>cells</code>
	 * and their children. Special care is taken to replace the anchor
	 * references between ports. (Iterative implementation.)
	 */
	public Map cloneCells(Object[] cells) {
		Map map = new Hashtable();
		// Add Cells to Queue
		ArrayList q = new ArrayList();
		for (int i = 0; i < cells.length; i++)
			q.add(cells[i]);
		// Iterate Queue
		while (!q.isEmpty()) {
			// Remove Front Client From Queue
			Object node = q.remove(0);
			if (node instanceof DefaultGraphCell) {
				// Enqueue Children
				for (int i = 0; i < getChildCount(node); i++)
					q.add(getChild(node, i));
				// Re-Establish Parent Relation for Front Client
				DefaultGraphCell cell = (DefaultGraphCell) node;
				DefaultGraphCell clone = (DefaultGraphCell) cell.clone();
				Object par = getParent(cell);
				if (par != null) {
					DefaultMutableTreeNode p =
						(DefaultMutableTreeNode) map.get(par);
					if (p != null)
						p.add(clone);
				}
				// Store (cell, clone)-pair
				map.put(cell, clone);
			}
		}
		// Replace Anchors
		Iterator it = map.values().iterator();
		while (it.hasNext()) {
			Object obj = it.next();
			// For All Ports in Result Map do...
			if (obj instanceof Port) {
				Object anchor = ((Port) obj).getAnchor();
				// Map Anchor to Cloned Anchor
				if (anchor != null)
					 ((Port) obj).setAnchor((Port) map.get(anchor));
			}
		}
		return map;
	}


	/**
	 * Returns the parent of <I>child</I> in the model.
	 * <I>child</I> must be a node previously obtained from
	 * this data source. This returns null if <i>child</i> is
	 * a root in the model.
	 *
	 * @param   child  a node in the graph, obtained from this data source
	 * @return  the parent of <I>child</I>
	 */
	public Object getParent(Object child) {
		if (child != null && child instanceof TreeNode)
			return ((TreeNode) child).getParent();
		return null;
	}

	/**
	 * Returns the index of child in parent.
	 * If either the parent or child is <code>null</code>, returns -1.
	 * @param parent a note in the tree, obtained from this data source
	 * @param child the node we are interested in
	 * @return the index of the child in the parent, or -1
	 *    if either the parent or the child is <code>null</code>
	 */
	public int getIndexOfChild(Object parent, Object child) {
		if (parent == null || child == null)
			return -1;
		return ((TreeNode) parent).getIndex((TreeNode) child);
	}

	/**
	 * Returns the child of <I>parent</I> at index <I>index</I> in the parent's
	 * child array.  <I>parent</I> must be a node previously obtained from
	 * this data source. This should not return null if <i>index</i>
	 * is a valid index for <i>parent</i> (that is <i>index</i> >= 0 &&
	 * <i>index</i> < getChildCount(<i>parent</i>)).
	 *
	 * @param   parent  a node in the tree, obtained from this data source
	 * @return  the child of <I>parent</I> at index <I>index</I>
	 */
	public Object getChild(Object parent, int index) {
		if (parent instanceof TreeNode)
			return ((TreeNode) parent).getChildAt(index);
		return null;
	}

	/**
	 * Returns the number of children of <I>parent</I>.  Returns 0 if the node
	 * is a leaf or if it has no children.  <I>parent</I> must be a node
	 * previously obtained from this data source.
	 *
	 * @param   parent  a node in the tree, obtained from this data source
	 * @return  the number of children of the node <I>parent</I>
	 */
	public int getChildCount(Object parent) {
		if (parent instanceof TreeNode)
			return ((TreeNode) parent).getChildCount();
		return 0;
	}

	/**
	 * Returns whether the specified node is a leaf node.
	 * The way the test is performed depends on the.
	 *
	 * @param node the node to check
	 * @return true if the node is a leaf node
	 */
	public boolean isLeaf(Object node) {
		if (asksAllowsChildren && node instanceof TreeNode)
			return !((TreeNode) node).getAllowsChildren();
		return ((TreeNode) node).isLeaf();
	}

	//
	// Change Support
	//

	/**
	 * Inserts the <code>roots</code> and connections into the model.
	 * Notifies the model- and undo listeners of the change. The passed-in
	 * edits are executed if they implement the
	 * <code>GraphModelEvent.ExecutableGraphChange</code> interface
	 * in ascending array-order, after execution of the model change.
	 * (Note: The external order is important in a
	 * special case: After insertion on a partial view, ie. one that does not
	 * display all cells of the model, the cell is made visible after
	 * it is inserted into the model. This requires the inserting view
	 * to be able to add the cell to the visible set before it is
	 * inserted into the model.)
	 * Note: The passed-in propertyMap may contains PortViews
	 * which must be turned into Points when stored in the model.
	 */
	public void insert(
		Object[] roots,
		Map attributes,
		ConnectionSet cs,
		ParentMap pm,
		UndoableEdit[] edits) {
		GraphModelEdit edit =
			createInsertEdit(roots, attributes, cs, pm, edits);
		if (edit != null) {
			edit.execute();
			if (edits != null) {
				for (int i = 0; i < edits.length; i++)
					if (edits[i]
						instanceof GraphModelEvent.ExecutableGraphChange)
						((GraphModelEvent.ExecutableGraphChange) edits[i])
							.execute();
			}
			postEdit(edit);
		}
	}

	/**
	 * Removes <code>cells</code> from the model.
	 * Notifies the model- and undo listeners of the change.
	 */
	public void remove(Object[] roots) {
		GraphModelEdit edit = createRemoveEdit(roots);
		if (edit != null) {
			edit.execute();
			postEdit(edit);
		}
	}

	/**
	 * Applies <code>attributes</code> and the connection changes to
	 * the model. The initial <code>edits</code> that triggered the call
	 * are considered to be part of this transaction.  The passed-in
	 * edits are executed if they implement the
	 * <code>GraphModelEvent.ExecutableGraphChange</code> interface
	 * in ascending array-order, after execution of the model change.
	 * Notifies the model- and undo listeners of the change.
	 * <strong>Note:</strong> If only <code>edits</code> is non-null, the
	 * edits are directly passed to the UndoableEditListeners.
	 * Note: The passed-in propertyMap may contains PortViews
	 * which must be turned into Points when stored in the model.
	 */
	public void edit(
		Map attributes,
		ConnectionSet cs,
		ParentMap pm,
		UndoableEdit[] edits) {
		if ((attributes == null || attributes.isEmpty())
			&& (cs == null || cs.isEmpty())
			&& pm == null
			&& edits != null
			&& edits.length == 1) {
			if (edits[0] instanceof GraphModelEvent.ExecutableGraphChange)
				 ((GraphModelEvent.ExecutableGraphChange) edits[0]).execute();
			postEdit(edits[0]); // UndoableEdit Relay
		} else {
			GraphModelEdit edit = createCellEdit(attributes, cs, pm, edits);
			//System.out.println("DefaultGraphModel_edit_attributes="+attributes);
			if (edit != null) {