MMR

// fs.writeFile('thing1',Buffer.from('34','hex'), (e,r,a)=>{console.log(e,r,a)})
/*
node
.load MMR.js

*/

class MMR extends Array{
  constructor(){
    super(0)
  }
  put(value){
    this.push(value)
    while(MMR.isRight(this.length-1)){
      this.push(MMR.hash(MMR.leftSib(this.length-1), this.length-1))
    }
  }

  get(n){
    let total = 0
    let ph = MMR.peakHeight(n-1) + 1
    while(ph >= 0){
      console.log("PH ", ph)
      if(n >= 2**ph){
        total += 2**(ph+1)-1
        n -= 2**ph
      }
      ph--
    }
    return total
  }
    // while(2**(exponent) < n){
    //   exponent++
    // }
    // return exponent - 2
  // get(0)
  // get(1)
  // get(2)
  // get(3)
  // get(4)
  // get(5)
  // get(6)
  // get(7)
  // get(8)
  // get(9)
  // prev(n){

  // }
  // next(n){

  // }

  static leftSib(i){
    return i + 1 - 2**(this.height(i) + 1)
  }
  static rightSib(i, h){
    return i + 2**(this.height(i) + 1) - 1
  }

  static isRight(i){
    let ph = this.peakHeight(i)
    while(ph > - 2){
      if(2**(ph+2) - 2 == i){
        return false
      }
      if(2**(ph+2) - 2 < i){
        i = i - (2**(ph+2) - 1)
      } 
      if(2**(ph+2) - 2 == i){
        return true
      }
      ph--
    }
  }

  static peakHeight(i){
    let exponent = 0
    while(2**exponent - 3 < i){ exponent++ }
    return exponent - 2
  }
  static peak(i){ 
    return 2**(this.peakHeight(i)+1) - 2
  }
  static height(i){
    let ph = this.peakHeight(i)
    while(ph > - 2){
      if(2**(ph+2) - 2 < i){
        i = i - (2**(ph+2) - 1)
      } 
      if(2**(ph+2) - 2 == i){
        return ph + 1
      }
      ph--
    }
  }
  static hash(a,b) {
    return "h("+a+","+b+")"
  }
}

r = new MMR()
r.put(0)
r.put(1)
r.put(3)
r.put(4)
r.put(7)
r.put(8)
r.put(10)
r.put(11)
r.put(15)
r.put(16)
r.put(18)



 // static getRight(gi){ //untested
  //   return gi + (2**(this.gh(gi)) - 1) -1
  // }
  // static isRight(i){
  //   let h = 1
  //   while(2**h-1 <= i){ h++ }
  //   while(h > 0){
  //     if(2**h-1 == i){
  //       return false
  //     }
  //     if(2**h-1 < i){
  //       i = i - (2**h-1)
  //     } 
  //     if(2**h-1 == i){
  //       return true
  //     }
  //     h--
  //   }
  // }

// class Node{
//   constructor(index, value, height){
//     this.index = index
//     this.value = value
//     this.height = height
//   }
//   getHeight(){
//     if(this.height){
//       return this.height
//     }else{
//       let h = 1
//       while(2**h-1 <= this.index){ h++ }
//       while(h > 0){
//         if(2**h-1 < this.index){
//           this.index = this.index - (2**h-1)
//         } 
//         if(2**h-1 == this.index){
//           return h - 1
//         }
//         h--
//       }
//     }
//   }
// }

// function peakHeight(input){
//   let output = 0
//   for(let i = 0 ; 2**i - 1 <= input ; i++){
//     output = i - 1
//   }
//   return output
// }
// function peak(input){
//   let output = 0
//   for(let i = 0 ; 2**i -1 <= input ; i++){
//     output = 2**i - 1
//   }
//   return output
// }
// function peaks(input){
//     let lastPeak = peak(input)
//     let output = [lastPeak]
//     for(let i = 0 ; lastPeak >= input ; i++){
//         //console.log(input, lastPeak)
//         tempPeak = peak(input - lastPeak)
//         output.push(lastPeak + tempPeak)
//         lastPeak = lastPeak + tempPeak
//     }
//     return output
// }
// function leftSib(input, h){ // √
//     return input - 2**(h+1) + 1
// }
// function rightSib(input, h){
//     return input + 2**(h+1) - 1
// }
// function direction(i){
//   let h = 1
//   while(2**h-1 <= i){ h++ }
//   while(h > 0){
//     if(2**h-1 == i){
//       return "left"
//     }
//     if(2**h-1 < i){
//       i = i - (2**h-1)
//     } 
//     if(2**h-1 == i){
//       return "right"
//     }
//     h--
//   }
// }
// function direction(i){
//   let index = i
//   let h = 1
//   while(2**h-1 <= i){ h++ }
//   while(h > 0){
//     if(2**h-1 == i){
//       return "left"
//     }
//     if(2**h-1 < i){
//       i = i - (2**h-1)
//     } 
//     if(2**h-1 == i){
//       return "hash("+index+""+ index - 1")"
//     }
//     h--
//   }
// }

// function peaks(input){
//   let output = []
//   for(let i = 0 ; 2**i - 1 < input ; i++){
//     output.push()
//   }
//   return output
// }