Subversion Repositories Applications.papyrus

Rev

Rev 1318 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
1318 alexandre_ 1 
/*
2 
	Copyright (c) 2004-2006, The Dojo Foundation
3 
	All Rights Reserved.
4 
 
5 
	Licensed under the Academic Free License version 2.1 or above OR the
6 
	modified BSD license. For more information on Dojo licensing, see:
7 
 
8 
		http://dojotoolkit.org/community/licensing.shtml
9 
*/
10 
 
1422 alexandre_ 11 
 
12 
 
1318 alexandre_ 13 
dojo.provide("dojo.collections.Graph");
14 
dojo.require("dojo.collections.Collections");
15 
dojo.experimental("dojo.collections.Graph");
16 
dojo.collections.Graph = function (nodes) {
17 
	function node(key, data, neighbors) {
18 
		this.key = key;
19 
		this.data = data;
20 
		this.neighbors = neighbors || new adjacencyList();
21 
		this.addDirected = function () {
22 
			if (arguments[0].constructor == edgeToNeighbor) {
23 
				this.neighbors.add(arguments[0]);
24 
			} else {
25 
				var n = arguments[0];
26 
				var cost = arguments[1] || 0;
27 
				this.neighbors.add(new edgeToNeighbor(n, cost));
28 
			}
29 
		};
30 
	}
31 
	function nodeList() {
32 
		var d = new dojo.collections.Dictionary();
33 
		function nodelistiterator() {
34 
			var o = [];
35 
			var e = d.getIterator();
36 
			while (e.get()) {
37 
				o[o.length] = e.element;
38 
			}
39 
			var position = 0;
40 
			this.element = o[position] || null;
41 
			this.atEnd = function () {
42 
				return (position >= o.length);
43 
			};
44 
			this.get = function () {
45 
				if (this.atEnd()) {
46 
					return null;
47 
				}
48 
				this.element = o[position++];
49 
				return this.element;
50 
			};
51 
			this.map = function (fn, scope) {
52 
				var s = scope || dj_global;
53 
				if (Array.map) {
54 
					return Array.map(o, fn, s);
55 
				} else {
56 
					var arr = [];
57 
					for (var i = 0; i < o.length; i++) {
58 
						arr.push(fn.call(s, o[i]));
59 
					}
60 
					return arr;
61 
				}
62 
			};
63 
			this.reset = function () {
64 
				position = 0;
65 
				this.element = o[position];
66 
			};
67 
		}
68 
		this.add = function (node) {
69 
			d.add(node.key, node);
70 
		};
71 
		this.clear = function () {
72 
			d.clear();
73 
		};
74 
		this.containsKey = function (key) {
75 
			return d.containsKey(key);
76 
		};
77 
		this.getIterator = function () {
78 
			return new nodelistiterator(this);
79 
		};
80 
		this.item = function (key) {
81 
			return d.item(key);
82 
		};
83 
		this.remove = function (node) {
84 
			d.remove(node.key);
85 
		};
86 
	}
87 
	function edgeToNeighbor(node, cost) {
88 
		this.neighbor = node;
89 
		this.cost = cost;
90 
	}
91 
	function adjacencyList() {
92 
		var d = [];
93 
		this.add = function (o) {
94 
			d.push(o);
95 
		};
96 
		this.item = function (i) {
97 
			return d[i];
98 
		};
99 
		this.getIterator = function () {
100 
			return new dojo.collections.Iterator([].concat(d));
101 
		};
102 
	}
103 
	this.nodes = nodes || new nodeList();
104 
	this.count = this.nodes.count;
105 
	this.clear = function () {
106 
		this.nodes.clear();
107 
		this.count = 0;
108 
	};
109 
	this.addNode = function () {
110 
		var n = arguments[0];
111 
		if (arguments.length > 1) {
112 
			n = new node(arguments[0], arguments[1]);
113 
		}
114 
		if (!this.nodes.containsKey(n.key)) {
115 
			this.nodes.add(n);
116 
			this.count++;
117 
		}
118 
	};
119 
	this.addDirectedEdge = function (uKey, vKey, cost) {
120 
		var uNode, vNode;
121 
		if (uKey.constructor != node) {
122 
			uNode = this.nodes.item(uKey);
123 
			vNode = this.nodes.item(vKey);
124 
		} else {
125 
			uNode = uKey;
126 
			vNode = vKey;
127 
		}
128 
		var c = cost || 0;
129 
		uNode.addDirected(vNode, c);
130 
	};
131 
	this.addUndirectedEdge = function (uKey, vKey, cost) {
132 
		var uNode, vNode;
133 
		if (uKey.constructor != node) {
134 
			uNode = this.nodes.item(uKey);
135 
			vNode = this.nodes.item(vKey);
136 
		} else {
137 
			uNode = uKey;
138 
			vNode = vKey;
139 
		}
140 
		var c = cost || 0;
141 
		uNode.addDirected(vNode, c);
142 
		vNode.addDirected(uNode, c);
143 
	};
144 
	this.contains = function (n) {
145 
		return this.nodes.containsKey(n.key);
146 
	};
147 
	this.containsKey = function (k) {
148 
		return this.nodes.containsKey(k);
149 
	};
150 
};
151