inequality.js

// a > b, b > c, b > a //=> false
// a > b, b > c //=> true


//can i talk about my thought now?
//hao a

//assume there's no duplicate name?
//every 'a' means the same element

//we could make a directed graph/tree (有向图)like structure
//like, a->b->c 
//a->b
// <-

//then we detect if there's circulation in the structure
//that's my thoughts

//so about implementation
//1. generate data structure from input
//- we need:
// ---node class
// ---hash object(we don;t want to generate duplication nodes, also, we need to remember the depth of each node)

//2.we need to do a BFS to see if there;s a circle
//- we need:
// --- queue for BFS
// --- the hash that generated from step 1
//---  the grpah generated from step 1

//3.we know there;s a circle when:
// no node has depth 0 after generated
// there's node has depth more than 0 after BFS

//done.

//omg
//i'm doing something i never did, putting both the node and the depth inside one hash
//i think it could work

var input0 = [
  ['a', 'b', 'c'],
  ['b', 'a']
]

var input1 = [
  ['z', 'a', 'b', 'c'],
  ['b', 'a']
]

var input2 = [
  ['a', 'b'],
  ['b', 'c']
]

var input3 = [
  [1,2,3,4],
  [4,1]
]

console.log(isValid(input0)) //=> false
console.log(isValid(input1)) //=> false
console.log(isValid(input2)) //=> true
console.log(isValid(input3)) //=> false

function isValid(arr){
  var hash = generate(arr)
  return detect(hash)
}

function Node(val){
  this.val = val
  this.children = []
}

function generate(arr){
  
  var hash = {}
  var root
  arr.forEach(function(path){
    root = null

    if(hash.hasOwnProperty(path[0])){
      root = hash[path[0]].node
    }else{
      root = new Node(path[0])
      hash[path[0]] = {
        node: root,
        depth: 0
      }
    }

    for(var i = 1; i < path.length; i++){

      var node = null

      if(hash.hasOwnProperty(path[i])){
         node = hash[path[i]].node
      }else{
        node = new Node(path[i])
        hash[path[i]] = {
          node: node,
          depth: 0
        }
      }  
      hash[path[i]].depth++
      root.children.push(node)
      root = node        
    }    
  })
  return hash
}

function detect(hash){
  var queue = []
  for(var key in hash){
    if(hash[key].depth === 0){
      queue.push(hash[key].node)
    }
  }
  
  if(queue.length === 0) return false
  
  while(queue.length > 0){
    var node = queue.shift()
    node.children.forEach(function(child){
      hash[child.val].depth--
      if(hash[child.val].depth === 0){
        queue.push(child)
      }
    })
  }
  
  for(var key in hash){
    if(hash[key].depth !== 0){
      return false
    }
  }
  
  return true
  
}