#include <list>
#include <map>
#include <iostream>
#include <string>
#include <memory>
#include <stdexcept>

namespace mem=std;//::tr1;
namespace fun=std;//::tr1;

//Original of the non-templatized version: http://w...content-available-to-author-only...k.com/index.php?title=Design_pattern_memento
//continued here: https://g...content-available-to-author-only...b.com/d-led/undoredo-cpp

/// to be able to talk undoables uniformly
struct Undoable
{
    virtual void Undo()=0;
    virtual ~Undoable() {}
};

/// Memento for the encapsulation of the state and its handling
template <class T>
class Memento
{

private:

    T state_;

public:

    Memento(const T& stateToSave) : state_(stateToSave) { }
    const T& getSavedState()
    {
        return state_;
    }
};

/// A convenience class for storage of mementos
template <class T, class TMemento = typename T::MementoType>
struct MementoStore : public Undoable
{
    virtual void Save(T* t)=0;
    virtual void Undo(T* t)=0;
    virtual void Undo()=0;
    virtual ~MementoStore() {}
};

/// the default implementation of the store
template<class T, class TMemento = typename T::MementoType>
class StlMementoStore : public MementoStore<T, TMemento>
{
private:
    typedef std::map<T*,std::list<mem::shared_ptr<TMemento> > > StoreType;
    StoreType Store;

public:

    void PushState(T* t,mem::shared_ptr<TMemento> m)
    {
        if (t)
        {
            Store[t].push_back(m);
        }
    }

    mem::shared_ptr<TMemento> PopState(T* t)
    {
        if (!t || Store[t].size()<1) throw std::runtime_error("No more undo states");
        mem::shared_ptr<TMemento> res=Store[t].back();
        Store[t].pop_back();
        return res;
    }

    virtual void Save(T* t)
    {
        PushState(t,t->SaveState());
    }

    virtual void Undo(T* t)
    {
        t->RestoreState(PopState(t));
    }

/// tries to undo 1 state change per object for all objects
    virtual void Undo()
    {
        TryUndoAll();
    }

private:
    void TryUndoAll()
    {
        for (typename StoreType::iterator it=Store.begin(); it!=Store.end(); ++it)
        {
            try
            {
                it->first->RestoreState(PopState(it->first));
            }
            catch(std::exception& e)
            {
                /*trying, anyway*/ e;
            }
        }
    }
};

/// A container of undoables that undos all
class UndoableAggregate : public Undoable
{
    typedef std::list<mem::shared_ptr<Undoable> > Container;
private:
    Container list_;

public:
    virtual void Undo()
    {
        for (Container::iterator it=list_.begin(); it!=list_.end(); ++it)
        {
            (*it)->Undo();
        }
    }

public:
    void AddUndoable(mem::shared_ptr<Undoable> instance)
    {
        list_.push_back(instance);
    }
};

/// example state-undoable class
class MyOriginator
{
private:
    struct State
    {
        std::string s;
    };
    State state_;

public:

    void Set(const std::string& state)
    {
        std::cout << "MyOriginator::Setting state to: " << state << std::endl;
        state_.s = state;
    }

//--- class-specific memento

public:
    typedef Memento<State> MementoType;
    typedef MementoStore<MyOriginator> MementoStoreType;

    mem::shared_ptr<MementoType> SaveState()
    {
        std::cout << "MyOriginator::Saving state to Memento." << std::endl;
        return mem::shared_ptr<MementoType>(new MementoType(state_));
    }

    void RestoreState(mem::shared_ptr<MementoType> memento)
    {
        state_ = memento->getSavedState();
        std::cout << "MyOriginator::Restoring state from Memento: " << state_.s << std::endl;
    }
};

/// the other example class
class MySecondOriginator
{
private:
    int s;

public:

    void Set(int state)
    {
        std::cout << "MySecondOriginator::Setting state to: " << state << std::endl;
        s = state;
    }

    MySecondOriginator():s(0){}

//--- class-specific memento

public:
    typedef Memento<int> MementoType;
    typedef MementoStore<MySecondOriginator> MementoStoreType;

    mem::shared_ptr<MementoType> SaveState()
    {
        std::cout << "MySecondOriginator::Saving state to Memento." << std::endl;
        return mem::shared_ptr<MementoType>(new MementoType(s));
    }

    void RestoreState(mem::shared_ptr<MementoType> memento)
    {
        s = memento->getSavedState();
        std::cout << "MySecondOriginator::Restoring state from Memento: " << s << std::endl;
    }
};

template <class T>
mem::shared_ptr<typename T::MementoStoreType> NewMementoStore()
{
    return mem::shared_ptr<typename T::MementoStoreType>(new StlMementoStore<T>);
}

//----- Prototype for transaction based undo

typedef fun::function<void ()> Action;
typedef std::pair<Action/*Undo*/,Action/*Redo*/> Transaction;


/// Storage of transactions
class TransactionStore
{
private:
    std::list<Transaction> Undo_;
    std::list<Transaction> Redo_;

public:

    void AddTransaction(Transaction t)
    {
        if (t.first && t.second)
        {
            Undo_.push_back(t);
            Redo_.clear();
        }
    }

    void UndoLastTransaction()
    {
        if (Undo_.size()<1) throw std::runtime_error("No more undo transactions");
        Undo_.back().first();
        Redo_.push_back(Undo_.back());
        Undo_.pop_back();
    }

    void RedoLastTransaction()
    {
        if (Redo_.size()<1) throw std::runtime_error("No more redo transactions");
        Redo_.back().second();
        Undo_.push_back(Redo_.back());
        Redo_.pop_back();
    }

    void Purge()
    {
        Undo_.clear();
        Redo_.clear();
    }
};

class CompositeTransaction : public fun::enable_shared_from_this<CompositeTransaction>
{
private:
    std::list<Transaction> Undo_;
    std::list<Transaction> Redo_;

public:

    void AddTransaction(Transaction t)
    {
        if (t.first && t.second)
        {
            Undo_.push_back(t);
            Redo_.clear();
        }
    }

    void UndoAll()
    {
        while (Undo_.size())
        {
            Undo_.back().first();
            Redo_.push_back(Undo_.back());
            Undo_.pop_back();
        }
    }

    void RedoAll()
    {
        while (Redo_.size())
        {
            Redo_.back().second();
            Undo_.push_back(Redo_.back());
            Redo_.pop_back();
        }
    }

/// a composite transaction, instance must be in shared_ptr
    Transaction Get()
    {
        return std::make_pair(fun::bind(&CompositeTransaction::UndoAll,shared_from_this()),
                              fun::bind(&CompositeTransaction::RedoAll,shared_from_this()));
    }
};


/// Transaction-undoable example class
class MyThirdOriginator : public mem::enable_shared_from_this<MyThirdOriginator>
{
private:
    int state;
    std::string name;

public:

    void Set(int s)
    {
        std::cout << "MyThirdOriginator("<<name<<")::Setting state to: " << s << std::endl;
        state=s;
    }

    void SetName(std::string n)
    {
        std::cout << "MyThirdOriginator("<<name<<")::Setting name to: " << n << std::endl;
        name=n;
    }

//---- class-specific transaction

    Transaction UndoableSet(int s,std::string n)
    {
        mem::shared_ptr<CompositeTransaction> res(new CompositeTransaction);
        if (n!=name)
        {
            res->AddTransaction(std::make_pair(
                                    fun::bind(&MyThirdOriginator::SetName,shared_from_this(),name),
                                    fun::bind(&MyThirdOriginator::SetName,shared_from_this(),n)
                                ));
            SetName(n);
        }
        if (s!=state)
        {
            res->AddTransaction(std::make_pair(
                                    fun::bind(&MyThirdOriginator::Set,shared_from_this(),state),
                                    fun::bind(&MyThirdOriginator::Set,shared_from_this(),s)
                                ));
            Set(s);
        }
        return res->Get();
    }

public:

    MyThirdOriginator(std::string n):state(0),name(n) {}

    ~MyThirdOriginator()
    {
        std::cout<<"Destroying MyThirdOriginator("<<name<<")" << std::endl;
    }
};

static void Print(const char * t)
{
    std::cout<<t;
}

static Transaction RepeatedPrint(const char * t)
{
    Print(t);
    return std::make_pair(fun::bind(Print,t),fun::bind(Print,t));
}

/// the default implementation of the store
template<class T, class TMemento = typename T::MementoType>
class DelayedTransaction : public mem::enable_shared_from_this<DelayedTransaction<T,typename T::MementoType> >
{
private:
    mem::shared_ptr<TMemento> Undo_;
    mem::shared_ptr<TMemento> Redo_;
    T* Object_;

public:

    DelayedTransaction(T* t)
    {
        Object_=t;
    }

    void BeginTransaction()
    {
        Undo_=Object_->SaveState();
    }

    Transaction EndTransaction()
    {
        Redo_=Object_->SaveState();
        return Get();
    }

    Transaction Get()
    {
        return std::make_pair(fun::bind(&DelayedTransaction<T>::Undo,this->shared_from_this()),
                              fun::bind(&DelayedTransaction<T>::Redo,this->shared_from_this()));
    }

private:

    virtual void Undo()
    {
        Object_->RestoreState(Undo_);
    }
    
    virtual void Redo()
    {
        Object_->RestoreState(Redo_);
    }
};

int main()
{
    std::auto_ptr<UndoableAggregate> allStores(new UndoableAggregate);

    //example class 1
    MyOriginator originator;
    mem::shared_ptr<MyOriginator::MementoStoreType> savedStates(NewMementoStore<MyOriginator>()); //without c++0x
    //auto savedStates=NewMementoStore<MyOriginator>();
    allStores->AddUndoable(savedStates);
    //
    originator.Set("StateA");
    originator.Set("StateB");
    savedStates->Save(&originator);
    originator.Set("StateC");
    savedStates->Save(&originator);
    originator.Set("StateD");
    savedStates->Save(&originator);
    //
    MyOriginator originator2;
    originator2.Set("StateA(2)");
    savedStates->Save(&originator2);
    originator2.Set("StateB(2)");
    savedStates->Save(&originator2);

    //example class 2
    MySecondOriginator originator3;
    mem::shared_ptr<MySecondOriginator::MementoStoreType> savedStates2(NewMementoStore<MySecondOriginator>());
    //auto savedStates2=NewMementoStore<MySecondOriginator>();
    allStores->AddUndoable(savedStates2);
    //
    originator3.Set(1);
    savedStates2->Save(&originator3);
    originator3.Set(2);
    savedStates2->Save(&originator3);

    try
    {
        allStores->Undo(); //try to undo all objects in all stores
        allStores->Undo();

        savedStates->Undo(&originator);
        savedStates->Undo(&originator);
        savedStates->Undo(&originator);
        savedStates->Undo(&originator);
    }
    catch (std::exception& e)
    {
        std::cout<<e.what()<<std::endl;
    }


// transaction-based undo prototype
    mem::shared_ptr<MyThirdOriginator> o1(new MyThirdOriginator("o1")),o2(new MyThirdOriginator("o2"));
    TransactionStore ts;
    ts.AddTransaction(RepeatedPrint("-----------------\n"));
    ts.AddTransaction(o1->UndoableSet(1,"o1"));
    ts.AddTransaction(o1->UndoableSet(2,"o1"));
    ts.AddTransaction(o1->UndoableSet(3,"o1->1"));
    ts.AddTransaction(o1->UndoableSet(4,"o1->2"));
    ts.AddTransaction(RepeatedPrint("-----------------\n"));
    ts.AddTransaction(o2->UndoableSet(4,"o2"));
    ts.AddTransaction(o2->UndoableSet(5,"o2"));
    ts.AddTransaction(RepeatedPrint("-----------------\n"));

    ts.UndoLastTransaction();
    std::cout<<"Undo : ";
    ts.UndoLastTransaction();
    std::cout<<"Undo : ";
    ts.UndoLastTransaction();
    std::cout<<"Redo : ";
    ts.RedoLastTransaction();
    std::cout<<"Redo : ";
    ts.RedoLastTransaction();
    ts.RedoLastTransaction();

    while (true)
    {
        try
        {
            ts.UndoLastTransaction();
        }
        catch(std::exception& e)
        {
            std::cout<<e.what()<<std::endl;
            break;
        }
    }

    Print("-----------------\n");
    std::cout<<"Redo test : "<<std::endl;


    ts.AddTransaction(RepeatedPrint("Action 1\n"));

    mem::shared_ptr<CompositeTransaction> A2(new CompositeTransaction);
    A2->AddTransaction(RepeatedPrint("Action 2.1\n"));
    A2->AddTransaction(RepeatedPrint("Action 2.2\n"));

    ts.AddTransaction(A2->Get());

    ts.AddTransaction(RepeatedPrint("Action 3\n"));

    std::cout<<"Undo : ";
    ts.UndoLastTransaction();
    std::cout<<"Undo : ";
    ts.UndoLastTransaction();

    ts.AddTransaction(RepeatedPrint("Action 4\n"));


    while (true)
    {
        try
        {
            ts.RedoLastTransaction();
        }
        catch(std::exception& e)
        {
            std::cout<<e.what()<<std::endl;
            break;
        }
    }

    Print("-----------------\n");
    std::cout<<"Lifetime test : "<<std::endl;

    ts.Purge();

    {
        mem::shared_ptr<MyThirdOriginator> O3(new MyThirdOriginator("O3"));
        ts.AddTransaction(O3->UndoableSet(1,"O3.1"));
        ts.AddTransaction(O3->UndoableSet(2,"O3.2"));
    }

    std::cout<<"Undo : ";
    ts.UndoLastTransaction();
    std::cout<<"Undo : ";
    ts.UndoLastTransaction();
    std::cout<<"Redo : ";
    ts.RedoLastTransaction();
    std::cout<<"Redo : ";
    ts.RedoLastTransaction();

    Print("-----------------\n");
    std::cout<<"Purging undo history ..."<<std::endl;
    ts.Purge();
    std::cout<<"Purged undo history"<<std::endl;


    Print("-----------------\n");
    std::cout<<"Memento transaction test : "<<std::endl;
    mem::shared_ptr<MySecondOriginator> MSO(new MySecondOriginator);

    mem::shared_ptr<DelayedTransaction<MySecondOriginator> > DT(new DelayedTransaction<MySecondOriginator>(MSO.get()));

    DT.reset(new DelayedTransaction<MySecondOriginator>(MSO.get()));
    DT->BeginTransaction();
    MSO->Set(1);
    ts.AddTransaction(DT->EndTransaction());

    DT.reset(new DelayedTransaction<MySecondOriginator>(MSO.get()));
    DT->BeginTransaction();
    MSO->Set(2);
    ts.AddTransaction(DT->EndTransaction());

    DT.reset(new DelayedTransaction<MySecondOriginator>(MSO.get()));
    DT->BeginTransaction();
    MSO->Set(3);
    MSO->Set(4);
    ts.AddTransaction(DT->EndTransaction());

    DT.reset(new DelayedTransaction<MySecondOriginator>(MSO.get()));
    DT->BeginTransaction();
    MSO->Set(5);
    ts.AddTransaction(DT->EndTransaction());

    std::cout<<"Undo : ";
    ts.UndoLastTransaction();
    std::cout<<"Undo : ";
    ts.UndoLastTransaction();
    std::cout<<"Undo : ";
    ts.UndoLastTransaction();
    std::cout<<"Redo : ";
    ts.RedoLastTransaction();
    std::cout<<"Redo : ";
    ts.RedoLastTransaction();
    std::cout<<"Redo : ";
    ts.RedoLastTransaction();

    ts.Purge();

//todo: lifetime management in the combination of memento and transactions
    return 0;
}