immutable hashmaps for dummies

hash.js

// murmurhash2 via https://gist.github.com/raycmorgan/588423

export default function doHash(str, seed) {
  var m = 0x5bd1e995;
  var r = 24;
  var h = seed ^ str.length;
  var length = str.length;
  var currentIndex = 0;

  while (length >= 4) {
    var k = UInt32(str, currentIndex);

    k = Umul32(k, m);
    k ^= k >>> r;
    k = Umul32(k, m);

    h = Umul32(h, m);
    h ^= k;

    currentIndex += 4;
    length -= 4;
  }

  switch (length) {
  case 3:
    h ^= UInt16(str, currentIndex);
    h ^= str.charCodeAt(currentIndex + 2) << 16;
    h = Umul32(h, m);
    break;

  case 2:
    h ^= UInt16(str, currentIndex);
    h = Umul32(h, m);
    break;

  case 1:
    h ^= str.charCodeAt(currentIndex);
    h = Umul32(h, m);
    break;
  }

  h ^= h >>> 13;
  h = Umul32(h, m);
  h ^= h >>> 15;

  return h >>> 0;
}

function UInt32(str, pos) {
  return (str.charCodeAt(pos++)) +
         (str.charCodeAt(pos++) << 8) +
         (str.charCodeAt(pos++) << 16) +
         (str.charCodeAt(pos) << 24);
}

function UInt16(str, pos) {
  return (str.charCodeAt(pos++)) +
         (str.charCodeAt(pos++) << 8);
}

function Umul32(n, m) {
  n = n | 0;
  m = m | 0;
  var nlo = n & 0xffff;
  var nhi = n >>> 16;
  var res = ((nlo * m) + (((nhi * m) & 0xffff) << 16)) | 0;
  return res;
}

function getBucket(str, buckets) {
  var hash = doHash(str, str.length);
  var bucket = hash % buckets;
  return bucket;
}

test.js

let t = make()
  ::log()

let t2 = set(t, 'x', 1)::log()

let t3 = del(set(set(set(t2, 'y', 2), 'z', 5), 'x', 3), 'z')::log()

map(t3, v => v +1)::log()

t::get('z')::log()

tree.js

function log() {
  console.dir(this)
  return this
}
const hasProp = {}.hasOwnProperty

function omit(obj, key) {
  if (!obj::hasProp(key)) {
    return obj
  }
  return Object.keys(obj).reduce((o, k) =>
    k === key ?
      o :
      (o[k] = obj[k], o),
    {})
}


import doHash from './hash'

function getHash(level = 0, key) {
  // generate a number between 0 - 31
  return doHash(`${level}:${key}`, 5381)%32 + ''
}

export function make(level = 0) {
  return {
    level, hashes: {}
  }
}

export function isTree(tree) {
  return tree && tree::hasProp('hashes') && tree::hasProp('level')
}

export function set(tree, key, value) {
  let hash = getHash(tree.level, key),
    hashes = tree.hashes

  if(!hasHash(tree, key)) {
    return {
      ...tree,
      hashes: {
        ...hashes,
        [hash]: { key, value }
      }
    }
  }
  else if(isTree(hashes[hash])) {
    return {
      ...tree,
      hashes: {
        ...hashes,
        [hash]: set(hashes[hash], key, value)
      }
    }
  }
  else {
    if(hashes[hash].key === key) {
      if(hashes[hash].value === value) {
        return tree
      }
      return {
        ...tree,
        hashes: {
          ...hashes,
          [hash]: { key, value }
        }
      }
    }
    return {
      ...tree,
      hashes: {
        ...hashes,
        [hash]: set(
          set(
            make(tree.level + 1),
            hashes[hash].key,
            hashes[hash].value),
          key,
          value)
      }
    }
  }
}


export function get(tree, key) {
  let hash = getHash(tree.level, key),
    { hashes } = tree

  if(!hasHash(tree, key)) {
    return
  }
  else if(isTree(hashes[hash])) {
    return get(hashes[hash], key)
  }
  else {
    if(hashes[hash].key === key) {
      return hashes[hash].value
    }
  }
}

export function del(tree, key) {
  let hash = getHash(tree.level, key),
    { hashes } = tree

  if(!hasHash(tree, key)) {
    return tree
  }

  else if(isTree(hashes[hash])) {
    return del(hashes[hash], key)
  }
  else {
    if(hashes[hash].key === key) {
      return {
        ...tree,
        hashes: omit(hashes, hash)
      }
    }
    return tree
  }
}

export function *entries(tree) {
  let hashes = tree.hashes
  for(let key of Object.keys(hashes)) {
    if(!isTree(hashes[key])) {
      yield [ hashes[key].key, hashes[key].value ]
    }
    else{
      yield* entries(hashes[key])
    }
  }
}

// todo - more performant
export function map(tree, fn) {
  let mapped = tree
  for(let [ key, value ] of entries(tree)) {
    let computed = fn(value, key)
    if(computed !== value) {
      mapped = set(mapped, key, computed)
    }
  }
  return mapped
}

export function hasHash(tree, key) {
  return tree.hashes::hasProp(getHash(tree.level, key))
}