Playing with Data.js

data.js

//     (c) 2011 Michael Aufreiter
//     Data.js is freely distributable under the MIT license.
//     Portions of Data.js are inspired or borrowed from Underscore.js,
//     Backbone.js and Google's Visualization API.
//     For all details and documentation:
//     http://substance.io/#michael/data-js

(function(){

  // Initial Setup
  // -------------

  // The top-level namespace. All public Data.js classes and modules will
  // be attached to this. Exported for both CommonJS and the browser.
  var Data;
  if (typeof exports !== 'undefined') {
    Data = exports;
  } else {
    Data = this.Data = {};
  }
  
  // Current version of the library. Keep in sync with `package.json`.
  Data.VERSION = '0.4.1';

  // Require Underscore, if we're on the server, and it's not already present.
  var _ = this._;
  if (!_ && (typeof require !== 'undefined')) _ = require("underscore");
  
  
  // Top Level API
  // -------

  Data.VALUE_TYPES = [
    'string',
    'object',
    'number',
    'boolean',
    'date'
  ];
  
  Data.isValueType = function (type) {
    return _.include(Data.VALUE_TYPES, type);
  };
  
  // Returns true if a certain object matches a particular query object
  // TODO: optimize!
  Data.matches = function(node, queries) {
    queries = _.isArray(queries) ? queries : [queries];
    var matched = false;
    // Matches at least one query
    _.each(queries, function(query) {
      if (matched) return;
      var rejected = false;
      _.each(query, function(value, key) {
        if (rejected) return;
        var condition;
        // Extract operator
        var matches = key.match(/^([a-z_]{1,30})(=|==|!=|>|>=|<|<=|\|=|&=)?$/),
            property = matches[1],
            operator = matches[2] || (property == "type" || _.isArray(value) ? "|=" : "=");
        
        if (operator === "|=") { // one of operator
          var values = _.isArray(value) ? value : [value];
          var objectValues = _.isArray(node[property]) ? node[property] : [node[property]];
          condition = false;
          _.each(values, function(val) {
            if (_.include(objectValues, val)) {
              condition = true;
            }
          });
        } else if (operator === "&=") {
          var values = _.isArray(value) ? value : [value];
          var objectValues = _.isArray(node[property]) ? node[property] : [node[property]];
          condition = _.intersect(objectValues, values).length === values.length;
        } else { // regular operators
          switch (operator) {
            case "!=": condition = !_.isEqual(node[property], value); break;
            case ">": condition = node[property] > value; break;
            case ">=": condition = node[property] >= value; break;
            case "<": condition = node[property] < value; break;
            case "<=": condition = node[property] <= value; break;
            default : condition = _.isEqual(node[property], value); break;
          }
        }
        // TODO: Make sure we exit the loop and return immediately when a condition is not met
        if (!condition) return rejected = true;
      });
      if (!rejected) return matched = true;
    });
    return matched;
  };
  
  
  /*!
  Math.uuid.js (v1.4)
  http://www.broofa.com
  mailto:robert@broofa.com

  Copyright (c) 2010 Robert Kieffer
  Dual licensed under the MIT and GPL licenses.
  */

  Data.uuid = function (prefix) {
    var chars = '0123456789abcdefghijklmnopqrstuvwxyz'.split(''),
        uuid = [],
        radix = 16,
        len = 32;

    if (len) {
      // Compact form
      for (var i = 0; i < len; i++) uuid[i] = chars[0 | Math.random()*radix];
    } else {
      // rfc4122, version 4 form
      var r;

      // rfc4122 requires these characters
      uuid[8] = uuid[13] = uuid[18] = uuid[23] = '-';
      uuid[14] = '4';

      // Fill in random data.  At i==19 set the high bits of clock sequence as
      // per rfc4122, sec. 4.1.5
      for (var i = 0; i < 36; i++) {
        if (!uuid[i]) {
          r = 0 | Math.random()*16;
          uuid[i] = chars[(i == 19) ? (r & 0x3) | 0x8 : r];
        }
      }
    }
    return (prefix ? prefix : "") + uuid.join('');
  };

  // Helpers
  // -------

  // _.Events (borrowed from Backbone.js)
  // -----------------
  
  // A module that can be mixed in to *any object* in order to provide it with
  // custom events. You may `bind` or `unbind` a callback function to an event;
  // `trigger`-ing an event fires all callbacks in succession.
  //
  //     var object = {};
  //     _.extend(object, Backbone.Events);
  //     object.bind('expand', function(){ alert('expanded'); });
  //     object.trigger('expand');
  //
  
  _.Events = {

    // Bind an event, specified by a string name, `ev`, to a `callback` function.
    // Passing `"all"` will bind the callback to all events fired.
    bind : function(ev, callback) {
      var calls = this._callbacks || (this._callbacks = {});
      var list  = this._callbacks[ev] || (this._callbacks[ev] = []);
      list.push(callback);
      return this;
    },

    // Remove one or many callbacks. If `callback` is null, removes all
    // callbacks for the event. If `ev` is null, removes all bound callbacks
    // for all events.
    unbind : function(ev, callback) {
      var calls;
      if (!ev) {
        this._callbacks = {};
      } else if (calls = this._callbacks) {
        if (!callback) {
          calls[ev] = [];
        } else {
          var list = calls[ev];
          if (!list) return this;
          for (var i = 0, l = list.length; i < l; i++) {
            if (callback === list[i]) {
              list.splice(i, 1);
              break;
            }
          }
        }
      }
      return this;
    },

    // Trigger an event, firing all bound callbacks. Callbacks are passed the
    // same arguments as `trigger` is, apart from the event name.
    // Listening for `"all"` passes the true event name as the first argument.
    trigger : function(ev) {
      var list, calls, i, l;
      if (!(calls = this._callbacks)) return this;
      if (list = calls[ev]) {
        for (i = 0, l = list.length; i < l; i++) {
          list[i].apply(this, Array.prototype.slice.call(arguments, 1));
        }
      }
      if (list = calls['all']) {
        for (i = 0, l = list.length; i < l; i++) {
          list[i].apply(this, arguments);
        }
      }
      return this;
    }
  };

  // Shared empty constructor function to aid in prototype-chain creation.
  var ctor = function(){};

  // Helper function to correctly set up the prototype chain, for subclasses.
  // Similar to `goog.inherits`, but uses a hash of prototype properties and
  // class properties to be extended.
  // Taken from Underscore.js (c) Jeremy Ashkenas
  _.inherits = function(parent, protoProps, staticProps) {
    var child;

    // The constructor function for the new subclass is either defined by you
    // (the "constructor" property in your `extend` definition), or defaulted
    // by us to simply call `super()`.
    if (protoProps && protoProps.hasOwnProperty('constructor')) {
      child = protoProps.constructor;
    } else {
      child = function(){ return parent.apply(this, arguments); };
    }

    // Set the prototype chain to inherit from `parent`, without calling
    // `parent`'s constructor function.
    ctor.prototype = parent.prototype;
    child.prototype = new ctor();

    // Add prototype properties (instance properties) to the subclass,
    // if supplied.
    if (protoProps) _.extend(child.prototype, protoProps);

    // Add static properties to the constructor function, if supplied.
    if (staticProps) _.extend(child, staticProps);

    // Correctly set child's `prototype.constructor`, for `instanceof`.
    child.prototype.constructor = child;

    // Set a convenience property in case the parent's prototype is needed later.
    child.__super__ = parent.prototype;

    return child;
  };
  
  
  // Data.Hash
  // --------------

  // A Hash data structure that provides a simple layer of abstraction for
  // managing a sortable data-structure with hash semantics. It's heavily
  // used throughout Data.js.
  
  Data.Hash = function(data) {
    var that = this;
    this.data = {};
    this.keyOrder = [];
    this.length = 0;

    if (data instanceof Array) {
      _.each(data, function(datum, index) {
        that.set(index, datum);
      });
    } else if (data instanceof Object) {
      _.each(data, function(datum, key) {
        that.set(key, datum);
      });
    }
    
    if (this.initialize) this.initialize(attributes, options);
  };

  _.extend(Data.Hash.prototype, _.Events, {

    // Returns a copy of the Hash
    // Used by transformation methods
    clone: function () {
      var copy = new Data.Hash();
      copy.length = this.length;
      _.each(this.data, function(value, key) {
        copy.data[key] = value;
      });
      copy.keyOrder = this.keyOrder.slice(0, this.keyOrder.length);
      return copy;
    },
    
    // Set a value at a given *key*
    set: function (key, value, targetIndex) {
      var index;
      if (key === undefined)
        return this;
      
      if (!this.data[key]) {
        if (targetIndex !== undefined) { // insert at a given index
          var front = this.select(function(item, key, i) {
            return i < targetIndex;
          });

          var back = this.select(function(item, key, i) {
            return i >= targetIndex;
          });

          this.keyOrder = [].concat(front.keyOrder);
          this.keyOrder.push(key);
          this.keyOrder = this.keyOrder.concat(back.keyOrder);
        } else {
          this.keyOrder.push(key);
        }
        index = this.length;
        this.length += 1;
      } else {
        index = this.index(key);
      }
      this.data[key] = value;
      this[index] = this.data[key];
      
      this.trigger('set', key);
      return this;
    },
    
    // Delete entry at given *key*
    del: function (key) {
      if (this.data[key]) {
        var l = this.length;
        var index = this.index(key);
        delete this.data[key];
        this.keyOrder.splice(index, 1);
        Array.prototype.splice.call(this, index, 1);
        this.length = l-1;
        this.trigger('del', key);
      }
      return this;
    },
    
    // Get value at given *key*
    get: function (key) {
      return this.data.hasOwnProperty(key) ? this.data[key] : undefined;
    },
    
    // Get value at given *index*
    at: function (index) {
      var key = this.keyOrder[index];
      return this.data[key];
    },
    
    // Get first item
    first: function () {
      return this.at(0);
    },
    
    // Returns a sub-range of the current *hash*
    range: function(start, end) {
      var result = new Data.Hash();
      for(var i=start; i<=end; i++) {
        result.set(this.key(i), this.at(i));
      }
      return result;
    },
    
    // Returns the rest of the elements. 
    // Pass an index to return the items from that index onward.
    rest: function(index) {
      return this.range(index, this.length-1);
    },
    
    // Get last item
    last: function () {
      return this.at(this.length-1);
    },
    
    // Returns for an index the corresponding *key*
    key: function (index) {
      return this.keyOrder[index];
    },
    
    // Returns for a given *key* the corresponding *index*
    index: function(key) {
      return this.keyOrder.indexOf(key);
    },
    
    // Iterate over values contained in the `Data.Hash`
    each: function (fn) {
      var that = this;
      _.each(this.keyOrder, function(key, index) {
        fn.call(that, that.data[key], key, index);
      });
      return this;
    },
    
    // Convert to an ordinary JavaScript Array containing just the values
    values: function () {
      var result = [];
      this.each(function(value, key, index) {
        result.push(value);
      });
      return result;
    },

    // Returns all keys in current order
    keys: function () {
      return _.clone(this.keyOrder);
    },
    
    // Convert to an ordinary JavaScript Array containing
    // key value pairs. Used by `sort`.
    toArray: function () {
      var result = [];
    
      this.each(function(value, key) {
        result.push({key: key, value: value});
      });
    
      return result;
    },
    
    // Serialize
    toJSON: function() {
      var result = {};
      
      this.each(function(value, key) {
        result[key] = value.toJSON ? value.toJSON() : value;
      });
      return result;
    },

    // Map the `Data.Hash` to your needs
    map: function (fn) {
      var result = this.clone(),
          that = this;
      result.each(function(item, key, index) {
        result.data[that.key(index)] = fn.call(result, item);
      });
      return result;
    },

    // Select items that match some conditions expressed by a matcher function
    select: function (fn) {
      var result = new Data.Hash(),
          that = this;
    
      this.each(function(value, key, index) {
        if (fn.call(that, value, key, index)) {
          result.set(key, value);
        }
      });
      return result;
    },
    
    // Performs a sort
    sort: function (comparator) {
      var result = this.clone();
          sortedKeys = result.toArray().sort(comparator);
    
      // update keyOrder
      result.keyOrder = _.map(sortedKeys, function(k) {
        return k.key;
      });
      return result;
    },
    
    // Performs an intersection with the given *hash*
    intersect: function(hash) {
      var that = this,
          result = new Data.Hash();
      
      // Ensure that is the smaller one
      if (hash.length < that.length) {
        that = hash;
        hash = this;
      }
      that.each(function(value,key) {
        if (hash.get(key)) result.set(key, value);
      });
      return result;
    },
    
    // Performs an union with the given *hash*
    union: function(hash) {
      var that = this,
          result = new Data.Hash();
          
      this.each(function(value, key) {
        result.set(key, value);
      });
      hash.each(function(value, key) {
        if (!result.get(key)) result.set(key, value);
      });
      return result;
    },
    
    // Computes the difference between the current *hash* and a given *hash*
    difference: function(hash) {
      var that = this;
          result = new Data.Hash();
      this.each(function(value, key) {
        if (!hash.get(key)) result.set(key, value);
      });
      return result;
    }
  });
  
  
  // Data.Comparators
  // --------------

  Data.Comparators = {};
  
  Data.Comparators.ASC = function(item1, item2) {
    return item1.value === item2.value ? 0 : (item1.value < item2.value ? -1 : 1);
  };

  Data.Comparators.DESC = function(item1, item2) {
    return item1.value === item2.value ? 0 : (item1.value > item2.value ? -1 : 1);
  };
  
  
  // Data.Aggregators
  // --------------

  Data.Aggregators = {};

  Data.Aggregators.SUM = function (values) {
    var result = 0;
    values.each(function(value, key, index) {
      if (_.isNumber(value)) result += value;
    });
    return result;
  };

  Data.Aggregators.MIN = function (values) {
    var result = Infinity;
    values.each(function(value, key, index) {
      if (_.isNumber(value) && value < result) result = value;
    });
    return result;
  };

  Data.Aggregators.MAX = function (values) {
    var result = -Infinity;
    values.each(function(value, key, index) {
      if (_.isNumber(value) && value > result) result = value;
    });
    return result;
  };

  Data.Aggregators.AVG = function (values) {
    var sum = 0,
        count = 0;
    values.each(function(value, key, index) {
      if (_.isNumber(value)) {
        sum += value;
        count += 1;
      }
    });
    return count === 0 ? 0 : (sum / count);
  };

  Data.Aggregators.COUNT = function (values) {
    return values.length;
  };
  
  
  // Data.Modifiers
  // --------------
  
  Data.Modifiers = {};

  // The default modifier simply does nothing
  Data.Modifiers.DEFAULT = function (attribute) {
    return attribute;
  };

  Data.Modifiers.MONTH = function (attribute) {
    return attribute.getMonth();
  };

  Data.Modifiers.QUARTER = function (attribute) {
    return Math.floor(attribute.getMonth() / 3) + 1;
  };
  
  // Data.Transformers
  // --------------
  
  Data.Transformers = {
    group: function(g, type, keys, properties) {
      var gspec = {},
          type = g.get(type),
          groups = {},
          count = 0;
      
      gspec[type._id] = {"type": "/type/type", "properties": {}, indexes: type.indexes};

      // Include group keys to the output graph
      _.each(keys, function(key) {
        gspec[type._id].properties[key] = type.properties().get(key).toJSON();
      });
      
      // Include additional properties
      _.each(properties, function(options, key) {
        var p = type.properties().get(options.property || key).toJSON();
        if (options.name) p.name = options.name;
        gspec[type._id].properties[key] = p;
      });
      
      var groupedGraph = new Data.Graph(gspec);
      
      _.each(keys, function(key) {
        groups[key] = type.properties().get(key).all('values');
      });

      function aggregate(key) {
        var members = new Data.Hash();

        _.each(keys, function(k, index) {
          var objects = groups[keys[index]].get(key[index]).referencedObjects;
          members = index === 0 ? members.union(objects) : members.intersect(objects);
        });
        
        // Empty group key
        if (key.length === 0) members = g.objects();
        if (members.length === 0) return null;
        
        var res = {type: type._id};
        _.each(gspec[type._id].properties, function(p, pk) {
          if (_.include(keys, pk)) {
            res[pk] = key[_.indexOf(keys, pk)];
          } else {
            var numbers = members.map(function(obj) {
              return obj.get(properties[pk].property || pk);
            });
            var aggregator = properties[pk].aggregator || Data.Aggregators.SUM;
            res[pk] = aggregator(numbers);
          }
        });
        return res;
      }

      function extractGroups(keyIndex, key) {
        if (keyIndex === keys.length-1) {
          var aggregatedItem = aggregate(key);
          if (aggregatedItem) groupedGraph.set(key.join('::'), aggregatedItem);
        } else {
          keyIndex += 1;
          groups[keys[keyIndex]].each(function(grp, grpkey) {
            extractGroups(keyIndex, key.concat([grpkey]));
          });
        }
      }
      extractGroups(-1, []);
      return groupedGraph;
    }
  };
  
  
  // Data.Node
  // --------------
  
  // JavaScript Node implementation that hides graph complexity from
  // the interface. It introduces properties, which group types of edges
  // together. Therefore multi-partite graphs are possible without any hassle.
  // Every Node simply contains properties which conform to outgoing edges.
  // It makes heavy use of hashing through JavaScript object properties to
  // allow random access whenever possible. If I've got it right, it should 
  // perform sufficiently fast, allowing speedy graph traversals.
  
  Data.Node = function(options) {
    this.nodeId = Data.Node.generateId();
    if (options) {
      this.val = options.value;
    }
    this._properties = {};
    
    if (this.initialize) this.initialize(options);
  };
  
  Data.Node.nodeCount = 0;
  
  // Generates a unique id for each node
  Data.Node.generateId = function () {
    return Data.Node.nodeCount += 1;
  };
  
  _.extend(Data.Node.prototype, _.Events, {
    // Node identity, which is simply the node's id
    identity: function() {
      return this.nodeId;
    },
    
    // Replace a property with a complete `Hash`
    replace: function(property, hash) {
      this._properties[property] = hash;
    },

    // Set a Node's property
    // 
    // Takes a property key, a value key and value. Values that aren't
    // instances of `Data.Node` wrapped are automatically.
    set: function (property, key, value) {
      if (!this._properties[property]) {
        this._properties[property] = new Data.Hash();
      }
      this._properties[property].set(key, value instanceof Data.Node ? value : new Data.Node({value: value}));
      return this;
    },

    // Get node for given *property* at given *key*
    get: function (property, key) {
      if (key !== undefined && this._properties[property] !== undefined) {
        return this._properties[property].get(key);
      }
    },

    // Get all connected nodes at given *property*
    all: function(property) {
      return this._properties[property];
    },
    
    // Get first connected node at given *property*
    // 
    // Useful if you want to mimic the behavior of unique properties.
    // That is, if you know that there's always just one associated node
    // at a given property.
    first: function(property) {
      var p = this._properties[property];
      return p ? p.first() : null;  
    },

    // Value of first connected target node at given *property*
    value: function(property) {
      return this.values(property).first();
    },
    
    // Values of associated target nodes for non-unique properties
    values: function(property) {
      if (!this.all(property)) return new Data.Hash();
      return this.all(property).map(function(n) {
        return n.val;
      });
    }
  });
  
  
  // Data.Adapter
  // --------------
  
  // An abstract interface for writing and reading Data.Graphs.
  
  Data.Adapter = function(config) {
    // The config object is used to describe database credentials
    this.config = config;
  };
  
  // Namespace where Data.Adapters can register
  Data.Adapters = {};
  
  // Data.Property
  // --------------
  
  // Meta-data (data about data) is represented as a set of properties that
  // belongs to a certain `Data.Type`. A `Data.Property` holds a key, a name
  // and an expected type, telling whether the data is numeric or textual, etc.
  
  Data.Property = _.inherits(Data.Node, {
    constructor: function(type, id, options) {
      Data.Node.call(this);
      this.key = id;
      this._id = id;
      this.type = type;
      this.unique = options.unique;
      this.name = options.name;
      this.meta = options.meta || {};
      this.validator = options.validator;
      this.required = options["required"];
      this["default"] = options["default"];
      
      // TODO: ensure that object and value types are not mixed
      this.expectedTypes = _.isArray(options['type']) ? options['type'] : [options['type']];
      this.replace('values', new Data.Hash());
    },
    
    // TODO: this desctroys Data.Node#values
    // values: function() {
    //   return this.all('values');
    // },
    
    isValueType: function() {
      return Data.isValueType(this.expectedTypes[0]);
    },
    
    isObjectType: function() {
      return !this.isValueType();
    },
    
    // Register values of a certain object
    registerValues: function(values, obj) {
      var that = this;
      var res = new Data.Hash();
            
      _.each(values, function(v, index) {
        if (v === undefined) return; // skip
        var val;
        
        // Skip registration for object type values
        // TODO: check edge cases!
        if (that.isValueType() && that.expectedTypes[0] === 'object') {
          val = new Data.Node({value: v});
          res.set(index, val);
          return;
        }
        
        // Check if we can recycle an old value of that object
        if (obj.all(that.key)) val = obj.all(that.key).get(v);
        
        if (!val) { // Can't recycle
          val = that.get('values', v);
          if (!val) {
            // Well, a new value needs to be created
            if (that.isObjectType()) {
              // Create on the fly if an object is passed as a value
              if (typeof v === 'object') v = that.type.g.set(null, v)._id;
              val = that.type.g.get('nodes', v);
              if (!val) {
                // Register the object (even if not yet loaded)
                val = new Data.Object(that.type.g, v);
                that.type.g.set('nodes', v, val);
              }
            } else {
              val = new Data.Node({value: v});
              val.referencedObjects = new Data.Hash();
            }
            // Register value on the property
            that.set('values', v, val);
          }
          val.referencedObjects.set(obj._id, obj);
        }
        
        res.set(v, val);
      });
      
      // Unregister values that are no longer used on the object
      if (obj.all(that.key)) {
        this.unregisterValues(obj.all(that.key).difference(res), obj);
      }
      return res;
    },
    
    // Unregister values from a certain object
    unregisterValues: function(values, obj) {
      var that = this;

      values.each(function(val, key) {
        if (val.referencedObjects && val.referencedObjects.length>1) {
          val.referencedObjects.del(obj._id);
        } else {
          that.all('values').del(key);
        }
      });
    },
        
    // Aggregates the property's values
    aggregate: function (fn) {
      return fn(this.values("values"));
    },
    
    // Serialize a propery definition
    toJSON: function() {
      return {
        name: this.name,
        type: this.expectedTypes,
        unique: this.unique,
        meta: this.meta,
        validator: this.validator,
        required: this.required,
        "default": this["default"]
      }
    }
  });
  
   
  // Data.Type
  // --------------
  
  // A `Data.Type` denotes an IS A relationship about a `Data.Object`. 
  // For example, if you type the object 'Shakespear' with the type 'Person'
  // you are saying that Shakespeare IS A person. Types are also used to hold
  // collections of properties that belong to a certain group of objects.
  
  Data.Type = _.inherits(Data.Node, {
    constructor: function(g, id, type) {
      var that = this;
      Data.Node.call(this);
  
      this.g = g; // Belongs to the DataGraph
      this.key = id;
      this._id = id;
      this._rev = type._rev;
      this._conflicted = type._conflicted;
      this.type = type.type;
      this.name = type.name;
      this.meta = type.meta || {};
      this.indexes = type.indexes;
      
      that.replace('properties', new Data.Hash);
      // Extract properties
      _.each(type.properties, function(property, key) {
        that.set('properties', key, new Data.Property(that, key, property));
      });
    },
    
    // Convenience function for accessing properties
    properties: function() {
      return this.all('properties');
    },
    
    // Objects of this type
    objects: function() {
      return this.all('nodes');
    },
    
    // Serialize a single type node
    toJSON: function() {
      var result = {
        _id: this._id,
        type: '/type/type',
        name: this.name,
        properties: {}
      };
      
      if (this._rev) result._rev = this._rev;
      if (this.meta && _.keys(this.meta).length > 0) result.meta = this.meta;
      if (this.indexes && _.keys(this.indexes).length > 0) result.indexes = this.indexes;
      
      this.all('properties').each(function(property) {
        var p = result.properties[property.key] = {
          name: property.name,
          unique: property.unique,
          type: property.expectedTypes,
          required: property.required ? true : false
        };
        if (property["default"]) p["default"] = property["default"];
        if (property.validator) p.validator = property.validator;
        if (property.meta && _.keys(property.meta).length > 0) p.meta = property.meta;
      });
      return result;
    }
  });
  

  // Data.Object
  // --------------
  
  // Represents a typed data object within a `Data.Graph`.
  // Provides access to properties, defined on the corresponding `Data.Type`.
  
  Data.Object = _.inherits(Data.Node, {
    constructor: function(g, id, data) {
      var that = this;
      Data.Node.call(this);
      
      this.g = g;
      
      // TODO: remove in favor of _id
      this.key = id;
      this._id = id;
      this.html_id = id.replace(/\//g, '_');
      this._dirty = true; // Every constructed node is dirty by default
      
      this.errors = []; // Stores validation errors
      this._types = new Data.Hash();
      
      // Associated Data.Objects
      this.referencedObjects = new Data.Hash();
      
      // Memoize raw data for the build process
      if (data) this.data = data;
    },
    
    // Convenience function for accessing all related types
    types: function() {
      return this._types;
    },
    
    toString: function() {
      return this.get('name') || this.val || this._id;
    },
    
    // Properties from all associated types
    properties: function() {
      var properties = new Data.Hash();
      // Prototypal inheritance in action: overriden properties belong to the last type specified
      this._types.each(function(type) {
        type.all('properties').each(function(property) {
          properties.set(property.key, property);
        });
      });
      return properties;
    },
    
    // After all nodes are recognized the object can be built
    build: function() {
      var that = this;
      var types = _.isArray(this.data.type) ? this.data.type : [this.data.type];
      
      if (!this.data) throw new Error('Object has no data, and cannot be built');
      
      this._rev = this.data._rev;
      this._conflicted = this.data._conflicted;
      this._deleted = this.data._deleted;
      
      // Initialize primary type (backward compatibility)
      this.type = this.g.get('nodes', _.last(types));
            
      // Initialize types
      _.each(types, function(type) {
        that._types.set(type, that.g.get('nodes', type));
        // Register properties for all types
        that._types.get(type).all('properties').each(function(property, key) {        
          function applyValue(value) {
            var values = _.isArray(value) ? value : [value];
            // Apply property values
            that.replace(property.key, property.registerValues(values, that));
          }
          
          if (that.data[key] !== undefined) {
            applyValue(that.data[key]);
          } else if (property["default"]) {
            applyValue(property["default"]);
          }
        });
      });
      if (this._dirty) this.g.trigger('dirty', this);
    },
    
    // Validates an object against its type (=schema)
    validate: function() {
      if (this.type.key === '/type/type') return true; // Skip type nodes
      
      var that = this;
      this.errors = [];
      this.properties().each(function(property, key) {
        // Required property?
        if ((that.get(key) === undefined || that.get(key) === null) || that.get(key) === "") {
          if (property.required) {
            that.errors.push({property: key, message: "Property \"" + property.name + "\" is required"});
          }
        } else {
          // Correct type?
          var types = property.expectedTypes;

          function validType(value, types) {
            if (_.include(types, typeof value)) return true;
            // FIXME: assumes that unloaded objects are valid properties
            if (!value.data) return true;
            if (value instanceof Data.Object && _.intersect(types, value.types().keys()).length>0) return true;
            if (typeof value === 'object' && _.include(types, value.constructor.name.toLowerCase())) return true;
            return false;
          }
          
          // Unique properties
          if (property.unique && !validType(that.get(key), types)) {
            that.errors.push({property: key, message: "Invalid type for property \"" + property.name + "\""});
          }
          
          // Non unique properties
          if (!property.unique && !_.all(that.get(key).values(), function(v) { return validType(v, types); })) {
            that.errors.push({property: key, message: "Invalid value type for property \"" + property.name + "\""});
          }
        }
        
        // Validator satisfied?
        function validValue() {
          return new RegExp(property.validator).test(that.get(key));
        }
        
        if (property.validator) {
          if (!validValue()) {
            that.errors.push({property: key, message: "Invalid value for property \"" + property.name + "\""});
          }
        }
      });
      return this.errors.length === 0;
    },
    
    // There are four different access scenarios for getting a certain property
    // 
    // * Unique value types
    // * Non-unique value types
    // * Unique object types 
    // * Non-Unique object types 
    // 
    // For convenience there's a get method, which always returns the right
    // result depending on the schema information. However, internally, every
    // property of a resource is represented as a non-unique `Data.Hash` 
    // of `Data.Node` objects, even if it's a unique property. So if you want 
    // to be explicit you should use the native methods of `Data.Node`. If
    // two arguments are provided `get` delegates to `Data.Node#get`.
    
    get: function(property, key) {
      if (!this.data) return null;
      var p = this.properties().get(property);
      if (!p) return null;
    
      if (arguments.length === 1) {
        if (p.isObjectType()) {
          return p.unique ? this.first(property) : this.all(property);
        } else {
          return p.unique ? this.value(property) : this.values(property);
        }
      } else {
        return Data.Node.prototype.get.call(this, property, key);
      }
    },
    
    // Sets properties on the object
    // Existing properties are overridden / replaced
    set: function(properties) {
      var that = this;
      
      if (arguments.length === 1) {
        _.each(properties, function(value, key) {
          var p = that.properties().get(key);
          if (!p) return; // Property not found on type
          
          // Setup values
          that.replace(p.key, p.registerValues(_.isArray(value) ? value : [value], that));
          
          that._dirty = true;
          that.g.trigger('dirty', that);
          that.g.snapshot();
        });
      } else {
        return Data.Node.prototype.set.call(this, arguments[0], arguments[1], arguments[2]);
      }
    },
    
    // Serialize an `Data.Object`'s properties
    toJSON: function() {
      var that = this;
      result = {};
      _.each(this._properties, function(value, key) {
        var p = that.properties().get(key);
        if (p.isObjectType()) {
          result[key] = p.unique ? that.all(key).keys()[0] : that.all(key).keys()
        } else {
          result[key] = p.unique ? that.value(key) : that.values(key).values();
        }
      });
      result['type'] = this.types().keys();
      result['_id'] = this._id;
      if (this._rev !== undefined) result['_rev'] = this._rev;
      if (this._deleted) result['_deleted'] = this._deleted;
      return result;
    }
  });
  
  _.extend(Data.Object.prototype, _.Events);
  
  
  // Data.Graph
  // --------------
  
  // A `Data.Graph` can be used for representing arbitrary complex object
  // graphs. Relations between objects are expressed through links that
  // point to referred objects. Data.Graphs can be traversed in various ways.
  // See the testsuite for usage.
  
  // Set a new Data.Adapter and enable Persistence API

  Data.Graph = _.inherits(Data.Node, {
    constructor: function(g, options) {
      var that = this;
      Data.Node.call(this);
      
      this.watchers = {};
      this.replace('nodes', new Data.Hash());
      if (!g) return;
      this.merge(g, options.dirty);
      
      if (options.persistent) {
        this.persistent = options.persistent;
        this.restore(); // Restore data
      }
    },
    
    connect: function(name, config) {
      if (typeof exports !== 'undefined') {
        var Adapter = require(__dirname + '/adapters/'+name+'_adapter');
        this.adapter = new Adapter(this, config);
      } else {
        if (!Data.Adapters[name]) throw new Error('Adapter "'+name+'" not found');
        this.adapter = new Data.Adapters[name](this, config);
      }
      return this;
    },
    
    // Called when the Data.Adapter is ready
    connected: function(callback) {
      if (this.adapter.realtime) {
        this.connectedCallback = callback;
      } else {
        callback();
      }
    },
    
    // Serve graph along with an httpServer instance
    serve: function(server, options) {
      require(__dirname + '/server').initialize(server, this);
    },
    
    // Watch for graph updates
    watch: function(channel, query, callback) {
      this.watchers[channel] = callback;
      this.adapter.watch(channel, query, function(err) {});
    },
    
    // Stop watching that channel
    unwatch: function(channel, callback) {
      delete this.watchers[channel];
      this.adapter.unwatch(channel, function() {});
    },
    
    // Empty graph
    empty: function() {
      var that = this;
      _.each(this.objects().keys(), function(id) {
        that.del(id);
        that.all('nodes').del(id);
      });
    },
    
    // Merges in another Graph
    merge: function(g, dirty) {
      var that = this;
      
      // Process schema nodes
      var types = _.select(g, function(node, key) {
        if (node.type === '/type/type' || node.type === 'type') {
          if (!that.get('nodes', key)) {
            that.set('nodes', key, new Data.Type(that, key, node));
            that.get(key)._dirty = node._dirty ? node._dirty : dirty;
          }
          return true;
        }
        return false;
      });
      
      // Process object nodes
      var objects = _.select(g, function(node, key) {
        if (node.type !== '/type/type' && node.type !== 'type') {
          var res = that.get('nodes', key);
          var types = _.isArray(node.type) ? node.type : [node.type];
          if (!res) {
            res = new Data.Object(that, key, node);
            that.set('nodes', key, res);
          } else {
            // Populate existing node with data in order to be rebuilt
            res.data = node;
          }
          // Check for type existence
          _.each(types, function(type) {
            if (!that.get('nodes', type)) {
              throw new Error("Type '"+type+"' not found for "+key+"...");
            }
            that.get('nodes', type).set('nodes', key, res);
          });
          that.get(key)._dirty = node._dirty ? node._dirty : dirty;
          
          if (!node._id) node._id = key;
          return true;
        }
        return false;
      });
      
      // Now that all new objects are registered we can build them
      _.each(objects, function(o) {
        var obj = that.get(o._id);
        if (obj.data) obj.build();
      });
      
      // Create a new snapshot
      this.snapshot();
      return this;
    },

    set: function(node) {
      var id, that = this;
      
      // Backward compatibility
      if (arguments.length === 2) node = _.extend(arguments[1], {_id: arguments[0]});

      var types = _.isArray(node.type) ? node.type : [node.type];
      if (arguments.length <= 2) {
        node._id = node._id ? node._id : Data.uuid('/' + _.last(_.last(types).split('/')) + '/');
        // Recycle existing object if there is one
        var res = that.get(node._id) ? that.get(node._id) : new Data.Object(that, node._id, _.clone(node), true);
        res.data = node;
        res._dirty = true;
        res.build();
        this.set('nodes', node._id, res);
        this.snapshot();
        return res;
      } else { // Delegate to Data.Node#set
        return Data.Node.prototype.set.call(this, arguments[0], arguments[1], arguments[2]);
      }
    },
    
    // API method for accessing objects in the graph space
    get: function(id) {
      if (arguments.length === 1) {
        return this.get('nodes', id);
      } else {
        return Data.Node.prototype.get.call(this, arguments[0], arguments[1]);
      }
    },
    
    // Delete node by id, referenced nodes remain untouched
    del: function(id) {
      var node = this.get(id);
      if (!node) return;
      node._deleted = true;
      node._dirty = true;
      // Remove registered values
      node.properties().each(function(p, key) {
        var values = node.all(key);
        if (values) p.unregisterValues(values, node);
      });
      this.trigger('dirty', node);
      this.snapshot();
    },
    
    // Find objects that match a particular query
    find: function(query) {
      return this.objects().select(function(o) {
        return Data.matches(o.toJSON(), query);
      });
    },
    
    // Memoize a snapshot of the current graph
    snapshot: function() {
      if (!this.persistent) return;
      localStorage.setItem("graph", JSON.stringify(this.toJSON(true)));
    },
    
    // Restore latest snapshot from localStorage
    restore: function() {
      var snapshot = JSON.parse(localStorage.getItem("graph"));
      if (snapshot) this.merge(snapshot);
    },
    
    // Fetches a new subgraph from the adapter and either merges the new nodes
    // into the current set of nodes
    fetch: function(query, options, callback) {
      var that = this,
          nodes = new Data.Hash(); // collects arrived nodes
      
      // Options are optional
      if (typeof options === 'function' && typeof callback === 'undefined') {
        callback = options;
        options = {};
      }
      
      this.adapter.read(query, options, function(err, graph) {
        if (graph) {          
          that.merge(graph, false);
          _.each(graph, function(node, key) {
            nodes.set(key, that.get(key));
          });
        }
        err ? callback(err) : callback(null, nodes);
      });
    },
    
    // Synchronize dirty nodes with the backend
    sync: function(callback) {
      callback = callback || function() {};
      var that = this,
          nodes = that.dirtyNodes();
      
      var validNodes = new Data.Hash();
      nodes.select(function(node, key) {
        if (!node.validate || (node.validate && node.validate())) {
          validNodes.set(key, node);
        }
      });
      
      this.adapter.write(validNodes.toJSON(), function(err, g) {
        if (err) return callback(err);
        that.merge(g, false);

        // Check for rejectedNodes / conflictedNodes
        validNodes.each(function(n, key) {
          if (g[key]) {
            n._dirty = false;
            n._rejected = false;
          } else {
            n._rejected = true;
          }
        });
        
        // Update localStorage
        if (this.persistent) that.snapshot();
        
        if (that.invalidNodes().length > 0) that.trigger('invalid');
        if (that.conflictedNodes().length > 0) that.trigger('conflicted');
        if (that.rejectedNodes().length > 0) that.trigger('rejected');
        
        var unsavedNodes = that.invalidNodes().union(that.conflictedNodes())
                           .union(that.rejectedNodes()).length;
        
        callback(unsavedNodes > 0 ? unsavedNodes+' unsaved nodes' : null);
      });
    },
    
    // Perform a group operation on a Data.Graph
    group: function(type, keys, properties) {
      var res = new Data.Collection();
      res.g = Data.Transformers.group(this, type, keys, properties);
      return res;
    },
    
    // Type nodes
    types: function() {
      return this.all('nodes').select(function(node, key) {
        return node.type === '/type/type' || node.type === 'type';
      });
    },
    
    // Object nodes
    objects: function() {
      return this.all('nodes').select(function(node, key) {
        return node.type !== '/type/type' && node.type !== 'type' && node.data && !node._deleted;
      });
    },
    
    // Get dirty nodes
    // Used by Data.Graph#sync
    dirtyNodes: function() {
      return this.all('nodes').select(function(obj, key) {
        return (obj._dirty && (obj.data || obj instanceof Data.Type));
      });
    },
    
    // Get invalid nodes
    invalidNodes: function() {
      return this.all('nodes').select(function(obj, key) {
        return (obj.errors && obj.errors.length > 0);
      });
    },
    
    // Get conflicting nodes
    conflictedNodes: function() {
      return this.all('nodes').select(function(obj, key) {
        return obj._conflicted;
      });
    },
    
    // Nodes that got rejected during sync
    rejectedNodes: function() {
      return this.all('nodes').select(function(obj, key) {
        return obj._rejected;
      });
    },
    
    // Serializes the graph to the JSON-based exchange format
    toJSON: function(extended) {
      var result = {};
      
      // Serialize object nodes
      this.all('nodes').each(function(obj, key) {
        // Only serialize fetched nodes
        if (obj.data || obj instanceof Data.Type) {
          result[key] = obj.toJSON();
          if (extended) {
            // include special properties
            if (obj._dirty) result[key]._dirty = true;
            if (obj._conflicted) result[key]._conclicted = true;
            if (obj._rejected) result[key].rejected = true;
          }
        }
      });
      
      return result;
    }
  });
  
  _.extend(Data.Graph.prototype, _.Events);
  

  // Data.Collection
  // --------------
  
  // A Collection is a simple data abstraction format where a dataset under
  // investigation conforms to a collection of data items that describes all
  // facets of the underlying data in a simple and universal way. You can
  // think of a Collection as a table of data, except it provides precise
  // information about the data contained (meta-data). A Data.Collection
  // just wraps a `Data.Graph` internally, in order to simplify the interface,
  // for cases where you do not have to deal with linked data.
  
  Data.Collection = function(spec) {
    var that = this,
        gspec = { "/type/item": { "type": "/type/type", "properties": {}} };
        
    if (spec) gspec["/type/item"]["indexes"] = spec.indexes || {};

    // Convert to Data.Graph serialization format
    if (spec) {
      _.each(spec.properties, function(property, key) {
        gspec["/type/item"].properties[key] = property;
      });
      this.g = new Data.Graph(gspec);
      _.each(spec.items, function(item, key) {
        that.set(key, item);
      });
    } else {
      this.g = new Data.Graph();
    }
  };
  
  _.extend(Data.Collection.prototype, {

    // Get an object (item) from the collection
    get: function(key) {
      return this.g.get.apply(this.g, arguments);
    },
    
    // Set (add) a new object to the collection
    set: function(id, properties) {
      this.g.set(id, _.extend(properties, {type: "/type/item"}));
    },
    
    // Find objects that match a particular query
    find: function(query) {
      query["type|="] = "/type/item";
      return this.g.find(query);
    },
    
    // Returns a filtered collection containing only items that match a certain query
    filter: function(query) {
      return new Data.Collection({
        properties: this.properties().toJSON(),
        items: this.find(query).toJSON()
      });
    },
        
    // Perform a group operation on the collection
    group: function(keys, properties) {
      var res = new Data.Collection();
      res.g = Data.Transformers.group(this.g, "/type/item", keys, properties);
      return res;
    },
    
    // Convenience function for accessing properties
    properties: function() {
      return this.g.get('nodes', '/type/item').all('properties');
    },
    
    // Convenience function for accessing items
    items: function() {
      return this.g.objects();
    },
    
    // Convenience function for accessing indexes defined on the collection
    indexes: function() {
      return this.g.get('/type/item').indexes;
    },
    
    // Serialize
    toJSON: function() {
      return {
        properties: this.g.toJSON()["/type/item"].properties,
        items: this.g.objects().toJSON()
      }
    }
  });
})();

index.html

<!DOCTYPE html>
<html>
  <head>
    <title>Playing with data.js</title>
  </head>

  <body>

    <script type="text/javascript" src="underscore.js"></script>
    <script type="text/javascript" src="data.js"></script>
    <script type="text/javascript" src="playing-with-data.js"></script>
  </body>
</html>

playing-with-data.js

var schema = {
  "/type/person": {
    "type": "type",
    "name": "Person",
    "properties": {
      "name": {"name": "Name", "unique": true, "type": "string", "required": true},
      "origin": {"name": "Origin", "unique": true, "type": "/type/location" }
    }
  },
  "/type/location": {
    "type": "type",
    "name": "Location",
    "properties": {
      "name": { "name": "Name", "unique": true, "type": "string", "required": true },
      "citizens": {"name": "Citizens", "unique": false, "type": "/type/person"}
    }
  }
};

var graph = new Data.Graph(schema, {persistent: true});


graph.set({
  _id: "/person/bart",
  type: "/type/person",
  name: "Bart Simpson"
});

graph.set({
  _id: '/location/springfield',
  type: '/type/location',
  name: 'Springfield',
  citizens: ['/person/bart']
});

graph.get('/person/bart')
  .set({origin: '/location/springfield'});

graph.set({
  _id: "/person/homer",
  type: "/type/person",
  name: "Homer Simpson",
  origin: "/location/springfield",
});

graph.get('/location/springfield').set({
  citizens: ['/person/bart', '/person/homer']
});


graph.get('/location/springfield').get('citizens').each(function(person) {
  console.log(person.get('name'));
});

underscore.js

//     Underscore.js 1.1.7
//     (c) 2011 Jeremy Ashkenas, DocumentCloud Inc.
//     Underscore is freely distributable under the MIT license.
//     Portions of Underscore are inspired or borrowed from Prototype,
//     Oliver Steele's Functional, and John Resig's Micro-Templating.
//     For all details and documentation:
//     http://documentcloud.github.com/underscore

(function() {

  // Baseline setup
  // --------------

  // Establish the root object, `window` in the browser, or `global` on the server.
  var root = this;

  // Save the previous value of the `_` variable.
  var previousUnderscore = root._;

  // Establish the object that gets returned to break out of a loop iteration.
  var breaker = {};

  // Save bytes in the minified (but not gzipped) version:
  var ArrayProto = Array.prototype, ObjProto = Object.prototype, FuncProto = Function.prototype;

  // Create quick reference variables for speed access to core prototypes.
  var slice            = ArrayProto.slice,
      unshift          = ArrayProto.unshift,
      toString         = ObjProto.toString,
      hasOwnProperty   = ObjProto.hasOwnProperty;

  // All **ECMAScript 5** native function implementations that we hope to use
  // are declared here.
  var
    nativeForEach      = ArrayProto.forEach,
    nativeMap          = ArrayProto.map,
    nativeReduce       = ArrayProto.reduce,
    nativeReduceRight  = ArrayProto.reduceRight,
    nativeFilter       = ArrayProto.filter,
    nativeEvery        = ArrayProto.every,
    nativeSome         = ArrayProto.some,
    nativeIndexOf      = ArrayProto.indexOf,
    nativeLastIndexOf  = ArrayProto.lastIndexOf,
    nativeIsArray      = Array.isArray,
    nativeKeys         = Object.keys,
    nativeBind         = FuncProto.bind;

  // Create a safe reference to the Underscore object for use below.
  var _ = function(obj) { return new wrapper(obj); };

  // Export the Underscore object for **CommonJS**, with backwards-compatibility
  // for the old `require()` API. If we're not in CommonJS, add `_` to the
  // global object.
  if (typeof module !== 'undefined' && module.exports) {
    module.exports = _;
    _._ = _;
  } else {
    // Exported as a string, for Closure Compiler "advanced" mode.
    root['_'] = _;
  }

  // Current version.
  _.VERSION = '1.1.7';

  // Collection Functions
  // --------------------

  // The cornerstone, an `each` implementation, aka `forEach`.
  // Handles objects with the built-in `forEach`, arrays, and raw objects.
  // Delegates to **ECMAScript 5**'s native `forEach` if available.
  var each = _.each = _.forEach = function(obj, iterator, context) {
    if (obj == null) return;
    if (nativeForEach && obj.forEach === nativeForEach) {
      obj.forEach(iterator, context);
    } else if (obj.length === +obj.length) {
      for (var i = 0, l = obj.length; i < l; i++) {
        if (i in obj && iterator.call(context, obj[i], i, obj) === breaker) return;
      }
    } else {
      for (var key in obj) {
        if (hasOwnProperty.call(obj, key)) {
          if (iterator.call(context, obj[key], key, obj) === breaker) return;
        }
      }
    }
  };

  // Return the results of applying the iterator to each element.
  // Delegates to **ECMAScript 5**'s native `map` if available.
  _.map = function(obj, iterator, context) {
    var results = [];
    if (obj == null) return results;
    if (nativeMap && obj.map === nativeMap) return obj.map(iterator, context);
    each(obj, function(value, index, list) {
      results[results.length] = iterator.call(context, value, index, list);
    });
    return results;
  };

  // **Reduce** builds up a single result from a list of values, aka `inject`,
  // or `foldl`. Delegates to **ECMAScript 5**'s native `reduce` if available.
  _.reduce = _.foldl = _.inject = function(obj, iterator, memo, context) {
    var initial = memo !== void 0;
    if (obj == null) obj = [];
    if (nativeReduce && obj.reduce === nativeReduce) {
      if (context) iterator = _.bind(iterator, context);
      return initial ? obj.reduce(iterator, memo) : obj.reduce(iterator);
    }
    each(obj, function(value, index, list) {
      if (!initial) {
        memo = value;
        initial = true;
      } else {
        memo = iterator.call(context, memo, value, index, list);
      }
    });
    if (!initial) throw new TypeError("Reduce of empty array with no initial value");
    return memo;
  };

  // The right-associative version of reduce, also known as `foldr`.
  // Delegates to **ECMAScript 5**'s native `reduceRight` if available.
  _.reduceRight = _.foldr = function(obj, iterator, memo, context) {
    if (obj == null) obj = [];
    if (nativeReduceRight && obj.reduceRight === nativeReduceRight) {
      if (context) iterator = _.bind(iterator, context);
      return memo !== void 0 ? obj.reduceRight(iterator, memo) : obj.reduceRight(iterator);
    }
    var reversed = (_.isArray(obj) ? obj.slice() : _.toArray(obj)).reverse();
    return _.reduce(reversed, iterator, memo, context);
  };

  // Return the first value which passes a truth test. Aliased as `detect`.
  _.find = _.detect = function(obj, iterator, context) {
    var result;
    any(obj, function(value, index, list) {
      if (iterator.call(context, value, index, list)) {
        result = value;
        return true;
      }
    });
    return result;
  };

  // Return all the elements that pass a truth test.
  // Delegates to **ECMAScript 5**'s native `filter` if available.
  // Aliased as `select`.
  _.filter = _.select = function(obj, iterator, context) {
    var results = [];
    if (obj == null) return results;
    if (nativeFilter && obj.filter === nativeFilter) return obj.filter(iterator, context);
    each(obj, function(value, index, list) {
      if (iterator.call(context, value, index, list)) results[results.length] = value;
    });
    return results;
  };

  // Return all the elements for which a truth test fails.
  _.reject = function(obj, iterator, context) {
    var results = [];
    if (obj == null) return results;
    each(obj, function(value, index, list) {
      if (!iterator.call(context, value, index, list)) results[results.length] = value;
    });
    return results;
  };

  // Determine whether all of the elements match a truth test.
  // Delegates to **ECMAScript 5**'s native `every` if available.
  // Aliased as `all`.
  _.every = _.all = function(obj, iterator, context) {
    var result = true;
    if (obj == null) return result;
    if (nativeEvery && obj.every === nativeEvery) return obj.every(iterator, context);
    each(obj, function(value, index, list) {
      if (!(result = result && iterator.call(context, value, index, list))) return breaker;
    });
    return result;
  };

  // Determine if at least one element in the object matches a truth test.
  // Delegates to **ECMAScript 5**'s native `some` if available.
  // Aliased as `any`.
  var any = _.some = _.any = function(obj, iterator, context) {
    iterator = iterator || _.identity;
    var result = false;
    if (obj == null) return result;
    if (nativeSome && obj.some === nativeSome) return obj.some(iterator, context);
    each(obj, function(value, index, list) {
      if (result |= iterator.call(context, value, index, list)) return breaker;
    });
    return !!result;
  };

  // Determine if a given value is included in the array or object using `===`.
  // Aliased as `contains`.
  _.include = _.contains = function(obj, target) {
    var found = false;
    if (obj == null) return found;
    if (nativeIndexOf && obj.indexOf === nativeIndexOf) return obj.indexOf(target) != -1;
    any(obj, function(value) {
      if (found = value === target) return true;
    });
    return found;
  };

  // Invoke a method (with arguments) on every item in a collection.
  _.invoke = function(obj, method) {
    var args = slice.call(arguments, 2);
    return _.map(obj, function(value) {
      return (method.call ? method || value : value[method]).apply(value, args);
    });
  };

  // Convenience version of a common use case of `map`: fetching a property.
  _.pluck = function(obj, key) {
    return _.map(obj, function(value){ return value[key]; });
  };

  // Return the maximum element or (element-based computation).
  _.max = function(obj, iterator, context) {
    if (!iterator && _.isArray(obj)) return Math.max.apply(Math, obj);
    var result = {computed : -Infinity};
    each(obj, function(value, index, list) {
      var computed = iterator ? iterator.call(context, value, index, list) : value;
      computed >= result.computed && (result = {value : value, computed : computed});
    });
    return result.value;
  };

  // Return the minimum element (or element-based computation).
  _.min = function(obj, iterator, context) {
    if (!iterator && _.isArray(obj)) return Math.min.apply(Math, obj);
    var result = {computed : Infinity};
    each(obj, function(value, index, list) {
      var computed = iterator ? iterator.call(context, value, index, list) : value;
      computed < result.computed && (result = {value : value, computed : computed});
    });
    return result.value;
  };

  // Sort the object's values by a criterion produced by an iterator.
  _.sortBy = function(obj, iterator, context) {
    return _.pluck(_.map(obj, function(value, index, list) {
      return {
        value : value,
        criteria : iterator.call(context, value, index, list)
      };
    }).sort(function(left, right) {
      var a = left.criteria, b = right.criteria;
      return a < b ? -1 : a > b ? 1 : 0;
    }), 'value');
  };

  // Groups the object's values by a criterion produced by an iterator
  _.groupBy = function(obj, iterator) {
    var result = {};
    each(obj, function(value, index) {
      var key = iterator(value, index);
      (result[key] || (result[key] = [])).push(value);
    });
    return result;
  };

  // Use a comparator function to figure out at what index an object should
  // be inserted so as to maintain order. Uses binary search.
  _.sortedIndex = function(array, obj, iterator) {
    iterator || (iterator = _.identity);
    var low = 0, high = array.length;
    while (low < high) {
      var mid = (low + high) >> 1;
      iterator(array[mid]) < iterator(obj) ? low = mid + 1 : high = mid;
    }
    return low;
  };

  // Safely convert anything iterable into a real, live array.
  _.toArray = function(iterable) {
    if (!iterable)                return [];
    if (iterable.toArray)         return iterable.toArray();
    if (_.isArray(iterable))      return slice.call(iterable);
    if (_.isArguments(iterable))  return slice.call(iterable);
    return _.values(iterable);
  };

  // Return the number of elements in an object.
  _.size = function(obj) {
    return _.toArray(obj).length;
  };

  // Array Functions
  // ---------------

  // Get the first element of an array. Passing **n** will return the first N
  // values in the array. Aliased as `head`. The **guard** check allows it to work
  // with `_.map`.
  _.first = _.head = function(array, n, guard) {
    return (n != null) && !guard ? slice.call(array, 0, n) : array[0];
  };

  // Returns everything but the first entry of the array. Aliased as `tail`.
  // Especially useful on the arguments object. Passing an **index** will return
  // the rest of the values in the array from that index onward. The **guard**
  // check allows it to work with `_.map`.
  _.rest = _.tail = function(array, index, guard) {
    return slice.call(array, (index == null) || guard ? 1 : index);
  };

  // Get the last element of an array.
  _.last = function(array) {
    return array[array.length - 1];
  };

  // Trim out all falsy values from an array.
  _.compact = function(array) {
    return _.filter(array, function(value){ return !!value; });
  };

  // Return a completely flattened version of an array.
  _.flatten = function(array) {
    return _.reduce(array, function(memo, value) {
      if (_.isArray(value)) return memo.concat(_.flatten(value));
      memo[memo.length] = value;
      return memo;
    }, []);
  };

  // Return a version of the array that does not contain the specified value(s).
  _.without = function(array) {
    return _.difference(array, slice.call(arguments, 1));
  };

  // Produce a duplicate-free version of the array. If the array has already
  // been sorted, you have the option of using a faster algorithm.
  // Aliased as `unique`.
  _.uniq = _.unique = function(array, isSorted) {
    return _.reduce(array, function(memo, el, i) {
      if (0 == i || (isSorted === true ? _.last(memo) != el : !_.include(memo, el))) memo[memo.length] = el;
      return memo;
    }, []);
  };

  // Produce an array that contains the union: each distinct element from all of
  // the passed-in arrays.
  _.union = function() {
    return _.uniq(_.flatten(arguments));
  };

  // Produce an array that contains every item shared between all the
  // passed-in arrays. (Aliased as "intersect" for back-compat.)
  _.intersection = _.intersect = function(array) {
    var rest = slice.call(arguments, 1);
    return _.filter(_.uniq(array), function(item) {
      return _.every(rest, function(other) {
        return _.indexOf(other, item) >= 0;
      });
    });
  };

  // Take the difference between one array and another.
  // Only the elements present in just the first array will remain.
  _.difference = function(array, other) {
    return _.filter(array, function(value){ return !_.include(other, value); });
  };

  // Zip together multiple lists into a single array -- elements that share
  // an index go together.
  _.zip = function() {
    var args = slice.call(arguments);
    var length = _.max(_.pluck(args, 'length'));
    var results = new Array(length);
    for (var i = 0; i < length; i++) results[i] = _.pluck(args, "" + i);
    return results;
  };

  // If the browser doesn't supply us with indexOf (I'm looking at you, **MSIE**),
  // we need this function. Return the position of the first occurrence of an
  // item in an array, or -1 if the item is not included in the array.
  // Delegates to **ECMAScript 5**'s native `indexOf` if available.
  // If the array is large and already in sort order, pass `true`
  // for **isSorted** to use binary search.
  _.indexOf = function(array, item, isSorted) {
    if (array == null) return -1;
    var i, l;
    if (isSorted) {
      i = _.sortedIndex(array, item);
      return array[i] === item ? i : -1;
    }
    if (nativeIndexOf && array.indexOf === nativeIndexOf) return array.indexOf(item);
    for (i = 0, l = array.length; i < l; i++) if (array[i] === item) return i;
    return -1;
  };


  // Delegates to **ECMAScript 5**'s native `lastIndexOf` if available.
  _.lastIndexOf = function(array, item) {
    if (array == null) return -1;
    if (nativeLastIndexOf && array.lastIndexOf === nativeLastIndexOf) return array.lastIndexOf(item);
    var i = array.length;
    while (i--) if (array[i] === item) return i;
    return -1;
  };

  // Generate an integer Array containing an arithmetic progression. A port of
  // the native Python `range()` function. See
  // [the Python documentation](http://docs.python.org/library/functions.html#range).
  _.range = function(start, stop, step) {
    if (arguments.length <= 1) {
      stop = start || 0;
      start = 0;
    }
    step = arguments[2] || 1;

    var len = Math.max(Math.ceil((stop - start) / step), 0);
    var idx = 0;
    var range = new Array(len);

    while(idx < len) {
      range[idx++] = start;
      start += step;
    }

    return range;
  };

  // Function (ahem) Functions
  // ------------------

  // Create a function bound to a given object (assigning `this`, and arguments,
  // optionally). Binding with arguments is also known as `curry`.
  // Delegates to **ECMAScript 5**'s native `Function.bind` if available.
  // We check for `func.bind` first, to fail fast when `func` is undefined.
  _.bind = function(func, obj) {
    if (func.bind === nativeBind && nativeBind) return nativeBind.apply(func, slice.call(arguments, 1));
    var args = slice.call(arguments, 2);
    return function() {
      return func.apply(obj, args.concat(slice.call(arguments)));
    };
  };

  // Bind all of an object's methods to that object. Useful for ensuring that
  // all callbacks defined on an object belong to it.
  _.bindAll = function(obj) {
    var funcs = slice.call(arguments, 1);
    if (funcs.length == 0) funcs = _.functions(obj);
    each(funcs, function(f) { obj[f] = _.bind(obj[f], obj); });
    return obj;
  };

  // Memoize an expensive function by storing its results.
  _.memoize = function(func, hasher) {
    var memo = {};
    hasher || (hasher = _.identity);
    return function() {
      var key = hasher.apply(this, arguments);
      return hasOwnProperty.call(memo, key) ? memo[key] : (memo[key] = func.apply(this, arguments));
    };
  };

  // Delays a function for the given number of milliseconds, and then calls
  // it with the arguments supplied.
  _.delay = function(func, wait) {
    var args = slice.call(arguments, 2);
    return setTimeout(function(){ return func.apply(func, args); }, wait);
  };

  // Defers a function, scheduling it to run after the current call stack has
  // cleared.
  _.defer = function(func) {
    return _.delay.apply(_, [func, 1].concat(slice.call(arguments, 1)));
  };

  // Internal function used to implement `_.throttle` and `_.debounce`.
  var limit = function(func, wait, debounce) {
    var timeout;
    return function() {
      var context = this, args = arguments;
      var throttler = function() {
        timeout = null;
        func.apply(context, args);
      };
      if (debounce) clearTimeout(timeout);
      if (debounce || !timeout) timeout = setTimeout(throttler, wait);
    };
  };

  // Returns a function, that, when invoked, will only be triggered at most once
  // during a given window of time.
  _.throttle = function(func, wait) {
    return limit(func, wait, false);
  };

  // Returns a function, that, as long as it continues to be invoked, will not
  // be triggered. The function will be called after it stops being called for
  // N milliseconds.
  _.debounce = function(func, wait) {
    return limit(func, wait, true);
  };

  // Returns a function that will be executed at most one time, no matter how
  // often you call it. Useful for lazy initialization.
  _.once = function(func) {
    var ran = false, memo;
    return function() {
      if (ran) return memo;
      ran = true;
      return memo = func.apply(this, arguments);
    };
  };

  // Returns the first function passed as an argument to the second,
  // allowing you to adjust arguments, run code before and after, and
  // conditionally execute the original function.
  _.wrap = function(func, wrapper) {
    return function() {
      var args = [func].concat(slice.call(arguments));
      return wrapper.apply(this, args);
    };
  };

  // Returns a function that is the composition of a list of functions, each
  // consuming the return value of the function that follows.
  _.compose = function() {
    var funcs = slice.call(arguments);
    return function() {
      var args = slice.call(arguments);
      for (var i = funcs.length - 1; i >= 0; i--) {
        args = [funcs[i].apply(this, args)];
      }
      return args[0];
    };
  };

  // Returns a function that will only be executed after being called N times.
  _.after = function(times, func) {
    return function() {
      if (--times < 1) { return func.apply(this, arguments); }
    };
  };


  // Object Functions
  // ----------------

  // Retrieve the names of an object's properties.
  // Delegates to **ECMAScript 5**'s native `Object.keys`
  _.keys = nativeKeys || function(obj) {
    if (obj !== Object(obj)) throw new TypeError('Invalid object');
    var keys = [];
    for (var key in obj) if (hasOwnProperty.call(obj, key)) keys[keys.length] = key;
    return keys;
  };

  // Retrieve the values of an object's properties.
  _.values = function(obj) {
    return _.map(obj, _.identity);
  };

  // Return a sorted list of the function names available on the object.
  // Aliased as `methods`
  _.functions = _.methods = function(obj) {
    var names = [];
    for (var key in obj) {
      if (_.isFunction(obj[key])) names.push(key);
    }
    return names.sort();
  };

  // Extend a given object with all the properties in passed-in object(s).
  _.extend = function(obj) {
    each(slice.call(arguments, 1), function(source) {
      for (var prop in source) {
        if (source[prop] !== void 0) obj[prop] = source[prop];
      }
    });
    return obj;
  };

  // Fill in a given object with default properties.
  _.defaults = function(obj) {
    each(slice.call(arguments, 1), function(source) {
      for (var prop in source) {
        if (obj[prop] == null) obj[prop] = source[prop];
      }
    });
    return obj;
  };

  // Create a (shallow-cloned) duplicate of an object.
  _.clone = function(obj) {
    return _.isArray(obj) ? obj.slice() : _.extend({}, obj);
  };

  // Invokes interceptor with the obj, and then returns obj.
  // The primary purpose of this method is to "tap into" a method chain, in
  // order to perform operations on intermediate results within the chain.
  _.tap = function(obj, interceptor) {
    interceptor(obj);
    return obj;
  };

  // Perform a deep comparison to check if two objects are equal.
  _.isEqual = function(a, b) {
    // Check object identity.
    if (a === b) return true;
    // Different types?
    var atype = typeof(a), btype = typeof(b);
    if (atype != btype) return false;
    // Basic equality test (watch out for coercions).
    if (a == b) return true;
    // One is falsy and the other truthy.
    if ((!a && b) || (a && !b)) return false;
    // Unwrap any wrapped objects.
    if (a._chain) a = a._wrapped;
    if (b._chain) b = b._wrapped;
    // One of them implements an isEqual()?
    if (a.isEqual) return a.isEqual(b);
    if (b.isEqual) return b.isEqual(a);
    // Check dates' integer values.
    if (_.isDate(a) && _.isDate(b)) return a.getTime() === b.getTime();
    // Both are NaN?
    if (_.isNaN(a) && _.isNaN(b)) return false;
    // Compare regular expressions.
    if (_.isRegExp(a) && _.isRegExp(b))
      return a.source     === b.source &&
             a.global     === b.global &&
             a.ignoreCase === b.ignoreCase &&
             a.multiline  === b.multiline;
    // If a is not an object by this point, we can't handle it.
    if (atype !== 'object') return false;
    // Check for different array lengths before comparing contents.
    if (a.length && (a.length !== b.length)) return false;
    // Nothing else worked, deep compare the contents.
    var aKeys = _.keys(a), bKeys = _.keys(b);
    // Different object sizes?
    if (aKeys.length != bKeys.length) return false;
    // Recursive comparison of contents.
    for (var key in a) if (!(key in b) || !_.isEqual(a[key], b[key])) return false;
    return true;
  };

  // Is a given array or object empty?
  _.isEmpty = function(obj) {
    if (_.isArray(obj) || _.isString(obj)) return obj.length === 0;
    for (var key in obj) if (hasOwnProperty.call(obj, key)) return false;
    return true;
  };

  // Is a given value a DOM element?
  _.isElement = function(obj) {
    return !!(obj && obj.nodeType == 1);
  };

  // Is a given value an array?
  // Delegates to ECMA5's native Array.isArray
  _.isArray = nativeIsArray || function(obj) {
    return toString.call(obj) === '[object Array]';
  };

  // Is a given variable an object?
  _.isObject = function(obj) {
    return obj === Object(obj);
  };

  // Is a given variable an arguments object?
  _.isArguments = function(obj) {
    return !!(obj && hasOwnProperty.call(obj, 'callee'));
  };

  // Is a given value a function?
  _.isFunction = function(obj) {
    return !!(obj && obj.constructor && obj.call && obj.apply);
  };

  // Is a given value a string?
  _.isString = function(obj) {
    return !!(obj === '' || (obj && obj.charCodeAt && obj.substr));
  };

  // Is a given value a number?
  _.isNumber = function(obj) {
    return !!(obj === 0 || (obj && obj.toExponential && obj.toFixed));
  };

  // Is the given value `NaN`? `NaN` happens to be the only value in JavaScript
  // that does not equal itself.
  _.isNaN = function(obj) {
    return obj !== obj;
  };

  // Is a given value a boolean?
  _.isBoolean = function(obj) {
    return obj === true || obj === false;
  };

  // Is a given value a date?
  _.isDate = function(obj) {
    return !!(obj && obj.getTimezoneOffset && obj.setUTCFullYear);
  };

  // Is the given value a regular expression?
  _.isRegExp = function(obj) {
    return !!(obj && obj.test && obj.exec && (obj.ignoreCase || obj.ignoreCase === false));
  };

  // Is a given value equal to null?
  _.isNull = function(obj) {
    return obj === null;
  };

  // Is a given variable undefined?
  _.isUndefined = function(obj) {
    return obj === void 0;
  };

  // Utility Functions
  // -----------------

  // Run Underscore.js in *noConflict* mode, returning the `_` variable to its
  // previous owner. Returns a reference to the Underscore object.
  _.noConflict = function() {
    root._ = previousUnderscore;
    return this;
  };

  // Keep the identity function around for default iterators.
  _.identity = function(value) {
    return value;
  };

  // Run a function **n** times.
  _.times = function (n, iterator, context) {
    for (var i = 0; i < n; i++) iterator.call(context, i);
  };

  // Add your own custom functions to the Underscore object, ensuring that
  // they're correctly added to the OOP wrapper as well.
  _.mixin = function(obj) {
    each(_.functions(obj), function(name){
      addToWrapper(name, _[name] = obj[name]);
    });
  };

  // Generate a unique integer id (unique within the entire client session).
  // Useful for temporary DOM ids.
  var idCounter = 0;
  _.uniqueId = function(prefix) {
    var id = idCounter++;
    return prefix ? prefix + id : id;
  };

  // By default, Underscore uses ERB-style template delimiters, change the
  // following template settings to use alternative delimiters.
  _.templateSettings = {
    evaluate    : /<%([\s\S]+?)%>/g,
    interpolate : /<%=([\s\S]+?)%>/g
  };

  // JavaScript micro-templating, similar to John Resig's implementation.
  // Underscore templating handles arbitrary delimiters, preserves whitespace,
  // and correctly escapes quotes within interpolated code.
  _.template = function(str, data) {
    var c  = _.templateSettings;
    var tmpl = 'var __p=[],print=function(){__p.push.apply(__p,arguments);};' +
      'with(obj||{}){__p.push(\'' +
      str.replace(/\\/g, '\\\\')
         .replace(/'/g, "\\'")
         .replace(c.interpolate, function(match, code) {
           return "'," + code.replace(/\\'/g, "'") + ",'";
         })
         .replace(c.evaluate || null, function(match, code) {
           return "');" + code.replace(/\\'/g, "'")
                              .replace(/[\r\n\t]/g, ' ') + "__p.push('";
         })
         .replace(/\r/g, '\\r')
         .replace(/\n/g, '\\n')
         .replace(/\t/g, '\\t')
         + "');}return __p.join('');";
    var func = new Function('obj', tmpl);
    return data ? func(data) : func;
  };

  // The OOP Wrapper
  // ---------------

  // If Underscore is called as a function, it returns a wrapped object that
  // can be used OO-style. This wrapper holds altered versions of all the
  // underscore functions. Wrapped objects may be chained.
  var wrapper = function(obj) { this._wrapped = obj; };

  // Expose `wrapper.prototype` as `_.prototype`
  _.prototype = wrapper.prototype;

  // Helper function to continue chaining intermediate results.
  var result = function(obj, chain) {
    return chain ? _(obj).chain() : obj;
  };

  // A method to easily add functions to the OOP wrapper.
  var addToWrapper = function(name, func) {
    wrapper.prototype[name] = function() {
      var args = slice.call(arguments);
      unshift.call(args, this._wrapped);
      return result(func.apply(_, args), this._chain);
    };
  };

  // Add all of the Underscore functions to the wrapper object.
  _.mixin(_);

  // Add all mutator Array functions to the wrapper.
  each(['pop', 'push', 'reverse', 'shift', 'sort', 'splice', 'unshift'], function(name) {
    var method = ArrayProto[name];
    wrapper.prototype[name] = function() {
      method.apply(this._wrapped, arguments);
      return result(this._wrapped, this._chain);
    };
  });

  // Add all accessor Array functions to the wrapper.
  each(['concat', 'join', 'slice'], function(name) {
    var method = ArrayProto[name];
    wrapper.prototype[name] = function() {
      return result(method.apply(this._wrapped, arguments), this._chain);
    };
  });

  // Start chaining a wrapped Underscore object.
  wrapper.prototype.chain = function() {
    this._chain = true;
    return this;
  };

  // Extracts the result from a wrapped and chained object.
  wrapper.prototype.value = function() {
    return this._wrapped;
  };

})();