// Please do what you want with this code

#ifndef ADOPTED_HPP
#define ADOPTED_HPP

#include "text.hpp"
#include "cid.hpp"

#include <vector>
#include <list>
#include <set>
#include <deque>
#include <memory>

#include <ostream>
#include <sstream>

#include <cassert>
#include <cstdlib>
#include <stdexcept>

const unsigned int USER_COUNT = 5;

typedef obby::text string_type;

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

using namespace adopted;

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

  virtual void apply(string_type& 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;

  virtual bool need_cid(const operation& other) const = 0;
  virtual cid get_cid(const operation& other) const = 0;

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

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

class insert_operation: public operation
{
  friend class delete_operation;
  friend class remote_delete_operation;
private:
  unsigned int m_pos;
  string_type m_text;
public:
  insert_operation(unsigned int pos, const string_type& text):
    m_pos(pos), m_text(text) {}
  insert_operation(const insert_operation& other):
    m_pos(other.m_pos), m_text(other.m_text) {}

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

  unsigned int pos() const { return m_pos; }
  const string_type& str() const { return m_text; }

  virtual void apply(string_type& 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 << "," << static_cast<const std::string&>(m_text) << ")";
    return stream.str();
  };

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

  virtual bool need_cid(const operation& other) const {
    const insert_operation* insert_other = dynamic_cast<const insert_operation*>(&other);
    if(insert_other && insert_other->m_pos == m_pos)
      return true;
    return false;
  }

  virtual cid get_cid(const operation& other) const {
    const insert_operation* insert_other = dynamic_cast<const insert_operation*>(&other);
    if(insert_other)
    {
      if(insert_other->m_pos < m_pos)
        return cid::self;
      else if(insert_other->m_pos > m_pos)
        return cid::other;
      else
        return cid::none;
    }
/*
    const delete_operation* delete_other = dynamic_cast<const delete_operation*>(&other);
    if(delete_other)
    {
      if(delete_other->m_pos + delete_other->len() <= m_pos)
        return cid::self;
      else if(delete_other->m_pos >= m_pos)
        return cid::other;
      else
        // TODO: (Not yet investigated)
        { assert(false); return cid::none; }
    }

    const remote_delete_operation* remdel_other = dynamic_cast<const remote_delete_operation*>(&other);
    if(remdel_other)
    {
      if(remdel_other->m_pos + remdel_other->len() <= m_pos)
        return cid::self;
      else if(remdel_other->m-pos >= m_pos)
        return cid::other;
      else
        // TODO: (Not yet investigated)
        { assert(false); return cid::none; }
    }*/

    // TODO: Maybe split op (not yet investigated)
    assert(false);
  }

protected:
  virtual std::auto_ptr<operation> transform_insert(const insert_operation& ins, cid cid) const;
  virtual std::auto_ptr<operation> transform_delete(const delete_operation& del, cid cid) const;
  virtual std::auto_ptr<operation> transform_remote(const remote_delete_operation& del, cid cid) const;
};

class delete_operation: public operation
{
  friend class insert_operation;
  friend class no_operation;
  friend class remote_delete_operation;
private:
  unsigned int m_pos;
  string_type m_text;
public:
  delete_operation(unsigned int pos, const string_type& text):
    m_pos(pos), m_text(text) {}
  delete_operation(const delete_operation& other):
    m_pos(other.m_pos), m_text(other.m_text) {}

  unsigned int pos() const { return m_pos; }
  const string_type& str() const { return m_text; }

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

  virtual void apply(string_type& doc) const {
    if(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_text.length());
  }

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

  virtual std::string to_string() const {
    std::stringstream stream;
    stream << "del(" << m_pos << "," << static_cast<const std::string&>(m_text) << ")";

    return stream.str();
  };

  virtual std::auto_ptr<operation> inverse() const;

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

  virtual bool need_cid(const operation& other) const { return false; }

  virtual cid get_cid(const operation& other) const { assert(false); return cid::none; } // TODO: Investigate

protected:
  virtual std::auto_ptr<operation> transform_insert(const insert_operation& ins, cid cid) const;
  virtual std::auto_ptr<operation> transform_delete(const delete_operation& del, cid cid) const;
  virtual std::auto_ptr<operation> transform_remote(const remote_delete_operation& del, cid cid) const;
};

class remote_delete_operation: public operation
{
  friend class insert_operation;
  friend class delete_operation;
private:
  typedef std::list<std::pair<unsigned int, string_type> > recon_type;

  unsigned int m_pos;
  unsigned int m_len;

  recon_type m_recon;
  unsigned int m_offset;

  static recon_type transfer_to_recon(const recon_type& recon, unsigned int pos, const string_type& 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;
  }

  virtual bool need_cid(const operation& other) const { return false; }

  virtual cid get_cid(const operation& other) const { assert(false); return cid::none; } // TODO: Investigate

public:
  remote_delete_operation(unsigned int pos, unsigned int len):
    m_pos(pos), m_len(len), m_offset(0) {}
  remote_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) {}
  remote_delete_operation(const remote_delete_operation& other):
    m_pos(other.m_pos), m_len(other.m_len), m_recon(other.m_recon), m_offset(other.m_offset) {}

  unsigned int pos() const { return m_pos; }
  unsigned int len() const { return m_len; }

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

  virtual void apply(string_type& doc) const {
    doc.erase(m_pos, m_len);
  }

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

  virtual std::string to_string() const {
    std::stringstream stream;
    stream << "rdel(" << m_pos << "," << m_len << ")";

    return stream.str();
  };

  virtual std::auto_ptr<operation> inverse() const { throw std::runtime_error("Cannot inverse remote delete operation"); }

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

  std::auto_ptr<operation> make_reversible(const operation& with, const string_type& doc) const;

protected:
  virtual std::auto_ptr<operation> transform_insert(const insert_operation& ins, cid cid) const;
  virtual std::auto_ptr<operation> transform_delete(const delete_operation& del, cid cid) const;
  virtual std::auto_ptr<operation> transform_remote(const remote_delete_operation& del, cid cid) const;
};

class no_operation: public operation
{
private:

public:
  no_operation() {}
  no_operation(const no_operation& other) {}

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

  virtual void apply(string_type& doc) const {}
  virtual std::auto_ptr<operation> inverse() const {
    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, cid cid) const {
    return clone();
  }

  virtual bool need_cid(const operation& other) const { return false; }

  virtual cid get_cid(const operation& other) const { assert(false); return cid::none; } // TODO: Investigate
protected:
  virtual std::auto_ptr<operation> transform_insert(const insert_operation& ins, cid cid) const {
    return ins.clone();
  }

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

class split_operation: public operation
{
  friend class remote_delete_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 void apply(string_type& doc) const {
    std::auto_ptr<operation> new_op2 = m_op2->transform_against(*m_op1, cid::none);
    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, cid::none);
    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);

    typedef std::vector<const operation*> intermediate_container;

    // split_ops are also equal if the contained operations
    // are in different order
    intermediate_container op_1;
    intermediate_container op_2;

    std::insert_iterator<intermediate_container> insert_iter(op_1, op_1.begin());
    strip(insert_iter);

    if(split_other)
    {
      std::insert_iterator<intermediate_container> ii(op_2, op_2.begin());
      split_other->strip(ii);
    }
    else
      op_2.push_back(&other);

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

      intermediate_container::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(intermediate_container::iterator iter_2 = op_2.begin(); iter_2 != op_2.end(); ++ iter_2)
    {
      if(dynamic_cast<const no_operation*>(*iter_2) != NULL) continue;

      intermediate_container::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, cid cid) const {
    std::auto_ptr<operation> new_op1 = m_op1->transform_against(trans, cid);
    std::auto_ptr<operation> new_op2 = m_op2->transform_against(trans, cid);
    return unsplit(new_op1, new_op2);
  }

  virtual bool need_cid(const operation& other) const { return false; }

  virtual cid get_cid(const operation& other) const { assert(false); return cid::none; } // TODO: Investigate
protected:
  virtual std::auto_ptr<operation> transform_insert(const insert_operation& ins, cid cid) const {
    std::auto_ptr<operation> tmp = m_op1->transform_insert(ins, cid);
    std::auto_ptr<operation> new_op2 = m_op2->transform_against(*m_op1, cid::none);
    return tmp->transform_against(*new_op2, -cid);
  }

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

  virtual std::auto_ptr<operation> transform_remote(const remote_delete_operation& del, cid cid) const {
    std::auto_ptr<operation> tmp = m_op1->transform_remote(del, cid);
    std::auto_ptr<operation> new_op2 = m_op2->transform_against(*m_op1, cid::none);
    return tmp->transform_against(*new_op2, -cid);
  }
};

inline std::auto_ptr<operation>
operation::from_string(const std::string& str, unsigned int user)
{
  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");

    string_type text(str.substr(start, pos - start), user);
    return std::auto_ptr<operation>(new insert_operation(ins_pos, text));
  }
  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);
    return std::auto_ptr<operation>(new remote_delete_operation(del_pos, del_len));
  }
  else
  {
    throw std::runtime_error(str.substr(0, pos) + " is not a supported operation");
  }
}

inline std::auto_ptr<operation> remote_delete_operation::make_reversible(const operation& with, const string_type& doc) const
{
  const split_operation* split_with;
  string_type chunk;
  unsigned int offset = 0;
  
  typedef std::list<const operation*> op_list_type;
  op_list_type list;

  split_with = dynamic_cast<const split_operation*>(&with);

  if(split_with != NULL)
  {
    std::insert_iterator<op_list_type> insert_iter(list, list.begin());
    split_with->strip(insert_iter);
  }
  else
  {
    list.push_back(&with);
  }

  /* We assume the list of remote delete operations to be in order */
  for(op_list_type::const_iterator iter = list.begin(); iter != list.end(); ++ iter)
  {
    const remote_delete_operation* del_with = dynamic_cast<const remote_delete_operation*>(*iter);
    assert(del_with != NULL);

    recon_type recon;
    if(del_with->m_len > 0)
    {
      recon = transfer_to_recon(del_with->m_recon, 0, doc.substr(del_with->m_pos, del_with->m_len));
    }
    else
    {
      recon = del_with->m_recon;
    }

    for(recon_type::const_iterator iter = recon.begin(); iter != recon.end(); ++ iter)
    {
      assert(del_with->m_offset + iter->first == chunk.length());
      chunk.append(iter->second);
    }
  }

  return std::auto_ptr<operation>(new delete_operation(m_pos, chunk));
}

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

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

inline 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);
}

inline 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_text != del_other->m_text) return false;
  return true;
}

inline bool remote_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 remote_delete_operation* del_other = dynamic_cast<const remote_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;
  return true;
}

inline 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);
}

inline std::auto_ptr<operation> insert_operation::transform_insert(const insert_operation& ins, cid cid) const
{
  const unsigned int a1 = ins.m_pos;
  const unsigned int a2 = m_pos;

  // Note: ins is other, *this is self (cid gets swapped if ins calls into this method)
  if(a1 < a2 || (a1 == a2 && cid == cid::self))
    return ins.clone();
  else if((a1 > a2 || (a1 == a2 && cid == cid::other)))
    return std::auto_ptr<operation>(new insert_operation(ins.m_pos + m_text.length(), ins.m_text));
  else
    throw std::runtime_error("insert_operation::transform_insert: a1 == a2 and cid=none");
}

inline std::auto_ptr<operation> insert_operation::transform_delete(const delete_operation& del, cid cid) const
{
  if(m_pos >= del.m_pos + del.m_text.length())
    return del.clone();
  else if(m_pos <= del.m_pos)
      return std::auto_ptr<operation>(new delete_operation(del.m_pos + m_text.length(), del.m_text));
  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)))
    ));
}

inline std::auto_ptr<operation> insert_operation::transform_remote(const remote_delete_operation& del, cid cid) const
{
  if(m_pos >= del.m_pos + del.m_len)
    return del.clone();
  else if(m_pos <= del.m_pos)
    return std::auto_ptr<operation>(new remote_delete_operation(del.m_pos + m_text.length(), del.m_len, del.m_recon, del.m_offset));
  else
  {
    // Split recon and op
    remote_delete_operation::recon_type first_recon;
    remote_delete_operation::recon_type second_recon;

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

    for(remote_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 remote_delete_operation(del.m_pos, m_pos - del.m_pos, first_recon, del.m_offset)),
      std::auto_ptr<operation>(new remote_delete_operation(m_pos + m_text.length(), del.m_len + del.m_pos - m_pos, second_recon, del.m_offset + split_pos + cur_len))
    ));
  }
}

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

inline std::auto_ptr<operation> delete_operation::transform_delete(const delete_operation& del, cid cid) const
{
  if(del.m_pos + del.m_text.length() <= m_pos)
    return del.clone();
  else if(del.m_pos >= m_pos + m_text.length())
      return std::auto_ptr<operation>(new delete_operation(del.m_pos - m_text.length(), del.m_text));
  else if(m_pos <= del.m_pos && m_pos + m_text.length() >= del.m_pos + del.m_text.length())
    return std::auto_ptr<operation>(new no_operation());
  else if(m_pos <= del.m_pos && m_pos + m_text.length() < del.m_pos + del.m_text.length())
    return std::auto_ptr<operation>(new delete_operation(m_pos, del.m_text.substr(m_pos + m_text.length() - del.m_pos)));
  else if(m_pos > del.m_pos && m_pos + m_text.length() >= del.m_pos + del.m_text.length())
    return std::auto_ptr<operation>(new delete_operation(del.m_pos, del.m_text.substr(0, m_pos - del.m_pos)));
  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_text.length() - del.m_pos)));
}

inline std::auto_ptr<operation> delete_operation::transform_remote(const remote_delete_operation& del, cid cid) const
{
  if(del.m_pos + del.m_len <= m_pos)
    return del.clone();
  else if(del.m_pos >= m_pos + m_text.length())
  {
    return std::auto_ptr<operation>(new remote_delete_operation(del.m_pos - m_text.length(), del.m_len, del.m_recon, del.m_offset));
  }
  else if(m_pos <= del.m_pos && m_pos + m_text.length() >= del.m_pos + del.m_len)
  {
    remote_delete_operation::recon_type recon(del.m_recon);
    recon = remote_delete_operation::transfer_to_recon(recon, 0, m_text.substr(del.m_pos - m_pos, del.m_len));
    return std::auto_ptr<operation>(new remote_delete_operation(m_pos, 0, recon, del.m_offset));
  }
  else if(m_pos <= del.m_pos && m_pos + m_text.length() < del.m_pos + del.m_len)
  {
    remote_delete_operation::recon_type recon(del.m_recon);
    recon = remote_delete_operation::transfer_to_recon(recon, 0, m_text.substr(del.m_pos - m_pos));
    return std::auto_ptr<operation>(new remote_delete_operation(m_pos, del.m_len - (m_pos + m_text.length() - del.m_pos), recon, del.m_offset));
  }
  else if(m_pos > del.m_pos && m_pos + m_text.length() >= del.m_pos + del.m_len)
  {
    // Initial recon
    remote_delete_operation::recon_type recon(del.m_recon);
    // Add recon from self
    recon = remote_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 remote_delete_operation(del.m_pos, m_pos - del.m_pos, recon, del.m_offset));
  }
  else
  {
    // Initial recon
    remote_delete_operation::recon_type recon(del.m_recon);
    // Add recon from self
    recon = remote_delete_operation::transfer_to_recon(recon, m_pos - del.m_pos, m_text);
    // Recon done
    return std::auto_ptr<operation>(new remote_delete_operation(del.m_pos, m_pos - del.m_pos + del.m_len - (m_pos + m_text.length() - del.m_pos), recon, del.m_offset));
  }
}

// Only required for C1/2 tests, and split transforms
inline std::auto_ptr<operation> remote_delete_operation::transform_insert(const insert_operation& ins, cid cid) 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));
  else if(ins.m_pos < m_pos)
    return ins.clone();
  else
    return std::auto_ptr<operation>(new insert_operation(m_pos, ins.m_text));
}

inline std::auto_ptr<operation> remote_delete_operation::transform_delete(const delete_operation& del, cid cid) const
{
  if(del.m_pos + del.m_text.length() <= m_pos)
    return del.clone();
  else if(del.m_pos >= m_pos + m_len)
      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_text.length())
    return std::auto_ptr<operation>(new no_operation());
  else if(m_pos <= del.m_pos && m_pos + m_len < del.m_pos + del.m_text.length())
    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_text.length())
    return std::auto_ptr<operation>(new delete_operation(del.m_pos, del.m_text.substr(0, m_pos - del.m_pos)));
  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)));
}

inline std::auto_ptr<operation> remote_delete_operation::transform_remote(const remote_delete_operation& del, cid cid) const
{
  // Cannot reconstruct recon, must not overlay in split transform, doesn't matter in C1/2 tests
  if(del.m_pos + del.m_len <= m_pos)
    return del.clone();
  else if(del.m_pos >= m_pos + m_len)
      return std::auto_ptr<operation>(new remote_delete_operation(del.m_pos - m_len, del.m_len));
  else if(m_pos <= del.m_pos && m_pos + m_len >= del.m_pos + del.m_len)
//    return std::auto_ptr<operation>(new remote_delete_operation(m_pos, 0));
    return std::auto_ptr<operation>(new no_operation()); // Is not ignored by split_operation::operator==.
  else if(m_pos <= del.m_pos && m_pos + m_len < del.m_pos + del.m_len)
    return std::auto_ptr<operation>(new remote_delete_operation(m_pos, del.m_len - (m_pos + m_len - del.m_pos)));
  else if(m_pos > del.m_pos && m_pos + m_len >= del.m_pos + del.m_len)
    return std::auto_ptr<operation>(new remote_delete_operation(del.m_pos, m_pos - del.m_pos));
  else
    return std::auto_ptr<operation>(new remote_delete_operation(del.m_pos, m_pos - del.m_pos + del.m_len - (m_pos + m_len - del.m_pos)));
}

/* 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];
  }

  basic_state_vector<N> operator-(const basic_state_vector<N>& other) {
    basic_state_vector<N> retval(*this);
    for(unsigned int i = 0; i < N; ++ i) {
      assert(m_n[i] >= other.m_n[i]);
      retval.m_n[i] -= other.m_n[i];
    }
    return retval;
  }

  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; }

  basic_state_vector<N> set(unsigned int i, unsigned int to) const { assert(i < N); basic_state_vector<N> v = *this; v.m_n[i] = to; return v; }

  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;
  }

  basic_state_vector<N> lcs(const basic_state_vector<N>& other) const {
    basic_state_vector<N> result(*this);
    for(unsigned int i = 0; i < N; ++ i)
      if(other.m_n[i] > result.m_n[i])
        result.m_n[i] = other.m_n[i];
    return result;
  }

private:
  unsigned int m_n[N];
};

template<unsigned int N>
std::ostream& operator<<(std::ostream& out, const basic_state_vector<N>& vec)
{
  out << "[";
  for(unsigned i = 0; i < N; ++ i)
  {
    if(i > 0) out << ", ";
    out << vec[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) {}

  request& operator=(const request& r)
  {
    if(this == &r) return *this;

    if(r.m_op.get() != NULL)
      m_op = r.m_op->clone();
    else
      m_op.reset(NULL);

    m_v = r.m_v;
    m_user = r.m_user;
    m_type = r.m_type;
    return *this;
  }

  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 algorithm {
private:
  typedef std::vector<std::vector<request*> > log_type;
  typedef std::set<request*> queue_type;

  string_type m_state;
  log_type m_log;
  queue_type m_queue;
  state_vector m_v;
  const unsigned int m_user;

public:
  algorithm(unsigned int user, const string_type& initial): m_state(initial), m_log(USER_COUNT), m_user(user) {}

  ~algorithm()
  {
    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 string_type& 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);

        /* Adjust time of undo/redo requests.
         * These only depend on their associated request(s) */
        if(req->type() != request::DO)
        {
          request* old_req = req;
          const request& original = original_request(*req);
          req = new request(original.v().set(original.user(), req->v()[original.user()]), original.user(), req->type());
          delete old_req;
        }

        // TODO: Clear req if the following throws
        // Translate
        std::auto_ptr<request> translated = translate_request(*req, m_v);
        
        request* req_log = req;
        if(req->type() == request::DO)
        {
          const remote_delete_operation* remdel_op = dynamic_cast<const remote_delete_operation*>(&req->op());
          if(remdel_op != NULL)
          {
            std::auto_ptr<operation> reversible = remdel_op->make_reversible(translated->op(), m_state);
            req_log = new request(reversible, req->v(), req->user());
            delete req;
          }
        }

        translated->op().apply(m_state);
        m_v = m_v.inc(translated->user(), 1);
        m_log[req_log->user()].push_back(req_log);

        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)
    {
      if(r.v() == to)
        return std::auto_ptr<request>(new request(r));
    }
    else
    {
      const request& associated = associated_request(r);

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

      if(reachable(v))
        return mirror(*translate_request(associated, v), to[r.user()] - v[r.user()]);
    }

    // Fold first
    for(unsigned int i = 0; i < USER_COUNT; ++ i)
    {
      if(i == r.user()) continue;
      if(to[i] == 0) 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]);
        v = to.set(i, begin.v()[i]);

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

      // Could not fold, default transform
      if(r.v()[i] >= to[i]) 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]);
/*        if(against.v() <= r.v())
          return transform(*translate_request(r, v), *translate_request(*translate_request(against, r.v()), v));
        else if(r.v() <= against.v())
          return transform(*translate_request(*translate_request(r, against.v()), v), *translate_request(against, v));
        else*/
          return transform(r, against, v); //*translate_request(r, v), *translate_request(against, v), r, v);
      }
    }
    
    // Note: The following is currently merged with the upper fold
    // loop. I am not yet 100% sure it is correct, but it passes the tests.
    // I am keeping this to easily revert if it still fails in some situation.

#if 0
    // 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]);
        if(against.v() <= r.v())
          return transform(*translate_request(r, v), *translate_request(*translate_request(against, r.v()), v));
        else if(r.v() <= against.v())
          return transform(*translate_request(*translate_request(r, against.v()), v), *translate_request(against, v));
        else
          return transform(*translate_request(r, v), *translate_request(against, v));
      }
    }
#endif

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

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

    std::auto_ptr<request> req1_at(translate_request(req1, at));
    std::auto_ptr<request> req2_at(translate_request(req2, at));
    assert(req1_at->type() == request::DO && req2_at->type() == request::DO);

    cid cid(cid::none);
#if 1
    if(req1_at->op().need_cid(req2_at->op()))
    {
      state_vector lcs = req1.v().lcs(req2.v());
      assert(req1.v() <= lcs);
      assert(req2.v() <= lcs);
      assert(lcs <= at);

      std::auto_ptr<request> req1_lcs(translate_request(req1, lcs));
      std::auto_ptr<request> req2_lcs(translate_request(req2, lcs));
      assert(req1_lcs->type() == request::DO && req2_lcs->type() == request::DO);

      cid = req1_lcs->op().get_cid(req2_lcs->op());
      if(cid == cid::none)
        cid = req1.user() > req2.user() ? cid::other : cid::self; // arbitrary
    }
#else
        cid = req1.user() > req2.user() ? cid::other : cid::self; // arbitrary
#endif
    return std::auto_ptr<request>(new request(
      req1_at->op().transform_against(req2_at->op(), cid),
      req1_at->v().inc(req2_at->user(), 1),
      req1_at->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.v() <= 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()));
  }
};

#endif // ADOPTED_HPP

/* vim:set et sw=2 ts=2: */