PersistentMap.js

"use strict";

function freeze(o) {
  if(!Object.isFrozen(o)) {
    Object.freeze(o);
  }
  return o;
}

Number.prototype.toBinary = function(word) {
  var bin = this.toString(2),
      pad = new Array(word - bin.length + 1),
      ret = pad.join('0') + bin;

  return ret.match(/.{1,4}/g).join(' ');
};


function PersistentHashMapLeaf(k, v, values, collided) {
  this._key      = k;
  this._value    = v;
  this._values   = values ? freeze(values) : values;
  this._collided = collided;
  
  freeze(this);
};

PersistentHashMapLeaf.EMPTY = new PersistentHashMapLeaf(null, null, null, false);

PersistentHashMapLeaf.prototype.set = function(key, value) {
  var newValues, k;
  
  if(this === PersistentHashMapLeaf.EMPTY) {
    // It's the EMPTY node
    return new PersistentHashMapLeaf(key, value, this._values, this._collided);  
 
  } else if((this._key === key && this._value === value) || (this._values && this._values[key] === value)) {
    // no modifications
    return this;
    
  } else if(this._key === key) {
    // The value at the primary key has changed
    return new PersistentHashMapLeaf(key, value, this._values, this._collided);
    
  } else if(this._collided) {
    newValues = {};
    
    for(k in this._values) {
      if(this._values.hasOwnProperty(k)) {
        newValues[k] = this._values[k];
      }
    }
    
    newValues[key] = value;
    
    return new PersistentHashMapLeaf(this._key, this._value, newValues, this._collided);
    
  } else {
    newValues = {};
    newValues[key] = value;
    
    return new PersistentHashMapLeaf(this._key, this._value, newValues, true);
  }
};

PersistentHashMapLeaf.prototype.get = function(key) {
  if(this._key === key) {
    return this._value;

  } else if(this._collided) {
    return this._values[key];
  
  } else {
    return undefined;
    
  }
};

PersistentHashMapLeaf.prototype.remove = function(key) {
  var newValues = {}, k,
      newPk, newPv, i;

  if(this._key === key && !this._collided) {
    return null;
  } else if(this._key === key) {
    i = 0;
    
    for(k in this._values) {
      if(this._values.hasOwnProperty(k)) {
        if(!newPk) {
          newPk = k;
          newPv = this._values[k];
        } else {
          i += 1;
          newValues[k] = this._values[k];
        }
      }
    }
        
    return new PersistentHashMapLeaf(newPk, newPv, newValues, i > 0);

  
  } else if(this._collided) {
    
    for(k in this._values) {
      if(this._values.hasOwnProperty(k) && k !== key) {
        newValues[k] = this._values[k];
      }
    }

    return new PersistentHashMapLeaf(this._key, this._value, newValues, this._collided);

  } else {
    // Nothing to remove.
    return this;  
  }
};



function PersistentMapNode(mask, children) {
  this._mask     = mask;
  this._children = freeze(children);

  freeze(this);
}

PersistentMapNode.EMPTY = new PersistentMapNode(0, []);

// Based on Bagwell's popcount implementation in Ideal Hash Trees
PersistentMapNode.prototype._popcount = function(bits) {
  var SK5  = 0x55555555,
      SK3  = 0x33333333,
      SKF0 = 0x0f0f0f0f,
      SKFF = 0xff00ff;

  bits -= (bits >> 1) & SK5;
  bits  = (bits & SK3) + ((bits >> 2) & SK3);
  bits  = (bits & SKF0) + ((bits >> 4) & SKF0);
  bits += bits >> 8;

  return (bits + (bits >> 15)) & 63;
};

PersistentMapNode.prototype.set = function(shift, hash, key, value) {
  var mask     = this._mask,
      children = this._children,
      maskPos  = 1 << ((hash >>> shift) & 31), // calcluates posistion in bitmask
      index    = this._popcount(mask & (maskPos - 1)),
      child,
      newChildren;

  if(mask & maskPos) {
    child = children[index];

    if(child instanceof PersistentHashMapLeaf) {
      return new PersistentMapNode(mask, [].concat(
        children.slice(0,index),
        child.set(key, value),
        children.slice(index + 1)
      ));
    } else if(child instanceof PersistentMapNode) {
      return new PersistentMapNode(mask, [].concat(
        children.slice(0, index),
        child.set(shift + 5, hash, key, value),
        children.slice(index + 1)
      ));
    }    
  } else {
    newChildren = [].concat(
      children.slice(0,index),
      PersistentHashMapLeaf.EMPTY.set(key, value),
      children.slice(index));

    return new PersistentMapNode(mask | maskPos, newChildren);
  }
};


PersistentMapNode.prototype.get = function(shift, hash, key) {
  var mask = this._mask,
      maskPos = 1 << ((hash >>> shift) & 31),
      child;

  if(mask & maskPos) {
    child = this._children[this._popcount(mask & (maskPos - 1))];

    if(child instanceof PersistentMapNode) {
      return child.get(shift + 5, hash, key);
    } else if(child instanceof PersistentHashMapLeaf) {
      return child.get(key);
    }
  }

  return undefined;
};

PersistentMapNode.prototype.unset = function(shift, hash, key) {
  var mask = this._mask,
      maskPos = 1 << ((hash >>> shift) & 31),
      newChild,
      index,
      child;

  if(mask & maskPos) {
    index = this._popcount(mask & (maskPos - 1))
    child = this._children[index];

    if(child instanceof PersistentMapNode) {
      newChild = child.unset(shift + 5, hash, key);

      return new PersistentMapNode(mask, [].concat(
        this._children.slice(0, index),
        newChild,
        this._children.slice(index)
      ));
    } else if(child instanceof PersistentHashMapLeaf)  {
      newChild = child.remove(key);
      
      if(newChild === null) {
        return new PersistentMapNode(mask & (~maskPos), [].concat(
          this._children.slice(0,index),
          this._children.slice(index+1)
        ));
      } else {
        return new PersistentMapNode(mask, [].concat(
          this._children.slice(0,index),
          newChild,
          this._children.slice(index+1)
        ));
      }
      
    }
  }
  return this;
};


function PersistentMap(root) {
  this._root  = root;
  freeze(this);
}

PersistentMap.EMPTY = new PersistentMap(PersistentMapNode.EMPTY);

PersistentMap.create = function(map) {
  var ret = PersistentMap.EMPTY,
      k;

  for(k in map) {
    if(map.hasOwnProperty(k)) {
      ret = ret.set(k, map[k]);
    }
  }
  
  return ret;
};

PersistentMap.prototype._hash = function(v) {
  if(typeof v === 'number') {
    return v >> 0;
  } else if(typeof v === 'string') {
    for(var h = 0, i = 0, l = v.length; i < l; i += 1) {
      h = (((h << 5) - h) + v.charCodeAt(i));
    }
    return (h >> 0);
  } else {
    throw new Error("Value " + v + " is not string or number!");
  }
};

PersistentMap.prototype.keys = function() {};
PersistentMap.prototype.values = function() {};
PersistentMap.prototype.set = function(key, value) {
  return new PersistentMap(this._root.set(0, this._hash(key), key, value))
};
PersistentMap.prototype.unset = function(key) {
  return new PersistentMap(this._root.unset(0, this._hash(key), key));
};
PersistentMap.prototype.get = function(key) {
  return this._root.get(0, this._hash(key), key);
};
PersistentMap.prototype.toObject = function() {};


PersistentMap.create({
  foo: "bar",
  baz: "bam"
}).unset("foo").get("baz");