Travelling Salesman Sketches: BinaryTree

index.html

<div>
  <h1>No Sort</h1>
  <ul></ul>
</div>
<div>
  <h1>By X</h1>
  <ul></ul>
</div>
<div>
  <h1>By Y</h1>
  <ul></ul>
</div>
<div>
  <h1>By Prox</h1>
  <ul></ul>
</div>

script.babel

console.clear();
let tmpId = 0;

class BinaryTree {
  constructor(title) {
    this.title = title;
    this.rootNode = null;
    this.orderAB = null;
    this.orderBA = null;
  }

  // Setting a node as this tree's rootNode, or passing along to the rootNode
  add(node) {
    this.rootNode ? this.rootNode.add(node) : (this.rootNode = node);
  }

  // Recursively traversing through nodes to build an array of ids
  save() {
    let ascending = this.rootNode ? this.rootNode.traverse([]) : [];
    this.ascending = ascending;
    this.descending = ascending ? ascending.slice().reverse() : [];
  }

  // Recursively searching nodes for a value, returns an array of ids.
  search(value) {
    return this.rootNode ? this.rootNode.search(value) : [];
  }
}

class BinaryNode {
  // BinaryNode takes the value to sort by, and an identifier to return it's position by
  constructor({ value, id }) {
    // Ids is always an array (for handling duplicates)
    this.ids = [id];
    // Set the value
    this.value = value;
    if (value === undefined) console.warn(`No value provided for BinaryNode ${id}`);
    // Left is the "less than" node
    this.left = null;
    // Right is the "greater than" node
    this.right = null;
  }

  // Recursive function for finding a value in this node or this node's children
  search(value) {
    // If value is found here, return this node's ids.
    if (this.value === value) {
      return this.ids;
      // If value is less than here, and we have left, search "less thans".
    } else if (value < this.value && this.left) {
      return this.left.search(value);
      // If value is more than here, and we have right, search "greater thans".
    } else if (value > this.value && this.right) {
      return this.right.search(value);
    }
    // Value does not exist
    return null;
  }

  // Recursive function for building an array of ids in a sorted order
  traverse(array) {
    // If left, visit "less thans" down the chain
    if (this.left) array = this.left.traverse(array);
    // Add this node's ids
    array = array.concat(this.ids);
    // If right, visit "greater thans" down the chain
    if (this.right) array = this.right.traverse(array);
    // Return the array
    return array;
  }

  // Recursive function to set node as this node's left or right position
  //   or to pass along down left or right chain.
  add(node) {
    // If less, we defer to or set left
    if (node.value < this.value) {
      this.left ? this.left.add(node) : (this.left = node);
      // If greater, we defer to or set right
    } else if (node.value > this.value) {
      this.right ? this.right.add(node) : (this.right = node);
      // If same value, we add ids to this node
    } else {
      this.ids = this.ids.concat(node.ids);
    }
  }
}

// A dummy class containing data we want to be able to search.
class Vector {
  constructor({ x, y }) {
    this.x = x;
    this.y = y;
    this.prox = Math.hypot(0.5 - x, 0.5 - y);
    this.id = generateId();
    this.info = [
      `#${this.id}`,
      `${this.x}x`,
      `${this.y}y`,
      `${Math.round(this.prox)}p`
    ];
  }
}

let indexX = new BinaryTree("Vector X");
let indexY = new BinaryTree("Vector Y");
let indexP = new BinaryTree("Vector Proximity");

let vectors = {};
for (let i = 0; i < 50; i++) {
  let x = Math.round(Math.random() * 1000);
  let y = Math.round(Math.random() * 1000);
  let vector = new Vector({ x, y });
  vectors[vector.id] = vector;
  indexX.add(new BinaryNode({ id: vector.id, value: vector.x }));
  indexY.add(new BinaryNode({ id: vector.id, value: vector.y }));
  indexP.add(new BinaryNode({ id: vector.id, value: vector.prox }));
}

indexX.save();
indexY.save();
indexP.save();












let $ulS = document.querySelector('div:nth-of-type(1) ul');
let $ulX = document.querySelector('div:nth-of-type(2) ul');
let $ulY = document.querySelector('div:nth-of-type(3) ul');
let $ulP = document.querySelector('div:nth-of-type(4) ul');
Object.keys(vectors).forEach((id) => { 
  $ulS.appendChild(li(id, vectors[id].info));
});
indexX.ascending.forEach((id) => { 
  $ulX.appendChild(li(id, vectors[id].info));
});
indexY.ascending.forEach((id) => { 
  $ulY.appendChild(li(id, vectors[id].info));
});
indexP.ascending.forEach((id) => { 
  $ulP.appendChild(li(id, vectors[id].info));
});

function li(id, value) {
  let $li = document.createElement('li');
  $li.className = `id${id}`;
  $li.innerHTML = `<span>${value.join('</span><span>')}</span>`;
  $li.addEventListener('mouseenter', () => { handleMouseEnter(id); });
  $li.addEventListener('mouseleave', () => { handleMouseLeave(id); });
  return $li;
}

function handleMouseEnter(id) {
  let els = document.body.querySelectorAll(`.id${id}`);
  for (let i = 0; i < els.length; i++) els[i].classList.add('active');
}
  
function handleMouseLeave(id) {
  let els = document.body.querySelectorAll(`.id${id}.active`);
  for (let i = 0; i < els.length; i++) els[i].classList.remove('active');
}
  

let lis = document.body.querySelectorAll('li');
Array.from(lis).forEach((li) => {
  li.addEventListener('hover', () => {
    let classname = li.className;
    let els = document.body.querySelectorAll(`li.id${classname}`);
    Array.from(els).forEach((el) => {
      el.classList.add('active')
    })
  });
})

function generateId() {
  tmpId++;
  if (tmpId < 10) return `00${tmpId}`;
  if (tmpId < 100) return `0${tmpId}`;
  return tmpId.toString();
}

style.scss

html, body {
  height: 100%;
}
h1 {
  font-weight: 300;
  font-family: 'Helvetica Neue', Helvetica, sans-serif;
  color: white;
}
body {
  display: flex;
  padding: 0 0.5rem;
  background: #121212;
  div {
    flex: 1;
    text-align: center;
    box-sizing: border-box;
    padding: 0 0.5rem;
  }
}

ul {
  list-style: none;
  padding: 0;
  font-family: 'Operator Mono SSm', monospace;
  font-size: 0.8rem;
}

li {
  cursor: pointer;
  padding: 0.25rem 0;
  display: flex;
  justify-content: space-between;
  flex-wrap: wrap;
  color: #444;
  span {
    text-align: center;
    flex: 1;
  }
}

li.active {
  color: white;
  background: black;
}

travelling-salesman-sketches-binarytree.markdown

Travelling Salesman Sketches: BinaryTree

A Tree and Node class for Binary Search. Three unique sorts are shown here.

A Pen by HARUN PEHLİVAN on CodePen.

License.