text: 'use strict';
  
  var extend = require('./deps/extend');
  
  
  // for a better overview of what this is doing, read:
  // https://github.com/apache/couchdb/blob/master/src/couchdb/couch_key_tree.erl
  //
  // But for a quick intro, CouchDB uses a revision tree to store a documents
  // history, A -> B -> C, when a document has conflicts, that is a branch in the
  // tree, A -> (B1 | B2 -> C), We store these as a nested array in the format
  //
  // KeyTree = [Path ... ]
  // Path = {pos: position_from_root, ids: Tree}
  // Tree = [Key, Opts, [Tree, ...]], in particular single node: [Key, []]
  
  // Turn a path as a flat array into a tree with a single branch
  function pathToTree(path) {
    var doc = path.shift();
    var root = [doc.id, doc.opts, []];
    var leaf = root;
    var nleaf;
  
    while (path.length) {
      doc = path.shift();
      nleaf = [doc.id, doc.opts, []];
      leaf[2].push(nleaf);
      leaf = nleaf;
    }
    return root;
  }
  
  // Merge two trees together
  // The roots of tree1 and tree2 must be the same revision
  function mergeTree(in_tree1, in_tree2) {
    var queue = [{tree1: in_tree1, tree2: in_tree2}];
    var conflicts = false;
    while (queue.length > 0) {
      var item = queue.pop();
      var tree1 = item.tree1;
      var tree2 = item.tree2;
  
      if (tree1[1].status || tree2[1].status) {
        tree1[1].status = (tree1[1].status ===  'available' ||
                           tree2[1].status === 'available') ? 'available' : 'missing';
      }
  
      for (var i = 0; i < tree2[2].length; i++) {
        if (!tree1[2][0]) {
          conflicts = 'new_leaf';
          tree1[2][0] = tree2[2][i];
          continue;
        }
  
        var merged = false;
        for (var j = 0; j < tree1[2].length; j++) {
          if (tree1[2][j][0] === tree2[2][i][0]) {
            queue.push({tree1: tree1[2][j], tree2: tree2[2][i]});
            merged = true;
          }
        }
        if (!merged) {
          conflicts = 'new_branch';
          tree1[2].push(tree2[2][i]);
          tree1[2].sort();
        }
      }
    }
    return {conflicts: conflicts, tree: in_tree1};
  }
  
  function doMerge(tree, path, dontExpand) {
    var restree = [];
    var conflicts = false;
    var merged = false;
    var res;
  
    if (!tree.length) {
      return {tree: [path], conflicts: 'new_leaf'};
    }
  
    tree.forEach(function (branch) {
      if (branch.pos === path.pos && branch.ids[0] === path.ids[0]) {
        // Paths start at the same position and have the same root, so they need
        // merged
        res = mergeTree(branch.ids, path.ids);
        restree.push({pos: branch.pos, ids: res.tree});
        conflicts = conflicts || res.conflicts;
        merged = true;
      } else if (dontExpand !== true) {
        // The paths start at a different position, take the earliest path and
        // traverse up until it as at the same point from root as the path we want to
        // merge.  If the keys match we return the longer path with the other merged
        // After stemming we dont want to expand the trees
  
        var t1 = branch.pos < path.pos ? branch : path;
        var t2 = branch.pos < path.pos ? path : branch;
        var diff = t2.pos - t1.pos;
  
        var candidateParents = [];
  
        var trees = [];
        trees.push({ids: t1.ids, diff: diff, parent: null, parentIdx: null});
        while (trees.length > 0) {
          var item = trees.pop();
          if (item.diff === 0) {
            if (item.ids[0] === t2.ids[0]) {
              candidateParents.push(item);
            }
            continue;
          }
          if (!item.ids) {
            continue;
          }
          /*jshint loopfunc:true */
          item.ids[2].forEach(function (el, idx) {
            trees.push({ids: el, diff: item.diff - 1, parent: item.ids, parentIdx: idx});
          });
        }
  
        var el = candidateParents[0];
  
        if (!el) {
          restree.push(branch);
        } else {
          res = mergeTree(el.ids, t2.ids);
          el.parent[2][el.parentIdx] = res.tree;
          restree.push({pos: t1.pos, ids: t1.ids});
          conflicts = conflicts || res.conflicts;
          merged = true;
        }
      } else {
        restree.push(branch);
      }
    });
  
    // We didnt find
    if (!merged) {
      restree.push(path);
    }
  
    restree.sort(function (a, b) {
      return a.pos - b.pos;
    });
  
    return {
      tree: restree,
      conflicts: conflicts || 'internal_node'
    };
  }
  
  // To ensure we dont grow the revision tree infinitely, we stem old revisions
  function stem(tree, depth) {
    // First we break out the tree into a complete list of root to leaf paths,
    // we cut off the start of the path and generate a new set of flat trees
    var stemmedPaths = PouchMerge.rootToLeaf(tree).map(function (path) {
      var stemmed = path.ids.slice(-depth);
      return {
        pos: path.pos + (path.ids.length - stemmed.length),
        ids: pathToTree(stemmed)
      };
    });
    // Then we remerge all those flat trees together, ensuring that we dont
    // connect trees that would go beyond the depth limit
    return stemmedPaths.reduce(function (prev, current, i, arr) {
      return doMerge(prev, current, true).tree;
    }, [stemmedPaths.shift()]);
  }
  
  var PouchMerge = {};
  
  PouchMerge.merge = function (tree, path, depth) {
    // Ugh, nicer way to not modify arguments in place?
    tree = extend(true, [], tree);
    path = extend(true, {}, path);
    var newTree = doMerge(tree, path);
    return {
      tree: stem(newTree.tree, depth),
      conflicts: newTree.conflicts
    };
  };
  
  // We fetch all leafs of the revision tree, and sort them based on tree length
  // and whether they were deleted, undeleted documents with the longest revision
  // tree (most edits) win
  // The final sort algorithm is slightly documented in a sidebar here:
  // http://guide.couchdb.org/draft/conflicts.html
  PouchMerge.winningRev = function (metadata) {
    var leafs = [];
    PouchMerge.traverseRevTree(metadata.rev_tree,
                                function (isLeaf, pos, id, something, opts) {
      if (isLeaf) {
        leafs.push({pos: pos, id: id, deleted: !!opts.deleted});
      }
    });
    leafs.sort(function (a, b) {
      if (a.deleted !== b.deleted) {
        return a.deleted > b.deleted ? 1 : -1;
      }
      if (a.pos !== b.pos) {
        return b.pos - a.pos;
      }
      return a.id < b.id ? 1 : -1;
    });
  
    return leafs[0].pos + '-' + leafs[0].id;
  };
  
  // Pretty much all below can be combined into a higher order function to
  // traverse revisions
  // The return value from the callback will be passed as context to all
  // children of that node
  PouchMerge.traverseRevTree = function (revs, callback) {
    var toVisit = [];
  
    revs.forEach(function (tree) {
      toVisit.push({pos: tree.pos, ids: tree.ids});
    });
    while (toVisit.length > 0) {
      var node = toVisit.pop();
      var pos = node.pos;
      var tree = node.ids;
      var newCtx = callback(tree[2].length === 0, pos, tree[0], node.ctx, tree[1]);
      /*jshint loopfunc: true */
      tree[2].forEach(function (branch) {
        toVisit.push({pos: pos + 1, ids: branch, ctx: newCtx});
      });
    }
  };
  
  PouchMerge.collectLeaves = function (revs) {
    var leaves = [];
    PouchMerge.traverseRevTree(revs, function (isLeaf, pos, id, acc, opts) {
      if (isLeaf) {
        leaves.unshift({rev: pos + "-" + id, pos: pos, opts: opts});
      }
    });
    leaves.sort(function (a, b) {
      return b.pos - a.pos;
    });
    leaves.map(function (leaf) { delete leaf.pos; });
    return leaves;
  };
  
  // returns revs of all conflicts that is leaves such that
  // 1. are not deleted and
  // 2. are different than winning revision
  PouchMerge.collectConflicts = function (metadata) {
    var win = PouchMerge.winningRev(metadata);
    var leaves = PouchMerge.collectLeaves(metadata.rev_tree);
    var conflicts = [];
    leaves.forEach(function (leaf) {
      if (leaf.rev !== win && !leaf.opts.deleted) {
        conflicts.push(leaf.rev);
      }
    });
    return conflicts;
  };
  
  PouchMerge.rootToLeaf = function (tree) {
    var paths = [];
    PouchMerge.traverseRevTree(tree, function (isLeaf, pos, id, history, opts) {
      history = history ? history.slice(0) : [];
      history.push({id: id, opts: opts});
      if (isLeaf) {
        var rootPos = pos + 1 - history.length;
        paths.unshift({pos: rootPos, ids: history});
      }
      return history;
    });
    return paths;
  };
  
  
  module.exports = PouchMerge;
  