/* 
 * © 2008 MySQL AB, 2008-2009 Sun Microsystems, Inc.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

#ifndef _LIST_DIFFERENCE_H
#define _LIST_DIFFERENCE_H

#include "stdext-lcs.h"
#include "stdext-algorithm.h"

namespace grt
{

template<
  class _tid,
  class _InIt1,//= _tid*,
  class _InIt2//= _tid*
>
struct ListDifference
{
protected:
  typedef typename std::multimap<int, _tid> Block;
  typedef std::vector<std::pair<_tid, Block> > ListTail;
  typedef std::pair<Block, ListTail> ListStructure;

  ListStructure structure;

public:
  // int, (int)stable_index
  typedef std::pair<int, int> Position;
  // _tid, Position
  typedef std::pair<_tid, Position> Item;
  // _tid, <Position, Position>
  typedef std::pair<Item, Item> ItemPair;

  typedef std::vector<Item> AddActionSet;
  typedef std::vector<Item> RemoveActionSet;
  typedef std::vector<ItemPair> MoveActionSet;

protected:

  int apply_removed_or_calc_index(const Item &action, bool apply_removed)
  {
    Block* block= &structure.first;

    int stable_index= action.second.second;
    if (stable_index > -1)
      block= &structure.second[stable_index].second;

    std::pair<typename Block::iterator, typename Block::iterator> res= block->equal_range(action.second.first);
    for(typename Block::iterator iter= res.first; iter!=res.second; ++iter)
      if (iter->second == action.first)
      {
        int res= calc_index(stable_index, std::distance(block->begin(), iter));
        if(apply_removed)
          block->erase(iter);
        return res;
      }

    assert(0);
    return -1;
  }

public:

  // warning! this become invalidated once after source is deleted (TODO)<- (move to protected virtual?)
  std::vector<_InIt1> stable1;
  // warning! this become invalidated once after target is deleted (TODO)<- (move to protected virtual?)
  std::vector<_InIt2> stable2;

  MoveActionSet moved;
  AddActionSet added;
  RemoveActionSet removed;

  //template<class _Op>
  //void for_each_stable(_Op Op)
  //{
  //  assert(stable1.size() == stable2.size());
  //  std::vector<_InIt1>::iterator iter1= stable1.begin();
  //  std::vector<_InIt2>::iterator iter2= stable2.begin();

  //  std::vector<_InIt1>::iterator end1= stable1.end();
  //  for(; iter1 != end1;)
  //    Op(*iter1++, *iter2++);
  //}

  //template<class _Op>
  //void for_each_moved(_Op Op)
  //{
  //  for(MoveActionSet::iterator iter= moved.begin(); iter != moved.end(); ++iter)
  //    Op(iter->first, iter->second);
  //}

  void clear()
  {
    stable1.clear();
    stable2.clear();
    added.clear();
    removed.clear();
    moved.clear();
    structure = ListStructure();
  }

  inline int calc_index(Position position)
  {
    return calc_index(position.second, position.first);
  }

  inline int calc_index_for_item_removed_action(const Item &action) const
  {
    return const_cast<ListDifference * const>(this)->apply_removed_or_calc_index(action, false);
  }

  _tid *get_id(unsigned index)
  {
    if (index < structure.first.size())
    {
      typename Block::iterator iter= structure.first.begin();
      while(index--)
        ++iter;
      return &iter->second;
    }
    index-= structure.first.size();

    typename ListTail::iterator iter= structure.second.begin();

    for(;iter != structure.second.end(); ++iter)
    {
      if (!index)
        return &iter->first;
      
      index--;
      if (index < iter->second.size())
      {
        typename Block::iterator iter1= iter->second.begin();
        while (index--)
            ++iter1;
        return &iter1->second;
      }

      index-= iter->second.size();
    }

    return NULL;
  }

  inline int calc_index(int stable_index, int offset)
  {
    assert(stable_index == -1 || stable_index < (int)structure.second.size());
    if (stable_index == -1)
      return offset;

    int res= (int)structure.first.size() + 1 + offset;

    for(int i= 0; i < stable_index; ++i)
      res+= 1 + (int)structure.second[i].second.size();
    
    return res;
  }

  int apply_added(Item &action)
  {
    Block* block= &structure.first;

    int stable_index= action.second.second;
    if (stable_index > -1)
      block= &(structure.second[stable_index].second);

    typename Block::iterator res= block->insert( std::make_pair(action.second.first, action.first) );
    return calc_index(stable_index, std::distance(block->begin(), res));
  }

  int apply_removed(Item &action)
  {
    return apply_removed_or_calc_index(action, true);
    //Block* block= &structure.first;

    //int stable_index= action.second.second;
    //if (stable_index > -1)
    //  block= &structure.second[stable_index].second;

    //std::pair<typename Block::iterator, typename Block::iterator> res= block->equal_range(action.second.first);
    //for(typename Block::iterator iter= res.first; iter!=res.second; ++iter)
    //  if (iter->second == action.first)
    //  {
    //    int res= calc_index(stable_index, std::distance(block->begin(), iter));
    //    block->erase(iter);
    //    return res;
    //  }

    //assert(0);
    //return -1;
  }

  std::pair<int, int> apply_moved(ItemPair &action)
  {
    std::pair<int, int> res;
    res.first= apply_removed(action.first);
    res.second= apply_added(action.second);

    // move forward
    //if (res.second < res.first)
    //  res.first--;
    //else
    //  res.first--;
    return res;
  }

  int item_count() const
  {
    int count= structure.first.size();
    for (typename ListTail::const_iterator iter= structure.second.begin(); iter != structure.second.end(); ++iter)
      count+= 1 + iter->second.size(); // we should add 1 because stable items are not in Block

    return count;
  }

  template<class _OutIt>
  _OutIt expand(_OutIt _Dest) const
  {
    for (typename Block::const_iterator iter= structure.first.begin(); iter != structure.first.end(); ++iter)
      *_Dest++ = iter->second;

    for (typename ListTail::const_iterator iter= structure.second.begin(); iter != structure.second.end(); ++iter)
    {
      *_Dest++ = iter->first;
      for (typename Block::const_iterator blo= iter->second.begin(); blo != iter->second.end(); ++blo)
        *_Dest++ = blo->second;
    }

    return _Dest;
  }


template<class T, class _LtOp>
struct lt_first
{
  lt_first(_LtOp _Lt) : Lt(_Lt) {}
  _LtOp Lt;
  bool operator ()(const T& l, const T& r)
  {
    return Lt(l.first, r.first);
  }
};


//template<class T>
//struct eq_first
//{
//  bool operator ()(const T& l, const T& r)
//  {
//    return l.first == r.first;
//  }
//};



template<
  class _EqOp,
  class _LtOp
> inline
void parse_structure(_InIt1 _First1, _InIt1 _Last1,
    _InIt2 _First2, _InIt2 _Last2,
    _EqOp _Eq, _LtOp _Lt)
{
  stdext::set_lcs_to_vectors(_First1, _Last1, _First2, _Last2, stable1, stable2, _Eq);

  assert(stable1.size() == stable2.size());

  typename std::vector<_InIt1>::iterator next_stable= stable1.begin();
  Block *block= &structure.first;
  _InIt1 iter= _First1;

  int i= 0;
  // this is case when no stable elements, i.e. everything removed
  for (; iter != (stable1.size()? *next_stable: _Last1); ++iter)
    block->insert(block->end(), std::make_pair(i++, *iter));

  // fill the structure
  if (stable1.size())
    do
    {
      structure.second.push_back(std::make_pair(**next_stable, Block()));
      block= &structure.second.back().second;

      int i= 0;
      ++next_stable;
      ++iter;

      for (; iter != ((next_stable==stable1.end())?_Last1:*next_stable); ++iter)
        block->insert(block->end(), std::make_pair(i++, *iter));
    }
    while(next_stable != stable1.end());

  // sort
  {
    RemoveActionSet items1;
    AddActionSet items2;
    {
      _InIt1 iter= _First1;
      int i= 0;
      for (; iter != (stable1.size()? stable1.front(): _Last1);)
        items1.push_back(std::make_pair(*iter++, std::make_pair(i++, -1)));

      for (typename std::vector<_InIt1>::iterator stbl1= stable1.begin(); stbl1 != stable1.end(); ++stbl1)
        for (i= 0, iter= *stbl1 + 1; iter != ((stbl1+1==stable1.end())?_Last1:*(stbl1 + 1));)
          items1.push_back(std::make_pair(*iter++, std::make_pair(i++, stbl1 - stable1.begin())));
    }
    {
      _InIt2 iter= _First2;
      int i= 0;
      for (; iter != (stable2.size()? stable2.front(): _Last2);)
        items2.push_back(std::make_pair(*iter++, std::make_pair(i++, -1)));

      for (typename std::vector<_InIt2>::iterator stbl2= stable2.begin(); stbl2!= stable2.end(); ++stbl2)
        for (i= 0, iter= *stbl2 + 1; iter != ((stbl2+1==stable2.end())?_Last2:*(stbl2 + 1));)
          items2.push_back(std::make_pair(*iter++, std::make_pair(i++, stbl2 - stable2.begin())));
    }

    std::sort(items1.begin(), items1.end(), lt_first<typename RemoveActionSet::value_type, _LtOp>(_Lt));
    std::sort(items2.begin(), items2.end(), lt_first<typename AddActionSet::value_type, _LtOp>(_Lt));

    stdext::set_full_difference_to_vectors<Item>(
      items1.begin(), items1.end(), 
      items2.begin(), items2.end(), 
      removed, 
      added, 
      moved, 
      lt_first<typename RemoveActionSet::value_type, _LtOp>(_Lt));
  }
}
};


}

#endif
