[857] | 1 | /* Copyright 2003-2005 Joaquín M López Muñoz.
|
---|
| 2 | * Distributed under the Boost Software License, Version 1.0.
|
---|
| 3 | * (See accompanying file LICENSE_1_0.txt or copy at
|
---|
| 4 | * http://www.boost.org/LICENSE_1_0.txt)
|
---|
| 5 | *
|
---|
| 6 | * See http://www.boost.org/libs/multi_index for library home page.
|
---|
| 7 | */
|
---|
| 8 |
|
---|
| 9 | #ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_HPP
|
---|
| 10 | #define BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_HPP
|
---|
| 11 |
|
---|
| 12 | #if defined(_MSC_VER)&&(_MSC_VER>=1200)
|
---|
| 13 | #pragma once
|
---|
| 14 | #endif
|
---|
| 15 |
|
---|
| 16 | #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
|
---|
| 17 | #include <algorithm>
|
---|
| 18 | #include <boost/noncopyable.hpp>
|
---|
| 19 | #include <boost/multi_index/detail/auto_space.hpp>
|
---|
| 20 | #include <cstddef>
|
---|
| 21 | #include <functional>
|
---|
| 22 |
|
---|
| 23 | namespace boost{
|
---|
| 24 |
|
---|
| 25 | namespace multi_index{
|
---|
| 26 |
|
---|
| 27 | namespace detail{
|
---|
| 28 |
|
---|
| 29 | /* index_matcher compares a sequence of elements against a
|
---|
| 30 | * base sequence, identifying those elements that belong to the
|
---|
| 31 | * longest subsequence which is ordered with respect to the base.
|
---|
| 32 | * For instance, if the base sequence is:
|
---|
| 33 | *
|
---|
| 34 | * 0 1 2 3 4 5 6 7 8 9
|
---|
| 35 | *
|
---|
| 36 | * and the compared sequence (not necesarilly the same length):
|
---|
| 37 | *
|
---|
| 38 | * 1 4 2 3 0 7 8 9
|
---|
| 39 | *
|
---|
| 40 | * the elements of the longest ordered subsequence are:
|
---|
| 41 | *
|
---|
| 42 | * 1 2 3 7 8 9
|
---|
| 43 | *
|
---|
| 44 | * The algorithm for obtaining such a subsequence is called
|
---|
| 45 | * Patience Sorting, described in ch. 1 of:
|
---|
| 46 | * Aldous, D., Diaconis, P.: "Longest increasing subsequences: from
|
---|
| 47 | * patience sorting to the Baik-Deift-Johansson Theorem", Bulletin
|
---|
| 48 | * of the American Mathematical Society, vol. 36, no 4, pp. 413-432,
|
---|
| 49 | * July 1999.
|
---|
| 50 | * http://www.ams.org/bull/1999-36-04/S0273-0979-99-00796-X/
|
---|
| 51 | * S0273-0979-99-00796-X.pdf
|
---|
| 52 | *
|
---|
| 53 | * This implementation is not fully generic since it assumes that
|
---|
| 54 | * the sequences given are pointed to by index iterators (having a
|
---|
| 55 | * get_node() memfun.)
|
---|
| 56 | */
|
---|
| 57 |
|
---|
| 58 | namespace index_matcher{
|
---|
| 59 |
|
---|
| 60 | /* The algorithm stores the nodes of the base sequence and a number
|
---|
| 61 | * of "piles" that are dynamically updated during the calculation
|
---|
| 62 | * stage. From a logical point of view, nodes form an independent
|
---|
| 63 | * sequence from piles. They are stored together so as to minimize
|
---|
| 64 | * allocated memory.
|
---|
| 65 | */
|
---|
| 66 |
|
---|
| 67 | struct entry
|
---|
| 68 | {
|
---|
| 69 | entry(void* node_,std::size_t pos_=0):node(node_),pos(pos_){}
|
---|
| 70 |
|
---|
| 71 | /* node stuff */
|
---|
| 72 |
|
---|
| 73 | void* node;
|
---|
| 74 | std::size_t pos;
|
---|
| 75 | entry* previous;
|
---|
| 76 | bool ordered;
|
---|
| 77 |
|
---|
| 78 | struct less_by_node
|
---|
| 79 | {
|
---|
| 80 | bool operator()(
|
---|
| 81 | const entry& x,const entry& y)const
|
---|
| 82 | {
|
---|
| 83 | return std::less<void*>()(x.node,y.node);
|
---|
| 84 | }
|
---|
| 85 | };
|
---|
| 86 |
|
---|
| 87 | /* pile stuff */
|
---|
| 88 |
|
---|
| 89 | std::size_t pile_top;
|
---|
| 90 | entry* pile_top_entry;
|
---|
| 91 |
|
---|
| 92 | struct less_by_pile_top
|
---|
| 93 | {
|
---|
| 94 | bool operator()(
|
---|
| 95 | const entry& x,const entry& y)const
|
---|
| 96 | {
|
---|
| 97 | return x.pile_top<y.pile_top;
|
---|
| 98 | }
|
---|
| 99 | };
|
---|
| 100 | };
|
---|
| 101 |
|
---|
| 102 | /* common code operating on void *'s */
|
---|
| 103 |
|
---|
| 104 | template<typename Allocator>
|
---|
| 105 | class algorithm_base:private noncopyable
|
---|
| 106 | {
|
---|
| 107 | protected:
|
---|
| 108 | algorithm_base(const Allocator& al,std::size_t size):
|
---|
| 109 | spc(al,size),size_(size),n(0),sorted(false)
|
---|
| 110 | {
|
---|
| 111 | }
|
---|
| 112 |
|
---|
| 113 | void add(void* node)
|
---|
| 114 | {
|
---|
| 115 | entries()[n]=entry(node,n);
|
---|
| 116 | ++n;
|
---|
| 117 | }
|
---|
| 118 |
|
---|
| 119 | void begin_algorithm()const
|
---|
| 120 | {
|
---|
| 121 | if(!sorted){
|
---|
| 122 | std::sort(entries(),entries()+size_,entry::less_by_node());
|
---|
| 123 | sorted=true;
|
---|
| 124 | }
|
---|
| 125 | num_piles=0;
|
---|
| 126 | }
|
---|
| 127 |
|
---|
| 128 | void add_node_to_algorithm(void* node)const
|
---|
| 129 | {
|
---|
| 130 | entry* ent=
|
---|
| 131 | std::lower_bound(
|
---|
| 132 | entries(),entries()+size_,
|
---|
| 133 | entry(node),entry::less_by_node()); /* localize entry */
|
---|
| 134 | ent->ordered=false;
|
---|
| 135 | std::size_t n=ent->pos; /* get its position */
|
---|
| 136 |
|
---|
| 137 | entry dummy(0);
|
---|
| 138 | dummy.pile_top=n;
|
---|
| 139 |
|
---|
| 140 | entry* pile_ent= /* find the first available pile */
|
---|
| 141 | std::lower_bound( /* to stack the entry */
|
---|
| 142 | entries(),entries()+num_piles,
|
---|
| 143 | dummy,entry::less_by_pile_top());
|
---|
| 144 |
|
---|
| 145 | pile_ent->pile_top=n; /* stack the entry */
|
---|
| 146 | pile_ent->pile_top_entry=ent;
|
---|
| 147 |
|
---|
| 148 | /* if not the first pile, link entry to top of the preceding pile */
|
---|
| 149 | if(pile_ent>&entries()[0]){
|
---|
| 150 | ent->previous=(pile_ent-1)->pile_top_entry;
|
---|
| 151 | }
|
---|
| 152 |
|
---|
| 153 | if(pile_ent==&entries()[num_piles]){ /* new pile? */
|
---|
| 154 | ++num_piles;
|
---|
| 155 | }
|
---|
| 156 | }
|
---|
| 157 |
|
---|
| 158 | void finish_algorithm()const
|
---|
| 159 | {
|
---|
| 160 | if(num_piles>0){
|
---|
| 161 | /* Mark those elements which are in their correct position, i.e. those
|
---|
| 162 | * belonging to the longest increasing subsequence. These are those
|
---|
| 163 | * elements linked from the top of the last pile.
|
---|
| 164 | */
|
---|
| 165 |
|
---|
| 166 | entry* ent=entries()[num_piles-1].pile_top_entry;
|
---|
| 167 | for(std::size_t n=num_piles;n--;){
|
---|
| 168 | ent->ordered=true;
|
---|
| 169 | ent=ent->previous;
|
---|
| 170 | }
|
---|
| 171 | }
|
---|
| 172 | }
|
---|
| 173 |
|
---|
| 174 | bool is_ordered(void * node)const
|
---|
| 175 | {
|
---|
| 176 | return std::lower_bound(
|
---|
| 177 | entries(),entries()+size_,
|
---|
| 178 | entry(node),entry::less_by_node())->ordered;
|
---|
| 179 | }
|
---|
| 180 |
|
---|
| 181 | private:
|
---|
| 182 | entry* entries()const{return spc.data();}
|
---|
| 183 |
|
---|
| 184 | auto_space<entry,Allocator> spc;
|
---|
| 185 | std::size_t size_;
|
---|
| 186 | std::size_t n;
|
---|
| 187 | mutable bool sorted;
|
---|
| 188 | mutable std::size_t num_piles;
|
---|
| 189 | };
|
---|
| 190 |
|
---|
| 191 | /* The algorithm has three phases:
|
---|
| 192 | * - Initialization, during which the nodes of the base sequence are added.
|
---|
| 193 | * - Execution.
|
---|
| 194 | * - Results querying, through the is_ordered memfun.
|
---|
| 195 | */
|
---|
| 196 |
|
---|
| 197 | template<typename Node,typename Allocator>
|
---|
| 198 | class algorithm:private algorithm_base<Allocator>
|
---|
| 199 | {
|
---|
| 200 | typedef algorithm_base<Allocator> super;
|
---|
| 201 |
|
---|
| 202 | public:
|
---|
| 203 | algorithm(const Allocator& al,std::size_t size):super(al,size){}
|
---|
| 204 |
|
---|
| 205 | void add(Node* node)
|
---|
| 206 | {
|
---|
| 207 | super::add(node);
|
---|
| 208 | }
|
---|
| 209 |
|
---|
| 210 | template<typename IndexIterator>
|
---|
| 211 | void execute(IndexIterator first,IndexIterator last)const
|
---|
| 212 | {
|
---|
| 213 | super::begin_algorithm();
|
---|
| 214 |
|
---|
| 215 | for(IndexIterator it=first;it!=last;++it){
|
---|
| 216 | add_node_to_algorithm(get_node(it));
|
---|
| 217 | }
|
---|
| 218 |
|
---|
| 219 | super::finish_algorithm();
|
---|
| 220 | }
|
---|
| 221 |
|
---|
| 222 | bool is_ordered(Node* node)const
|
---|
| 223 | {
|
---|
| 224 | return super::is_ordered(node);
|
---|
| 225 | }
|
---|
| 226 |
|
---|
| 227 | private:
|
---|
| 228 | void add_node_to_algorithm(Node* node)const
|
---|
| 229 | {
|
---|
| 230 | super::add_node_to_algorithm(node);
|
---|
| 231 | }
|
---|
| 232 |
|
---|
| 233 | template<typename IndexIterator>
|
---|
| 234 | static Node* get_node(IndexIterator it)
|
---|
| 235 | {
|
---|
| 236 | return static_cast<Node*>(it.get_node());
|
---|
| 237 | }
|
---|
| 238 | };
|
---|
| 239 |
|
---|
| 240 | } /* namespace multi_index::detail::index_matcher */
|
---|
| 241 |
|
---|
| 242 | } /* namespace multi_index::detail */
|
---|
| 243 |
|
---|
| 244 | } /* namespace multi_index */
|
---|
| 245 |
|
---|
| 246 | } /* namespace boost */
|
---|
| 247 |
|
---|
| 248 | #endif
|
---|