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