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

Revision 857, 5.4 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_NODE_HPP
10#define BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_NODE_HPP
11
12#if defined(_MSC_VER)&&(_MSC_VER>=1200)
13#pragma once
14#endif
15
16#include <algorithm>
17
18namespace boost{
19
20namespace multi_index{
21
22namespace detail{
23
24/* doubly-linked node for use by sequenced_index */
25
26struct sequenced_index_node_impl
27{
28  sequenced_index_node_impl*&       prior(){return prior_;}
29  sequenced_index_node_impl*const & prior()const{return prior_;}
30  sequenced_index_node_impl*&       next(){return next_;}
31  sequenced_index_node_impl*const & next()const{return next_;}
32
33  /* interoperability with index_iterator */
34
35  static void increment(sequenced_index_node_impl*& x){x=x->next();}
36  static void decrement(sequenced_index_node_impl*& x){x=x->prior();}
37
38  /* interoperability with index_proxy */
39
40  static sequenced_index_node_impl* begin(sequenced_index_node_impl* header)
41  {
42    return header->next();
43  }
44
45  static sequenced_index_node_impl* end(sequenced_index_node_impl* header)
46  {
47    return header;
48  }
49
50  /* algorithmic stuff */
51
52  static void link(
53    sequenced_index_node_impl* x,sequenced_index_node_impl* header)
54  {
55    x->prior()=header->prior();
56    x->next()=header;
57    x->prior()->next()=x->next()->prior()=x;
58  };
59
60  static void unlink(sequenced_index_node_impl* x)
61  {
62    x->prior()->next()=x->next();
63    x->next()->prior()=x->prior();
64  }
65
66  static void relink(
67    sequenced_index_node_impl* position,sequenced_index_node_impl* x)
68  {
69    unlink(x);
70    x->prior()=position->prior();
71    x->next()=position;
72    x->prior()->next()=x->next()->prior()=x;
73  }
74
75  static void relink(
76    sequenced_index_node_impl* position,
77    sequenced_index_node_impl* x,sequenced_index_node_impl* y)
78  {
79    /* position is assumed not to be in [x,y) */
80
81    if(x!=y){
82      sequenced_index_node_impl* z=y->prior();
83      x->prior()->next()=y;
84      y->prior()=x->prior();
85      x->prior()=position->prior();
86      z->next()=position;
87      x->prior()->next()=x;
88      z->next()->prior()=z;
89    }
90  }
91
92  static void reverse(sequenced_index_node_impl* header)
93  {
94    sequenced_index_node_impl* x=header;
95    do{
96      sequenced_index_node_impl* y=x->next();
97      std::swap(x->prior(),x->next());
98      x=y;
99    }while(x!=header);
100  }
101
102  static void swap(sequenced_index_node_impl* x,sequenced_index_node_impl* y)
103  {
104    /* This swap function does not exchange the header nodes,
105     * but rather their pointers. This is *not* used for implementing
106     * sequenced_index::swap.
107     */
108
109    if(x->next()!=x){
110      if(y->next()!=y){
111        std::swap(x->next(),y->next());
112        std::swap(x->prior(),y->prior());
113        x->next()->prior()=x->prior()->next()=x;
114        y->next()->prior()=y->prior()->next()=y;
115      }
116      else{
117        y->next()=x->next();
118        y->prior()=x->prior();
119        x->next()=x->prior()=x;
120        y->next()->prior()=y->prior()->next()=y;
121      }
122    }
123    else if(y->next()!=y){
124      x->next()=y->next();
125      x->prior()=y->prior();
126      y->next()=y->prior()=y;
127      x->next()->prior()=x->prior()->next()=x;
128    }
129  }
130
131private:
132  sequenced_index_node_impl();
133
134  sequenced_index_node_impl* prior_;
135  sequenced_index_node_impl* next_;
136};
137
138template<typename Super>
139struct sequenced_index_node_trampoline:sequenced_index_node_impl{};
140
141template<typename Super>
142struct sequenced_index_node:Super,sequenced_index_node_trampoline<Super>
143{
144  sequenced_index_node_impl*&       prior(){return impl_type::prior();}
145  sequenced_index_node_impl*const & prior()const{return impl_type::prior();}
146  sequenced_index_node_impl*&       next(){return impl_type::next();}
147  sequenced_index_node_impl*const & next()const{return impl_type::next();}
148
149  sequenced_index_node_impl*       impl()
150    {return static_cast<impl_type*>(this);}
151  const sequenced_index_node_impl* impl()const
152    {return static_cast<const impl_type*>(this);}
153
154  static sequenced_index_node* from_impl(sequenced_index_node_impl *x)
155    {return static_cast<sequenced_index_node*>(static_cast<impl_type*>(x));}
156  static const sequenced_index_node* from_impl(
157    const sequenced_index_node_impl* x)
158  {
159    return static_cast<const sequenced_index_node*>(
160      static_cast<const impl_type*>(x));
161  }
162
163  /* interoperability with index_iterator */
164
165  static void increment(sequenced_index_node*& x)
166  {
167    sequenced_index_node_impl* xi=x->impl();
168    impl_type::increment(xi);
169    x=from_impl(xi);
170  }
171
172  static void decrement(sequenced_index_node*& x)
173  {
174    sequenced_index_node_impl* xi=x->impl();
175    impl_type::decrement(xi);
176    x=from_impl(xi);
177  }
178
179  /* interoperability with index_proxy */
180
181  static sequenced_index_node* begin(sequenced_index_node* header)
182  {
183    return from_impl(impl_type::begin(header->impl()));
184  }
185
186  static sequenced_index_node* end(sequenced_index_node* header)
187  {
188    return from_impl(impl_type::end(header->impl()));
189  }
190
191private:
192  typedef sequenced_index_node_trampoline<Super> impl_type;
193};
194
195} /* namespace multi_index::detail */
196
197} /* namespace multi_index */
198
199} /* namespace boost */
200
201#endif
Note: See TracBrowser for help on using the repository browser.