Subversion Repositories Applications.papyrus

Rev

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