text: var diff = require('fast-diff');
  var equal = require('deep-equal');
  var extend = require('extend');
  var op = require('./op');
  
  
  var NULL_CHARACTER = String.fromCharCode(0);  // Placeholder char for embed in diff()
  
  
  var Delta = function (ops) {
    // Assume we are given a well formed ops
    if (Array.isArray(ops)) {
      this.ops = ops;
    } else if (ops != null && Array.isArray(ops.ops)) {
      this.ops = ops.ops;
    } else {
      this.ops = [];
    }
  };
  
  
  Delta.prototype.insert = function (text, attributes) {
    var newOp = {};
    if (text.length === 0) return this;
    newOp.insert = text;
    if (attributes != null && typeof attributes === 'object' && Object.keys(attributes).length > 0) {
      newOp.attributes = attributes;
    }
    return this.push(newOp);
  };
  
  Delta.prototype['delete'] = function (length) {
    if (length <= 0) return this;
    return this.push({ 'delete': length });
  };
  
  Delta.prototype.retain = function (length, attributes) {
    if (length <= 0) return this;
    var newOp = { retain: length };
    if (attributes != null && typeof attributes === 'object' && Object.keys(attributes).length > 0) {
      newOp.attributes = attributes;
    }
    return this.push(newOp);
  };
  
  Delta.prototype.push = function (newOp) {
    var index = this.ops.length;
    var lastOp = this.ops[index - 1];
    newOp = extend(true, {}, newOp);
    if (typeof lastOp === 'object') {
      if (typeof newOp['delete'] === 'number' && typeof lastOp['delete'] === 'number') {
        this.ops[index - 1] = { 'delete': lastOp['delete'] + newOp['delete'] };
        return this;
      }
      // Since it does not matter if we insert before or after deleting at the same index,
      // always prefer to insert first
      if (typeof lastOp['delete'] === 'number' && newOp.insert != null) {
        index -= 1;
        lastOp = this.ops[index - 1];
        if (typeof lastOp !== 'object') {
          this.ops.unshift(newOp);
          return this;
        }
      }
      if (equal(newOp.attributes, lastOp.attributes)) {
        if (typeof newOp.insert === 'string' && typeof lastOp.insert === 'string') {
          this.ops[index - 1] = { insert: lastOp.insert + newOp.insert };
          if (typeof newOp.attributes === 'object') this.ops[index - 1].attributes = newOp.attributes
          return this;
        } else if (typeof newOp.retain === 'number' && typeof lastOp.retain === 'number') {
          this.ops[index - 1] = { retain: lastOp.retain + newOp.retain };
          if (typeof newOp.attributes === 'object') this.ops[index - 1].attributes = newOp.attributes
          return this;
        }
      }
    }
    if (index === this.ops.length) {
      this.ops.push(newOp);
    } else {
      this.ops.splice(index, 0, newOp);
    }
    return this;
  };
  
  Delta.prototype.filter = function (predicate) {
    return this.ops.filter(predicate);
  };
  
  Delta.prototype.forEach = function (predicate) {
    this.ops.forEach(predicate);
  };
  
  Delta.prototype.map = function (predicate) {
    return this.ops.map(predicate);
  };
  
  Delta.prototype.partition = function (predicate) {
    var passed = [], failed = [];
    this.forEach(function(op) {
      var target = predicate(op) ? passed : failed;
      target.push(op);
    });
    return [passed, failed];
  };
  
  Delta.prototype.reduce = function (predicate, initial) {
    return this.ops.reduce(predicate, initial);
  };
  
  Delta.prototype.chop = function () {
    var lastOp = this.ops[this.ops.length - 1];
    if (lastOp && lastOp.retain && !lastOp.attributes) {
      this.ops.pop();
    }
    return this;
  };
  
  Delta.prototype.length = function () {
    return this.reduce(function (length, elem) {
      return length + op.length(elem);
    }, 0);
  };
  
  Delta.prototype.slice = function (start, end) {
    start = start || 0;
    if (typeof end !== 'number') end = Infinity;
    var ops = [];
    var iter = op.iterator(this.ops);
    var index = 0;
    while (index < end && iter.hasNext()) {
      var nextOp;
      if (index < start) {
        nextOp = iter.next(start - index);
      } else {
        nextOp = iter.next(end - index);
        ops.push(nextOp);
      }
      index += op.length(nextOp);
    }
    return new Delta(ops);
  };
  
  
  Delta.prototype.compose = function (other) {
    var thisIter = op.iterator(this.ops);
    var otherIter = op.iterator(other.ops);
    var delta = new Delta();
    while (thisIter.hasNext() || otherIter.hasNext()) {
      if (otherIter.peekType() === 'insert') {
        delta.push(otherIter.next());
      } else if (thisIter.peekType() === 'delete') {
        delta.push(thisIter.next());
      } else {
        var length = Math.min(thisIter.peekLength(), otherIter.peekLength());
        var thisOp = thisIter.next(length);
        var otherOp = otherIter.next(length);
        if (typeof otherOp.retain === 'number') {
          var newOp = {};
          if (typeof thisOp.retain === 'number') {
            newOp.retain = length;
          } else {
            newOp.insert = thisOp.insert;
          }
          // Preserve null when composing with a retain, otherwise remove it for inserts
          var attributes = op.attributes.compose(thisOp.attributes, otherOp.attributes, typeof thisOp.retain === 'number');
          if (attributes) newOp.attributes = attributes;
          delta.push(newOp);
        // Other op should be delete, we could be an insert or retain
        // Insert + delete cancels out
        } else if (typeof otherOp['delete'] === 'number' && typeof thisOp.retain === 'number') {
          delta.push(otherOp);
        }
      }
    }
    return delta.chop();
  };
  
  Delta.prototype.concat = function (other) {
    var delta = new Delta(this.ops.slice());
    if (other.ops.length > 0) {
      delta.push(other.ops[0]);
      delta.ops.push.apply(delta.ops, other.ops.slice(1));
    }
    return delta;
  };
  
  Delta.prototype.diff = function (other, index) {
    if (this.ops === other.ops) {
      return new Delta();
    }
    var strings = [this, other].map(function (delta) {
      return delta.map(function (op) {
        if (op.insert != null) {
          return typeof op.insert === 'string' ? op.insert : NULL_CHARACTER;
        }
        var prep = (delta === other) ? 'on' : 'with';
        throw new Error('diff() called ' + prep + ' non-document');
      }).join('');
    });
    var delta = new Delta();
    var diffResult = diff(strings[0], strings[1], index);
    var thisIter = op.iterator(this.ops);
    var otherIter = op.iterator(other.ops);
    diffResult.forEach(function (component) {
      var length = component[1].length;
      while (length > 0) {
        var opLength = 0;
        switch (component[0]) {
          case diff.INSERT:
            opLength = Math.min(otherIter.peekLength(), length);
            delta.push(otherIter.next(opLength));
            break;
          case diff.DELETE:
            opLength = Math.min(length, thisIter.peekLength());
            thisIter.next(opLength);
            delta['delete'](opLength);
            break;
          case diff.EQUAL:
            opLength = Math.min(thisIter.peekLength(), otherIter.peekLength(), length);
            var thisOp = thisIter.next(opLength);
            var otherOp = otherIter.next(opLength);
            if (equal(thisOp.insert, otherOp.insert)) {
              delta.retain(opLength, op.attributes.diff(thisOp.attributes, otherOp.attributes));
            } else {
              delta.push(otherOp)['delete'](opLength);
            }
            break;
        }
        length -= opLength;
      }
    });
    return delta.chop();
  };
  
  Delta.prototype.eachLine = function (predicate, newline) {
    newline = newline || '\n';
    var iter = op.iterator(this.ops);
    var line = new Delta();
    var i = 0;
    while (iter.hasNext()) {
      if (iter.peekType() !== 'insert') return;
      var thisOp = iter.peek();
      var start = op.length(thisOp) - iter.peekLength();
      var index = typeof thisOp.insert === 'string' ?
        thisOp.insert.indexOf(newline, start) - start : -1;
      if (index < 0) {
        line.push(iter.next());
      } else if (index > 0) {
        line.push(iter.next(index));
      } else {
        if (predicate(line, iter.next(1).attributes || {}, i) === false) {
          return;
        }
        i += 1;
        line = new Delta();
      }
    }
    if (line.length() > 0) {
      predicate(line, {}, i);
    }
  };
  
  Delta.prototype.transform = function (other, priority) {
    priority = !!priority;
    if (typeof other === 'number') {
      return this.transformPosition(other, priority);
    }
    var thisIter = op.iterator(this.ops);
    var otherIter = op.iterator(other.ops);
    var delta = new Delta();
    while (thisIter.hasNext() || otherIter.hasNext()) {
      if (thisIter.peekType() === 'insert' && (priority || otherIter.peekType() !== 'insert')) {
        delta.retain(op.length(thisIter.next()));
      } else if (otherIter.peekType() === 'insert') {
        delta.push(otherIter.next());
      } else {
        var length = Math.min(thisIter.peekLength(), otherIter.peekLength());
        var thisOp = thisIter.next(length);
        var otherOp = otherIter.next(length);
        if (thisOp['delete']) {
          // Our delete either makes their delete redundant or removes their retain
          continue;
        } else if (otherOp['delete']) {
          delta.push(otherOp);
        } else {
          // We retain either their retain or insert
          delta.retain(length, op.attributes.transform(thisOp.attributes, otherOp.attributes, priority));
        }
      }
    }
    return delta.chop();
  };
  
  Delta.prototype.transformPosition = function (index, priority) {
    priority = !!priority;
    var thisIter = op.iterator(this.ops);
    var offset = 0;
    while (thisIter.hasNext() && offset <= index) {
      var length = thisIter.peekLength();
      var nextType = thisIter.peekType();
      thisIter.next();
      if (nextType === 'delete') {
        index -= Math.min(length, index - offset);
        continue;
      } else if (nextType === 'insert' && (offset < index || !priority)) {
        index += length;
      }
      offset += length;
    }
    return index;
  };
  
  
  module.exports = Delta;
  