/* Copyright 2003-2008 Joaquin M Lopez Munoz. | |
* 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 |