/**

* $Id: mxGraphModel.java,v 1.93 2012/04/16 10:49:24 david Exp $

* Copyright (c) 2007, Gaudenz Alder

*/

package com.mxgraph.model;

import java.io.IOException;

import java.io.ObjectInputStream;

import java.io.Serializable;

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.List;

import java.util.Map;

import java.util.Set;

import com.mxgraph.util.mxEvent;

import com.mxgraph.util.mxEventObject;

import com.mxgraph.util.mxEventSource;

import com.mxgraph.util.mxPoint;

import com.mxgraph.util.mxUndoableEdit;

/**

* Extends mxEventSource to implement a graph model. The graph model acts as

* a wrapper around the cells which are in charge of storing the actual graph

* datastructure. The model acts as a transactional wrapper with event

* notification for all changes, whereas the cells contain the atomic

* operations for updating the actual datastructure.

*

* Layers:

*

* The cell hierarchy in the model must have a top-level root cell which

* contains the layers (typically one default layer), which in turn contain the

* top-level cells of the layers. This means each cell is contained in a layer.

* If no layers are required, then all new cells should be added to the default

* layer.

*

* Layers are useful for hiding and showing groups of cells, or for placing

* groups of cells on top of other cells in the display. To identify a layer,

* the <isLayer> function is used. It returns true if the parent of the given

* cell is the root of the model.

*

* This class fires the following events:

*

* mxEvent.CHANGE fires when an undoable edit is dispatched. The <code>edit</code>

* property contains the mxUndoableEdit. The <code>changes</code> property

* contains the list of undoable changes inside the undoable edit. The changes

* property is deprecated, please use edit.getChanges() instead.

*

* mxEvent.EXECUTE fires between begin- and endUpdate and after an atomic

* change was executed in the model. The <code>change</code> property contains

* the atomic change that was executed.

*

* mxEvent.BEGIN_UPDATE fires after the updateLevel was incremented in

* beginUpdate. This event contains no properties.

*

* mxEvent.END_UPDATE fires after the updateLevel was decreased in endUpdate

* but before any notification or change dispatching. The <code>edit</code>

* property contains the current mxUndoableEdit.

*

* mxEvent.BEFORE_UNDO fires before the change is dispatched after the update

* level has reached 0 in endUpdate. The <code>edit</code> property contains

* the current mxUndoableEdit.

*

* mxEvent.UNDO fires after the change was dispatched in endUpdate. The

* <code>edit</code> property contains the current mxUndoableEdit.

*/

public class mxGraphModel extends mxEventSource implements mxIGraphModel,

Serializable

{

/**

* Holds the root cell, which in turn contains the cells that represent the

* layers of the diagram as child cells. That is, the actual element of the

* diagram are supposed to live in the third generation of cells and below.

*/

protected mxICell root;

/**

* Maps from Ids to cells.

*/

protected Map<String, Object> cells;

/**

* Specifies if edges should automatically be moved into the nearest common

* ancestor of their terminals. Default is true.

*/

protected boolean maintainEdgeParent = true;

/**

* Specifies if the model should automatically create Ids for new cells.

* Default is true.

*/

protected boolean createIds = true;

/**

* Specifies the next Id to be created. Initial value is 0.

*/

protected int nextId = 0;

/**

* Holds the changes for the current transaction. If the transaction is

* closed then a new object is created for this variable using

* createUndoableEdit.

*/

protected transient mxUndoableEdit currentEdit;

/**

* Counter for the depth of nested transactions. Each call to beginUpdate

* increments this counter and each call to endUpdate decrements it. When

* the counter reaches 0, the transaction is closed and the respective

* events are fired. Initial value is 0.

*/

protected transient int updateLevel = 0;

/**

*

*/

protected transient boolean endingUpdate = false;

/**

* Constructs a new empty graph model.

*/

public mxGraphModel()

{

this(null);

}

/**

* Constructs a new graph model. If no root is specified

* then a new root mxCell with a default layer is created.

*

* @param root Cell that represents the root cell.

*/

public mxGraphModel(Object root)

{

currentEdit = createUndoableEdit();

if (root != null)

{

setRoot(root);

}

else

{

clear();

}

}

/**

* Sets a new root using createRoot.

*/

public void clear()

{

setRoot(createRoot());

}

/**

*

*/

public int getUpdateLevel()

{

return updateLevel;

}

/**

* Creates a new root cell with a default layer (child 0).

*/

public Object createRoot()

{

mxCell root = new mxCell();

root.insert(new mxCell());

return root;

}

/**

* Returns the internal lookup table that is used to map from Ids to cells.

*/

public Map<String, Object> getCells()

{

return cells;

}

/**

* Returns the cell for the specified Id or null if no cell can be

* found for the given Id.

*

* @param id A string representing the Id of the cell.

* @return Returns the cell for the given Id.

*/

public Object getCell(String id)

{

Object result = null;

if (cells != null)

{

result = cells.get(id);

}

return result;

}

/**

* Returns true if the model automatically update parents of edges so that

* the edge is contained in the nearest-common-ancestor of its terminals.

*

* @return Returns true if the model maintains edge parents.

*/

public boolean isMaintainEdgeParent()

{

return maintainEdgeParent;

}

/**

* Specifies if the model automatically updates parents of edges so that

* the edge is contained in the nearest-common-ancestor of its terminals.

*

* @param maintainEdgeParent Boolean indicating if the model should

* maintain edge parents.

*/

public void setMaintainEdgeParent(boolean maintainEdgeParent)

{

this.maintainEdgeParent = maintainEdgeParent;

}

/**

* Returns true if the model automatically creates Ids and resolves Id

* collisions.

*

* @return Returns true if the model creates Ids.

*/

public boolean isCreateIds()

{

return createIds;

}

/**

* Specifies if the model automatically creates Ids for new cells and

* resolves Id collisions.

*

* @param value Boolean indicating if the model should created Ids.

*/

public void setCreateIds(boolean value)

{

createIds = value;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#getRoot()

*/

public Object getRoot()

{

return root;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#setRoot(Object)

*/

public Object setRoot(Object root)

{

execute(new mxRootChange(this, root));

return root;

}

/**

* Inner callback to change the root of the model and update the internal

* datastructures, such as cells and nextId. Returns the previous root.

*/

protected Object rootChanged(Object root)

{

Object oldRoot = this.root;

this.root = (mxICell) root;

// Resets counters and datastructures

nextId = 0;

cells = null;

cellAdded(root);

return oldRoot;

}

/**

* Creates a new undoable edit.

*/

protected mxUndoableEdit createUndoableEdit()

{

return new mxUndoableEdit(this)

{

public void dispatch()

{

// LATER: Remove changes property (deprecated)

((mxGraphModel) source).fireEvent(new mxEventObject(

mxEvent.CHANGE, "edit", this, "changes", changes));

}

};

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#cloneCells(Object[], boolean)

*/

public Object[] cloneCells(Object[] cells, boolean includeChildren)

{

Map<Object, Object> mapping = new Hashtable<Object, Object>();

Object[] clones = new Object[cells.length];

for (int i = 0; i < cells.length; i++)

{

try

{

clones[i] = cloneCell(cells[i], mapping, includeChildren);

}

catch (CloneNotSupportedException e)

{

// ignore

}

}

for (int i = 0; i < cells.length; i++)

{

restoreClone(clones[i], cells[i], mapping);

}

return clones;

}

/**

* Inner helper method for cloning cells recursively.

*/

protected Object cloneCell(Object cell, Map<Object, Object> mapping,

boolean includeChildren) throws CloneNotSupportedException

{

if (cell instanceof mxICell)

{

mxICell mxc = (mxICell) ((mxICell) cell).clone();

mapping.put(cell, mxc);

if (includeChildren)

{

int childCount = getChildCount(cell);

for (int i = 0; i < childCount; i++)

{

Object clone = cloneCell(getChildAt(cell, i), mapping, true);

mxc.insert((mxICell) clone);

}

}

return mxc;

}

return null;

}

/**

* Inner helper method for restoring the connections in

* a network of cloned cells.

*/

protected void restoreClone(Object clone, Object cell,

Map<Object, Object> mapping)

{

if (clone instanceof mxICell)

{

mxICell mxc = (mxICell) clone;

Object source = getTerminal(cell, true);

if (source instanceof mxICell)

{

mxICell tmp = (mxICell) mapping.get(source);

if (tmp != null)

{

tmp.insertEdge(mxc, true);

}

}

Object target = getTerminal(cell, false);

if (target instanceof mxICell)

{

mxICell tmp = (mxICell) mapping.get(target);

if (tmp != null)

{

tmp.insertEdge(mxc, false);

}

}

}

int childCount = getChildCount(clone);

for (int i = 0; i < childCount; i++)

{

restoreClone(getChildAt(clone, i), getChildAt(cell, i), mapping);

}

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#isAncestor(Object, Object)

*/

public boolean isAncestor(Object parent, Object child)

{

while (child != null && child != parent)

{

child = getParent(child);

}

return child == parent;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#contains(Object)

*/

public boolean contains(Object cell)

{

return isAncestor(getRoot(), cell);

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#getParent(Object)

*/

public Object getParent(Object child)

{

return (child instanceof mxICell) ? ((mxICell) child).getParent()

: null;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#add(Object, Object, int)

*/

public Object add(Object parent, Object child, int index)

{

if (child != parent && parent != null && child != null)

{

boolean parentChanged = parent != getParent(child);

execute(new mxChildChange(this, parent, child, index));

// Maintains the edges parents by moving the edges

// into the nearest common ancestor of its

// terminals

if (maintainEdgeParent && parentChanged)

{

updateEdgeParents(child);

}

}

return child;

}

/**

* Invoked after a cell has been added to a parent. This recursively

* creates an Id for the new cell and/or resolves Id collisions.

*

* @param cell Cell that has been added.

*/

protected void cellAdded(Object cell)

{

if (cell instanceof mxICell)

{

mxICell mxc = (mxICell) cell;

if (mxc.getId() == null && isCreateIds())

{

mxc.setId(createId(cell));

}

if (mxc.getId() != null)

{

Object collision = getCell(mxc.getId());

if (collision != cell)

{

while (collision != null)

{

mxc.setId(createId(cell));

collision = getCell(mxc.getId());

}

if (cells == null)

{

cells = new Hashtable<String, Object>();

}

cells.put(mxc.getId(), cell);

}

}

// Makes sure IDs of deleted cells are not reused

try

{

int id = Integer.parseInt(mxc.getId());

nextId = Math.max(nextId, id + 1);

}

catch (NumberFormatException e)

{

// ignore

}

int childCount = mxc.getChildCount();

for (int i = 0; i < childCount; i++)

{

cellAdded(mxc.getChildAt(i));

}

}

}

/**

* Creates a new Id for the given cell and increments the global counter

* for creating new Ids.

*

* @param cell Cell for which a new Id should be created.

* @return Returns a new Id for the given cell.

*/

public String createId(Object cell)

{

String id = String.valueOf(nextId);

nextId++;

return id;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#remove(Object)

*/

public Object remove(Object cell)

{

if (cell == root)

{

setRoot(null);

}

else if (getParent(cell) != null)

{

execute(new mxChildChange(this, null, cell));

}

return cell;

}

/**

* Invoked after a cell has been removed from the model. This recursively

* removes the cell from its terminals and removes the mapping from the Id

* to the cell.

*

* @param cell Cell that has been removed.

*/

protected void cellRemoved(Object cell)

{

if (cell instanceof mxICell)

{

mxICell mxc = (mxICell) cell;

int childCount = mxc.getChildCount();

for (int i = 0; i < childCount; i++)

{

cellRemoved(mxc.getChildAt(i));

}

if (cells != null && mxc.getId() != null)

{

cells.remove(mxc.getId());

}

}

}

/**

* Inner callback to update the parent of a cell using mxCell.insert

* on the parent and return the previous parent.

*/

protected Object parentForCellChanged(Object cell, Object parent, int index)

{

mxICell child = (mxICell) cell;

mxICell previous = (mxICell) getParent(cell);

if (parent != null)

{

if (parent != previous || previous.getIndex(child) != index)

{

((mxICell) parent).insert(child, index);

}

}

else if (previous != null)

{

int oldIndex = previous.getIndex(child);

previous.remove(oldIndex);

}

// Checks if the previous parent was already in the

// model and avoids calling cellAdded if it was.

if (!contains(previous) && parent != null)

{

cellAdded(cell);

}

else if (parent == null)

{

cellRemoved(cell);

}

return previous;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#getChildCount(Object)

*/

public int getChildCount(Object cell)

{

return (cell instanceof mxICell) ? ((mxICell) cell).getChildCount() : 0;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#getChildAt(Object, int)

*/

public Object getChildAt(Object parent, int index)

{

return (parent instanceof mxICell) ? ((mxICell) parent)

.getChildAt(index) : null;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#getTerminal(Object, boolean)

*/

public Object getTerminal(Object edge, boolean isSource)

{

return (edge instanceof mxICell) ? ((mxICell) edge)

.getTerminal(isSource) : null;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#setTerminal(Object, Object, boolean)

*/

public Object setTerminal(Object edge, Object terminal, boolean isSource)

{

boolean terminalChanged = terminal != getTerminal(edge, isSource);

execute(new mxTerminalChange(this, edge, terminal, isSource));

if (maintainEdgeParent && terminalChanged)

{

updateEdgeParent(edge, getRoot());

}

return terminal;

}

/**

* Inner helper function to update the terminal of the edge using

* mxCell.insertEdge and return the previous terminal.

*/

protected Object terminalForCellChanged(Object edge, Object terminal,

boolean isSource)

{

mxICell previous = (mxICell) getTerminal(edge, isSource);

if (terminal != null)

{

((mxICell) terminal).insertEdge((mxICell) edge, isSource);

}

else if (previous != null)

{

previous.removeEdge((mxICell) edge, isSource);

}

return previous;

}

/**

* Updates the parents of the edges connected to the given cell and all its

* descendants so that each edge is contained in the nearest common

* ancestor.

*

* @param cell Cell whose edges should be checked and updated.

*/

public void updateEdgeParents(Object cell)

{

updateEdgeParents(cell, getRoot());

}

/**

* Updates the parents of the edges connected to the given cell and all its

* descendants so that the edge is contained in the nearest-common-ancestor.

*

* @param cell Cell whose edges should be checked and updated.

* @param root Root of the cell hierarchy that contains all cells.

*/

public void updateEdgeParents(Object cell, Object root)

{

// Updates edges on children first

int childCount = getChildCount(cell);

for (int i = 0; i < childCount; i++)

{

Object child = getChildAt(cell, i);

updateEdgeParents(child, root);

}

// Updates the parents of all connected edges

int edgeCount = getEdgeCount(cell);

List<Object> edges = new ArrayList<Object>(edgeCount);

for (int i = 0; i < edgeCount; i++)

{

edges.add(getEdgeAt(cell, i));

}

Iterator<Object> it = edges.iterator();

while (it.hasNext())

{

Object edge = it.next();

// Updates edge parent if edge and child have

// a common root node (does not need to be the

// model root node)

if (isAncestor(root, edge))

{

updateEdgeParent(edge, root);

}

}

}

/**

* Inner helper method to update the parent of the specified edge to the

* nearest-common-ancestor of its two terminals.

*

* @param edge Specifies the edge to be updated.

* @param root Current root of the model.

*/

public void updateEdgeParent(Object edge, Object root)

{

Object source = getTerminal(edge, true);

Object target = getTerminal(edge, false);

Object cell = null;

// Uses the first non-relative descendants of the source terminal

while (source != null && !isEdge(source) &&

getGeometry(source) != null && getGeometry(source).isRelative())

{

source = getParent(source);

}

// Uses the first non-relative descendants of the target terminal

while (target != null && !isEdge(target) &&

getGeometry(target) != null && getGeometry(target).isRelative())

{

target = getParent(target);

}

if (isAncestor(root, source) && isAncestor(root, target))

{

if (source == target)

{

cell = getParent(source);

}

else

{

cell = getNearestCommonAncestor(source, target);

}

// Keeps the edge in the same layer

if (cell != null

&& (getParent(cell) != root || isAncestor(cell, edge))

&& getParent(edge) != cell)

{

mxGeometry geo = getGeometry(edge);

if (geo != null)

{

mxPoint origin1 = getOrigin(getParent(edge));

mxPoint origin2 = getOrigin(cell);

double dx = origin2.getX() - origin1.getX();

double dy = origin2.getY() - origin1.getY();

geo = (mxGeometry) geo.clone();

geo.translate(-dx, -dy);

setGeometry(edge, geo);

}

add(cell, edge, getChildCount(cell));

}

}

}

/**

* Returns the absolute, accumulated origin for the children inside the

* given parent.

*/

public mxPoint getOrigin(Object cell)

{

mxPoint result = null;

if (cell != null)

{

result = getOrigin(getParent(cell));

if (!isEdge(cell))

{

mxGeometry geo = getGeometry(cell);

if (geo != null)

{

result.setX(result.getX() + geo.getX());

result.setY(result.getY() + geo.getY());

}

}

}

else

{

result = new mxPoint();

}

return result;

}

/**

* Returns the nearest common ancestor for the specified cells.

*

* @param cell1 Cell that specifies the first cell in the tree.

* @param cell2 Cell that specifies the second cell in the tree.

* @return Returns the nearest common ancestor of the given cells.

*/

public Object getNearestCommonAncestor(Object cell1, Object cell2)

{

if (cell1 != null && cell2 != null)

{

// Creates the cell path for the second cell

String path = mxCellPath.create((mxICell) cell2);

if (path != null && path.length() > 0)

{

// Bubbles through the ancestors of the first

// cell to find the nearest common ancestor.

Object cell = cell1;

String current = mxCellPath.create((mxICell) cell);

while (cell != null)

{

Object parent = getParent(cell);

// Checks if the cell path is equal to the beginning

// of the given cell path

if (path.indexOf(current + mxCellPath.PATH_SEPARATOR) == 0

&& parent != null)

{

return cell;

}

current = mxCellPath.getParentPath(current);

cell = parent;

}

}

}

return null;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#getEdgeCount(Object)

*/

public int getEdgeCount(Object cell)

{

return (cell instanceof mxICell) ? ((mxICell) cell).getEdgeCount() : 0;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#getEdgeAt(Object, int)

*/

public Object getEdgeAt(Object parent, int index)

{

return (parent instanceof mxICell) ? ((mxICell) parent)

.getEdgeAt(index) : null;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#isVertex(Object)

*/

public boolean isVertex(Object cell)

{

return (cell instanceof mxICell) ? ((mxICell) cell).isVertex() : false;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#isEdge(Object)

*/

public boolean isEdge(Object cell)

{

return (cell instanceof mxICell) ? ((mxICell) cell).isEdge() : false;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#isConnectable(Object)

*/

public boolean isConnectable(Object cell)

{

return (cell instanceof mxICell) ? ((mxICell) cell).isConnectable()

: true;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#getValue(Object)

*/

public Object getValue(Object cell)

{

return (cell instanceof mxICell) ? ((mxICell) cell).getValue() : null;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#setValue(Object, Object)

*/

public Object setValue(Object cell, Object value)

{

execute(new mxValueChange(this, cell, value));

return value;

}

/**

* Inner callback to update the user object of the given mxCell

* using mxCell.setValue and return the previous value,

* that is, the return value of mxCell.getValue.

*/

protected Object valueForCellChanged(Object cell, Object value)

{

Object oldValue = ((mxICell) cell).getValue();

((mxICell) cell).setValue(value);

return oldValue;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#getGeometry(Object)

*/

public mxGeometry getGeometry(Object cell)

{

return (cell instanceof mxICell) ? ((mxICell) cell).getGeometry()

: null;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#setGeometry(Object, mxGeometry)

*/

public mxGeometry setGeometry(Object cell, mxGeometry geometry)

{

if (geometry != getGeometry(cell))

{

execute(new mxGeometryChange(this, cell, geometry));

}

return geometry;

}

/**

* Inner callback to update the mxGeometry of the given mxCell using

* mxCell.setGeometry and return the previous mxGeometry.

*/

protected mxGeometry geometryForCellChanged(Object cell, mxGeometry geometry)

{

mxGeometry previous = getGeometry(cell);

((mxICell) cell).setGeometry(geometry);

return previous;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#getStyle(Object)

*/

public String getStyle(Object cell)

{

return (cell instanceof mxICell) ? ((mxICell) cell).getStyle() : null;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#setStyle(Object, String)

*/

public String setStyle(Object cell, String style)

{

if (style == null || !style.equals(getStyle(cell)))

{

execute(new mxStyleChange(this, cell, style));

}

return style;

}

/**

* Inner callback to update the style of the given mxCell

* using mxCell.setStyle and return the previous style.

*/

protected String styleForCellChanged(Object cell, String style)

{

String previous = getStyle(cell);

((mxICell) cell).setStyle(style);

return previous;

}

/* (non-Javadoc)

* @see com.mxgraph.model.mxIGraphModel#isCollapsed(Object)

*/