BinTree.m

Go to the documentation of this file.

/* (Autoinserted by mtoc++)
 * This source code has been filtered by the mtoc++ executable,
 * which generates code that can be processed by the doxygen documentation tool.
 *
 * On the other hand, it can neither be interpreted by MATLAB, nor can it be compiled with a C++ compiler.
 * Except for the comments, the function bodies of your M-file functions are untouched.
 * Consequently, the FILTER_SOURCE_FILES doxygen switch (default in our Doxyfile.template) will produce
 * attached source files that are highly readable by humans.
 *
 * Additionally, links in the doxygen generated documentation to the source code of functions and class members refer to
 * the correct locations in the source code browser.
 * However, the line numbers most likely do not correspond to the line numbers in the original MATLAB source files.
 */

class BinTree
  :public handle {
    private:

        root = "[]";

        
    public: /* ( Dependent ) */

        Height;

        Values;

        
    public: /* ( Dependent ) */


        
#if 0 //mtoc++: 'get.Height'
function h = Height() {
            h = this.height(this.root);
        }

#endif


        
#if 0 //mtoc++: 'get.Values'
function v = Values() {
            v = this.getvalues(this.root);
        }

#endif


        function  clear() {
            if ~isempty(this.root)
                this.root.delete;
                this.root= [];
            end
        }


        function  Insert(key,value) {
            if nargin < 3
                value = key;
            end
            if numel(key) ~= numel(value)
                error(" If key and value arguments are given they must have the same number of elements. ");
            end
            if KerMor.App.Verbose > 2
                cnt = 0; cp = 0;
                m = numel(value);
                fprintf(" Filling tree (%d values)..  ",m); 
                for idx=1:m
                    this.root= this.insert(this.root, key(idx), value(idx));
                    p = round(idx*100/m);
                    if p >= cp
                       fprintf(" %d%%  ",p); 
                       cp = cp+10;
                    end
                end
                fprintf(" \n "); 
            else
                for idx=1:numel(value)
                    this.root= this.insert(this.root, key(idx), value(idx));
                end
            end
        }


        function values = Find(keys) {
                values = this.find(this.root, keys);
/*              end */
        }
        function [l , u ] = FindClosest(keys) {
            n = numel(keys);
            if n == 1
                [l, u] = this.findclosest(this.root, keys);
            elseif n < 15
                l = zeros(1:n);
                u = zeros(1:n);
                for idx=1:n
                    [l(idx), u(idx)] = this.findclosest(this.root, keys(idx));
                end
            else
                [l, u] = this.findclosestmulti(repmat(this.root,1,length(keys)), keys);
            end
        }


        function  display() {
            this.printTree(this.root,0);
        }

        
    private: /* ( Dependent ) */


        function value = find(n,key) {
            value = [];
            while ~isempty(n)
                if lt(key,n.Key)
                    n = n.left;
                elseif gt(key,n.Key)
                    n = n.right;
                else
                    value = n.Value;
                    return;
                end
            end
        }
        function [l , u ] = findclosest(n,key) {
            u = []; l = [];
/*              minu = [];
 *             maxl = [];
             * Initialize with this node n, as it might be the smallest/largest */
            minu = n;
            maxl = n;
            while ~isempty(n)
                if lt(key,n.Key)
                    minu = n;
                    n = n.left;
                elseif gt(key,n.Key)
                    maxl = n;
                    n = n.right;
                else
                    l = n.Value;
                    u = l;
                    return;
                end
            end
            if ~isempty(minu)
               u = minu.Value;
            end
            if ~isempty(maxl)
               l = maxl.Value;
            end
        }
        function [l , u ] = findclosestmulti(n,keys) {
            u = inf(size(keys));
            l = -u;
            minu = BinTreeNode.empty(0,1);
            maxl = minu;
            while true
                lempt = cellfun(" isempty ",[n.left]);
                rempt = cellfun(" isempty ",[n.right]);

                low = lt(keys,[n.Key]);
                gre = gt(keys,[n.Key]);

                minu(low) = n(low);
                maxl(gre) = n(gre);

                golow = low & ~lempt;
                if any(golow)
                    n(golow) = [n(golow).left];
                end
                goup = gre & ~rempt;
                if any(goup)
                    n(goup) = [n(goup).right];
                end
                eq = ~low & ~gre;
                if any(eq)
                    u(eq) = [n(eq).Value];
                    l(eq) = [n(eq).Value];
                end
                if all(~golow & ~goup)
                    break;
                end
            end
            hasu = ~isnan([minu.Key]);
            u(hasu) = [minu(hasu).Value];
            hasl = ~isnan([maxl.Key]);
            l(hasl) = [maxl(hasl).Value];
        }
        function v = getvalues(n) {
            v = [];
            if ~isempty(n)
                v = [this.getvalues(n.left) n.Value this.getvalues(n.right)];
            end
        }



        function n = insert(n,key,value) {
            if isempty(n)
                n = BinTreeNode(key, value);
            elseif lt(key,n.Key)
                n.left= this.insert(n.left, key, value);
                if n.left.height - this.height(n.right)== 2
                    if lt(key, n.left.Key)
                        n = this.rotateWithLeftChild(n);
                    else
                        n = this.doubleWithLeftChild(n);
                    end
                end
            elseif gt(key, n.Key)
                n.right= this.insert(n.right, key, value);
                if  n.right.height - this.height(n.left) == 2
                    if gt(key, n.right.Key)
                        n = this.rotateWithRightChild(n);
                    else
                        n = this.doubleWithRightChild(n);
                    end
                end
            else
                error(" Duplicate entry! ");
            end
            n.height= max(this.height(n.left), this.height(n.right)) + 1;
        }


        function h = height(n) {
            if isempty(n)
                h = -1;
            else
                h = n.height;
            end
        }


        function n = rotateWithLeftChild(n2) {
            n = n2.left;
            n2.left= n.right;
            n.right= n2;
            n2.height= max(this.height(n2.left), this.height(n2.right)) + 1;
            n.height= max(this.height(n.left), n2.height) + 1;
        }


        function n = rotateWithRightChild(n2) {
            n = n2.right;
            n2.right= n.left;
            n.left= n2;
            n2.height= max(this.height(n2.left), this.height(n2.right)) + 1;
            n.height= max(this.height(n.right), n2.height ) + 1;
        }


        function n = doubleWithLeftChild(n) {
            n.left= this.rotateWithRightChild(n.left);
            n = this.rotateWithLeftChild(n);
        }


        function n = doubleWithRightChild(n) {
            n.right= this.rotateWithLeftChild(n.right);
            n = this.rotateWithRightChild(n);
        }


        function  printTree(n,ntabs) {
            if ~isempty(n)
                this.printTree(n.left,ntabs+1);
                fprintf([repmat(" \t ",1,ntabs) " %f => %f\n "], n.Key, n.Value);
                this.printTree(n.right,ntabs+1);
            end
        }

    
    public: /* ( Static ) */ /* ( Dependent ) */

        static function res = test_BinTree() {
            res = true;

            /* % Init */
            t = BinTree;
            n = 2^4;

            /* % Test usage as Key-Value BinaryTree */
            k = randperm(n);
            v = randperm(n);
            t.Insert(k,v);

            /*  Find all values for keys */
            for idx = 1:length(k)
                res = res && v(idx) == t.Find(k(idx));
            end
            /*  Test nonexistent key */
            res = res && isempty(t.Find(2*n));

            /*  Test multi-find
 *             vs = t.Find([k n+1]);
 *             res = res && all(v == vs(1:end-1)) && isnan(vs(end)); */

            /* % Test usage as simple BinaryTree */
            t.clear;
            v = randperm(n);
            t.Insert(v);

            /*  Check for correct ordering */
            res = res && all(sort(v) == t.Values);

            /*  Find all values */
            for value=v
                res = res && ~isempty(t.Find(value));
            end

            /*  Height check */
            h = t.Height;
            hlp = n / (2^(h+1));
            res = res && hlp <= 1;

            /*  Closeness check - select some random positions and check */
            ex = randperm(n-1)+1;
            ex = ex(1:round(n/2));
            ks = sort(k);
            for i=1:length(ex)
                ru = ks(ex(i));
                rl = ru-1;
                [l,u] = t.FindClosest((rl+ru)/2);
                res = res && l == rl && u == ru;
            end

            M = [2, 10, 100, 1000, 10000];
            R = [100, 60, 40, 20, 10]; 
            for j = 1:length(R)
                m = M(j);
                r = R(j);
                k = linspace(0,n+1,m);
                tmp = tic;
                for idx = 1:length(k)
                    [l,u] = t.FindClosest(k(idx)); /* #ok<*NASGU> */

                end
                ti(1,j) = toc(tmp); /* #ok<*AGROW> */


                tmp = tic;
                [l,u] = t.FindClosest(k);
                ti(2,j) = toc(tmp);
                ti = sum(ti,2)/r;
                fprintf(" Speed test of multi-find-closest of %d values (averaged over %d runs): %fs loop to %fs multi (factor %f faster).\n ",m,r,ti(1),ti(2),ti(1)/ti(2));
            end

            fprintf(" BinTree test finished with n=%d, h=%d, n/2^(h+1)=%f <! 1\n ",n,h,hlp);
        }

};