/**

* $Id: mxGraphModel.js,v 1.2 2013/02/12 12:34:43 gaudenz Exp $

* Copyright (c) 2006-2010, JGraph Ltd

*/

/**

* Class: mxGraphModel

*

* 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.

*

* Events:

*

* See events section for more details. There is a new set of events for

* tracking transactional changes as they happen. The events are called

* startEdit for the initial beginUpdate, executed for each executed change

* and endEdit for the terminal endUpdate. The executed event contains a

* property called change which represents the change after execution.

*

* Encoding the model:

*

* To encode a graph model, use the following code:

*

* (code)

* var enc = new mxCodec();

* var node = enc.encode(graph.getModel());

* (end)

*

* This will create an XML node that contains all the model information.

*

* Encoding and decoding changes:

*

* For the encoding of changes, a graph model listener is required that encodes

* each change from the given array of changes.

*

* (code)

* model.addListener(mxEvent.CHANGE, function(sender, evt)

* {

* var changes = evt.getProperty('edit').changes;

* var nodes = [];

* var codec = new mxCodec();

*

* for (var i = 0; i < changes.length; i++)

* {

* nodes.push(codec.encode(changes[i]));

* }

* // do something with the nodes

* });

* (end)

*

* For the decoding and execution of changes, the codec needs a lookup function

* that allows it to resolve cell IDs as follows:

*

* (code)

* var codec = new mxCodec();

* codec.lookup = function(id)

* {

* return model.getCell(id);

* }

* (end)

*

* For each encoded change (represented by a node), the following code can be

* used to carry out the decoding and create a change object.

*

* (code)

* var changes = [];

* var change = codec.decode(node);

* change.model = model;

* change.execute();

* changes.push(change);

* (end)

*

* The changes can then be dispatched using the model as follows.

*

* (code)

* var edit = new mxUndoableEdit(model, false);

* edit.changes = changes;

*

* edit.notify = function()

* {

* edit.source.fireEvent(new mxEventObject(mxEvent.CHANGE,

* 'edit', edit, 'changes', edit.changes));

* edit.source.fireEvent(new mxEventObject(mxEvent.NOTIFY,

* 'edit', edit, 'changes', edit.changes));

* }

*

* model.fireEvent(new mxEventObject(mxEvent.UNDO, 'edit', edit));

* model.fireEvent(new mxEventObject(mxEvent.CHANGE,

* 'edit', edit, 'changes', changes));

* (end)

*

* Event: mxEvent.CHANGE

*

* Fires when an undoable edit is dispatched. The <code>edit</code> property

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

* the array of atomic changes inside the undoable edit. The changes property

* is <strong>deprecated</strong>, please use edit.changes instead.

*

* Example:

*

* For finding newly inserted cells, the following code can be used:

*

* (code)

* graph.model.addListener(mxEvent.CHANGE, function(sender, evt)

* {

* var changes = evt.getProperty('edit').changes;

*

* for (var i = 0; i < changes.length; i++)

* {

* var change = changes[i];

*

* if (change instanceof mxChildChange &&

* change.change.previous == null)

* {

* graph.startEditingAtCell(change.child);

* break;

* }

* }

* });

* (end)

*

*

* Event: mxEvent.NOTIFY

*

* Same as <mxEvent.CHANGE>, this event can be used for classes that need to

* implement a sync mechanism between this model and, say, a remote model. In

* such a setup, only local changes should trigger a notify event and all

* changes should trigger a change event.

*

* Event: 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.

*

* Event: mxEvent.EXECUTED

*

* Fires between START_EDIT and END_EDIT after an atomic change was executed.

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

*

* Event: mxEvent.BEGIN_UPDATE

*

* Fires after the <updateLevel> was incremented in <beginUpdate>. This event

* contains no properties.

*

* Event: mxEvent.START_EDIT

*

* Fires after the <updateLevel> was changed from 0 to 1. This event

* contains no properties.

*

* Event: 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 <currentEdit>.

*

* Event: mxEvent.END_EDIT

*

* Fires after the <updateLevel> was changed from 1 to 0. This event

* contains no properties.

*

* Event: 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 <curreneEdit>.

*

* Event: mxEvent.UNDO

*

* Fires after the change was dispatched in <endUpdate>. The <code>edit</code>

* property contains the <currentEdit>.

*

* Constructor: mxGraphModel

*

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

* <mxCell> with a default layer is created.

*

* Parameters:

*

* root - <mxCell> that represents the root cell.

*/

function mxGraphModel(root)

{

this.currentEdit = this.createUndoableEdit();

if (root != null)

{

this.setRoot(root);

}

else

{

this.clear();

}

};

/**

* Extends mxEventSource.

*/

mxGraphModel.prototype = new mxEventSource();

mxGraphModel.prototype.constructor = mxGraphModel;

/**

* Variable: root

*

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

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

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

*/

mxGraphModel.prototype.root = null;

/**

* Variable: cells

*

* Maps from Ids to cells.

*/

mxGraphModel.prototype.cells = null;

/**

* Variable: maintainEdgeParent

*

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

* ancestor of their terminals. Default is true.

*/

mxGraphModel.prototype.maintainEdgeParent = true;

/**

* Variable: createIds

*

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

* Default is true.

*/

mxGraphModel.prototype.createIds = true;

/**

* Variable: prefix

*

* Defines the prefix of new Ids. Default is an empty string.

*/

mxGraphModel.prototype.prefix = '';

/**

* Variable: postfix

*

* Defines the postfix of new Ids. Default is an empty string.

*/

mxGraphModel.prototype.postfix = '';

/**

* Variable: nextId

*

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

*/

mxGraphModel.prototype.nextId = 0;

/**

* Variable: currentEdit

*

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

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

* <createUndoableEdit>.

*/

mxGraphModel.prototype.currentEdit = null;

/**

* Variable: updateLevel

*

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

* will increment this number and each call to <endUpdate> will decrement

* it. When the counter reaches 0, the transaction is closed and the

* respective events are fired. Initial value is 0.

*/

mxGraphModel.prototype.updateLevel = 0;

/**

* Variable: endingUpdate

*

* True if the program flow is currently inside endUpdate.

*/

mxGraphModel.prototype.endingUpdate = false;

/**

* Function: clear

*

* Sets a new root using <createRoot>.

*/

mxGraphModel.prototype.clear = function()

{

this.setRoot(this.createRoot());

};

/**

* Function: isCreateIds

*

* Returns <createIds>.

*/

mxGraphModel.prototype.isCreateIds = function()

{

return this.createIds;

};

/**

* Function: setCreateIds

*

* Sets <createIds>.

*/

mxGraphModel.prototype.setCreateIds = function(value)

{

this.createIds = value;

};

/**

* Function: createRoot

*

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

*/

mxGraphModel.prototype.createRoot = function()

{

var cell = new mxCell();

cell.insert(new mxCell());

return cell;

};

/**

* Function: getCell

*

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

* found for the given Id.

*

* Parameters:

*

* id - A string representing the Id of the cell.

*/

mxGraphModel.prototype.getCell = function(id)

{

return (this.cells != null) ? this.cells[id] : null;

};

/**

* Function: filterCells

*

* Returns the cells from the given array where the fiven filter function

* returns true.

*/

mxGraphModel.prototype.filterCells = function(cells, filter)

{

var result = null;

if (cells != null)

{

result = [];

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

{

if (filter(cells[i]))

{

result.push(cells[i]);

}

}

}

return result;

};

/**

* Function: getDescendants

*

* Returns all descendants of the given cell and the cell itself in an array.

*

* Parameters:

*

* parent - <mxCell> whose descendants should be returned.

*/

mxGraphModel.prototype.getDescendants = function(parent)

{

return this.filterDescendants(null, parent);

};

/**

* Function: filterDescendants

*

* Visits all cells recursively and applies the specified filter function

* to each cell. If the function returns true then the cell is added

* to the resulting array. The parent and result paramters are optional.

* If parent is not specified then the recursion starts at <root>.

*

* Example:

* The following example extracts all vertices from a given model:

* (code)

* var filter = function(cell)

* {

* return model.isVertex(cell);

* }

* var vertices = model.filterDescendants(filter);

* (code)

*

* Parameters:

*

* filter - JavaScript function that takes an <mxCell> as an argument

* and returns a boolean.

* parent - Optional <mxCell> that is used as the root of the recursion.

*/

mxGraphModel.prototype.filterDescendants = function(filter, parent)

{

// Creates a new array for storing the result

var result = [];

// Recursion starts at the root of the model

parent = parent || this.getRoot();

// Checks if the filter returns true for the cell

// and adds it to the result array

if (filter == null || filter(parent))

{

result.push(parent);

}

// Visits the children of the cell

var childCount = this.getChildCount(parent);

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

{

var child = this.getChildAt(parent, i);

result = result.concat(this.filterDescendants(filter, child));

}

return result;

};

/**

* Function: getRoot

*

* Returns the root of the model or the topmost parent of the given cell.

*

* Parameters:

*

* cell - Optional <mxCell> that specifies the child.

*/

mxGraphModel.prototype.getRoot = function(cell)

{

var root = cell || this.root;

if (cell != null)

{

while (cell != null)

{

root = cell;

cell = this.getParent(cell);

}

}

return root;

};

/**

* Function: setRoot

*

* Sets the <root> of the model using <mxRootChange> and adds the change to

* the current transaction. This resets all datastructures in the model and

* is the preferred way of clearing an existing model. Returns the new

* root.

*

* Example:

*

* (code)

* var root = new mxCell();

* root.insert(new mxCell());

* model.setRoot(root);

* (end)

*

* Parameters:

*

* root - <mxCell> that specifies the new root.

*/

mxGraphModel.prototype.setRoot = function(root)

{

this.execute(new mxRootChange(this, root));

return root;

};

/**

* Function: rootChanged

*

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

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

*

* Parameters:

*

* root - <mxCell> that specifies the new root.

*/

mxGraphModel.prototype.rootChanged = function(root)

{

var oldRoot = this.root;

this.root = root;

// Resets counters and datastructures

this.nextId = 0;

this.cells = null;

this.cellAdded(root);

return oldRoot;

};

/**

* Function: isRoot

*

* Returns true if the given cell is the root of the model and a non-null

* value.

*

* Parameters:

*

* cell - <mxCell> that represents the possible root.

*/

mxGraphModel.prototype.isRoot = function(cell)

{

return cell != null && this.root == cell;

};

/**

* Function: isLayer

*

* Returns true if <isRoot> returns true for the parent of the given cell.

*

* Parameters:

*

* cell - <mxCell> that represents the possible layer.

*/

mxGraphModel.prototype.isLayer = function(cell)

{

return this.isRoot(this.getParent(cell));

};

/**

* Function: isAncestor

*

* Returns true if the given parent is an ancestor of the given child.

*

* Parameters:

*

* parent - <mxCell> that specifies the parent.

* child - <mxCell> that specifies the child.

*/

mxGraphModel.prototype.isAncestor = function(parent, child)

{

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

{

child = this.getParent(child);

}

return child == parent;

};

/**

* Function: contains

*

* Returns true if the model contains the given <mxCell>.

*

* Parameters:

*

* cell - <mxCell> that specifies the cell.

*/

mxGraphModel.prototype.contains = function(cell)

{

return this.isAncestor(this.root, cell);

};

/**

* Function: getParent

*

* Returns the parent of the given cell.

*

* Parameters:

*

* cell - <mxCell> whose parent should be returned.

*/

mxGraphModel.prototype.getParent = function(cell)

{

return (cell != null) ? cell.getParent() : null;

};

/**

* Function: add

*

* Adds the specified child to the parent at the given index using

* <mxChildChange> and adds the change to the current transaction. If no

* index is specified then the child is appended to the parent's array of

* children. Returns the inserted child.

*

* Parameters:

*

* parent - <mxCell> that specifies the parent to contain the child.

* child - <mxCell> that specifies the child to be inserted.

* index - Optional integer that specifies the index of the child.

*/

mxGraphModel.prototype.add = function(parent, child, index)

{

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

{

// Appends the child if no index was specified

if (index == null)

{

index = this.getChildCount(parent);

}

var parentChanged = parent != this.getParent(child);

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

// Maintains the edges parents by moving the edges

// into the nearest common ancestor of its

// terminals

if (this.maintainEdgeParent && parentChanged)

{

this.updateEdgeParents(child);

}

}

return child;

};

/**

* Function: cellAdded

*

* Inner callback to update <cells> when a cell has been added. This

* implementation resolves collisions by creating new Ids. To change the

* ID of a cell after it was inserted into the model, use the following

* code:

*

* (code

* delete model.cells[cell.getId()];

* cell.setId(newId);

* model.cells[cell.getId()] = cell;

* (end)

*

* If the change of the ID should be part of the command history, then the

* cell should be removed from the model and a clone with the new ID should

* be reinserted into the model instead.

*

* Parameters:

*

* cell - <mxCell> that specifies the cell that has been added.

*/

mxGraphModel.prototype.cellAdded = function(cell)

{

if (cell != null)

{

// Creates an Id for the cell if not Id exists

if (cell.getId() == null && this.createIds)

{

cell.setId(this.createId(cell));

}

if (cell.getId() != null)

{

var collision = this.getCell(cell.getId());

if (collision != cell)

{

// Creates new Id for the cell

// as long as there is a collision

while (collision != null)

{

cell.setId(this.createId(cell));

collision = this.getCell(cell.getId());

}

// Lazily creates the cells dictionary

if (this.cells == null)

{

this.cells = new Object();

}

this.cells[cell.getId()] = cell;

}

}

// Makes sure IDs of deleted cells are not reused

if (mxUtils.isNumeric(cell.getId()))

{

this.nextId = Math.max(this.nextId, cell.getId());

}

// Recursively processes child cells

var childCount = this.getChildCount(cell);

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

{

this.cellAdded(this.getChildAt(cell, i));

}

}

};

/**

* Function: createId

*

* Hook method to create an Id for the specified cell. This implementation

* concatenates <prefix>, id and <postfix> to create the Id and increments

* <nextId>. The cell is ignored by this implementation, but can be used in

* overridden methods to prefix the Ids with eg. the cell type.

*

* Parameters:

*

* cell - <mxCell> to create the Id for.

*/

mxGraphModel.prototype.createId = function(cell)

{

var id = this.nextId;

this.nextId++;

return this.prefix + id + this.postfix;

};

/**

* Function: updateEdgeParents

*

* Updates the parent for all edges that are connected to cell or one of

* its descendants using <updateEdgeParent>.

*/

mxGraphModel.prototype.updateEdgeParents = function(cell, root)

{

// Gets the topmost node of the hierarchy

root = root || this.getRoot(cell);

// Updates edges on children first

var childCount = this.getChildCount(cell);

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

{

var child = this.getChildAt(cell, i);

this.updateEdgeParents(child, root);

}

// Updates the parents of all connected edges

var edgeCount = this.getEdgeCount(cell);

var edges = [];

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

{

edges.push(this.getEdgeAt(cell, i));

}

for (var i = 0; i < edges.length; i++)

{

var edge = edges[i];

// Updates edge parent if edge and child have

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

// model root node)

if (this.isAncestor(root, edge))

{

this.updateEdgeParent(edge, root);

}

}

};

/**

* Function: updateEdgeParent

*

* Inner callback to update the parent of the specified <mxCell> to the

* nearest-common-ancestor of its two terminals.

*

* Parameters:

*

* edge - <mxCell> that specifies the edge.

* root - <mxCell> that represents the current root of the model.

*/

mxGraphModel.prototype.updateEdgeParent = function(edge, root)

{

var source = this.getTerminal(edge, true);

var target = this.getTerminal(edge, false);

var cell = null;

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

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

source.geometry != null && source.geometry.relative)

{

source = this.getParent(source);

}

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

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

target.geometry != null && target.geometry.relative)

{

target = this.getParent(target);

}

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

{

if (source == target)

{

cell = this.getParent(source);

}

else

{

cell = this.getNearestCommonAncestor(source, target);

}

if (cell != null && (this.getParent(cell) != this.root ||

this.isAncestor(cell, edge)) && this.getParent(edge) != cell)

{

var geo = this.getGeometry(edge);

if (geo != null)

{

var origin1 = this.getOrigin(this.getParent(edge));

var origin2 = this.getOrigin(cell);

var dx = origin2.x - origin1.x;

var dy = origin2.y - origin1.y;

geo = geo.clone();

geo.translate(-dx, -dy);

this.setGeometry(edge, geo);

}

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

}

}

};

/**

* Function: getOrigin

*

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

* given parent as an <mxPoint>.

*/

mxGraphModel.prototype.getOrigin = function(cell)

{

var result = null;

if (cell != null)

{

result = this.getOrigin(this.getParent(cell));

if (!this.isEdge(cell))

{

var geo = this.getGeometry(cell);

if (geo != null)

{

result.x += geo.x;

result.y += geo.y;

}

}

}

else

{

result = new mxPoint();

}

return result;

};

/**

* Function: getNearestCommonAncestor

*

* Returns the nearest common ancestor for the specified cells.

*

* Parameters:

*

* cell1 - <mxCell> that specifies the first cell in the tree.

* cell2 - <mxCell> that specifies the second cell in the tree.

*/

mxGraphModel.prototype.getNearestCommonAncestor = function(cell1, cell2)

{

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

{

// Creates the cell path for the second cell

var path = mxCellPath.create(cell2);

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

{

// Bubbles through the ancestors of the first

// cell to find the nearest common ancestor.

var cell = cell1;

var current = mxCellPath.create(cell);

// Inverts arguments

if (path.length < current.length)

{

cell = cell2;

var tmp = current;

current = path;

path = tmp;

}

while (cell != null)

{

var parent = this.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;

};

/**

* Function: remove

*

* Removes the specified cell from the model using <mxChildChange> and adds

* the change to the current transaction. This operation will remove the

* cell and all of its children from the model. Returns the removed cell.

*

* Parameters:

*

* cell - <mxCell> that should be removed.

*/

mxGraphModel.prototype.remove = function(cell)

{

if (cell == this.root)

{

this.setRoot(null);

}

else if (this.getParent(cell) != null)

{

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

}

return cell;

};

/**

* Function: cellRemoved

*

* Inner callback to update <cells> when a cell has been removed.

*

* Parameters:

*

* cell - <mxCell> that specifies the cell that has been removed.

*/

mxGraphModel.prototype.cellRemoved = function(cell)

{

if (cell != null && this.cells != null)

{

// Recursively processes child cells

var childCount = this.getChildCount(cell);

for (var i = childCount - 1; i >= 0; i--)

{

this.cellRemoved(this.getChildAt(cell, i));

}

// Removes the dictionary entry for the cell

if (this.cells != null && cell.getId() != null)

{

delete this.cells[cell.getId()];

}

}

};

/**

* Function: parentForCellChanged

*

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

* on the parent and return the previous parent.

*

* Parameters:

*

* cell - <mxCell> to update the parent for.

* parent - <mxCell> that specifies the new parent of the cell.

* index - Optional integer that defines the index of the child

* in the parent's child array.

*/

mxGraphModel.prototype.parentForCellChanged = function(cell, parent, index)

{

var previous = this.getParent(cell);

if (parent != null)

{

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

{

parent.insert(cell, index);

}

}

else if (previous != null)

{

var oldIndex = previous.getIndex(cell);