// Please do what you want with this code
// TODO: Test test test and test

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <map>
#include <stdexcept>
#include <cassert>

const unsigned int USER_COUNT = 5;
//#define LOWER_TRANSFER

template<typename ValueT>
class pword;

template<typename ValueT>
std::ostream& operator<<(std::ostream& out, const pword<ValueT>& obj);

class operation;
class insert_operation;
class delete_operation;
class no_operation;
class split_operation;

template<typename ValueT>
class pword
{
  friend std::ostream& operator<< <>(std::ostream& out, const pword<ValueT>& obj);
public:
  typedef ValueT value_type;
private:
  typedef std::vector<value_type> pword_type;

public:
  pword() {};
  pword(const pword& other): m_pword(other.m_pword) {}
  pword(const pword& other, const value_type& next): m_pword(other.m_pword) { m_pword.push_back(next); }
  typename pword_type::size_type size() const { return m_pword.size(); }

  const value_type& current() { return m_pword.back(); }
  const value_type& origin() { return m_pword.front(); }

  int compare(const pword& other) const
  {
    typename pword_type::const_reverse_iterator iter1 = m_pword.rbegin();
    typename pword_type::const_reverse_iterator iter2 = other.m_pword.rbegin();

    for(; iter1 != m_pword.rend() && iter2 != other.m_pword.rend(); ++ iter1, ++ iter2)
    {
      if(*iter1 < *iter2)
        return -1;
      if(*iter1 > *iter2)
        return 1;
    }

    if(iter1 == m_pword.rend() && iter2 != other.m_pword.rend())
      return 1;
    else if(iter1 != m_pword.rend() && iter2 == other.m_pword.rend())
      return -1;
    return 0;
  }

  bool operator==(const pword& other) const { return compare(other) == 0; }
  bool operator<=(const pword& other) const { return compare(other) <= 0; }
  bool operator<(const pword& other) const { return compare(other) < 0; }
  bool operator>=(const pword& other) const { return compare(other) >= 0; }
  bool operator>(const pword& other) const { return compare(other) > 0; }

private:
  pword_type m_pword;
};

template<typename ValueT>
std::ostream& operator<<(std::ostream& out, const pword<ValueT>& obj) {
  out << "[";
  for(typename pword<ValueT>::pword_type::const_iterator iter = obj.m_pword.begin();
      iter != obj.m_pword.end(); ++ iter)
  {
    if(iter != obj.m_pword.begin())
      out << ", ";

    out << *iter;
  }

  out << "]";
  return out;
}

class operation
{
  friend class insert_operation;
  friend class delete_operation;
  friend class no_operation;
  friend class split_operation;
public:
  virtual ~operation() {}
  virtual std::auto_ptr<operation> clone() const = 0;
  virtual std::auto_ptr<operation> transform_against(const operation& trans) const = 0;

  virtual bool lowered() const  = 0;
  virtual std::auto_ptr<operation> lower() const = 0;
  virtual std::auto_ptr<operation> restore(const operation& lowered, const std::string& doc) const = 0;
  virtual std::auto_ptr<operation> merge(const operation& other) const = 0;

  virtual void apply(std::string& doc) const = 0;
  virtual std::auto_ptr<operation> inverse() const = 0;
  virtual bool operator==(const operation& other) const = 0;
  virtual std::string to_string() const = 0;

  static std::auto_ptr<operation> from_string(const std::string& str, const std::string& doc);

protected:
  virtual std::auto_ptr<operation> transform_insert(const insert_operation& ins) const = 0;
  virtual std::auto_ptr<operation> transform_delete(const delete_operation& del) const = 0;
};

class insert_operation: public operation
{
  friend class delete_operation;
private:
  unsigned int m_pos;
  std::string m_text;
  typedef pword<unsigned int> pword_type;
  pword_type m_pword;
public:
  insert_operation(unsigned int pos, const std::string& text):
    m_pos(pos), m_text(text) {}
  insert_operation(unsigned int pos, const std::string& text,
                   const pword_type& pword):
    m_pos(pos), m_text(text), m_pword(pword) {}
  insert_operation(const insert_operation& other):
    m_pos(other.m_pos), m_text(other.m_text), m_pword(other.m_pword) {}

  virtual std::auto_ptr<operation> clone() const {
    return std::auto_ptr<operation>(new insert_operation(*this));
  }

  virtual bool lowered() const  { return false; }
  virtual std::auto_ptr<operation> lower() const { return clone(); } // Cannot actually lower insert operation
  virtual std::auto_ptr<operation> restore(const operation& lowered, const std::string& doc) const { throw std::runtime_error("Insert operation cannot restore anything"); }
  virtual std::auto_ptr<operation> merge(const operation& other) const { throw std::runtime_error("Cannot merge insert operations"); }

  virtual void apply(std::string& doc) const { doc.insert(m_pos, m_text); }
  virtual std::auto_ptr<operation> inverse() const;
  virtual bool operator==(const operation& other) const;

  virtual std::string to_string() const {
    std::stringstream stream;
    stream << "ins(" << m_pos << "," << m_text << "," << m_pword << ")";
    return stream.str();
  };

  /* TODO: Put m_pos as current position into pword */
  pword_type pw() const {
    return pword_type(m_pword, m_pos);
  };

  virtual std::auto_ptr<operation> transform_against(const operation& trans) const {
    return trans.transform_insert(*this);
  }

protected:
  virtual std::auto_ptr<operation> transform_insert(const insert_operation& ins) const;

  virtual std::auto_ptr<operation> transform_delete(const delete_operation& del) const;
};

class delete_operation: public operation
{
  friend class insert_operation;
  friend class no_operation;
public:
  typedef std::list<std::pair<unsigned int, std::string> > recon_type;

private:
  unsigned int m_pos;
  unsigned int m_len;
  std::string m_text;

  recon_type m_recon;
  unsigned int m_offset;

  static recon_type transfer_to_recon(const recon_type& recon, unsigned int pos, const std::string& text)
  {
    recon_type result;
    unsigned int text_pos = 0;
    unsigned int cur_len = 0;
    for(recon_type::const_iterator iter = recon.begin(); iter != recon.end(); ++ iter)
    {
      if(pos + text_pos + cur_len < iter->first && text_pos < text.length())
      {
        unsigned int text_len = iter->first - pos - text_pos - cur_len;
	if(text_len > text.length() - text_pos)
	  text_len = text.length() - text_pos;

        result.push_back(std::make_pair(pos + text_pos + cur_len, text.substr(text_pos, text_len)));

        text_pos += text_len;
      }

      cur_len += iter->second.length();

      result.push_back(*iter);
    }

    if(text_pos < text.length())
    {
      result.push_back(std::make_pair(pos + text_pos + cur_len, text.substr(text_pos)));
    }
    
    return result;
  }

  static std::string recon_to_text(const recon_type& recon)
  {
    std::string text;
    for(recon_type::const_iterator iter = recon.begin(); iter != recon.end(); ++ iter)
    {
      assert(text.length() == iter->first);
      text += iter->second;
    }

    return text;
  }

public:
  delete_operation(unsigned int pos, const std::string& text):
    m_pos(pos), m_len(text.length()), m_text(text), m_offset(0) {}
  delete_operation(unsigned int pos, unsigned int len, const recon_type& recon, unsigned int offset):
    m_pos(pos), m_len(len), m_recon(recon), m_offset(offset) {}
  delete_operation(const delete_operation& other):
    m_pos(other.m_pos), m_len(other.m_len), m_text(other.m_text), m_recon(other.m_recon), m_offset(other.m_offset) {}

  virtual std::auto_ptr<operation> clone() const {
    return std::auto_ptr<operation>(new delete_operation(*this));
  }

  virtual bool lowered() const  { bool lowered = m_text.empty() && m_len > 0; if(!lowered) assert(m_text.length() == m_len); return lowered; }

  virtual std::auto_ptr<operation> lower() const { assert(!lowered()); return std::auto_ptr<operation>(new delete_operation(m_pos, m_len, recon_type(), 0)); }
  virtual std::auto_ptr<operation> restore(const operation& lowered_, const std::string& doc) const
  {
    const delete_operation* delete_lowered = dynamic_cast<const delete_operation*>(&lowered_);
    if(delete_lowered == NULL) throw std::runtime_error("delete_operation cannot restore non-delete operation");

    assert(lowered());
    assert(delete_lowered->lowered());

    // TODO: Note that if we are part of a split operation it may happen that m_len < delete_lowered->m_len
    recon_type recon = transfer_to_recon(m_recon, 0, doc.substr(m_pos, m_len));
    std::string text = recon_to_text(recon);
    //assert(text.length() == delete_lowered->m_len); // TODO: This might not hold if we are part of a split operation
    return std::auto_ptr<operation>(new delete_operation(delete_lowered->m_pos + m_offset, text));
  }

  virtual std::auto_ptr<operation> merge(const operation& other) const
  {
    const delete_operation* delete_other = dynamic_cast<const delete_operation*>(&other);
    if(delete_other == NULL) throw std::runtime_error("Cannot merge delete operation with non-delete operation");

    assert( (!lowered() && !delete_other->lowered()));

    assert(m_pos + m_len == delete_other->m_pos ||
           delete_other->m_pos + delete_other->m_len  == m_pos);

    if(m_pos + m_len == delete_other->m_pos)
    { 
      return std::auto_ptr<operation>(new delete_operation(m_pos, m_text + delete_other->m_text));
    }
    else
    {
      return std::auto_ptr<operation>(new delete_operation(delete_other->m_pos, delete_other->m_text + m_text));
    }
  }

  virtual void apply(std::string& doc) const {
    if(!lowered() && doc.substr(m_pos, m_text.length()) != m_text)
      throw std::runtime_error("delete_operation::apply: Text in document does not match deleted text");

    doc.erase(m_pos, m_len);
  }

  virtual std::auto_ptr<operation> inverse() const;
  virtual bool operator==(const operation& other) const;

  virtual std::string to_string() const {
    std::stringstream stream;
    if(lowered())
      stream << "del(" << m_pos << "," << m_len << ")";
    else
      stream << "del(" << m_pos << "," << m_text << ")";

    return stream.str();
  };

  virtual std::auto_ptr<operation> transform_against(const operation& trans) const {
    return trans.transform_delete(*this);
  }

protected:
  virtual std::auto_ptr<operation> transform_insert(const insert_operation& ins) const;

  virtual std::auto_ptr<operation> transform_delete(const delete_operation& del) const;
};

class no_operation: public operation
{
private:
  std::string m_text;
  unsigned int m_offset;

public:
  no_operation(): m_offset(0) {}
  no_operation(const std::string& text, unsigned int offset): m_text(text), m_offset(offset) {}
  no_operation(const no_operation& other):
    m_text(other.m_text), m_offset(other.m_offset) {}

  virtual std::auto_ptr<operation> clone() const {
    return std::auto_ptr<operation>(new no_operation(*this));
  }

  virtual bool lowered() const  { return !m_text.empty(); }
  virtual std::auto_ptr<operation> lower() const { throw std::runtime_error("Cannot lower no operation"); }
  virtual std::auto_ptr<operation> restore(const operation& lowered_, const std::string& doc) const
  {
    const delete_operation* delete_lowered = dynamic_cast<const delete_operation*>(&lowered_);
    if(delete_lowered == NULL) throw std::runtime_error("No operation can only restore delete operation");

    assert(lowered());
    assert(delete_lowered->lowered());

    return std::auto_ptr<operation>(new delete_operation(m_offset + delete_lowered->m_pos, m_text));
  }

  virtual std::auto_ptr<operation> merge(const operation& other) const { throw std::runtime_error("Cannot merge no operation"); }

  virtual void apply(std::string& doc) const {}
  virtual std::auto_ptr<operation> inverse() const {
    if(m_text.length() > 0)
      throw std::runtime_error("Cannot inverse lowered no_operation");
    return clone();
  }

  virtual bool operator==(const operation& other) const;

  virtual std::string to_string() const {
    return "nop()";
  };

  virtual std::auto_ptr<operation> transform_against(const operation& trans) const {
    return clone();
  }

protected:
  virtual std::auto_ptr<operation> transform_insert(const insert_operation& ins) const {
    return ins.clone();
  }

  virtual std::auto_ptr<operation> transform_delete(const delete_operation& del) const {
    return del.clone();
  }
};

class split_operation: public operation
{
private:
  std::auto_ptr<operation> m_op1;
  std::auto_ptr<operation> m_op2;

  static std::auto_ptr<operation> unsplit(std::auto_ptr<operation>& op1, std::auto_ptr<operation>& op2) 
  {/*
    if(dynamic_cast<no_operation*>(op1.get()) != NULL)
      return op2;
    if(dynamic_cast<no_operation*>(op2.get()) != NULL)
      return op1;*/
    // TODO: Merge two adjacent delete operations to a single one, and do
    // perhaps the same with insert operations.
    return std::auto_ptr<operation>(new split_operation(op1, op2));
  }

  template<typename InsertIterator>
  void strip(InsertIterator iter) const {
    if(dynamic_cast<split_operation*>(m_op1.get()) != NULL)
      static_cast<split_operation*>(m_op1.get())->strip(iter);
    else
      *iter = m_op1.get();

    if(dynamic_cast<split_operation*>(m_op2.get()) != NULL)
      static_cast<split_operation*>(m_op2.get())->strip(iter);
    else
      *iter = m_op2.get();
  }

public:
  split_operation(std::auto_ptr<operation> op1, std::auto_ptr<operation> op2):
    m_op1(op1), m_op2(op2) {}
  split_operation(const split_operation& other):
    m_op1(other.m_op1->clone()), m_op2(other.m_op2->clone()) {}

  virtual std::auto_ptr<operation> clone() const {
    return std::auto_ptr<operation>(new split_operation(
      std::auto_ptr<operation>(m_op1->clone()),
      std::auto_ptr<operation>(m_op2->clone())
    ));
  }

  virtual bool lowered() const  { return m_op1->lowered() || m_op2->lowered(); }
  virtual std::auto_ptr<operation> lower() const {
    return std::auto_ptr<operation>(new split_operation(
      m_op1->lowered() ? m_op1->clone() : m_op1->lower(),
      m_op2->lowered() ? m_op2->clone() : m_op2->lower()
    ));
  }

  virtual std::auto_ptr<operation> restore(const operation& lowered, const std::string& doc) const 
  {
    // Let both operations restore their part of lowered
    std::auto_ptr<operation> restored1 = m_op1->restore(lowered, doc);
    std::auto_ptr<operation> restored2 = m_op2->restore(lowered, doc);
    // Merge
    return restored1->merge(*restored2);
  }

  virtual std::auto_ptr<operation> merge(const operation& other) const { throw std::runtime_error("Cannot merge split operation"); }

  virtual void apply(std::string& doc) const {
    std::auto_ptr<operation> new_op2 = m_op2->transform_against(*m_op1);
    m_op1->apply(doc);
    new_op2->apply(doc);
  }

  virtual std::auto_ptr<operation> inverse() const {
    std::auto_ptr<operation> new_op2 = m_op2->transform_against(*m_op1);
    return std::auto_ptr<operation>(new split_operation(
      m_op1->inverse(),
      new_op2->inverse()
    ));
  }

  virtual bool operator==(const operation& other) const {
    const split_operation* split_other = dynamic_cast<const split_operation*>(&other);

    // split_ops are also equal if the contained operations
    // are in different order
    std::deque<const operation*> op_1;
    std::deque<const operation*> op_2;
    strip(std::insert_iterator<std::deque<const operation*> >(op_1, op_1.begin()));
    if(split_other)
      split_other->strip(std::insert_iterator<std::deque<const operation*> >(op_2, op_2.begin()));
    else
      op_2.push_back(&other);

    for(std::deque<const operation*>::iterator iter_1 = op_1.begin(); iter_1 != op_1.end(); ++ iter_1) {
      if(dynamic_cast<const no_operation*>(*iter_1) != NULL) continue;

      std::deque<const operation*>::iterator iter_2;
      for(iter_2 = op_2.begin(); iter_2 != op_2.end(); ++ iter_2) {
        if(**iter_1 == **iter_2)
          break;
      }

      if(iter_2 == op_2.end())
        return false;
    }

    for(std::deque<const operation*>::iterator iter_2 = op_2.begin(); iter_2 != op_2.end(); ++ iter_2)
    {
      if(dynamic_cast<const no_operation*>(*iter_2) != NULL) continue;

      std::deque<const operation*>::iterator iter_1;
      for(iter_1 = op_1.begin(); iter_1 != op_1.end(); ++ iter_1)
        if(**iter_1 == **iter_2)
	  break;

      if(iter_1 == op_1.end())
        return false;
    }

    return true;
  }

  virtual std::string to_string() const {
    return "split(" + m_op1->to_string() + "," + m_op2->to_string() + ")";
  };

  virtual std::auto_ptr<operation> transform_against(const operation& trans) const {
    std::auto_ptr<operation> new_op1 = m_op1->transform_against(trans);
    std::auto_ptr<operation> new_op2 = m_op2->transform_against(trans);
    return unsplit(new_op1, new_op2);
  }

protected:
  virtual std::auto_ptr<operation> transform_insert(const insert_operation& ins) const {
    std::auto_ptr<operation> tmp = m_op1->transform_insert(ins);
    std::auto_ptr<operation> new_op2 = m_op2->transform_against(*m_op1);
    return tmp->transform_against(*new_op2);
    //return new_op2->transform_insert(*tmp);
  }

  virtual std::auto_ptr<operation> transform_delete(const delete_operation& del) const {
    std::auto_ptr<operation> tmp = m_op1->transform_delete(del);
    std::auto_ptr<operation> new_op2 = m_op2->transform_against(*m_op1);
    return tmp->transform_against(*new_op2);
    //return new_op2->transform_delete(tmp);
  }
};

std::auto_ptr<operation> operation::from_string(const std::string& str, const std::string& doc)
{
  std::string::size_type pos = str.find('(');
  if(pos == std::string::npos) throw std::runtime_error("'(' not found");

  if(str.substr(0, pos) == "ins")
  {
    std::string::size_type start = pos + 1;
    pos = str.find(',', start);
    if(pos == std::string::npos) throw std::runtime_error("',' not found");
    unsigned int ins_pos = strtoul(str.substr(start, pos - start).c_str(), NULL, 10);
    start = pos + 1;
    pos = str.find(')', start);
    if(pos == std::string::npos) throw std::runtime_error("')' not found");
    return std::auto_ptr<operation>(new insert_operation(ins_pos, str.substr(start, pos - start)));
  }
  else if(str.substr(0, pos) == "del")
  {
    std::string::size_type start = pos + 1;
    pos = str.find(',', start);
    if(pos == std::string::npos) throw std::runtime_error("',' not found");
    unsigned int del_pos = strtoul(str.substr(start, pos - start).c_str(), NULL, 10);
    start = pos + 1;
    pos = str.find(')', start);
    if(pos == std::string::npos) throw std::runtime_error("')' not found");
    unsigned int del_len = strtoul(str.substr(start, pos - start).c_str(), NULL, 10);
    if(doc.length() < del_pos + del_len) throw std::runtime_error("Invalid delete range");
#ifdef LOWER_TRANSFER
    return std::auto_ptr<operation>(new delete_operation(del_pos, del_len, delete_operation::recon_type(), 0));
#else
    return std::auto_ptr<operation>(new delete_operation(del_pos, doc.substr(del_pos, del_len)));
#endif
  }
  else
  {
    throw std::runtime_error(str.substr(0, pos) + " is not a supported operation");
  }
}

bool insert_operation::operator==(const operation& other) const
{
  const split_operation* split_other = dynamic_cast<const split_operation*>(&other);
  if(split_other != NULL) return *split_other == *this;
  const insert_operation* ins_other = dynamic_cast<const insert_operation*>(&other);
  return (ins_other != NULL && m_pos == ins_other->m_pos && m_text == ins_other->m_text && pw().origin() == ins_other->pw().origin() && pw().current() == ins_other->pw().current());
}

bool delete_operation::operator==(const operation& other) const
{
  const split_operation* split_other = dynamic_cast<const split_operation*>(&other);
  if(split_other != NULL) return *split_other == *this;

  const delete_operation* del_other = dynamic_cast<const delete_operation*>(&other);
  if(del_other == NULL) return false;

  if(m_pos != del_other->m_pos) return false;
  if(m_len != del_other->m_len) return false;
  if(!lowered() && !del_other->lowered() && m_text != del_other->m_text) return false;
  return true;
}

bool no_operation::operator==(const operation& other) const
{
  const split_operation* split_other = dynamic_cast<const split_operation*>(&other);
  if(split_other != NULL) return *split_other == *this;

  const no_operation* no_other = dynamic_cast<const no_operation*>(&other);
  return (no_other != NULL);
}

std::auto_ptr<operation> insert_operation::inverse() const
{
  return std::auto_ptr<operation>(new delete_operation(m_pos, m_text));
}

std::auto_ptr<operation> delete_operation::inverse() const
{
  if(lowered()) { throw std::runtime_error("Cannot inverse lowered delete operation"); }
  return std::auto_ptr<operation>(new insert_operation(m_pos, m_text));
}

std::auto_ptr<operation> insert_operation::transform_insert(const insert_operation& ins) const
{
  const pword_type a1 = ins.pw();
  const pword_type a2 = pw();

  // Comparing simply positions does not satisfy C2
//  const unsigned int a1 = ins.m_pos;
//  const unsigned int a2 = m_pos;

  if(a1 < a2 || (a1 == a2 && m_text < ins.m_text))
    return ins.clone();
  else if(a1 > a2 || (a1 == a2 && m_text > ins.m_text))
    return std::auto_ptr<operation>(new insert_operation(ins.m_pos + m_text.length(), ins.m_text, pword_type(ins.m_pword, ins.m_pos)));
  else
    return ins.clone();
}

std::auto_ptr<operation> insert_operation::transform_delete(const delete_operation& del) const
{
  if(m_pos >= del.m_pos + del.m_len)
    return del.clone();
  else if(m_pos <= del.m_pos)
  {
    if(del.lowered())
      return std::auto_ptr<operation>(new delete_operation(del.m_pos + m_text.length(), del.m_len, del.m_recon, del.m_offset));
    else
      return std::auto_ptr<operation>(new delete_operation(del.m_pos + m_text.length(), del.m_text));
  }
  else
  {
/*    assert(false);
    FILE* f = fopen("foo.txt", "a");
    fprintf(f, "%u %u\n", del.m_pos, (del.lowered() ? del.m_len : del.m_text.length()));
    fclose(f);*/

    if(del.lowered())
    {
      // Split recon list
      delete_operation::recon_type first_recon;
      delete_operation::recon_type second_recon;

      unsigned int split_pos = m_pos - del.m_pos;
      unsigned int cur_len = 0;

      for(delete_operation::recon_type::const_iterator iter = del.m_recon.begin(); iter != del.m_recon.end(); ++ iter)
      {
        if(iter->first - cur_len <= split_pos)
	{
	  first_recon.push_back(std::make_pair(iter->first, iter->second));
	  cur_len += iter->second.length();
	}
	else
	{
	  second_recon.push_back(std::make_pair(iter->first - (split_pos + cur_len), iter->second));
	}
      }

      return std::auto_ptr<operation>(new split_operation(
        std::auto_ptr<operation>(new delete_operation(del.m_pos, m_pos - del.m_pos, first_recon, del.m_offset)),
        std::auto_ptr<operation>(new delete_operation(m_pos + m_text.length(), del.m_len + del.m_pos - m_pos, second_recon, del.m_offset + split_pos + cur_len))
      ));
    }
    else
      return std::auto_ptr<operation>(new split_operation(
        std::auto_ptr<operation>(new delete_operation(del.m_pos, del.m_text.substr(0, m_pos - del.m_pos))),
        std::auto_ptr<operation>(new delete_operation(m_pos + m_text.length(), del.m_text.substr(m_pos - del.m_pos)))
      ));
  }
}

std::auto_ptr<operation> delete_operation::transform_insert(const insert_operation& ins) const
{
  if(ins.m_pos >= m_pos + m_len)
    return std::auto_ptr<operation>(new insert_operation(ins.m_pos - m_len, ins.m_text, insert_operation::pword_type(ins.m_pword, ins.m_pos)));
  else if(ins.m_pos < m_pos)
    return std::auto_ptr<operation>(ins.clone());
  else
    return std::auto_ptr<operation>(new insert_operation(m_pos, ins.m_text, insert_operation::pword_type(ins.m_pword, ins.m_pos)));
}

std::auto_ptr<operation> delete_operation::transform_delete(const delete_operation& del) const
{
  if(del.m_pos + del.m_len <= m_pos)
    return del.clone();
  else if(del.m_pos >= m_pos + m_len)
  {
    if(del.lowered())
      return std::auto_ptr<operation>(new delete_operation(del.m_pos - m_len, del.m_len, del.m_recon, del.m_offset));
    else
      return std::auto_ptr<operation>(new delete_operation(del.m_pos - m_len, del.m_text));
  }
  else if(m_pos <= del.m_pos && m_pos + m_len >= del.m_pos + del.m_len)
  {
    if(del.lowered())
    {
      if(lowered()) // This is only required for c1 and c2 verification, not needed for adopted
      {
        return std::auto_ptr<operation>(new no_operation());
      }
      else // Keep recon info
      {
        delete_operation::recon_type recon(del.m_recon);
        recon = delete_operation::transfer_to_recon(recon, 0, m_text.substr(del.m_pos - m_pos, del.m_len));
        return std::auto_ptr<operation>(new no_operation(delete_operation::recon_to_text(recon), m_offset));
      }
    }
    else
      return std::auto_ptr<operation>(new no_operation());
  }
  else if(m_pos <= del.m_pos && m_pos + m_len < del.m_pos + del.m_len)
  {
    if(del.lowered())
    {
      if(lowered()) // This is only required for c1 and c2 verification, not needed for adopted
      {
        return std::auto_ptr<operation>(new delete_operation(m_pos, del.m_len - (m_pos + m_len - del.m_pos), recon_type(), 0));
      }
      else // Keep recon info
      {
        // Initial recon
        delete_operation::recon_type recon(del.m_recon);
        // Add recon from self
        recon = delete_operation::transfer_to_recon(recon, 0, m_text.substr(del.m_pos - m_pos));
        // Recon done
        return std::auto_ptr<operation>(new delete_operation(m_pos, del.m_len - (m_pos + m_len - del.m_pos), recon, del.m_offset));
      }
    }
    else
      return std::auto_ptr<operation>(new delete_operation(m_pos, del.m_text.substr(m_pos + m_len - del.m_pos)));
  }
  else if(m_pos > del.m_pos && m_pos + m_len >= del.m_pos + del.m_len)
  {
    if(del.lowered())
    {
      if(lowered()) // This is only required for c1 and c2 verification, not needed for adopted
      {
        return std::auto_ptr<operation>(new delete_operation(del.m_pos, m_pos - del.m_pos, recon_type(), 0));
      }
      else // Keep recon info
      {
        // Initial recon
        delete_operation::recon_type recon(del.m_recon);
        // Add recon from self
        recon = delete_operation::transfer_to_recon(recon, m_pos - del.m_pos, m_text.substr(0, del.m_pos + del.m_len - m_pos));
        // Recon done
        return std::auto_ptr<operation>(new delete_operation(del.m_pos, m_pos - del.m_pos, recon, del.m_offset));
      }
    }
    else
      return std::auto_ptr<operation>(new delete_operation(del.m_pos, del.m_text.substr(0, m_pos - del.m_pos)));
  }
  else
  {
    if(del.lowered())
    {
      if(lowered()) // This is only required for c1 and c2 verification, not needed for adopted
      {
        return std::auto_ptr<operation>(new delete_operation(del.m_pos, m_pos - del.m_pos + del.m_len - (m_pos + m_len - del.m_pos), recon_type(), 0));
      }
      else // Keep recon info
      {
        // Initial recon
        delete_operation::recon_type recon(del.m_recon);
        // Add recon from self
        recon = delete_operation::transfer_to_recon(recon, m_pos - del.m_pos, m_text);
        // Recon done
        return std::auto_ptr<operation>(new delete_operation(del.m_pos, m_pos - del.m_pos + del.m_len - (m_pos + m_len - del.m_pos), recon, del.m_offset));
      }
    }
    else
      return std::auto_ptr<operation>(new delete_operation(del.m_pos, del.m_text.substr(0, m_pos - del.m_pos) + del.m_text.substr(m_pos + m_len - del.m_pos)));
  }
}

std::auto_ptr<operation> T(const operation& op1, const operation& op2)
{
  return op1.transform_against(op2);
}

std::auto_ptr<operation> T(const operation& op1, const operation& op2, const operation& op3)
{
  return T(*T(op1, op2), op3);
}

const std::string EXAMPLE_DOCUMENT = "abcdefghijklmnopqrstuvwxyz1234567890";

void verify_c1(const operation& op1, const operation& op2)
{
  std::string first = EXAMPLE_DOCUMENT;
  std::string second = EXAMPLE_DOCUMENT;

  op1.apply(first);
  T(op2, op1)->apply(first);

  op2.apply(second);
  T(op1, op2)->apply(second);

  if(first != second)
  {
    throw std::runtime_error(
      "Operations " + op1.to_string() + " and " + op2.to_string() + " do not satisfy C1 on \"" + EXAMPLE_DOCUMENT + "\".\n[" + op1.to_string() + ";T(" + op2.to_string() + "," + op1.to_string() + ") = " + T(op2, op1)->to_string() + "] yields " + first + "\n[" + op2.to_string() + ";T(" + op1.to_string() + "," + op2.to_string() + ") = " + T(op1, op2)->to_string() + "] yields " + second
    );
  }
}

void verify_c2(const operation& op1, const operation& op2, const operation& op3)
{
  if(!(*T(op3, op1, *T(op2, op1)) == *T(op3, op2, *T(op1, op2))))
  {
    throw std::runtime_error(
      "Operations " + op1.to_string() + ", " + op2.to_string() + " and " + op3.to_string() + " do not satisfy C2\nT(" + op3.to_string() + "," + op1.to_string() + ", T(" + op2.to_string() + "," + op1.to_string() + ") = " + T(op2,op1)->to_string() + ") = " + T(op3, op1, *T(op2, op1))->to_string() + "\nT(" + op3.to_string() + "," + op2.to_string() + ", T(" + op1.to_string() + "," + op2.to_string() + ") = " + T(op1,op2)->to_string() + ") = " + T(op3, op2, *T(op1, op2))->to_string());
  }
}

template<typename InputIterator>
void test_c1(InputIterator begin, InputIterator end)
{
  for(InputIterator _1 = begin; _1 != end; ++ _1)
  {
    for(InputIterator _2 = begin; _2 != end; ++ _2)
    {
      try
      {
        std::auto_ptr<operation> op1 = operation::from_string(*_1, EXAMPLE_DOCUMENT);
        std::auto_ptr<operation> op2 = operation::from_string(*_2, EXAMPLE_DOCUMENT);
        verify_c1(*op1, *op2);
      }
      catch(std::runtime_error& e)
      {
        std::cerr << e.what() << std::endl;
      }
    }
  }
}

template<typename InputIterator>
void test_c2(InputIterator begin, InputIterator end)
{
  for(InputIterator _1 = begin; _1 != end; ++ _1)
  {
    for(InputIterator _2 = begin; _2 != end; ++ _2)
    {
      for(InputIterator _3 = begin; _3 != end; ++ _3)
      {
        try
        {
          std::auto_ptr<operation> op1 = operation::from_string(*_1, EXAMPLE_DOCUMENT);
          std::auto_ptr<operation> op2 = operation::from_string(*_2, EXAMPLE_DOCUMENT);
          std::auto_ptr<operation> op3 = operation::from_string(*_3, EXAMPLE_DOCUMENT);
          verify_c2(*op1, *op2, *op3);
        }
        catch(std::runtime_error& e)
        {
          std::cerr << e.what() << std::endl;
        }
      }
    }
  }
}

/* adOPTed implementation */

template<unsigned int N>
class basic_state_vector {
public:
  struct strict_weak {
    bool operator()(const basic_state_vector<N>& n1, const basic_state_vector<N>& n2) {
      for(unsigned int i = 0; i < N; ++ i) {
        if(n1[i] < n2[i])
          return true;
        if(n1[i] > n2[i])
          return false;
      }
      return false;
    }
  };

  basic_state_vector() { for(unsigned int i = 0; i < N; ++ i) m_n[i] = 0; }
  basic_state_vector(const basic_state_vector& other) {
    for(unsigned int i = 0; i < N; ++ i) m_n[i] = other.m_n[i];
  }

  unsigned int operator[](unsigned int i) const { assert(i < N); return m_n[i]; }

  basic_state_vector<N> dec(unsigned int i, unsigned int by) const { assert(i < N); assert(m_n[i] >= by); basic_state_vector<N> v = *this; v.m_n[i] -= by; return v; }
  basic_state_vector<N> inc(unsigned int i, unsigned int by) const { assert(i < N); basic_state_vector<N> v = *this; v.m_n[i] += by; return v; }

  // TODO: Deprecate
  void decr(unsigned int i, unsigned int by = 1) { assert(i < N); assert(m_n[i] >= by); m_n[i] -= by; }
  void incr(unsigned int i, unsigned int by = 1) { assert(i < N); m_n[i] += by; }

  bool operator==(const basic_state_vector<N>& other) const {
    for(unsigned int i = 0; i < N; ++ i)
      if(m_n[i] != other.m_n[i])
        return false;
    return true;
  }

  bool operator<=(const basic_state_vector<N>& other) const {
    for(unsigned int i = 0; i < N; ++ i)
      if(m_n[i] > other.m_n[i])
        return false;
    return true;
  }

private:
  unsigned int m_n[N];
};

template<unsigned int N>
std::ostream& operator<<(std::ostream& out, const basic_state_vector<N>& v)
{
  out << "[";
  for(unsigned int i = 0; i < N; ++ i)
  {
    if(i != 0)
      out << ", ";
    out << v[i];
  }
  out << "]";
  return out;
}

typedef basic_state_vector<USER_COUNT> state_vector;

class request {
public:
  enum rtype {
    DO,
    UNDO,
    REDO
  };

private:
  std::auto_ptr<operation> m_op;
  state_vector m_v;
  unsigned int m_user;

  rtype m_type;
public:
  request(std::auto_ptr<operation> op, const state_vector& v, unsigned int user):
    m_op(op), m_v(v), m_user(user), m_type(DO) {}

  // This generates a so-called pseudo-request. A pseudo request is a request
  // that does not carry an operation with it. This is used for undo requests
  // that do not carry the operation to undo because each client calculates
  // the undo operation for itself.
  request(const state_vector& v, unsigned int user, rtype type):
    m_op(NULL), m_v(v), m_user(user), m_type(type) {assert(type != DO);}
  request(const request& req):
    m_op((req.m_op.get() != NULL) ? req.m_op->clone() : std::auto_ptr<operation>(NULL)), m_v(req.m_v), m_user(req.m_user), m_type(req.m_type) {}

  const operation& op() const { assert(m_op.get() != NULL); return *m_op; }
  const state_vector& v() const { return m_v; }
  state_vector w() const { return m_v.inc(m_user, 1); }
  unsigned int user() const { return m_user; }
  rtype type() const { return m_type; }
};

class adopted {
private:
  typedef std::vector<std::vector<request*> > log_type;
  typedef std::set<request*> queue_type;
  typedef std::list<request*> timeline_type; 

  std::string m_state;
  log_type m_log;
  queue_type m_queue;
  state_vector m_v;
  const unsigned int m_user;

public:
  adopted(unsigned int user, const std::string& initial): m_state(initial), m_log(USER_COUNT), m_user(user) {}

  adopted(const adopted& other):
    m_state(other.m_state), m_log(USER_COUNT), m_v(other.m_v), m_user(other.m_user)
  {
    assert(other.m_queue.empty());
    for(unsigned int i = 0; i < USER_COUNT; ++ i)
    {
      for(std::vector<request*>::const_iterator iter = other.m_log[i].begin(); iter != other.m_log[i].end(); ++ iter)
        m_log[i].push_back(new request(**iter));
    }
  }

  ~adopted()
  {
    for(log_type::iterator iter1 = m_log.begin(); iter1 != m_log.end(); ++ iter1)
    {
      for(std::vector<request*>::iterator iter2 = iter1->begin(); iter2 != iter1->end(); ++ iter2)
        delete *iter2;
    }
  }

  const state_vector& v() const { return m_v; }

  const std::string& state() { return m_state; }

  request* generate_request(std::auto_ptr<operation> op) {
    request* req = new request(op, m_v, m_user);
    m_queue.insert(req);
    return req;
  }

  request* generate_undo() {
    request* req = new request(m_v, m_user, request::UNDO);
    m_queue.insert(req);
    return req;
  }

  request* generate_redo() {
    request* req = new request(m_v, m_user, request::REDO);
    m_queue.insert(req);
    return req;
  }

  void receive_request(const request& req) {
    request* req_copy = new request(req);
    m_queue.insert(req_copy);
  }

  bool queue_empty() const { return m_queue.empty(); }

  bool execute_request()
  {
    for(std::set<request*>::iterator iter = m_queue.begin(); iter != m_queue.end(); ++ iter)
    {
      request* req = *iter;
      if(executable(*req, m_v))
      {
        m_queue.erase(iter);
	// TODO: Clear req if the following throws

        // Lower if not already
	std::auto_ptr<request> lowered;
	if(req->type() != request::DO || req->op().lowered())
	  lowered.reset(new request(*req));
	else
	  lowered.reset(new request(req->op().lower(), req->v(), req->user()));

        // Note lowered->op().lower() does not necessarily return TRUE now 
	// because the operation might not be lowerable (e.g. insert operations)

        // Translate
        std::auto_ptr<request> translated = translate_request(*lowered, m_v);

        // Restore if we lowered
        std::auto_ptr<request> restored;
        if(lowered->type() != request::DO || !lowered->op().lowered())
	  restored.reset(new request(*lowered));
	else
	  restored.reset(new request(translated->op().restore(lowered->op(), m_state), req->v(), req->user()));

	// Note: In a real environment, req is not available
	if(req->type() == request::DO && !req->op().lowered())
	  assert(restored->op() == req->op());

        translated->op().apply(m_state);
        m_v = m_v.inc(translated->user(), 1);
        m_log[req->user()].push_back(restored.release());
        return true;
      }
    }

    return false;
  }

  std::auto_ptr<request> translate_request(const request& r, const state_vector& to)
  {
    assert(to <= m_v);
    assert(original_request(r).v() <= to);
    assert(reachable(to));

    if(r.type() != request::DO)
    {
      const request& associated = associated_request(r);

      state_vector v = to.dec(r.user(), to[r.user()] - associated.v()[r.user()]);

      if(reachable(v))
        return mirror(*translate_request(associated, v), to[r.user()] - associated.v()[r.user()]);
    }
    else
    {
      if(r.v() == to)
        return std::auto_ptr<request>(new request(r));
    }

    // Fold first
    for(unsigned int i = 0; i < USER_COUNT; ++ i)
    {
      if(i == r.user()) continue;
      if(to[i] == 0) continue;
      //if(original_request(r).v()[i] >= to[i]) continue;

      const request& prev = nth_request(i, to[i] - 1);
      if(prev.type() != request::DO)
      {
        const request& begin = associated_request(prev);
        state_vector v = to.dec(i, to[i] - begin.v()[i]);

        if(reachable(v) && r.v() <= v)
          return fold(*translate_request(r, v), i, to[i] - begin.v()[i]);
      }
    }

    // Prefer transforming into directions we are not going to fold later
    for(unsigned int i = 0; i < USER_COUNT; ++ i)
    {
      if(i == r.user()) continue;
      if(to[i] == 0) continue;
      if(original_request(r).v()[i] >= to[i]) continue;

      state_vector v = to.dec(i, 1);
      const request& prev = nth_request(i, to[i] - 1);

      if(prev.type() == request::DO && reachable(v))
      {
        const request& against = nth_request(i, v[i]);
        return transform(*translate_request(r, v), *translate_request(against, v));
      }
    }

    // Default transform
    for(unsigned int i = 0; i < USER_COUNT; ++ i)
    {
      if(i == r.user()) continue;
      if(to[i] == 0) continue;
      if(original_request(r).v()[i] >= to[i]) continue;

      state_vector v = to.dec(i, 1);
      if(reachable(v))
      {
        const request& against = nth_request(i, v[i]);
        return transform(*translate_request(r, v), *translate_request(against, v));
      }
    }

    throw std::runtime_error("adopted::translate_request: Did not find a transformation path");
  }

  std::auto_ptr<request> transform(const request& req1, const request& req2) {
    assert(req1.v() == req2.v());

    return std::auto_ptr<request>(new request(
      req1.op().transform_against(req2.op()),
      req1.v().inc(req2.user(), 1),
      req1.user()
    ));
  }

  bool executable(const request& r, const state_vector& v) {
    return r.v() <= v;
  }

  bool reachable_i(const state_vector& v, unsigned int i)
  {
    state_vector w = v;
    for(;;)
    {
      if(w[i] == 0) return true;

      const request& r = nth_request(i, w[i] - 1);
      if(r.type() == request::DO)
        return r.w() <= v;
      else
        w = associated_request(r).v();
    }
  }

  bool reachable(const state_vector& v)
  {
    assert(v <= m_v);
    for(unsigned int i = 0; i < USER_COUNT; ++ i)
      if(!reachable_i(v, i))
        return false;
    return true;
  }

  const request& nth_request(unsigned int user, unsigned int num) {
    assert(user < USER_COUNT);
    assert(num < m_log[user].size());
    return *m_log[user][num];
  }

  const request& original_request(const request& req)
  {
    switch(req.type())
    {
    case request::DO:
      return req;
    case request::UNDO:
    case request::REDO:
      return original_request(associated_request(req));
    default:
      assert(false);
    }
  }

  const request& associated_request(const request& to)
  {
    unsigned int ucount = 1;
    assert(to.type() != request::DO);

    for(unsigned int i = to.v()[to.user()]; i > 0; -- i)
    {
      const request& r = nth_request(to.user(), i - 1);

      // There cannot be a DO request between a undo/redo pair
      if(to.type() == request::REDO)
        assert(r.type() != request::DO);

      if(r.type() == to.type())
        ++ ucount;
      else
        -- ucount;

      if(ucount == 0)
      {
        -- i;
        assert( (to.v()[to.user()] - 1 - i)%2 == 0);
        assert(nth_request(to.user(), i).type() != to.type());
        return nth_request(to.user(), i);
      }
    }

    assert(false);
  }

  // By is the amount of operations between the original and the mirrored
  // operation.
  std::auto_ptr<request> mirror(const request& r, unsigned int by)
  {
    assert(by%2 == 1);
    if(r.v()[r.user()] + by < m_log[r.user()].size())
    {
      assert(associated_request(nth_request(r.user(), r.v()[r.user()] + by)).v()[r.user()] == r.v()[r.user()]);
    }

    state_vector v = r.v().inc(r.user(), by);
    return std::auto_ptr<request>(new request(r.op().inverse(), v, r.user()));
  }

  std::auto_ptr<request> fold(const request& r, unsigned int over, unsigned int by)
  {
    assert(by % 2 == 0);
    assert(associated_request(nth_request(over, r.v()[over] + by - 1)).v()[over] == r.v()[over]);

    state_vector v = r.v().inc(over, by);
    return std::auto_ptr<request>(new request(r.op().clone(), v, r.user()));
  }
};

/* adOPTed test routines */

enum request_type {
  OPERATION,
  SYNC,
  UNDO,
  REDO
};

struct request_test_component {
  request_type type;
  unsigned int user;

  union {
    const char* op;
    unsigned int from;
  };
};

/* Lets the given user perform the given operation */
request_test_component mkop(unsigned int user, const char* op) {
  if(user >= USER_COUNT)
    throw std::runtime_error("Invalid user");

  request_test_component test;
  test.type = OPERATION;
  test.user = user;
  test.op = op;
  return test;
}

/* Syncs all operations so that all operation queues are empty */
request_test_component mksync() {
  request_test_component test;
  test.type = SYNC;
  test.user = USER_COUNT;
  test.from = USER_COUNT;
  return test;
}

request_test_component mkundo(unsigned int user) {
  if(user >= USER_COUNT)
    throw std::runtime_error("Invalid user");

  request_test_component test;
  test.type = UNDO;
  test.user = user;
  return test;
}

request_test_component mkredo(unsigned int user) {
  if(user >= USER_COUNT)
    throw std::runtime_error("Invalid user");

  request_test_component test;
  test.type = REDO;
  test.user = user;
  return test;
}

class request_test {
protected:
  typedef std::vector<request_test_component> component_type;
  component_type m_components;
  std::string m_initial;

public:
  typedef component_type::const_iterator iterator;

  request_test(const std::string& initial): m_initial(initial) {}
  request_test(const request_test& other): m_components(other.m_components), m_initial(other.m_initial) {}

  template<typename InputIterator>
  request_test(const std::string& initial, InputIterator begin, InputIterator end): m_components(begin, end), m_initial(initial) {}

  request_test& operator<<(const request_test_component& comp) {
    m_components.push_back(comp);
    return *this;
  }

  const std::string& initial() const { return m_initial; }

  iterator begin() { return m_components.begin(); }
  iterator end() { return m_components.end(); }
};

class test_context {
private:
  adopted* m_adopted[USER_COUNT];
  request_test m_test;

public:
  typedef std::pair<unsigned int, unsigned int> test_result;

  test_context(const request_test& req_test):
    m_test(req_test)
  {
    for(unsigned int i = 0; i < USER_COUNT; ++ i)
      m_adopted[i] = new adopted(i, m_test.initial());
  }

  // Fork
  template<typename InputIterator>
  test_context(const test_context& other, InputIterator begin, InputIterator end):
    m_test(other.m_test.initial(), begin, end)
  {
    for(unsigned int i = 0; i < USER_COUNT; ++ i)
      m_adopted[i] = new adopted(*other.m_adopted[i]);
  }

  ~test_context()
  {
    for(unsigned int i = 0; i < USER_COUNT; ++ i)
      delete m_adopted[i];
  }

  test_result execute()
  {
    std::vector<request*> requests;
    test_result total_result(0,0);
    unsigned int sub_num = 0;

    for(request_test::iterator iter = m_test.begin(); iter != m_test.end(); ++ iter)
    {
      const request_test_component& test = *iter;
      switch(test.type)
      {
      case OPERATION:
        {
          std::auto_ptr<operation> op(operation::from_string(test.op, m_adopted[test.user]->state()));
          request* req = m_adopted[test.user]->generate_request(op);
//#ifdef LOWER_TRANSFER
//          requests.push_back(new request(req->op().lower(), req->v(), req->user()));
//#else
          requests.push_back(new request(*req));
//#endif
        }
        break;
      case UNDO:
        {
          request* req = m_adopted[test.user]->generate_undo();
          requests.push_back(new request(*req));
        }
        break;
      case REDO:
        {
          request* req = m_adopted[test.user]->generate_redo();
          requests.push_back(new request(*req));
        }
        break;
      case SYNC:
        {
          test_result result = do_sync(requests, sub_num ++);
          for(std::vector<request*>::iterator iter = requests.begin(); iter != requests.end(); ++ iter)
            delete *iter;
          requests.clear();
          total_result.first += result.first;
          total_result.second += result.second;

	  // No test succeeded, so we cannot continue because the remaining
	  // requests rely on the state being synchronized
	  if(result.first == 0)
	    return total_result;

          break;
        }
      }

      if(test.type != SYNC)
      {
        try {
          bool res = m_adopted[test.user]->execute_request();
	  assert(res == true);
	  assert(m_adopted[test.user]->queue_empty() == true);
        } catch(const std::runtime_error& e) {
          std::cerr << e.what() << std::endl;
          ++ total_result.second;
          return total_result;
        }
      }
    }

    return total_result;
  }

protected:
  // TODO: Perhaps we should make this more C++ish by using iterators
  void permutate_impl(const std::vector<request*> requests, const std::vector<request*> remaining, std::vector<std::vector<request*> >& dest)
  {
    if(remaining.empty())
    {
      dest.push_back(requests);
    }
    else
    {
      std::vector<bool> seen(USER_COUNT, false);
      for(std::vector<request*>::const_iterator iter = remaining.begin(); iter != remaining.end(); ++ iter)
      {
        // Keep request order. This is not necessarly guaranteed in a real-world
        // environment but is trivial to solve by keeping requests back. In
        // this test it would only produce redundant test cases.
        if(seen[(*iter)->user()]) continue;

        seen[(*iter)->user()] = true;
        std::vector<request*> new_remaining(remaining.begin(), iter);
        new_remaining.insert(new_remaining.end(), iter + 1, remaining.end());

        std::vector<request*> new_requests(requests);
        new_requests.push_back(*iter);

        permutate_impl(new_requests, new_remaining, dest);
      }
    }
  }

  // TODO: Perhaps we should make this more C++ish by using iterators
  std::vector<std::vector<request*> > permutate(const std::vector<request*> requests)
  {
    std::vector<std::vector<request*> > result;
    permutate_impl(std::vector<request*>(), requests, result);
    return result;
  }

  // TODO: Perhaps we should make this more C++ish by using iterators
  bool process(const std::vector<request*>& requests)
  {
    for(unsigned int i = 0; i < USER_COUNT; ++ i)
    {
      for(std::vector<request*>::const_iterator iter = requests.begin(); iter != requests.end(); ++ iter)
      {
        const request* req = *iter;
        if(req->user() != i)
        {
          m_adopted[i]->receive_request(*req);
          try {
            while(m_adopted[i]->execute_request() ) ;
          } catch(const std::runtime_error& e) {
            std::cerr << e.what() << std::endl;
            return false;
          }
        }
      }
    }

    return true;
  }

  // TODO: Perhaps we should make this more C++ish by using iterators
  test_result do_sync(const std::vector<request*>& requests, unsigned int sub_num)
  {
    std::vector<std::vector<request*> > permutations(permutate(requests));
    std::vector<std::vector<request*> >::const_iterator working = permutations.end();
    test_result result(0,0);

    for(std::vector<std::vector<request*> >::const_iterator iter = permutations.begin(); iter != permutations.end(); ++ iter)
    {
      for(unsigned int i = 0; i < sub_num; ++ i)
        std::cout << "  ";

      const std::vector<request*> permutation = *iter;
      for(std::vector<request*>::const_iterator iter2 = permutation.begin(); iter2 != permutation.end(); ++ iter2)
      {
        std::cout << (*iter2)->user() << " ";
      }

      std::cout << std::endl;

      test_context sub(*this, m_test.end(), m_test.end());

      ++ result.second;
      if(sub.process(permutation))
      {
        working = iter;
        ++ result.first;
      }
    }

    // Continue with a sequence that worked
    if(working != permutations.end())
      process(*working);
    else
      // TODO: Count the number of subsequent tests that we cannot process
      // now because we don't have a working permutation that is correct
      // up to the current sync
      ;

    return result;
  }
};

template<typename InputIterator>
void test_algo(InputIterator begin, InputIterator end)
{
  unsigned int passed = 0, total = 0;
  for(InputIterator iter = begin; iter != end; ++ iter)
  {
    test_context ctxt(*iter);
    std::pair<unsigned int, unsigned int> result = ctxt.execute();
    passed += result.first;
    total += result.second;
    std::cout << "\n";
  }

  std::cout << passed << " out of " << total << " tests passed" << std::endl;
}

request_test test_seqs[] = {
  request_test("") << mkop(0, "ins(0,a)") << mksync() << mkop(1, "ins(0,b)") << mkop(2, "ins(0,c)") << mkundo(1) << mksync(),
  request_test("") << mkop(0, "ins(0,a)") << mkop(1, "ins(0,b)") << mkundo(0) << mksync() << mkop(2, "ins(0,c)") << mkundo(1) << mkredo(0) << mksync(),
  request_test("") << mkop(2, "ins(0,a)") << mkop(1, "ins(0,b)") << mkundo(2) << mksync() << mkop(0, "ins(0,c)") << mkundo(1) << mkredo(1) << mkundo(0) << mkundo(1) << mkredo(1) << mkredo(0) << mkredo(2) << mksync(),
  request_test("") << mkop(0, "ins(0,a)") << mksync() << mkop(1, "ins(0,b)") << mkundo(0) << mksync() << mkop(2, "ins(0,c)") << mkundo(1) << mksync(),
  request_test("") << mkop(0, "ins(0,a)") << mksync() << mkop(1, "ins(0,b)") << mkop(0, "del(0,1)") << mksync() << mkop(2, "ins(0,c)") << mkundo(0) << mkundo(1) << mksync(),
  request_test("") << mkop(0, "ins(0,a)") << mksync() << mkop(1, "ins(0,b)") << mkundo(1) << mkundo(0) << mkredo(1) << mkredo(0) << mkundo(0) << mksync() << mkop(2, "ins(0,c)") << mkredo(0) << mkundo(1) << mkundo(2) << mksync(),
  request_test("") << mkop(0, "ins(0,a)") << mksync() << mkop(1, "ins(0,b)") << mksync() << mkundo(1) << mkundo(0) << mkredo(1) << mksync(),
  request_test("") << mkop(0, "ins(0,a)") << mkundo(0) << mksync() << mkredo(0) << mksync() << mkundo(0) << mksync() << mkop(2, "ins(0,b)") << mkredo(0) << mkundo(0) << mkredo(0) << mkundo(2) << mkundo(0) << mkredo(2) << mkredo(0) << mksync(),
  request_test("AC") << mkop(0, "del(0,2)") << mkop(1, "ins(1,B)") << mkundo(0) <<  mksync(),
  request_test("ABCDE") << mkop(0, "del(3,2)") << mkop(0, "ins(3,Y)") << mkop(1, "del(0,5)") << mkop(0, "ins(4,Z)") << mksync() << mkundo(1) << mksync() << mkundo(0) << mkundo(0) << mksync() << mkop(1, "ins(1,DEG)") << mksync() << mkundo(0) << mkundo(1) << mksync(),
  request_test("A") << mkop(0, "del(0,1)") << mkop(1, "del(0,1)") << mksync() << mkop(1, "ins(0,B)") << mkundo(0) << mkundo(1) << mkundo(1) << mksync(),
  request_test("") << mkop(0, "ins(0,a)") << mkop(0, "ins(0,b)") << mkundo(0) << mkundo(0) << mksync(),
  request_test("ab") << mkop(0, "del(1,1)") << mkop(0, "del(0,1)") << mkundo(0) << mkundo(0) << mksync(),
  request_test("M") << mkop(0, "ins(1,S)") << mksync() << mkop(1, "ins(1,A)") << mksync() << mkundo(0) << mksync(),
  request_test("") << mkop(0, "ins(0,ABCDE)") << mksync() << mkop(1, "del(2,2)") << mksync() << mkundo(1) << mksync() << mkundo(0) << mksync(),
  request_test("ab") << mkop(0, "del(0,1)") << mksync() << mkop(1, "del(0,1)") << mksync() << mkundo(0) << mksync() << mkundo(1) << mksync(),
  request_test("ab") << mkop(0, "del(0,1)") << mksync() << mkop(1, "ins(0,1)") << mksync() << mkundo(0) << mkundo(1) << mksync(),
  request_test("") << mkop(0, "ins(0,a)") << mkop(1, "ins(0,b)") << mkop(0, "del(0,1)") << mkundo(0) << mkundo(0) << mkundo(1) << mksync(),
  request_test("b") << mkop(0, "del(0,1)") << mkop(1, "del(0,1)") << mkundo(1) << mkundo(0) << mksync(),
  request_test("ab") << mksync() << mkop(0, "del(0,1)") << mkop(1, "del(1,1)") << mksync() << mkundo(0) << mksync() << mkundo(1) << mksync(),
  request_test("") << mkop(0, "ins(0,a)") << mksync() << mkop(0, "ins(0,b)") << mkop(1, "del(0,1)") << mksync() << mkop(1, "del(0,1)") << mksync(),
  request_test("") << mkop(0, "ins(0,a)") << mkop(1, "ins(0,b)") << mksync(),
  request_test("") << mkop(0, "ins(0,a)") << mkop(1, "ins(0,b)") << mkop(2, "ins(0,c)") << mksync(),
  request_test("") << mkop(0, "ins(0,a)") << mkop(1, "ins(0,b)") << mkop(2, "ins(0,c)") << mkop(3, "ins(0,d)") << mksync(),
  request_test("abcdefg") << mkop(0, "del(0,1)") << mkop(0, "del(0,1)") << mkop(0, "del(0,5)") << mkop(1, "ins(4,foo)") << mksync(),
  request_test("abcd") << mkop(1, "del(1,1)") << mkop(0, "ins(4,x)") << mkop(3, "ins(4,x)") << mkop(4, "del(3,1)") << mksync(),
  request_test("") << mkop(0, "ins(0,x)") << mkop(0, "del(0,1)") << mksync() << mkop(1, "ins(0,a)") << mkop(1, "del(0,1)") << mkop(1, "ins(0,a)") << mksync() << mkundo(0) << mkundo(0) << mksync(),
  request_test("") << mkop(0, "ins(0,x)") << mkop(0, "del(0,1)") << mksync() << mkop(1, "ins(0,a)") << mkundo(1) << mkredo(1) << mksync() << mkundo(0) << mkundo(0) << mksync(),
  request_test("a") << mkop(1, "del(0,1)") << mksync() << mkop(0, "ins(0,x)") << mkop(2, "ins(0,z)") << mksync() << mkop(2, "ins(0,a)") << mksync() << mkundo(2) << mksync() << mkop(1, "ins(0,y)") << mksync() << mkundo(2) << mksync() << mkredo(2) << mksync() << mkundo(1) << mksync() << mkredo(1) << mkundo(0) << mksync(),
  request_test("a") << mkop(0, "del(0,1)") << mkop(1, "ins(r,2)") << mkop(1, "ins(m,3)") << mkop(1, "ins(b,4)") << mkop(2, "del(0,1)") << mkop(2,"ins(0,h)") << mkop(2,"ins(1,h)") << mkop(2,"ins(2,h)") << mkundo(1) << mksync(),
  request_test("abcd") << mkop(1, "del(1,1)") << mkop(0, "ins(4,x)") << mkop(3, "ins(4,x)") << mkop(3, "del(2,2)") << mkundo(0) << mksync() << mkredo(0) << mksync() << mkop(1, "ins(3,y)") << mksync() << mkundo(0) << mkundo(3) << mkundo(3) << mkundo(1) << mksync(),
#if 0
  request_test("abcd") << mkop(1, "del(1,1)") << mkop(0, "ins(4,x)") << mkop(3, "ins(4,x)") << mkop(4, "del(3,1)") << mkundo(4) << mkop(3, "del(2,2)") << mkop(2, "ins(1,z)") << mkundo(0) << mkredo(4) << mksync() << mkundo(2) << mksync() << mkredo(0) << mkundo(4) << mkundo(1) << mkredo(4) << mkredo(1) << mkredo(2) << mksync() << mkop(2, "ins(0,a)") << mkundo(2) << mkop(1, "ins(3,y)") << mkundo(2) << mkredo(2) << mkredo(2) << mksync() << mkop(0, "del(0,6)") << mkop(2, "ins(1,g)") << mkundo(2) << mkundo(2) << mksync() << mkundo(1) << mkundo(2) << mkundo(0) << mkredo(1) << mkundo(3) << mkundo(3) <<  mksync() << mkredo(2) << mkredo(3) << mkredo(3) << mkop(3, "del(0,1)") << mkundo(3) << mksync() << mkop(0, "ins(0,tez)") << mkop(1, "ins(2,tar)") << mkundo(3) << mkundo(1) << mkundo(0) << mkredo(3) << mkredo(1) << mkundo(3) << mkundo(3) << mkredo(0) << mksync(), // TODO: This test is really CPU intesive.
#endif
};

std::string test_ops[] = {
  "ins(4,a)",
  "ins(4,b)",
  "ins(4,a)",
  "ins(2,ac)",
  "ins(3,bc)",
  "ins(2,gro)",
  "del(0,1)",
  "del(0,5)",
  "del(2,7)",
  "del(1,9)"
};

int main(int argc, char* argv[])
{
  test_c1(test_ops, test_ops + sizeof(test_ops)/sizeof(test_ops[0]));
  test_c2(test_ops, test_ops + sizeof(test_ops)/sizeof(test_ops[0]));
  test_algo(test_seqs, test_seqs + sizeof(test_seqs)/sizeof(test_seqs[0]));
  return 0;
}