Subversion Repositories Applications.papyrus

/*
        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.BinaryTree");
dojo.require("dojo.collections.Collections");
dojo.require("dojo.experimental");
dojo.experimental("dojo.collections.BinaryTree");
dojo.collections.BinaryTree = function (data) {
        function node(data, rnode, lnode) {
                this.value = data || null;
                this.right = rnode || null;
                this.left = lnode || null;
                this.clone = function () {
                        var c = new node();
                        if (this.value.value) {
                                c.value = this.value.clone();
                        } else {
                                c.value = this.value;
                        }
                        if (this.left) {
                                c.left = this.left.clone();
                        }
                        if (this.right) {
                                c.right = this.right.clone();
                        }
                };
                this.compare = function (n) {
                        if (this.value > n.value) {
                                return 1;
                        }
                        if (this.value < n.value) {
                                return -1;
                        }
                        return 0;
                };
                this.compareData = function (d) {
                        if (this.value > d) {
                                return 1;
                        }
                        if (this.value < d) {
                                return -1;
                        }
                        return 0;
                };
        }
        function inorderTraversalBuildup(current, a) {
                if (current) {
                        inorderTraversalBuildup(current.left, a);
                        a.add(current);
                        inorderTraversalBuildup(current.right, a);
                }
        }
        function preorderTraversal(current, sep) {
                var s = "";
                if (current) {
                        s = current.value.toString() + sep;
                        s += preorderTraversal(current.left, sep);
                        s += preorderTraversal(current.right, sep);
                }
                return s;
        }
        function inorderTraversal(current, sep) {
                var s = "";
                if (current) {
                        s = inorderTraversal(current.left, sep);
                        s += current.value.toString() + sep;
                        s += inorderTraversal(current.right, sep);
                }
                return s;
        }
        function postorderTraversal(current, sep) {
                var s = "";
                if (current) {
                        s = postorderTraversal(current.left, sep);
                        s += postorderTraversal(current.right, sep);
                        s += current.value.toString() + sep;
                }
                return s;
        }
        function searchHelper(current, data) {
                if (!current) {
                        return null;
                }
                var i = current.compareData(data);
                if (i == 0) {
                        return current;
                }
                if (i > 0) {
                        return searchHelper(current.left, data);
                } else {
                        return searchHelper(current.right, data);
                }
        }
        this.add = function (data) {
                var n = new node(data);
                var i;
                var current = root;
                var parent = null;
                while (current) {
                        i = current.compare(n);
                        if (i == 0) {
                                return;
                        }
                        parent = current;
                        if (i > 0) {
                                current = current.left;
                        } else {
                                current = current.right;
                        }
                }
                this.count++;
                if (!parent) {
                        root = n;
                } else {
                        i = parent.compare(n);
                        if (i > 0) {
                                parent.left = n;
                        } else {
                                parent.right = n;
                        }
                }
        };
        this.clear = function () {
                root = null;
                this.count = 0;
        };
        this.clone = function () {
                var c = new dojo.collections.BinaryTree();
                c.root = root.clone();
                c.count = this.count;
                return c;
        };
        this.contains = function (data) {
                return this.search(data) != null;
        };
        this.deleteData = function (data) {
                var current = root;
                var parent = null;
                var i = current.compareData(data);
                while (i != 0 && current != null) {
                        if (i > 0) {
                                parent = current;
                                current = current.left;
                        } else {
                                if (i < 0) {
                                        parent = current;
                                        current = current.right;
                                }
                        }
                        i = current.compareData(data);
                }
                if (!current) {
                        return;
                }
                this.count--;
                if (!current.right) {
                        if (!parent) {
                                root = current.left;
                        } else {
                                i = parent.compare(current);
                                if (i > 0) {
                                        parent.left = current.left;
                                } else {
                                        if (i < 0) {
                                                parent.right = current.left;
                                        }
                                }
                        }
                } else {
                        if (!current.right.left) {
                                if (!parent) {
                                        root = current.right;
                                } else {
                                        i = parent.compare(current);
                                        if (i > 0) {
                                                parent.left = current.right;
                                        } else {
                                                if (i < 0) {
                                                        parent.right = current.right;
                                                }
                                        }
                                }
                        } else {
                                var leftmost = current.right.left;
                                var lmParent = current.right;
                                while (leftmost.left != null) {
                                        lmParent = leftmost;
                                        leftmost = leftmost.left;
                                }
                                lmParent.left = leftmost.right;
                                leftmost.left = current.left;
                                leftmost.right = current.right;
                                if (!parent) {
                                        root = leftmost;
                                } else {
                                        i = parent.compare(current);
                                        if (i > 0) {
                                                parent.left = leftmost;
                                        } else {
                                                if (i < 0) {
                                                        parent.right = leftmost;
                                                }
                                        }
                                }
                        }
                }
        };
        this.getIterator = function () {
                var a = [];
                inorderTraversalBuildup(root, a);
                return new dojo.collections.Iterator(a);
        };
        this.search = function (data) {
                return searchHelper(root, data);
        };
        this.toString = function (order, sep) {
                if (!order) {
                        var order = dojo.collections.BinaryTree.TraversalMethods.Inorder;
                }
                if (!sep) {
                        var sep = " ";
                }
                var s = "";
                switch (order) {
                  case dojo.collections.BinaryTree.TraversalMethods.Preorder:
                        s = preorderTraversal(root, sep);
                        break;
                  case dojo.collections.BinaryTree.TraversalMethods.Inorder:
                        s = inorderTraversal(root, sep);
                        break;
                  case dojo.collections.BinaryTree.TraversalMethods.Postorder:
                        s = postorderTraversal(root, sep);
                        break;
                }
                if (s.length == 0) {
                        return "";
                } else {
                        return s.substring(0, s.length - sep.length);
                }
        };
        this.count = 0;
        var root = this.root = null;
        if (data) {
                this.add(data);
        }
};
dojo.collections.BinaryTree.TraversalMethods = {Preorder:1, Inorder:2, Postorder:3};