/* Copyright 2003-2005 Joaquín M López Muñoz.

 * Distributed under the Boost Software License, Version 1.0.

 * (See accompanying file LICENSE_1_0.txt or copy at

 * http://www.boost.org/LICENSE_1_0.txt)

 *

 * See http://www.boost.org/libs/multi_index for library home page.

 */

#ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_HPP

#define BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_HPP

#if defined(_MSC_VER)&&(_MSC_VER>=1200)

#pragma once

#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */

#include <algorithm>

#include <boost/noncopyable.hpp>

#include <boost/multi_index/detail/auto_space.hpp>

#include <cstddef>

#include <functional>

namespace boost{

namespace multi_index{

namespace detail{

/* index_matcher compares a sequence of elements against a

 * base sequence, identifying those elements that belong to the

 * longest subsequence which is ordered with respect to the base.

 * For instance, if the base sequence is:

 *

 *   0 1 2 3 4 5 6 7 8 9

 *

 * and the compared sequence (not necesarilly the same length):

 *

 *   1 4 2 3 0 7 8 9

 *

 * the elements of the longest ordered subsequence are:

 *

 *   1 2 3 7 8 9

 * 

 * The algorithm for obtaining such a subsequence is called

 * Patience Sorting, described in ch. 1 of:

 *   Aldous, D., Diaconis, P.: "Longest increasing subsequences: from

 *   patience sorting to the Baik-Deift-Johansson Theorem", Bulletin

 *   of the American Mathematical Society, vol. 36, no 4, pp. 413-432,

 *   July 1999.

 *   http://www.ams.org/bull/1999-36-04/S0273-0979-99-00796-X/

 *   S0273-0979-99-00796-X.pdf

 *

 * This implementation is not fully generic since it assumes that

 * the sequences given are pointed to by index iterators (having a

 * get_node() memfun.)

 */

namespace index_matcher{

/* The algorithm stores the nodes of the base sequence and a number

 * of "piles" that are dynamically updated during the calculation

 * stage. From a logical point of view, nodes form an independent

 * sequence from piles. They are stored together so as to minimize

 * allocated memory.

 */

struct entry

{

  entry(void* node_,std::size_t pos_=0):node(node_),pos(pos_){}

  /* node stuff */

  void*       node;

  std::size_t pos;

  entry*      previous;

  bool        ordered;

  struct less_by_node

  {

    bool operator()(

      const entry& x,const entry& y)const

    {

      return std::less<void*>()(x.node,y.node);

    }

  };

  /* pile stuff */

  std::size_t pile_top;

  entry*      pile_top_entry;

  struct less_by_pile_top

  {

    bool operator()(

      const entry& x,const entry& y)const

    {

      return x.pile_top<y.pile_top;

    }

  };

};

/* common code operating on void *'s */

template<typename Allocator>

class algorithm_base:private noncopyable

{

protected:

  algorithm_base(const Allocator& al,std::size_t size):

    spc(al,size),size_(size),n(0),sorted(false)

  {

  }

  void add(void* node)

  {

    entries()[n]=entry(node,n);

    ++n;

  }

  void begin_algorithm()const

  {

    if(!sorted){

      std::sort(entries(),entries()+size_,entry::less_by_node());

      sorted=true;

    }

    num_piles=0;

  }

  void add_node_to_algorithm(void* node)const

  {

    entry* ent=

      std::lower_bound(

        entries(),entries()+size_,

        entry(node),entry::less_by_node()); /* localize entry */

    ent->ordered=false;

    std::size_t n=ent->pos;                 /* get its position */

    entry dummy(0);

    dummy.pile_top=n;

    entry* pile_ent=                        /* find the first available pile */

      std::lower_bound(                     /* to stack the entry            */

        entries(),entries()+num_piles,

        dummy,entry::less_by_pile_top());

    pile_ent->pile_top=n;                   /* stack the entry */

    pile_ent->pile_top_entry=ent;        

    /* if not the first pile, link entry to top of the preceding pile */

    if(pile_ent>&entries()[0]){ 

      ent->previous=(pile_ent-1)->pile_top_entry;

    }

    if(pile_ent==&entries()[num_piles]){    /* new pile? */

      ++num_piles;

    }

  }

  void finish_algorithm()const

  {

    if(num_piles>0){

      /* Mark those elements which are in their correct position, i.e. those

       * belonging to the longest increasing subsequence. These are those

       * elements linked from the top of the last pile.

       */

      entry* ent=entries()[num_piles-1].pile_top_entry;

      for(std::size_t n=num_piles;n--;){

        ent->ordered=true;

        ent=ent->previous;

      }

    }

  }

  bool is_ordered(void * node)const

  {

    return std::lower_bound(

      entries(),entries()+size_,

      entry(node),entry::less_by_node())->ordered;

  }

private:

  entry* entries()const{return spc.data();}

  auto_space<entry,Allocator> spc;

  std::size_t                 size_;

  std::size_t                 n;

  mutable bool                sorted;

  mutable std::size_t         num_piles;

};

/* The algorithm has three phases:

 *   - Initialization, during which the nodes of the base sequence are added.

 *   - Execution.

 *   - Results querying, through the is_ordered memfun.

 */

template<typename Node,typename Allocator>

class algorithm:private algorithm_base<Allocator>

{

  typedef algorithm_base<Allocator> super;

public:

  algorithm(const Allocator& al,std::size_t size):super(al,size){}

  void add(Node* node)

  {

    super::add(node);

  }

  template<typename IndexIterator>

  void execute(IndexIterator first,IndexIterator last)const

  {

    super::begin_algorithm();

    for(IndexIterator it=first;it!=last;++it){

      add_node_to_algorithm(get_node(it));

    }

    super::finish_algorithm();

  }

  bool is_ordered(Node* node)const

  {

    return super::is_ordered(node);

  }

private:

  void add_node_to_algorithm(Node* node)const

  {

    super::add_node_to_algorithm(node);

  }

  template<typename IndexIterator>

  static Node* get_node(IndexIterator it)

  {

    return static_cast<Node*>(it.get_node());

  }

};

} /* namespace multi_index::detail::index_matcher */

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif