leftist tree/leftist heap

leftist.js

class Leftist<A> {
  left: leftist<A>
  right: leftist<A>
  value: A
  rank: number
  constructor(value: A, rank: number, left: leftist<A>, right: leftist<A>) {
    this.value = value
    this.rank = rank
    this.left = left
    this.right = right
  }
}
type leftist<A> = null | Leftist<A>
class Cmd {
  static id = 0
  id = ++Cmd.id
  type: 'pure' | 'lock' | 'effect'
  data: any
  constructor(type, data) {
    this.type = type
    this.data = data
  }
}
const cmdGreaterThan = (a, b) => {
  if (a.type === b.type) return a.id > b.id
  const types = ['pure', 'lock', 'effect']
  const arank = types.indexOf(a.type)
  const brank = types.indexOf(b.type)
  return arank > brank
}
function singleton<A>(k: A): leftist<A> {
  return new Leftist(k, 1, null, null)
}

function rank<A>(tree: leftist<A>): number {
  if (tree) {
    return tree.rank
  } else {
    return 0
  }
}

function merge<A>(_t1: leftist<A>, _t2: leftist<A>, comparator = caml_greaterthan): leftist<A> {
  while (true) {
    const t2 = _t2
    const t1 = _t1
    if (t1) {
      if (t2) {
        const k1 = t1.value
        const l = t1.left
        console.log(k1, t2.value, comparator(k1, t2.value))
        if (comparator(k1, t2.value)) {
          _t2 = t1
          _t1 = t2
          continue
        } else {
          const merged = merge(t1.right, t2)
          const rank_left = rank(l)
          const rank_right = rank(merged)
          if (rank_left >= rank_right) {
            return new Leftist(k1, (rank_right + 1), l, merged)
          } else {
            return new Leftist(k1, (rank_left + 1), merged, l)
          }
        }
      } else {
        return t1
      }
    } else {
      return t2
    }
  }
  /*::return _t1*/
}

function insert<A>(x: A, t: leftist<A>, comparator = caml_greaterthan): leftist<A> {
  return merge(singleton(x), t, comparator)
}

function get_min(param) {
  if (param) {
    return some(param.value)
  }
}

function delete_min<A>(param: leftist<A>, comparator = caml_greaterthan): [A, leftist<A>] {
  if (param) {
    return [param.value, merge(param.left, param.right, comparator)]
  }
  throw Error('Failure: empty')
}


const zeroTree = singleton(new Cmd('pure', 'foo'))
const oneTree = insert(new Cmd('lock', 'bar'), zeroTree, cmdGreaterThan)
const twoTree = insert(new Cmd('effect', 'baz'), oneTree, cmdGreaterThan)
const threeTree = insert(new Cmd('lock', 'bar'), twoTree, cmdGreaterThan)
console.log(rank(threeTree), threeTree)
console.log(...iterate(threeTree, cmdGreaterThan))
function iterate(tree, comparator = caml_greaterthan) {
  const results = []
  while (tree) {
    const extracted = delete_min(tree, comparator)
    results.push(extracted[0])
    tree = extracted[1]
  }
  return results
}

//bucklescript's bullshit

const undefinedHeader = /* array */ []
function some(x) {
  if (x === undefined) {
    const block = /* tuple */ [undefinedHeader, 0]
    block.tag = 256
    return block
  } else if (x !== null && x[0] === undefinedHeader) {
    const nid = (x[1] + 1) | 0
    const block$1 = /* tuple */ [undefinedHeader, nid]
    block$1.tag = 256
    return block$1
  } else {
    return x
  }
}
function caml_greaterthan(a, b) {
  return caml_compare(a, b) > 0
}
function caml_bool_compare(x, y): 0 | 1 | -1 {
  if (x) {
    if (y) {
      return 0
    } else {
      return 1
    }
  } else if (y) {
    return -1
  } else {
    return 0
  }
}
function caml_int_compare(x, y): 0 | 1 | -1 {
  if (x < y) {
    return -1
  } else if (x === y) {
    return 0
  } else {
    return 1
  }
}
function caml_string_compare(s1, s2): 0 | 1 | -1 {
  if (s1 === s2) {
    return 0
  } else if (s1 < s2) {
    return -1
  } else {
    return 1
  }
}
function caml_compare(_a, _b): 0 | -1 | 1 {
  while (true) {
    const b = _b
    const a = _a
    if (a === b) {
      return 0
    } else {
      const a_type = typeof a
      const b_type = typeof b
      let exit = 0
      switch (typeof a) {
        case 'boolean':
          if (typeof b === 'boolean') {
            return caml_bool_compare(a, b)
          } else {
            exit = 1
          }
          break
        case 'function':
          if (typeof b === 'function') {
            throw Error('Invalid argument: compare: functional value')
          } else {
            exit = 1
          }
          break
        case 'number':
          if (typeof b === 'number') {
            return caml_int_compare(a, b)
          } else {
            exit = 1
          }
          break
        case 'string':
          if (typeof b === 'string') {
            return caml_string_compare(a, b)
          } else {
            return 1
          }
        case 'undefined':
          return -1
        default:
          exit = 1
      }
      if (exit === 1) {
        switch (typeof b) {
          case 'string':
            return -1
          case 'undefined':
            return 1
          default:
            if (a_type === 'boolean') {
              return 1
            } else if (b_type === 'boolean') {
              return -1
            } else if (a_type === 'function') {
              return 1
            } else if (b_type === 'function') {
              return -1
            } else if (a_type === 'number') {
              if (b === null || b.tag === 256) {
                return 1
              } else {
                return -1
              }
            } else if (b_type === 'number') {
              if (a === null || a.tag === 256) {
                return -1
              } else {
                return 1
              }
            } else if (a === null) {
              if (b.tag === 256) {
                return 1
              } else {
                return -1
              }
            } else if (b === null) {
              if (a.tag === 256) {
                return -1
              } else {
                return 1
              }
            } else {
              const tag_a = a.tag | 0
              const tag_b = b.tag | 0
              if (tag_a === 250) {
                _a = a[0]
                continue
              } else if (tag_b === 250) {
                _b = b[0]
                continue
              } else if (tag_a === 256) {
                if (tag_b === 256) {
                  return caml_int_compare(a[1], b[1])
                } else {
                  return -1
                }
              } else if (tag_a === 248) {
                return caml_int_compare(a[1], b[1])
              } else if (tag_a === 251) {
                throw Error('Invalid argument: equal: abstract value')
              } else if (tag_a !== tag_b) {
                if (tag_a < tag_b) {
                  return -1
                } else {
                  return 1
                }
              } else {
                const len_a = a.length | 0
                const len_b = b.length | 0
                if (len_a === len_b) {
                  if (Array.isArray(a)) {
                    const a$1 = a
                    const b$1 = b
                    let _i = 0
                    const same_length = len_a
                    while (true) {
                      const i = _i
                      if (i === same_length) {
                        return 0
                      } else {
                        const res = caml_compare(a$1[i], b$1[i])
                        if (res !== 0) {
                          return res
                        } else {
                          _i = (i + 1) | 0
                          continue
                        }
                      }
                    }
                  } else {
                    const a$2 = a
                    const b$2 = b
                    const min_key_lhs = /* record */ [/* contents */ undefined]
                    const min_key_rhs = /* record */ [/* contents */ undefined]
                    const do_key = (param, key) => {
                      const min_key = param[2]
                      const b = param[1]
                      if (
                        !b.hasOwnProperty(key)
                        || caml_compare(param[0][key], b[key]) > 0
                      ) {
                        const match = min_key[0]
                        if (match !== undefined && key >= match) {
                          return 0
                        } else {
                          min_key[0] = key
                          return /* () */ 0
                        }
                      } else {
                        return 0
                      }
                    }
                    const partial_arg = /* tuple */ [a$2, b$2, min_key_rhs]
                    const partial_arg$1 = /* tuple */ [b$2, a$2, min_key_lhs]
                    for (const key in a$2) {
                      do_key(partial_arg, key)
                    }
                    for (const key in b$2) {
                      do_key(partial_arg$1, key)
                    }
                    const match = min_key_lhs[0]
                    const match$1 = min_key_rhs[0]
                    if (match !== undefined) {
                      if (match$1 !== undefined) {
                        return caml_string_compare(match, match$1)
                      } else {
                        return -1
                      }
                    } else if (match$1 !== undefined) {
                      return 1
                    } else {
                      return 0
                    }
                  }
                } else if (len_a < len_b) {
                  const a$3 = a
                  const b$3 = b
                  let _i$1 = 0
                  const short_length = len_a
                  while (true) {
                    const i$1 = _i$1
                    if (i$1 === short_length) {
                      return -1
                    } else {
                      const res$1 = caml_compare(a$3[i$1], b$3[i$1])
                      if (res$1 !== 0) {
                        return res$1
                      } else {
                        _i$1 = (i$1 + 1) | 0
                        continue
                      }
                    }
                  }
                } else {
                  const a$4 = a
                  const b$4 = b
                  let _i$2 = 0
                  const short_length$1 = len_b
                  while (true) {
                    const i$2 = _i$2
                    if (i$2 === short_length$1) {
                      return 1
                    } else {
                      const res$2 = caml_compare(a$4[i$2], b$4[i$2])
                      if (res$2 !== 0) {
                        return res$2
                      } else {
                        _i$2 = (i$2 + 1) | 0
                        continue
                      }
                    }
                  }
                }
              }
            }
        }
      }
    }
  }
  /*::return 0*/
}