source: NonGTP/Boost/boost/multi_index/detail/seq_index_ops.hpp @ 857

Revision 857, 5.2 KB checked in by igarcia, 19 years ago (diff)
Line 
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_SEQ_INDEX_OPS_HPP
10#define BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_OPS_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 <boost/aligned_storage.hpp>
18#include <boost/detail/no_exceptions_support.hpp>
19#include <boost/multi_index/detail/seq_index_node.hpp>
20#include <boost/limits.hpp>
21#include <cstddef>
22
23namespace boost{
24
25namespace multi_index{
26
27namespace detail{
28
29/* Common code for sequenced_index memfuns having templatized and
30 * non-templatized versions.
31 */
32
33template <typename SequencedIndex,typename Predicate>
34void sequenced_index_remove(SequencedIndex& x,Predicate pred)
35{
36  typedef typename SequencedIndex::iterator iterator;
37  iterator first=x.begin(),last=x.end();
38  while(first!=last){
39    if(pred(*first))x.erase(first++);
40    else ++first;
41  }
42}
43
44template <typename SequencedIndex,class BinaryPredicate>
45void sequenced_index_unique(SequencedIndex& x,BinaryPredicate binary_pred)
46{
47  typedef typename SequencedIndex::iterator iterator;
48  iterator first=x.begin();
49  iterator last=x.end();
50  if(first!=last){
51    for(iterator middle=first;++middle!=last;middle=first){
52      if(binary_pred(*middle,*first))x.erase(middle);
53      else first=middle;
54    }
55  }
56}
57
58template <typename SequencedIndex,typename Compare>
59void sequenced_index_merge(SequencedIndex& x,SequencedIndex& y,Compare comp)
60{
61  typedef typename SequencedIndex::iterator iterator;
62  if(x!=y){
63    iterator first0=x.begin(),last0=x.end();
64    iterator first1=y.begin(),last1=y.end();
65    while(first0!=last0&&first1!=last1){
66      if(comp(*first1,*first0))x.splice(first0,y,first1++);
67      else ++first0;
68    }
69    x.splice(last0,y,first1,last1);
70  }
71}
72
73/* sorting  */
74
75/* auxiliary stuff */
76
77template<typename Node,typename Compare>
78void sequenced_index_collate(
79  sequenced_index_node_impl* x,sequenced_index_node_impl* y,Compare comp
80  BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))
81{
82  sequenced_index_node_impl* first0=x->next();
83  sequenced_index_node_impl* last0=x;
84  sequenced_index_node_impl* first1=y->next();
85  sequenced_index_node_impl* last1=y;
86  while(first0!=last0&&first1!=last1){
87    if(comp(Node::from_impl(first1)->value,Node::from_impl(first0)->value)){
88      sequenced_index_node_impl* tmp=first1->next();
89      sequenced_index_node_impl::relink(first0,first1);
90      first1=tmp;
91    }
92    else first0=first0->next();
93  }
94  sequenced_index_node_impl::relink(last0,first1,last1);
95}
96
97template<typename Node,typename Compare>
98void sequenced_index_sort(Node* header,Compare comp)
99{
100  /* Musser's mergesort, see http://www.cs.rpi.edu/~musser/gp/List/lists1.html.
101   * The implementation is a little convoluted: in the original code
102   * counter elements and carry are std::lists: here we do not want
103   * to use multi_index instead, so we do things at a lower level, managing
104   * directly the internal node representation.
105   * Incidentally, the implementations I've seen of this algorithm (SGI,
106   * Dinkumware, STLPort) are not exception-safe: this is. Moreover, we do not
107   * use any dynamic storage.
108   */
109
110  if(header->next()==header->impl()||
111     header->next()->next()==header->impl())return;
112
113  BOOST_STATIC_CONSTANT(
114    std::size_t,
115    max_fill=(std::size_t)std::numeric_limits<std::size_t>::digits+1);
116
117  aligned_storage<
118    sizeof(sequenced_index_node_impl)>      carry_spc;
119  sequenced_index_node_impl&                carry=
120    *static_cast<sequenced_index_node_impl*>(carry_spc.address());
121  aligned_storage<
122    sizeof(
123      sequenced_index_node_impl[max_fill])> counter_spc;
124  sequenced_index_node_impl*                counter=
125    static_cast<sequenced_index_node_impl*>(counter_spc.address());
126  std::size_t                               fill=0;
127
128  carry.prior()=carry.next()=&carry;
129  counter[0].prior()=counter[0].next()=&counter[0];
130
131  BOOST_TRY{
132    while(header->next()!=header->impl()){
133      sequenced_index_node_impl::relink(carry.next(),header->next());
134      std::size_t i=0;
135      while(i<fill&&counter[i].next()!=&counter[i]){
136        sequenced_index_collate<Node>(&carry,&counter[i++],comp);
137      }
138      sequenced_index_node_impl::swap(&carry,&counter[i]);
139      if(i==fill){
140        ++fill;
141        counter[fill].prior()=counter[fill].next()=&counter[fill];
142      }
143    }
144
145    for(std::size_t i=1;i<fill;++i){
146      sequenced_index_collate<Node>(&counter[i],&counter[i-1],comp);
147    }
148    sequenced_index_node_impl::swap(header->impl(),&counter[fill-1]);
149  }
150  BOOST_CATCH(...)
151  {
152    sequenced_index_node_impl::relink(header->impl(),carry.next(),&carry);
153    for(std::size_t i=0;i<=fill;++i){
154      sequenced_index_node_impl::relink(
155        header->impl(),counter[i].next(),&counter[i]);
156    }
157    BOOST_RETHROW;
158  }
159  BOOST_CATCH_END
160}
161
162} /* namespace multi_index::detail */
163
164} /* namespace multi_index */
165
166} /* namespace boost */
167
168#endif
Note: See TracBrowser for help on using the repository browser.