Subversion Repositories Applications.papyrus

Rev

Rev 1318 | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

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