Subversion Repositories Applications.papyrus

Rev

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

/*
        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 = [];
                        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;
                                }
                                this.element = o[position++];
                                return this.element;
                        };
                        this.map = function (fn, scope) {
                                var s = scope || dj_global;
                                if (Array.map) {
                                        return Array.map(o, fn, s);
                                } else {
                                        var arr = [];
                                        for (var i = 0; i < o.length; i++) {
                                                arr.push(fn.call(s, o[i]));
                                        }
                                        return arr;
                                }
                        };
                        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);
        };
};