framework/images/webapp/images/dojo/src/collections/Graph.js

/*
	Copyright (c) 2004-2006, The Dojo Foundation
	All Rights Reserved.

	Licensed under the Academic Free License version 2.1 or above OR the
	modified BSD license. For more information on Dojo licensing, see:

		http://dojotoolkit.org/community/licensing.shtml
*/

dojo.provide("dojo.collections.Graph");
dojo.require("dojo.collections.Collections");

dojo.experimental("dojo.collections.Graph");

dojo.collections.Graph=function(nodes){
	function node(key, data, neighbors) {
		this.key=key;
		this.data=data;
		this.neighbors=neighbors||new adjacencyList();
		this.addDirected=function(){
			if (arguments[0].constructor==edgeToNeighbor){
				this.neighbors.add(arguments[0]);
			}else{
				var n=arguments[0];
				var cost=arguments[1]||0;
				this.neighbors.add(new edgeToNeighbor(n, cost));
			}
		}
	}
	function nodeList(){
		var d=new dojo.collections.Dictionary();
		function nodelistiterator(){
			var o=[] ;	//	Create an indexing array
			var e=d.getIterator();
			while(e.get()){
				o[o.length]=e.element;
			}

			var position=0;
			this.element=o[position]||null;
			this.atEnd=function(){
				return (position>=o.length);
			}
			this.get=function(){
				if(this.atEnd()){
					return null;		//	object
				}
				this.element=o[position++];
				return this.element;	//	object
			};
			this.map=function(/* function */fn, /* object? */scope){
				var s=scope||dj_global;
				if(Array.map){
					return Array.map(o,fn,s);	//	array
				}else{
					var arr=[];
					for(var i=0; i<o.length; i++){
						arr.push(fn.call(s,o[i]));
					}
					return arr;		//	array
				}
			};
			this.reset=function(){
				position=0;
				this.element=o[position];
			};
		}

		this.add=function(node){
			d.add(node.key, node);
		};
		this.clear=function(){
			d.clear();
		};
		this.containsKey=function(key){
			return d.containsKey(key);
		};
		this.getIterator=function(){
			return new nodelistiterator(this);
		};
		this.item=function(key){
			return d.item(key);
		};
		this.remove=function(node){
			d.remove(node.key);
		};
	}
	function edgeToNeighbor(node, cost){
		this.neighbor=node;
		this.cost=cost;
	}
	function adjacencyList(){
		var d=[];
		this.add=function(o){
			d.push(o);
		};
		this.item=function(i){
			return d[i];
		};
		this.getIterator=function(){
			return new dojo.collections.Iterator([].concat(d));
		};
	}

	this.nodes=nodes||new nodeList();
	this.count=this.nodes.count;
	this.clear=function(){
		this.nodes.clear();
		this.count=0;
	};
	this.addNode=function(){
		var n=arguments[0];
		if(arguments.length > 1){
			n=new node(arguments[0],arguments[1]);
		}
		if(!this.nodes.containsKey(n.key)){
			this.nodes.add(n);
			this.count++;
		}
	};
	this.addDirectedEdge=function(uKey, vKey, cost){
		var uNode,vNode;
		if(uKey.constructor!= node){
			uNode=this.nodes.item(uKey);
			vNode=this.nodes.item(vKey);
		}else{
			uNode=uKey;
			vNode=vKey;
		}
		var c=cost||0;
		uNode.addDirected(vNode,c);
	};
	this.addUndirectedEdge=function(uKey, vKey, cost){
		var uNode, vNode;
		if(uKey.constructor!=node){
			uNode=this.nodes.item(uKey);
			vNode=this.nodes.item(vKey);
		}else{
			uNode=uKey;
			vNode=vKey;
		}
		var c=cost||0;
		uNode.addDirected(vNode,c);
		vNode.addDirected(uNode,c);
	};
	this.contains=function(n){
		return this.nodes.containsKey(n.key);
	};
	this.containsKey=function(k){
		return this.nodes.containsKey(k);
	};
}