--- /dev/null
+/* Copyright 2003-2007 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
projects / senf.git / blobdiff