williamr@2: /* Copyright 2003-2005 Joaquín M López Muñoz. williamr@2: * Distributed under the Boost Software License, Version 1.0. williamr@2: * (See accompanying file LICENSE_1_0.txt or copy at williamr@2: * http://www.boost.org/LICENSE_1_0.txt) williamr@2: * williamr@2: * See http://www.boost.org/libs/multi_index for library home page. williamr@2: */ williamr@2: williamr@2: #ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_HPP williamr@2: #define BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_HPP williamr@2: williamr@2: #if defined(_MSC_VER)&&(_MSC_VER>=1200) williamr@2: #pragma once williamr@2: #endif williamr@2: williamr@2: #include /* keep it first to prevent nasty warns in MSVC */ williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: williamr@2: namespace boost{ williamr@2: williamr@2: namespace multi_index{ williamr@2: williamr@2: namespace detail{ williamr@2: williamr@2: /* index_matcher compares a sequence of elements against a williamr@2: * base sequence, identifying those elements that belong to the williamr@2: * longest subsequence which is ordered with respect to the base. williamr@2: * For instance, if the base sequence is: williamr@2: * williamr@2: * 0 1 2 3 4 5 6 7 8 9 williamr@2: * williamr@2: * and the compared sequence (not necesarilly the same length): williamr@2: * williamr@2: * 1 4 2 3 0 7 8 9 williamr@2: * williamr@2: * the elements of the longest ordered subsequence are: williamr@2: * williamr@2: * 1 2 3 7 8 9 williamr@2: * williamr@2: * The algorithm for obtaining such a subsequence is called williamr@2: * Patience Sorting, described in ch. 1 of: williamr@2: * Aldous, D., Diaconis, P.: "Longest increasing subsequences: from williamr@2: * patience sorting to the Baik-Deift-Johansson Theorem", Bulletin williamr@2: * of the American Mathematical Society, vol. 36, no 4, pp. 413-432, williamr@2: * July 1999. williamr@2: * http://www.ams.org/bull/1999-36-04/S0273-0979-99-00796-X/ williamr@2: * S0273-0979-99-00796-X.pdf williamr@2: * williamr@2: * This implementation is not fully generic since it assumes that williamr@2: * the sequences given are pointed to by index iterators (having a williamr@2: * get_node() memfun.) williamr@2: */ williamr@2: williamr@2: namespace index_matcher{ williamr@2: williamr@2: /* The algorithm stores the nodes of the base sequence and a number williamr@2: * of "piles" that are dynamically updated during the calculation williamr@2: * stage. From a logical point of view, nodes form an independent williamr@2: * sequence from piles. They are stored together so as to minimize williamr@2: * allocated memory. williamr@2: */ williamr@2: williamr@2: struct entry williamr@2: { williamr@2: entry(void* node_,std::size_t pos_=0):node(node_),pos(pos_){} williamr@2: williamr@2: /* node stuff */ williamr@2: williamr@2: void* node; williamr@2: std::size_t pos; williamr@2: entry* previous; williamr@2: bool ordered; williamr@2: williamr@2: struct less_by_node williamr@2: { williamr@2: bool operator()( williamr@2: const entry& x,const entry& y)const williamr@2: { williamr@2: return std::less()(x.node,y.node); williamr@2: } williamr@2: }; williamr@2: williamr@2: /* pile stuff */ williamr@2: williamr@2: std::size_t pile_top; williamr@2: entry* pile_top_entry; williamr@2: williamr@2: struct less_by_pile_top williamr@2: { williamr@2: bool operator()( williamr@2: const entry& x,const entry& y)const williamr@2: { williamr@2: return x.pile_top williamr@2: class algorithm_base:private noncopyable williamr@2: { williamr@2: protected: williamr@2: algorithm_base(const Allocator& al,std::size_t size): williamr@2: spc(al,size),size_(size),n(0),sorted(false) williamr@2: { williamr@2: } williamr@2: williamr@2: void add(void* node) williamr@2: { williamr@2: entries()[n]=entry(node,n); williamr@2: ++n; williamr@2: } williamr@2: williamr@2: void begin_algorithm()const williamr@2: { williamr@2: if(!sorted){ williamr@2: std::sort(entries(),entries()+size_,entry::less_by_node()); williamr@2: sorted=true; williamr@2: } williamr@2: num_piles=0; williamr@2: } williamr@2: williamr@2: void add_node_to_algorithm(void* node)const williamr@2: { williamr@2: entry* ent= williamr@2: std::lower_bound( williamr@2: entries(),entries()+size_, williamr@2: entry(node),entry::less_by_node()); /* localize entry */ williamr@2: ent->ordered=false; williamr@2: std::size_t n=ent->pos; /* get its position */ williamr@2: williamr@2: entry dummy(0); williamr@2: dummy.pile_top=n; williamr@2: williamr@2: entry* pile_ent= /* find the first available pile */ williamr@2: std::lower_bound( /* to stack the entry */ williamr@2: entries(),entries()+num_piles, williamr@2: dummy,entry::less_by_pile_top()); williamr@2: williamr@2: pile_ent->pile_top=n; /* stack the entry */ williamr@2: pile_ent->pile_top_entry=ent; williamr@2: williamr@2: /* if not the first pile, link entry to top of the preceding pile */ williamr@2: if(pile_ent>&entries()[0]){ williamr@2: ent->previous=(pile_ent-1)->pile_top_entry; williamr@2: } williamr@2: williamr@2: if(pile_ent==&entries()[num_piles]){ /* new pile? */ williamr@2: ++num_piles; williamr@2: } williamr@2: } williamr@2: williamr@2: void finish_algorithm()const williamr@2: { williamr@2: if(num_piles>0){ williamr@2: /* Mark those elements which are in their correct position, i.e. those williamr@2: * belonging to the longest increasing subsequence. These are those williamr@2: * elements linked from the top of the last pile. williamr@2: */ williamr@2: williamr@2: entry* ent=entries()[num_piles-1].pile_top_entry; williamr@2: for(std::size_t n=num_piles;n--;){ williamr@2: ent->ordered=true; williamr@2: ent=ent->previous; williamr@2: } williamr@2: } williamr@2: } williamr@2: williamr@2: bool is_ordered(void * node)const williamr@2: { williamr@2: return std::lower_bound( williamr@2: entries(),entries()+size_, williamr@2: entry(node),entry::less_by_node())->ordered; williamr@2: } williamr@2: williamr@2: private: williamr@2: entry* entries()const{return spc.data();} williamr@2: williamr@2: auto_space spc; williamr@2: std::size_t size_; williamr@2: std::size_t n; williamr@2: mutable bool sorted; williamr@2: mutable std::size_t num_piles; williamr@2: }; williamr@2: williamr@2: /* The algorithm has three phases: williamr@2: * - Initialization, during which the nodes of the base sequence are added. williamr@2: * - Execution. williamr@2: * - Results querying, through the is_ordered memfun. williamr@2: */ williamr@2: williamr@2: template williamr@2: class algorithm:private algorithm_base williamr@2: { williamr@2: typedef algorithm_base super; williamr@2: williamr@2: public: williamr@2: algorithm(const Allocator& al,std::size_t size):super(al,size){} williamr@2: williamr@2: void add(Node* node) williamr@2: { williamr@2: super::add(node); williamr@2: } williamr@2: williamr@2: template williamr@2: void execute(IndexIterator first,IndexIterator last)const williamr@2: { williamr@2: super::begin_algorithm(); williamr@2: williamr@2: for(IndexIterator it=first;it!=last;++it){ williamr@2: add_node_to_algorithm(get_node(it)); williamr@2: } williamr@2: williamr@2: super::finish_algorithm(); williamr@2: } williamr@2: williamr@2: bool is_ordered(Node* node)const williamr@2: { williamr@2: return super::is_ordered(node); williamr@2: } williamr@2: williamr@2: private: williamr@2: void add_node_to_algorithm(Node* node)const williamr@2: { williamr@2: super::add_node_to_algorithm(node); williamr@2: } williamr@2: williamr@2: template williamr@2: static Node* get_node(IndexIterator it) williamr@2: { williamr@2: return static_cast(it.get_node()); williamr@2: } williamr@2: }; williamr@2: williamr@2: } /* namespace multi_index::detail::index_matcher */ williamr@2: williamr@2: } /* namespace multi_index::detail */ williamr@2: williamr@2: } /* namespace multi_index */ williamr@2: williamr@2: } /* namespace boost */ williamr@2: williamr@2: #endif