#ifndef __ZIGZAG_PERSISTENCE_H__
#define __ZIGZAG_PERSISTENCE_H__

#include "cycles.h"
#include "utilities/types.h"
#include <sstream>

#if DEBUG_CONTAINERS
    #include <debug/list>
    using std::__debug::list;
    #warning "Using debug/list in ZigzagPersistence"
#else
    #include <list>
    using std::list;
#endif


/**
 * Class: ZigzagPersistence
 * TODO: this should probably be parametrized by Chain or Field
 */
template<class BirthID_ = Empty<>, class SimplexData_ = Empty<> >
class ZigzagPersistence
{
    public:
        typedef                         BirthID_                                BirthID;
        typedef                         SimplexData_                            SimplexData;

        struct ZNode;
        struct BNode;
        struct SimplexNode;

        typedef                         list<ZNode>                                     ZList;
        typedef                         typename ZList::iterator                        ZIndex;
        typedef                         list<BNode>                                     BList;
        typedef                         typename BList::iterator                        BIndex;
        typedef                         list<SimplexNode>                               SimplexList;
        typedef                         typename SimplexList::iterator                  SimplexIndex;

        // TODO: should all chains be DequeChains? probably not
        typedef                         typename DequeChains<ZIndex>::Chain             ZRow;
        typedef                         typename DequeChains<ZIndex>::Chain             BColumn;
        typedef                         typename VectorChains<BIndex>::Chain            BRow;
        typedef                         typename VectorChains<BIndex>::Chain            CRow;
        typedef                         typename VectorChains<SimplexIndex>::Chain      ZColumn;
        typedef                         typename VectorChains<SimplexIndex>::Chain      CColumn;

        typedef                         boost::optional<BirthID>                        Death;
        typedef                         std::pair<SimplexIndex, Death>                  IndexDeathPair;

        struct ZNode
        {
                                        ZNode(int o, BIndex l): 
                                            order(o), low(l)                            {}

            int                         order;
            ZColumn                     z_column;
            BRow                        b_row;
            BIndex                      low;            // which BColumn has this ZIndex as low

            BirthID                     birth;          // TODO: do we need to do empty-member optimization? 
                                                        //       i.e., does it ever make sense for birth to be empty?
        };

        struct BNode
        {
                                        BNode(unsigned o): order(o)                     {}

            unsigned                    order;
            BColumn                     b_column;
            CColumn                     c_column;
        };

        struct SimplexNode: public SimplexData
        {
                                        SimplexNode(unsigned o, ZIndex l): 
                                            order(o), low(l)                            {}

            unsigned                    order;
            ZRow                        z_row;
            CRow                        c_row;
            ZIndex                      low;            // which ZColumn has this SimplexNode as low
#if ZIGZAG_CONSISTENCY
            ZColumn                     boundary;       // NB: debug only
#endif
        };

        // Constructor: ZigzagPersistence()
                                        ZigzagPersistence()                             {}
        
        // Function: add(bdry, birth)
        IndexDeathPair                  add(ZColumn bdry, const BirthID& birth = BirthID())         { ZigzagVisitor zzv; return add<ZigzagVisitor>(bdry, birth, zzv); }
        
        // Function: remove(s, birth)
        Death                           remove(SimplexIndex s, const BirthID& birth = BirthID())    { ZigzagVisitor zzv; return remove<ZigzagVisitor>(s, birth, zzv); }


        ZIndex                          begin()                                                     { return z_list.begin(); }
        ZIndex                          end()                                                       { return z_list.end(); }

        bool                            is_alive(ZIndex i) const                                    { return i->low == b_list.end(); }
 
    protected:                                        
        // Function: add(s)
        template<class Visitor>
        IndexDeathPair                  add(ZColumn bdry, const BirthID& birth, Visitor& visitor);

        // Function: remove(s)
        template<class Visitor>
        Death                           remove(SimplexIndex s, const BirthID& birth, Visitor& visitor);

        // Struct: ZigzagVisitor
        // Various methods of an instance of this class are called at different stages of addition and removal algorithm.
        // NB: currently the places where it's called are catered for image zigzags, in the future this could be expanded 
        //     to provide simple support for other algorithms
        // TODO: not obvious that the methods should be const (and therefore the reference passed to add() and remove())
        //       revisit when working on ImageZigzag
        struct ZigzagVisitor
        {
            SimplexIndex                new_simplex(ZigzagPersistence& zz);

            // Function: new_z_in_add(zz, z, u)
            // Called when a new cycle is born after adding a simplex. The method is expected to add an element to z_list, and return its ZIndex.
            ZIndex                      new_z_in_add(ZigzagPersistence& zz, const ZColumn& z, const BRow& u);
            
            BIndex                      select_j_in_remove(ZigzagPersistence& zz, const CRow& c_row);

            ZIndex                      new_z_in_remove(ZigzagPersistence& zz);

            void                        erasing_z(ZigzagPersistence& zz, ZIndex j)      {}

            Death                       death(ZigzagPersistence& zz, ZIndex dying_z);
        };

    public:
        // Debug; non-const because Indices are iterators, and not const_iterators 
        void                            show_all();
        bool                            check_consistency(SimplexIndex s_skip, ZIndex z_skip, BIndex b_skip);
        bool                            check_consistency()                             { return check_consistency(s_list.end(), z_list.end(), b_list.end()); }

    protected:
        ZList                           z_list;
        BList                           b_list;
        SimplexList                     s_list;

        /* Helper functors */
        template<class Member, class Element>                                           struct Appender;
        template<class Member, class Element>                                           struct Remover;
        template<class Member, class Chain>                                             struct Adder;

        template<class Member, class Element>
        Appender<Member, Element>       make_appender(Member m, Element e) const        { return Appender<Member, Element>(m,e); }
        template<class Member, class Element>
        Remover<Member, Element>        make_remover(Member m, Element e) const         { return Remover<Member, Element>(m,e); }
        template<class Member, class Chain>
        Adder<Member, Chain>            make_adder(Member m, Chain& c) const            { return Adder<Member, Chain>(m, c); }

        template<class Index, class IndexFrom, class PrimaryMember, class SecondaryMember>
        void                            add_chains(Index bg, Index end, IndexFrom j, PrimaryMember pm, SecondaryMember sm);
        template<class IndexTo, class IndexFrom, class PrimaryMemberTo, class SecondaryMemberTo, class PrimaryMemberFrom>
        void                            add_chains(IndexTo bg, IndexTo end, IndexFrom j, 
                                                   PrimaryMemberTo   pmt, SecondaryMemberTo smt,
                                                   PrimaryMemberFrom pmf);
        template<class Index, class PrimaryMember, class SecondaryMember>
        void                            add_chain(Index to, Index from, 
                                                  PrimaryMember   pmt, SecondaryMember smt);
        template<class IndexTo, class IndexFrom, class PrimaryMemberTo, class SecondaryMemberTo, class PrimaryMemberFrom>
        void                            add_chain(IndexTo to, IndexFrom from, 
                                                  PrimaryMemberTo   pmt, SecondaryMemberTo smt,
                                                  PrimaryMemberFrom pmf);
        template<class IndexTo, class IndexFrom, class PrimaryMember, class SecondaryMember, class DualPrimaryMember, class DualSecondaryMember>
        void                            change_basis(IndexTo bg, IndexTo end, IndexFrom j, 
                                                     PrimaryMember pm, SecondaryMember sm, 
                                                     DualPrimaryMember dpm, DualSecondaryMember dsm);

    public:
        struct OrderComparison
        {
            template<class T> 
            bool                        operator()(T a, T b) const                      { return a->order < b->order; }
        }                               cmp;
        
        struct OrderOutput
        {
            template<class T> 
            std::string                 operator()(T a) const                           { std::stringstream s; s << a->order; return s.str(); }
        }                               out;
};

#include "zigzag-persistence.hpp"

#endif // __ZIGZAG_PERSISTENCE_H__