/**
 * Copyright (c) 2007, Gaudenz Alder
 */
package com.mxgraph.view;

import java.awt.Graphics;
import java.awt.Point;
import java.awt.Rectangle;
import java.awt.Shape;
import java.beans.PropertyChangeListener;
import java.beans.PropertyChangeSupport;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.logging.Level;
import java.util.logging.Logger;

import org.w3c.dom.Element;

import com.mxgraph.canvas.mxGraphics2DCanvas;
import com.mxgraph.canvas.mxICanvas;
import com.mxgraph.canvas.mxImageCanvas;
import com.mxgraph.model.mxCell;
import com.mxgraph.model.mxGeometry;
import com.mxgraph.model.mxGraphModel;
import com.mxgraph.model.mxGraphModel.Filter;
import com.mxgraph.model.mxGraphModel.mxChildChange;
import com.mxgraph.model.mxGraphModel.mxCollapseChange;
import com.mxgraph.model.mxGraphModel.mxGeometryChange;
import com.mxgraph.model.mxGraphModel.mxRootChange;
import com.mxgraph.model.mxGraphModel.mxStyleChange;
import com.mxgraph.model.mxGraphModel.mxTerminalChange;
import com.mxgraph.model.mxGraphModel.mxValueChange;
import com.mxgraph.model.mxGraphModel.mxVisibleChange;
import com.mxgraph.model.mxICell;
import com.mxgraph.model.mxIGraphModel;
import com.mxgraph.util.mxConstants;
import com.mxgraph.util.mxEvent;
import com.mxgraph.util.mxEventObject;
import com.mxgraph.util.mxEventSource;
import com.mxgraph.util.mxImageBundle;
import com.mxgraph.util.mxPoint;
import com.mxgraph.util.mxRectangle;
import com.mxgraph.util.mxResources;
import com.mxgraph.util.mxStyleUtils;
import com.mxgraph.util.mxUndoableEdit;
import com.mxgraph.util.mxUndoableEdit.mxUndoableChange;
import com.mxgraph.util.mxUtils;

/**
 * Implements a graph object that allows to create diagrams from a graph model
 * and stylesheet.
 * 
 * <h3>Images</h3>
 * To create an image from a graph, use the following code for a given
 * XML document (doc) and File (file):
 * 
 * <code>
 * Image img = mxCellRenderer.createBufferedImage(
 * 		graph, null, 1, Color.WHITE, false, null);
 * ImageIO.write(img, "png", file);
 * </code>
 * 
 * If the XML is given as a string rather than a document, the document can
 * be obtained using mxUtils.parse.
 * 
 * This class fires the following events:
 * 
 * mxEvent.ROOT fires if the root in the model has changed. This event has no
 * properties.
 * 
 * mxEvent.ALIGN_CELLS fires between begin- and endUpdate in alignCells. The
 * <code>cells</code> and <code>align</code> properties contain the respective
 * arguments that were passed to alignCells.
 * 
 * mxEvent.FLIP_EDGE fires between begin- and endUpdate in flipEdge. The
 * <code>edge</code> property contains the edge passed to flipEdge.
 * 
 * mxEvent.ORDER_CELLS fires between begin- and endUpdate in orderCells. The
 * <code>cells</code> and <code>back</code> properties contain the respective
 * arguments that were passed to orderCells.
 *
 * mxEvent.CELLS_ORDERED fires between begin- and endUpdate in cellsOrdered.
 * The <code>cells</code> and <code>back</code> arguments contain the
 * respective arguments that were passed to cellsOrdered.
 * 
 * mxEvent.GROUP_CELLS fires between begin- and endUpdate in groupCells. The
 * <code>group</code>, <code>cells</code> and <code>border</code> arguments
 * contain the respective arguments that were passed to groupCells.
 * 
 * mxEvent.UNGROUP_CELLS fires between begin- and endUpdate in ungroupCells.
 * The <code>cells</code> property contains the array of cells that was passed
 * to ungroupCells.
 * 
 * mxEvent.REMOVE_CELLS_FROM_PARENT fires between begin- and endUpdate in
 * removeCellsFromParent. The <code>cells</code> property contains the array of
 * cells that was passed to removeCellsFromParent.
 * 
 * mxEvent.ADD_CELLS fires between begin- and endUpdate in addCells. The
 * <code>cells</code>, <code>parent</code>, <code>index</code>,
 * <code>source</code> and <code>target</code> properties contain the
 * respective arguments that were passed to addCells.
 * 
 * mxEvent.CELLS_ADDED fires between begin- and endUpdate in cellsAdded. The
 * <code>cells</code>, <code>parent</code>, <code>index</code>,
 * <code>source</code>, <code>target</code> and <code>absolute</code>
 * properties contain the respective arguments that were passed to cellsAdded.
 * 
 * mxEvent.REMOVE_CELLS fires between begin- and endUpdate in removeCells. The
 * <code>cells</code> and <code>includeEdges</code> arguments contain the
 * respective arguments that were passed to removeCells.
 * 
 * mxEvent.CELLS_REMOVED fires between begin- and endUpdate in cellsRemoved.
 * The <code>cells</code> argument contains the array of cells that was
 * removed.
 * 
 * mxEvent.SPLIT_EDGE fires between begin- and endUpdate in splitEdge. The
 * <code>edge</code> property contains the edge to be splitted, the
 * <code>cells</code>, <code>newEdge</code>, <code>dx</code> and
 * <code>dy</code> properties contain the respective arguments that were passed
 * to splitEdge.
 * 
 * mxEvent.TOGGLE_CELLS fires between begin- and endUpdate in toggleCells. The
 * <code>show</code>, <code>cells</code> and <code>includeEdges</code>
 * properties contain the respective arguments that were passed to toggleCells.
 * 
 * mxEvent.FOLD_CELLS fires between begin- and endUpdate in foldCells. The
 * <code>collapse</code>, <code>cells</code> and <code>recurse</code>
 * properties contain the respective arguments that were passed to foldCells.
 * 
 * mxEvent.CELLS_FOLDED fires between begin- and endUpdate in cellsFolded. The
 * <code>collapse</code>, <code>cells</code> and <code>recurse</code>
 * properties contain the respective arguments that were passed to cellsFolded.
 * 
 * mxEvent.UPDATE_CELL_SIZE fires between begin- and endUpdate in
 * updateCellSize. The <code>cell</code> and <code>ignoreChildren</code>
 * properties contain the respective arguments that were passed to
 * updateCellSize.
 * 
 * mxEvent.RESIZE_CELLS fires between begin- and endUpdate in resizeCells. The
 * <code>cells</code> and <code>bounds</code> properties contain the respective
 * arguments that were passed to resizeCells.
 * 
 * mxEvent.CELLS_RESIZED fires between begin- and endUpdate in cellsResized.
 * The <code>cells</code> and <code>bounds</code> properties contain the
 * respective arguments that were passed to cellsResized.
 * 
 * mxEvent.MOVE_CELLS fires between begin- and endUpdate in moveCells. The
 * <code>cells</code>, <code>dx</code>, <code>dy</code>, <code>clone</code>,
 * <code>target</code> and <code>location</code> properties contain the
 * respective arguments that were passed to moveCells.
 * 
 * mxEvent.CELLS_MOVED fires between begin- and endUpdate in cellsMoved. The
 * <code>cells</code>, <code>dx</code>, <code>dy</code> and
 * <code>disconnect</code> properties contain the respective arguments that
 * were passed to cellsMoved.
 * 
 * mxEvent.CONNECT_CELL fires between begin- and endUpdate in connectCell. The
 * <code>edge</code>, <code>terminal</code> and <code>source</code> properties
 * contain the respective arguments that were passed to connectCell.
 * 
 * mxEvent.CELL_CONNECTED fires between begin- and endUpdate in cellConnected.
 * The <code>edge</code>, <code>terminal</code> and <code>source</code>
 * properties contain the respective arguments that were passed to
 * cellConnected.
 * 
 * mxEvent.REPAINT fires if a repaint was requested by calling repaint. The
 * <code>region</code> property contains the optional mxRectangle that was
 * passed to repaint to define the dirty region.
 */
public class mxGraph extends mxEventSource
{

	private static final Logger log = Logger.getLogger(mxGraph.class.getName());

	/**
	 * Adds required resources.
	 */
	static
	{
		try
		{
			mxResources.add("com.mxgraph.resources.graph");
		}
		catch (Exception e)
		{
			log.log(Level.SEVERE, "Failed to add the resource bundle", e);
		}
	}

	/**
	 * Holds the version number of this release. Current version
	 * is 4.0.0.
	 */
	public static final String VERSION = "4.0.0";

	/**
	 * 
	 */
	public interface mxICellVisitor
	{

		/**
		 * 
		 * @param vertex
		 * @param edge
		 */
		boolean visit(Object vertex, Object edge);

	}

	/**
	 * Property change event handling.
	 */
	protected PropertyChangeSupport changeSupport = new PropertyChangeSupport(
			this);

	/**
	 * Holds the model that contains the cells to be displayed.
	 */
	protected mxIGraphModel model;

	/**
	 * Holds the view that caches the cell states.
	 */
	protected mxGraphView view;

	/**
	 * Holds the stylesheet that defines the appearance of the cells.
	 */
	protected mxStylesheet stylesheet;

	/**
	 * Holds the <mxGraphSelection> that models the current selection.
	 */
	protected mxGraphSelectionModel selectionModel;

	/**
	 * Specifies the grid size. Default is 10.
	 */
	protected int gridSize = 10;

	/**
	 * Specifies if the grid is enabled. Default is true.
	 */
	protected boolean gridEnabled = true;

	/**
	 * Specifies if ports are enabled. This is used in <cellConnected> to update
	 * the respective style. Default is true.
	 */
	protected boolean portsEnabled = true;

	/**
	 * Value returned by getOverlap if isAllowOverlapParent returns
	 * true for the given cell. getOverlap is used in keepInside if
	 * isKeepInsideParentOnMove returns true. The value specifies the
	 * portion of the child which is allowed to overlap the parent.
	 */
	protected double defaultOverlap = 0.5;

	/**
	 * Specifies the default parent to be used to insert new cells.
	 * This is used in getDefaultParent. Default is null.
	 */
	protected Object defaultParent;

	/**
	 * Specifies the alternate edge style to be used if the main control point
	 * on an edge is being doubleclicked. Default is null.
	 */
	protected String alternateEdgeStyle;

	/**
	 * Specifies the return value for isEnabled. Default is true.
	 */
	protected boolean enabled = true;

	/**
	 * Specifies the return value for isCell(s)Locked. Default is false.
	 */
	protected boolean cellsLocked = false;

	/**
	 * Specifies the return value for isCell(s)Editable. Default is true.
	 */
	protected boolean cellsEditable = true;

	/**
	 * Specifies the return value for isCell(s)Sizable. Default is true.
	 */
	protected boolean cellsResizable = true;

	/**
	 * Specifies the return value for isCell(s)Movable. Default is true.
	 */
	protected boolean cellsMovable = true;

	/**
	 * Specifies the return value for isCell(s)Bendable. Default is true.
	 */
	protected boolean cellsBendable = true;

	/**
	 * Specifies the return value for isCell(s)Selectable. Default is true.
	 */
	protected boolean cellsSelectable = true;

	/**
	 * Specifies the return value for isCell(s)Deletable. Default is true.
	 */
	protected boolean cellsDeletable = true;

	/**
	 * Specifies the return value for isCell(s)Cloneable. Default is true.
	 */
	protected boolean cellsCloneable = true;

	/**
	 * Specifies the return value for isCellDisconntableFromTerminal. Default
	 * is true.
	 */
	protected boolean cellsDisconnectable = true;

	/**
	 * Specifies the return value for isLabel(s)Clipped. Default is false.
	 */
	protected boolean labelsClipped = false;

	/**
	 * Specifies the return value for edges in isLabelMovable. Default is true.
	 */
	protected boolean edgeLabelsMovable = true;

	/**
	 * Specifies the return value for vertices in isLabelMovable. Default is false.
	 */
	protected boolean vertexLabelsMovable = false;

	/**
	 * Specifies the return value for isDropEnabled. Default is true.
	 */
	protected boolean dropEnabled = true;

	/**
	 * Specifies if dropping onto edges should be enabled. Default is true.
	 */
	protected boolean splitEnabled = true;

	/**
	 * Specifies if the graph should automatically update the cell size
	 * after an edit. This is used in isAutoSizeCell. Default is false.
	 */
	protected boolean autoSizeCells = false;

	/**
	 * <mxRectangle> that specifies the area in which all cells in the
	 * diagram should be placed. Uses in getMaximumGraphBounds. Use a width
	 * or height of 0 if you only want to give a upper, left corner.
	 */
	protected mxRectangle maximumGraphBounds = null;

	/**
	 * mxRectangle that specifies the minimum size of the graph canvas inside
	 * the scrollpane.
	 */
	protected mxRectangle minimumGraphSize = null;

	/**
	 * Border to be added to the bottom and right side when the container is
	 * being resized after the graph has been changed. Default is 0.
	 */
	protected int border = 0;

	/**
	 * Specifies if edges should appear in the foreground regardless of their
	 * order in the model. This has precendence over keepEdgeInBackground
	 * Default is false.
	 */
	protected boolean keepEdgesInForeground = false;

	/**
	 * Specifies if edges should appear in the background regardless of their
	 * order in the model. Default is false.
	 */
	protected boolean keepEdgesInBackground = false;

	/**
	 * Specifies if the cell size should be changed to the preferred size when
	 * a cell is first collapsed. Default is true.
	 */
	protected boolean collapseToPreferredSize = true;

	/**
	 * Specifies if negative coordinates for vertices are allowed. Default is true.
	 */
	protected boolean allowNegativeCoordinates = true;

	/**
	 * Specifies the return value for isConstrainChildren. Default is true.
	 */
	protected boolean constrainChildren = true;

	/**
	 * Specifies if a parent should contain the child bounds after a resize of
	 * the child. Default is true.
	 */
	protected boolean extendParents = true;

	/**
	 * Specifies if parents should be extended according to the <extendParents>
	 * switch if cells are added. Default is true.
	 */
	protected boolean extendParentsOnAdd = true;

	/**
	 * Specifies if the scale and translate should be reset if
	 * the root changes in the model. Default is true.
	 */
	protected boolean resetViewOnRootChange = true;

	/**
	 * Specifies if loops (aka self-references) are allowed.
	 * Default is false.
	 */
	protected boolean resetEdgesOnResize = false;

	/**
	 * Specifies if edge control points should be reset after
	 * the move of a connected cell. Default is false.
	 */
	protected boolean resetEdgesOnMove = false;

	/**
	 * Specifies if edge control points should be reset after
	 * the the edge has been reconnected. Default is true.
	 */
	protected boolean resetEdgesOnConnect = true;

	/**
	 * Specifies if loops (aka self-references) are allowed.
	 * Default is false.
	 */
	protected boolean allowLoops = false;

	/**
	 * Specifies the multiplicities to be used for validation of the graph.
	 */
	protected mxMultiplicity[] multiplicities;

	/**
	 * Specifies the default style for loops.
	 */
	protected mxEdgeStyle.mxEdgeStyleFunction defaultLoopStyle = mxEdgeStyle.Loop;

	/**
	 * Specifies if multiple edges in the same direction between
	 * the same pair of vertices are allowed. Default is true.
	 */
	protected boolean multigraph = true;

	/**
	 * Specifies if edges are connectable. Default is false.
	 * This overrides the connectable field in edges.
	 */
	protected boolean connectableEdges = false;

	/**
	 * Specifies if edges with disconnected terminals are
	 * allowed in the graph. Default is false.
	 */
	protected boolean allowDanglingEdges = true;

	/**
	 * Specifies if edges that are cloned should be validated and only inserted
	 * if they are valid. Default is true.
	 */
	protected boolean cloneInvalidEdges = false;

	/**
	 * Specifies if edges should be disconnected from their terminals when they
	 * are moved. Default is true.
	 */
	protected boolean disconnectOnMove = true;

	/**
	 * Specifies if labels should be visible. This is used in
	 * getLabel. Default is true.
	 */
	protected boolean labelsVisible = true;

	/**
	 * Specifies the return value for isHtmlLabel. Default is false.
	 */
	protected boolean htmlLabels = false;

	/**
	 * Specifies if nesting of swimlanes is allowed. Default is true.
	 */
	protected boolean swimlaneNesting = true;

	/**
	 * Specifies the maximum number of changes that should be processed to find
	 * the dirty region. If the number of changes is larger, then the complete
	 * grah is repainted. A value of zero will always compute the dirty region
	 * for any number of changes. Default is 1000.
	 */
	protected int changesRepaintThreshold = 1000;

	/**
	 * Specifies if the origin should be automatically updated. 
	 */
	protected boolean autoOrigin = false;

	/**
	 * Holds the current automatic origin.
	 */
	protected mxPoint origin = new mxPoint();

	/**
	 * Holds the list of bundles.
	 */
	protected static List<mxImageBundle> imageBundles = new LinkedList<mxImageBundle>();

	/**
	 * Fires repaint events for full repaints.
	 */
	protected mxIEventListener fullRepaintHandler = new mxIEventListener()
	{
		public void invoke(Object sender, mxEventObject evt)
		{
			repaint();
		}
	};

	/**
	 * Fires repaint events for full repaints.
	 */
	protected mxIEventListener updateOriginHandler = new mxIEventListener()
	{
		public void invoke(Object sender, mxEventObject evt)
		{
			if (isAutoOrigin())
			{
				updateOrigin();
			}
		}
	};

	/**
	 * Fires repaint events for model changes.
	 */
	protected mxIEventListener graphModelChangeHandler = new mxIEventListener()
	{
		public void invoke(Object sender, mxEventObject evt)
		{
			mxRectangle dirty = graphModelChanged((mxIGraphModel) sender,
					(List<mxUndoableChange>) ((mxUndoableEdit) evt
							.getProperty("edit")).getChanges());
			repaint(dirty);
		}
	};

	/**
	 * Constructs a new graph with an empty
	 * {@link com.mxgraph.model.mxGraphModel}.
	 */
	public mxGraph()
	{
		this(null, null);
	}

	/**
	 * Constructs a new graph for the specified model. If no model is
	 * specified, then a new, empty {@link com.mxgraph.model.mxGraphModel} is
	 * used.
	 * 
	 * @param model Model that contains the graph data
	 */
	public mxGraph(mxIGraphModel model)
	{
		this(model, null);
	}

	/**
	 * Constructs a new graph for the specified model. If no model is
	 * specified, then a new, empty {@link com.mxgraph.model.mxGraphModel} is
	 * used.
	 * 
	 * @param stylesheet The stylesheet to use for the graph.
	 */
	public mxGraph(mxStylesheet stylesheet)
	{
		this(null, stylesheet);
	}

	/**
	 * Constructs a new graph for the specified model. If no model is
	 * specified, then a new, empty {@link com.mxgraph.model.mxGraphModel} is
	 * used.
	 * 
	 * @param model Model that contains the graph data
	 */
	public mxGraph(mxIGraphModel model, mxStylesheet stylesheet)
	{
		selectionModel = createSelectionModel();
		setModel((model != null) ? model : new mxGraphModel());
		setStylesheet((stylesheet != null) ? stylesheet : createStylesheet());
		setView(createGraphView());
	}

	/**
	 * Constructs a new selection model to be used in this graph.
	 */
	protected mxGraphSelectionModel createSelectionModel()
	{
		return new mxGraphSelectionModel(this);
	}

	/**
	 * Constructs a new stylesheet to be used in this graph.
	 */
	protected mxStylesheet createStylesheet()
	{
		return new mxStylesheet();
	}

	/**
	 * Constructs a new view to be used in this graph.
	 */
	protected mxGraphView createGraphView()
	{
		return new mxGraphView(this);
	}

	/**
	 * Returns the graph model that contains the graph data.
	 * 
	 * @return Returns the model that contains the graph data
	 */
	public mxIGraphModel getModel()
	{
		return model;
	}

	/**
	 * Sets the graph model that contains the data, and fires an
	 * mxEvent.CHANGE followed by an mxEvent.REPAINT event.
	 * 
	 * @param value Model that contains the graph data
	 */
	public void setModel(mxIGraphModel value)
	{
		if (model != null)
		{
			model.removeListener(graphModelChangeHandler);
		}

		Object oldModel = model;
		model = value;

		if (view != null)
		{
			view.revalidate();
		}

		model.addListener(mxEvent.CHANGE, graphModelChangeHandler);
		changeSupport.firePropertyChange("model", oldModel, model);
		repaint();
	}

	/**
	 * Returns the view that contains the cell states.
	 * 
	 * @return Returns the view that contains the cell states
	 */
	public mxGraphView getView()
	{
		return view;
	}

	/**
	 * Sets the view that contains the cell states.
	 * 
	 * @param value View that contains the cell states
	 */
	public void setView(mxGraphView value)
	{
		if (view != null)
		{
			view.removeListener(fullRepaintHandler);
			view.removeListener(updateOriginHandler);
		}

		Object oldView = view;
		view = value;

		if (view != null)
		{
			view.revalidate();
		}

		// Listens to changes in the view
		view.addListener(mxEvent.SCALE, fullRepaintHandler);
		view.addListener(mxEvent.SCALE, updateOriginHandler);
		view.addListener(mxEvent.TRANSLATE, fullRepaintHandler);
		view.addListener(mxEvent.SCALE_AND_TRANSLATE, fullRepaintHandler);
		view.addListener(mxEvent.SCALE_AND_TRANSLATE, updateOriginHandler);
		view.addListener(mxEvent.UP, fullRepaintHandler);
		view.addListener(mxEvent.DOWN, fullRepaintHandler);

		changeSupport.firePropertyChange("view", oldView, view);
	}

	/**
	 * Returns the stylesheet that provides the style.
	 * 
	 * @return Returns the stylesheet that provides the style.
	 */
	public mxStylesheet getStylesheet()
	{
		return stylesheet;
	}

	/**
	 * Sets the stylesheet that provides the style.
	 * 
	 * @param value Stylesheet that provides the style.
	 */
	public void setStylesheet(mxStylesheet value)
	{
		mxStylesheet oldValue = stylesheet;
		stylesheet = value;

		changeSupport.firePropertyChange("stylesheet", oldValue, stylesheet);
	}

	/**
	 * Returns the cells to be selected for the given list of changes.
	 */
	public void addTopmostVerticesAndEdges(Object cell, List<Object> cells)
	{
		if (!cells.contains(cell) && model.contains(cell))
		{
			if (model.isVertex(cell) || model.isEdge(cell))
			{
				cells.add(cell);
			}
			else
			{
				int childCount = model.getChildCount(cell);
				
				for (int i = 0; i < childCount; i++)
				{
					addTopmostVerticesAndEdges(model.getChildAt(cells, i), cells);
				}
			}
		}
	};
	
	/**
	 * Returns the cells to be selected for the given list of changes.
	 */
	public Object[] getSelectionCellsForChanges(List<mxUndoableChange> changes)
	{
		List<Object> cells = new ArrayList<Object>();
		Iterator<mxUndoableChange> it = changes.iterator();

		while (it.hasNext())
		{
			Object change = it.next();

			if (change instanceof mxChildChange)
			{
				addTopmostVerticesAndEdges(((mxChildChange) change).getChild(), cells);
			}
			else if (change instanceof mxTerminalChange)
			{
				addTopmostVerticesAndEdges(((mxTerminalChange) change).getCell(), cells);
			}
			else if (change instanceof mxValueChange)
			{
				addTopmostVerticesAndEdges(((mxValueChange) change).getCell(), cells);
			}
			else if (change instanceof mxStyleChange)
			{
				addTopmostVerticesAndEdges(((mxStyleChange) change).getCell(), cells);
			}
			else if (change instanceof mxGeometryChange)
			{
				addTopmostVerticesAndEdges(((mxGeometryChange) change).getCell(), cells);
			}
			else if (change instanceof mxCollapseChange)
			{
				addTopmostVerticesAndEdges(((mxCollapseChange) change).getCell(), cells);
			}
			else if (change instanceof mxVisibleChange)
			{
				mxVisibleChange vc = (mxVisibleChange) change;

				if (vc.isVisible())
				{
					addTopmostVerticesAndEdges(((mxVisibleChange) change).getCell(), cells);
				}
			}
		}

		return cells.toArray();
	}

	/**
	 * Called when the graph model changes. Invokes processChange on each
	 * item of the given array to update the view accordingly.
	 */
	public mxRectangle graphModelChanged(mxIGraphModel sender,
			List<mxUndoableChange> changes)
	{
		int thresh = getChangesRepaintThreshold();
		boolean ignoreDirty = thresh > 0 && changes.size() > thresh;

		// Ignores dirty rectangle if there was a root change
		if (!ignoreDirty)
		{
			Iterator<mxUndoableChange> it = changes.iterator();

			while (it.hasNext())
			{
				if (it.next() instanceof mxRootChange)
				{
					ignoreDirty = true;
					break;
				}
			}
		}

		mxRectangle dirty = processChanges(changes, true, ignoreDirty);
		view.validate();

		if (isAutoOrigin())
		{
			updateOrigin();
		}

		if (!ignoreDirty)
		{
			mxRectangle tmp = processChanges(changes, false, ignoreDirty);

			if (tmp != null)
			{
				if (dirty == null)
				{
					dirty = tmp;
				}
				else
				{
					dirty.add(tmp);
				}
			}
		}

		updateSelection();

		return dirty;
	}
	
	/**
	 * Function: updateSelection
	 * 
	 * Removes selection cells that are not in the model from the selection.
	 */
	protected void updateSelection()
	{
		Object[] cells = getSelectionCells();
		List<Object> removed = new ArrayList<Object>();
		
		for (int i = 0; i < cells.length; i++)
		{
			if (!model.contains(cells[i]))
			{
				removed.add(cells[i]);
			}
		}
		
		removeSelectionCells(removed.toArray());
	}

	/**
	 * Extends the canvas by doing another validation with a shifted
	 * global translation if the bounds of the graph are below (0,0).
	 * 
	 * The first validation is required to compute the bounds of the graph
	 * while the second validation is required to apply the new translate.
	 */
	protected void updateOrigin()
	{
		mxRectangle bounds = getGraphBounds();

		if (bounds != null)
		{
			double scale = getView().getScale();
			double x = bounds.getX() / scale - getBorder();
			double y = bounds.getY() / scale - getBorder();

			if (x < 0 || y < 0)
			{
				double x0 = Math.min(0, x);
				double y0 = Math.min(0, y);

				origin.setX(origin.getX() + x0);
				origin.setY(origin.getY() + y0);

				mxPoint t = getView().getTranslate();
				getView().setTranslate(
						new mxPoint(t.getX() - x0, t.getY() - y0));
			}
			else if ((x > 0 || y > 0)
					&& (origin.getX() < 0 || origin.getY() < 0))
			{
				double dx = Math.min(-origin.getX(), x);
				double dy = Math.min(-origin.getY(), y);

				origin.setX(origin.getX() + dx);
				origin.setY(origin.getY() + dy);

				mxPoint t = getView().getTranslate();
				getView().setTranslate(
						new mxPoint(t.getX() - dx, t.getY() - dy));
			}
		}
	}

	/**
	 * Processes the changes and returns the minimal rectangle to be
	 * repainted in the buffer. A return value of null means no repaint
	 * is required.
	 */
	public mxRectangle processChanges(List<mxUndoableChange> changes,
			boolean invalidate, boolean ignoreDirty)
	{
		mxRectangle bounds = null;
		Iterator<mxUndoableChange> it = changes.iterator();

		while (it.hasNext())
		{
			mxRectangle rect = processChange(it.next(), invalidate,
					ignoreDirty);

			if (bounds == null)
			{
				bounds = rect;
			}
			else
			{
				bounds.add(rect);
			}
		}

		return bounds;
	}

	/**
	 * Processes the given change and invalidates the respective cached data
	 * in <view>. This fires a <root> event if the root has changed in the
	 * model.
	 */
	public mxRectangle processChange(mxUndoableChange change,
			boolean invalidate, boolean ignoreDirty)
	{
		mxRectangle result = null;

		if (change instanceof mxRootChange)
		{
			result = (ignoreDirty) ? null : getGraphBounds();

			if (invalidate)
			{
				clearSelection();
				removeStateForCell(((mxRootChange) change).getPrevious());

				if (isResetViewOnRootChange())
				{
					view.setEventsEnabled(false);

					try
					{
						view.scaleAndTranslate(1, 0, 0);
					}
					finally
					{
						view.setEventsEnabled(true);
					}
				}

			}

			fireEvent(new mxEventObject(mxEvent.ROOT));
		}
		else if (change instanceof mxChildChange)
		{
			mxChildChange cc = (mxChildChange) change;

			// Repaints the parent area if it is a rendered cell (vertex or
			// edge) otherwise only the child area is repainted, same holds
			// if the parent and previous are the same object, in which case
			// only the child area needs to be repainted (change of order)
			if (!ignoreDirty)
			{
				if (cc.getParent() != cc.getPrevious())
				{
					if (model.isVertex(cc.getParent())
							|| model.isEdge(cc.getParent()))
					{
						result = getBoundingBox(cc.getParent(), true, true);
					}

					if (model.isVertex(cc.getPrevious())
							|| model.isEdge(cc.getPrevious()))
					{
						if (result != null)
						{
							result.add(getBoundingBox(cc.getPrevious(), true,
									true));
						}
						else
						{
							result = getBoundingBox(cc.getPrevious(), true,
									true);
						}
					}
				}

				if (result == null)
				{
					result = getBoundingBox(cc.getChild(), true, true);
				}
			}

			if (invalidate)
			{
				if (model.contains(cc.getParent()))
				{
					view.clear(cc.getChild(), false, true);
				}
				else
				{
					removeStateForCell(cc.getChild());
				}
			}
		}
		else if (change instanceof mxTerminalChange)
		{
			Object cell = ((mxTerminalChange) change).getCell();

			if (!ignoreDirty)
			{
				result = getBoundingBox(cell, true);
			}

			if (invalidate)
			{
				view.invalidate(cell);
			}
		}
		else if (change instanceof mxValueChange)
		{
			Object cell = ((mxValueChange) change).getCell();

			if (!ignoreDirty)
			{
				result = getBoundingBox(cell);
			}

			if (invalidate)
			{
				view.clear(cell, false, false);
			}
		}
		else if (change instanceof mxStyleChange)
		{
			Object cell = ((mxStyleChange) change).getCell();

			if (!ignoreDirty)
			{
				result = getBoundingBox(cell, true);
			}

			if (invalidate)
			{
				// TODO: Add includeEdges argument to clear method for
				// not having to call invalidate in this case (where it
				// is possible that the perimeter has changed, which
				// means the connected edges need to be invalidated)
				view.clear(cell, false, false);
				view.invalidate(cell);
			}
		}
		else if (change instanceof mxGeometryChange)
		{
			Object cell = ((mxGeometryChange) change).getCell();

			if (!ignoreDirty)
			{
				result = getBoundingBox(cell, true, true);
			}

			if (invalidate)
			{
				view.invalidate(cell);
			}
		}
		else if (change instanceof mxCollapseChange)
		{
			Object cell = ((mxCollapseChange) change).getCell();

			if (!ignoreDirty)
			{
				result = getBoundingBox(((mxCollapseChange) change).getCell(),
						true, true);
			}

			if (invalidate)
			{
				removeStateForCell(cell);
			}
		}
		else if (change instanceof mxVisibleChange)
		{
			Object cell = ((mxVisibleChange) change).getCell();

			if (!ignoreDirty)
			{
				result = getBoundingBox(((mxVisibleChange) change).getCell(),
						true, true);
			}

			if (invalidate)
			{
				removeStateForCell(cell);
			}
		}

		return result;
	}

	/**
	 * Removes all cached information for the given cell and its descendants.
	 * This is called when a cell was removed from the model.
	 * 
	 * @param cell Cell that was removed from the model.
	 */
	protected void removeStateForCell(Object cell)
	{
		int childCount = model.getChildCount(cell);

		for (int i = 0; i < childCount; i++)
		{
			removeStateForCell(model.getChildAt(cell, i));
		}

		view.invalidate(cell);
		view.removeState(cell);
	}

	//
	// Cell styles
	//

	/**
	 * Returns an array of key, value pairs representing the cell style for the
	 * given cell. If no string is defined in the model that specifies the
	 * style, then the default style for the cell is returned or <EMPTY_ARRAY>,
	 * if not style can be found.
	 * 
	 * @param cell Cell whose style should be returned.
	 * @return Returns the style of the cell.
	 */
	public Map<String, Object> getCellStyle(Object cell)
	{
		Map<String, Object> style = (model.isEdge(cell))
				? stylesheet.getDefaultEdgeStyle()
				: stylesheet.getDefaultVertexStyle();

		String name = model.getStyle(cell);

		if (name != null)
		{
			style = postProcessCellStyle(stylesheet.getCellStyle(name, style));
		}

		if (style == null)
		{
			style = mxStylesheet.EMPTY_STYLE;
		}

		return style;
	}

	/**
	 * Tries to resolve the value for the image style in the image bundles and
	 * turns short data URIs as defined in mxImageBundle to data URIs as
	 * defined in RFC 2397 of the IETF.
	 */
	protected Map<String, Object> postProcessCellStyle(
			Map<String, Object> style)
	{
		if (style != null)
		{
			String key = mxUtils.getString(style, mxConstants.STYLE_IMAGE);
			String image = getImageFromBundles(key);

			if (image != null)
			{
				style.put(mxConstants.STYLE_IMAGE, image);
			}
			else
			{
				image = key;
			}

			// Converts short data uris to normal data uris
			if (image != null && image.startsWith("data:image/"))
			{
				int comma = image.indexOf(',');

				if (comma > 0)
				{
					image = image.substring(0, comma) + ";base64,"
							+ image.substring(comma + 1);
				}

				style.put(mxConstants.STYLE_IMAGE, image);
			}
		}

		return style;
	}

	/**
	 * Sets the style of the selection cells to the given value.
	 * 
	 * @param style String representing the new style of the cells.
	 */
