binary-tree.html

<dom-module id="binary-tree">
  <template>
    <style>
      :host {
        position: relative;
        display: block;
        width: 100%;
        box-sizing: border-box;
      }
      paper-dialog {
        padding: 16px;
      }
      paper-item {
        cursor: pointer;
      }
      #context {
        position: fixed;
        visibility: collapse;
        background: white;
        z-index: 1;
        cursor: pointer;
      }
      #context paper-item:hover{
        background-color: rgba(255, 255, 255, 0.2);
      }
      #nodeContainer {
        margin: 8px;
        width: calc(100% - 32px);
        /*background: url(http://blog.hdwallsource.com/wp-content/uploads/2016/01/paper-wallpaper-45968-47250-hd-wallpapers.jpg);*/
        background: url(./background.jpg);
        height: 50px;
      }
      #connections {
        position: absolute;
      }
      binary-node#tree {
        left: calc(50% - 25px);
      }
      #name {
        position: absolute;
        left: calc(50% - 90px);
        top: -10px;
        width: 60px;
      }
      #completness {
        position: absolute;
        top: 15px;
        left: calc(50% + 25px);
        font-size: small;
      }
    </style>
    <paper-toast id="noVal" text="Please provide an value"></paper-toast>

    <paper-material id="context">
      <paper-item on-tap="_traverseSubtree">
        <iron-icon icon="filter-list" style="margin-right: 8px;"></iron-icon>
        Traverse Subtree
      </paper-item>
      <paper-item on-tap="_addNodeOrdered">
        <iron-icon icon="add" style="margin-right: 8px;"></iron-icon>
        Add Node ordered
      </paper-item>
      <paper-item on-tap="_deleteNode">
        <iron-icon icon="delete" style="margin-right: 8px;"></iron-icon>
        Delete Node
      </paper-item>
      <paper-item on-tap="_deleteSubtree">
        <iron-icon icon="delete" style="margin-right: 8px;"></iron-icon>
        Delete Subtree
      </paper-item>
      <paper-item on-tap="_copySubtree">
        <iron-icon icon="content-copy" style="margin-right: 8px;"></iron-icon>
        Copy Subtree
      </paper-item>
      <paper-item on-tap="_cutSubtree">
        <iron-icon icon="content-cut" style="margin-right: 8px;"></iron-icon>
        Cut Subtree
      </paper-item>
      <paper-item on-tap="_pasteSubtree">
        <iron-icon icon="content-paste" style="margin-right: 8px;"></iron-icon>
        Paste Subtree
      </paper-item>
    </paper-material>

    <paper-dialog id="selectValue" modal>
      <h2>Please insert a value for the node</h2>
      <paper-dialog-scrollable>
        <paper-input label="value" value="{{_value}}" autofocus required></paper-input>
      </paper-dialog-scrollable>
      <div class="buttons">
        <paper-button dialog-dismiss>Cancel</paper-button>
        <paper-button dialog-confirm>Add Node</paper-button>
      </div>
    </paper-dialog>

    <paper-material id="nodeContainer" class="unselectable" style$="[[_height]]">
      <canvas id="connections"></canvas>
      <div id="name">
        <paper-input label="name" value="{{name}}"></paper-input>
      </div>
      <div id="completness">[[completness]]</div>
      <binary-node id="tree" x="0" y="0"></binary-node>
    </paper-material>
  </template>
  <script>
    Polymer({
      is: 'binary-tree',

      properties: {
        /**
         * Name of the tree
         * @attribute name
         * @type String
         */
        name: {
          type: String,
          value: ''
        },
        history: {
          type: Array,
          value: function() {return [];}
        },
        /**
         * The complete tree structure
         * Each node has a `node`, a `left` and a `right` attribute,
         * where `right` and `left` are `Objects` (with same attributes) themself
         * @attribute tree
         * @type Object
         */
        tree: {
          type: Object,
          value: function () {
            return {
              left: null,
              right: null
            }
          }
        },
        /**
         * If the tree is complete
         * @attribute complete
         * @type Boolean
         */
        complete: {
          type: Boolean,
          value: false
        },
        /**
         * If the tree is full
         * @attribute full
         * @type Boolean
         */
        full: {
          type: Boolean,
          value: false
        }
      },

      listeners: {
        'nodeMoved': 'repaintConnections',
        'addChild': '_onAddChild',
        'iron-overlay-closed': 'addChild',
        'nodeContext': '_onNodeContext',
        'drawerChanged': 'repaintConnections'
      },

      observers: [
        '_treeUpdated(tree.*)',
        '_computeCompletnessString(full, complete)'
      ],

      /**
       * Set's the string indicating the completness of the tree
       * @param {Boolean} full If the tree is full
       * @param {Boolean} complete If the tree is complete
       */
      _computeCompletnessString: function(full, complete) {
        if(complete)
          this.completness = 'complete';
        else if(full)
          this.completness = 'full';
        else
          this.completness = 'Not complete or full';
      },

      /**
       * Checks whether the tree is `complete`, `full` or `neither`
       * @return An String indicating the completness
       */
      computeCompletness: function () {
        var d = this.getMaxDepth(this.tree);
        var children = this.getChildrenCount(this.tree);
        var computedChildren = Math.pow(2, d) - 1;

        if(children === computedChildren) {
          this.complete = true;
          this.full = true;
          return 'complete';
        } else if(this._isFull(this.tree)) {
          this.complete = false;
          this.full = true;
          return 'full';
        } else {
          this.complete = false;
          this.full = false;
          return 'neither';
        }
      },

      /**
       * Get's the max depth of a given node
       * @param {Object} node The node object to get the max depth from
       * @return The 'max depth of the node' + 1
       */
      getMaxDepth: function(node) {
        if(node) {
          var lDepth = this.getMaxDepth(node.left);
          var rDepth = this.getMaxDepth(node.right);

          if(lDepth > rDepth)
            return 1 + lDepth;
          return 1 + rDepth;
        } else {
          return 0;
        }
      },

      /**
       * Get's the total number of children
       * @param {Object} node The node object to get the total children number from
       * @return The total number of children
       */
      getChildrenCount: function(node) {
        if(node)
          return 1 + this.getChildrenCount(node.right) + this.getChildrenCount(node.left);
        return 0;
      },

      /**
       * Check's if each node has to children or none
       * @param {Object} node The node object to check for
       * @return If the tree is full
       */
      _isFull: function(node) {
        if(!node.left && !node.right)
          return true;
        if(node.left && !node.right)
          return false;
        if(node.right && !node.left)
          return false;
        return this._isFull(node.left) && this._isFull(node.right);
      },

      _treeUpdated: function (changeRecord) {
        this.computeCompletness();
        // var nodes = this.querySelectorAll('binary-node');
        // var node = changeRecord.value;
        var clone = JSON.parse(JSON.stringify(changeRecord));
        this.push('history', {
          changeRecord: clone,
          timestamp: new Date()
        });
        var path = changeRecord.path;

        // Remove Occurence of 'value'
        var valOcc = path.search('.value');
        if(valOcc !== -1)
          path = path.substring(0, valOcc);

        /*var pathElements = path.split('.');
        var parentId = pathElements.splice(0, pathElements.length - 1).join('.');
        var parent = this.getElementById(nodes, parentId);*/

        if(path === 'tree' && node == null) {
          this.fire('deleteTree');
          return;
        }

        this.repaintSubtree(path);

        /*for(var i=0; i<nodes.length; i++) {
          if(nodes[i].id === path) {
            if(node === null) {
              parent[pathElements[pathElements.length - 1]] = false;
              this.$.nodeContainer.removeChild(nodes[i]);
            } else if(typeof node === 'string') {
              nodes[i].value = node;
            }
          }
        }

        if(this.getElementById(nodes, path) == null) {
          var y = parent.y + 50;
          var parentX = parent.x;
          var x = (pathElements[pathElements.length - 1] === 'left') ? parentX - 50 : parentX + 50;
          var el = document.createElement('binary-node');

          el.id = path;
          el.value = node.value;

          el.x = x;
          el.y = y;

          this.$.nodeContainer.appendChild(el);
        }*/

        this.repaintConnections();
      },

      repaintSubtree: function(path) {
        var nodes = this.querySelectorAll('binary-node');
        var node = this.get(path);
        var nodeElement = this.getElementById(nodes, path);
        if(nodeElement) {
          if(node == null && path !== 'tree') {
            this.$.nodeContainer.removeChild(nodeElement);
          } else {
            nodeElement.value = node.value;
          }
        } else {
          if(node.value != null) {
            var pathElements = path.split('.');
            var parentId = pathElements.splice(0, pathElements.length - 1).join('.');
            var parent = this.getElementById(nodes, parentId);

            var y = parent.y + 50;
            var parentX = parent.x;
            var x = (pathElements[pathElements.length - 1] === 'left') ? parentX - 50 : parentX + 50;
            
            var el = document.createElement('binary-node');
            el.id = path;
            el.value = node.value;
            el.x = x;
            el.y = y;

            this.$.nodeContainer.appendChild(el);
          }
        }

        if(this.getElementById(nodes, path + '.left') || (node && node.left))
          this.repaintSubtree(path + '.left');
        if(this.getElementById(nodes, path + '.right') || (node && node.right))
          this.repaintSubtree(path + '.right');
      },

      /**
       * Callback for the addChild Event
       * @param {Object} e e.detail.left/.right defines if node should be added left/right
       */
      _onAddChild: function(e) {
        this._parent = e.target;
        if(e.detail.left) 
          this._side = 'left';
        else
          this._side = 'right';
        this._value = '';
        this._ordered = false;
        this.$.selectValue.open();
      },

      /**
       * Callback for the addNode Dialog, adds a child
       * @param {Object} e 
       */
      addChild: function (e) {
        if(e.detail.confirmed && this._value !== '') {
          if(this._ordered) {
            this.addNodeOrdered(this._path, this._value);
          } else {
            this._parent[this._side] = true;

            var path = this._parent.id + '.' + this._side;
            this.set(path, {
              value: this._value,
              right: null,
              left: null
            });
          }
        } else {
          if(this._value === '' && e.detail.confirmed)
            // Show warning for missing node value
            this.$.noVal.show();
        }
      },

      _addNodeOrdered: function() {
        var path = this._contextTarget.id;
        this.$.context.style.visibility = 'collapse';
        this._ordered = true;
        this._path = path;
        this._value = '';
        this.$.selectValue.open();
      },

      addNodeOrdered: function(path, value) {
        var node = this.get(path);

        if(this.compareNode(node.value, value) > 0) {
          if(node.left == null) {
            var nodes = this.querySelectorAll('binary-node');
            var parent = this.getElementById(nodes, path);
            parent.left = true;
            this.set(path + '.left', {
              value: this._value,
              right: null,
              left: null
            });
          } else {
            this.addNodeOrdered(path + '.left', value);
          }
        } else {
          if(node.right == null) {
            var nodes = this.querySelectorAll('binary-node');
            this.getElementById(nodes, path).right = true;
            this.set(path + '.right', {
              value: this._value,
              right: null,
              left: null
            });
          } else {
            this.addNodeOrdered(path + '.right', value);
          }
        }

      },

      _traverseSubtree: function() {
        this.$.context.style.visibility = 'collapse';
        this.fire('traverseSubtree', {
          node: this.get(this._contextTarget.id)
        });
      },

      /**
       * Listener method for the delete subtree context menu item
       */
      _deleteSubtree: function() {
        var path = this._contextTarget.id;
        this.$.context.style.visibility = 'collapse';
        this.deleteSubtree(path);
      },

      /**
       * Deletes a whole subtree
       * @param {String} path The path to the subtree
       */
      deleteSubtree: function(path) {
        this.set(path, null);
      },

       /**
       * Listener method for the delete subtree context menu item
       */
      _deleteNode: function() {
        var path = this._contextTarget.id;
        this.$.context.style.visibility = 'collapse';
        this.deleteNode(path);
      },

      /**
       * Deletes a node
       * @param {String} path The path to the node
       */
      deleteNode: function(path) {
        var node = this.get(path);
        if(!node.right && !node.left)
          this.set(path, null);
        else if(!node.right && node.left) {
          this.set(path + '.value', node.left.value);
          this.deleteNode(path + '.left');
        } else if(node.right && !node.left) {
          this.set(path + '.value', node.right.value);
          this.deleteNode(path + '.right');
        } else {
          var min = this.findMin(node.right);
          var value = min.value;
          var minPath = path + '.right' + min.path;
          this.set(path + '.value', value);
          this.deleteNode(minPath);
        }
      },

      _copySubtree: function() {
        var path = this._contextTarget.id;
        this.$.context.style.visibility = 'collapse';
        this.copySubtree(path);
      },

      copySubtree: function(path) {
        var node = this.get(path);
        var jsonNode = JSON.stringify(node);
        // cookie = MD5('clipboard')
        setCookie('bbc4df4047bb91ef515ce03a6317fd65', jsonNode, 100);
      },

      _cutSubtree: function() {
        var path = this._contextTarget.id;
        this.$.context.style.visibility = 'collapse';
        this.cutSubtree(path);
      },

      cutSubtree: function(path) {
        var node = this.get(path);
        var jsonNode = JSON.stringify(node);
        // cookie = MD5('clipboard')
        setCookie('bbc4df4047bb91ef515ce03a6317fd65', jsonNode, 100);
        this.set(path, null);
      },

      _pasteSubtree: function() {
        var path = this._contextTarget.id;
        this.$.context.style.visibility = 'collapse';
        this.pasteSubtree(path);
      },

      pasteSubtree: function(path) {
        // cookie = MD5('clipboard')
        var clipboard = getCookie('bbc4df4047bb91ef515ce03a6317fd65');
        var node = JSON.parse(clipboard);
        var parentNode = this.get(path);
        if(this.compareNode(parentNode.value, node.value) > 0)
          this.set(path + '.left', node);
        else
          this.set(path + '.right', node);
      },

      findMin: function(node) {
        if (!node) 
          return null;

        var min = {
          value: node.value,
          path: ''
        };

        if(node.left)
          var minL = this.findMin(node.left);
        if(node.right)
          var minR = this.findMin(node.right);

        if(minL) {
          if(this.compareNode(min.value, minL.value) > 0)
            min.value = minL.value;
        }
        if(minR) {
          if(this.compareNode(min.value, minR.value) > 0)
            min.value = minR.value;
        }

        if(minR && min.value === minR.value) {
          min.path = '.right' + minR.path;
        } else if(minL && min.value === minL.value) {
          min.path = '.left' + minL.path;
        }

        return min;
      },

      compareNode: function(ref, comp) {
        if(comp.match(/^[0-9]+$/) != null) {
            var refNum = new Number(ref);
            var compNum = new Number(comp);
            if(compNum < refNum)
              return 1;
          } else if(comp.localeCompare(ref) < 0) {
            return 1;
          }
          return -1;
      },

      /**
       * Count the occurrences of type type in an array
       * @param {Array} array The array to search in
       * @param type The variable to search in the array
       * @return The occurrences of the type
       */
      countOccurrences: function(array, type) {
        var result = 0;
        for(var i = 0; i< array.length; i++) {
          if(array[i] === type)
            result++;
        }
        return result;
      },

      _onNodeContext: function(e) {
        this._contextTarget = e.target;
        this.$.context.style.left = e.detail.x + 'px';
        this.$.context.style.top = e.detail.y + 'px';
        this.$.context.style.visibility = 'visible';
      },

      /**
       * Callback for the resize callback
       * Resizes the canvas height and width
       */
      _onResize: function () {
        var nodes = this.querySelectorAll('binary-node');
        var maxY = 0;

        for(var i=0; i<nodes.length; i++) {
          if(nodes[i].y > maxY) {
            maxY = nodes[i].y;
          }
        }

        this._height = 'height: calc(' + maxY + 'px + 50px)';

        var canvas = this.$.connections;

        var target = canvas.parentNode.getBoundingClientRect();
        if(target) {
          canvas.width = target.width;
          canvas.height = target.height;
        }
      },

      /**
       * Repaints all branches between the nodes
       */
      repaintConnections: function() {
        this._onResize();
        var nodes = this.querySelectorAll('binary-node');
        var canvas = this.$.connections;
        var ctx = canvas.getContext('2d');
        var width = canvas.width;
        var halfW = width / 2;
        var maxY = 0;

        ctx.clearRect(0 , 0, canvas.width, canvas.height);

        for(var i=0; i<nodes.length; i++) {
          var id = nodes[i].id;
          var node = this.get(id);
          var x = nodes[i].x;
          var y = nodes[i].y;

          if(node.right) {
            var childPath = id + '.right';
            var child = this.getElementById(nodes, childPath);
            var cX = child.x;
            var cY = child.y;

            ctx.beginPath();
            ctx.moveTo(x + 15 + halfW, y + 44);
            ctx.lineTo(cX + halfW, cY + 10);
            ctx.stroke();
          }
          if(node.left) {
            var childPath = id + '.left';
            var child = this.getElementById(nodes, childPath);
            var cX = child.x;
            var cY = child.y;
            
            ctx.beginPath();
            ctx.moveTo(x + 11 - 25 + halfW, y + 44);
            ctx.lineTo(cX + halfW, cY + 10);
            ctx.stroke();
          }
        }
      },

      /**
       * Get's an element by id in the base array
       * @param {Array} base The array to search in for the suitable id
       * @param {String} id The id to search for
       * @return The node with the id 
       */
      getElementById: function(base, id) {
        for(var i=0; i< base.length; i++) {
          if(base[i].id === id)
            return base[i];
        }
        return null;
      },

      closeContextMenu: function(e) {
        if(this.$.context.style.visibility === 'visible') {
          if(e.target.parentNode === this.$.context || e.target.parentNode.parentNode === this.$.context)
            return;
          this.$.context.style.visibility = 'collapse';
        }
      },

      setTree: function(path, value) {
        this.set(path, value);
      },

      getParentApp: function() {
        var parent = this;
        while(parent.tagName !== 'BINARYTREE-VISUALISATION') {
          parent = parent.parentNode;
        }
        return parent;
      },

      attached: function() {
        window.addEventListener('resize', this.repaintConnections.bind(this));
        window.addEventListener('click', this.closeContextMenu.bind(this));
        this._onResize();
      },

      detached: function() {
        window.removeEventListener('resize', this.repaintConnections);
        window.removeEventListener('click', this.closeContextMenu);

      }
    });
  </script>
</dom-module>