williamr@2
|
1 |
/* Copyright 2003-2006 Joaquín M López Muñoz.
|
williamr@2
|
2 |
* Distributed under the Boost Software License, Version 1.0.
|
williamr@2
|
3 |
* (See accompanying file LICENSE_1_0.txt or copy at
|
williamr@2
|
4 |
* http://www.boost.org/LICENSE_1_0.txt)
|
williamr@2
|
5 |
*
|
williamr@2
|
6 |
* See http://www.boost.org/libs/multi_index for library home page.
|
williamr@2
|
7 |
*/
|
williamr@2
|
8 |
|
williamr@2
|
9 |
#ifndef BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_NODE_HPP
|
williamr@2
|
10 |
#define BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_NODE_HPP
|
williamr@2
|
11 |
|
williamr@2
|
12 |
#if defined(_MSC_VER)&&(_MSC_VER>=1200)
|
williamr@2
|
13 |
#pragma once
|
williamr@2
|
14 |
#endif
|
williamr@2
|
15 |
|
williamr@2
|
16 |
#include <algorithm>
|
williamr@2
|
17 |
|
williamr@2
|
18 |
namespace boost{
|
williamr@2
|
19 |
|
williamr@2
|
20 |
namespace multi_index{
|
williamr@2
|
21 |
|
williamr@2
|
22 |
namespace detail{
|
williamr@2
|
23 |
|
williamr@2
|
24 |
/* doubly-linked node for use by sequenced_index */
|
williamr@2
|
25 |
|
williamr@2
|
26 |
struct sequenced_index_node_impl
|
williamr@2
|
27 |
{
|
williamr@2
|
28 |
sequenced_index_node_impl*& prior(){return prior_;}
|
williamr@2
|
29 |
sequenced_index_node_impl* prior()const{return prior_;}
|
williamr@2
|
30 |
sequenced_index_node_impl*& next(){return next_;}
|
williamr@2
|
31 |
sequenced_index_node_impl* next()const{return next_;}
|
williamr@2
|
32 |
|
williamr@2
|
33 |
/* interoperability with bidir_node_iterator */
|
williamr@2
|
34 |
|
williamr@2
|
35 |
static void increment(sequenced_index_node_impl*& x){x=x->next();}
|
williamr@2
|
36 |
static void decrement(sequenced_index_node_impl*& x){x=x->prior();}
|
williamr@2
|
37 |
|
williamr@2
|
38 |
/* algorithmic stuff */
|
williamr@2
|
39 |
|
williamr@2
|
40 |
static void link(
|
williamr@2
|
41 |
sequenced_index_node_impl* x,sequenced_index_node_impl* header)
|
williamr@2
|
42 |
{
|
williamr@2
|
43 |
x->prior()=header->prior();
|
williamr@2
|
44 |
x->next()=header;
|
williamr@2
|
45 |
x->prior()->next()=x->next()->prior()=x;
|
williamr@2
|
46 |
};
|
williamr@2
|
47 |
|
williamr@2
|
48 |
static void unlink(sequenced_index_node_impl* x)
|
williamr@2
|
49 |
{
|
williamr@2
|
50 |
x->prior()->next()=x->next();
|
williamr@2
|
51 |
x->next()->prior()=x->prior();
|
williamr@2
|
52 |
}
|
williamr@2
|
53 |
|
williamr@2
|
54 |
static void relink(
|
williamr@2
|
55 |
sequenced_index_node_impl* position,sequenced_index_node_impl* x)
|
williamr@2
|
56 |
{
|
williamr@2
|
57 |
unlink(x);
|
williamr@2
|
58 |
x->prior()=position->prior();
|
williamr@2
|
59 |
x->next()=position;
|
williamr@2
|
60 |
x->prior()->next()=x->next()->prior()=x;
|
williamr@2
|
61 |
}
|
williamr@2
|
62 |
|
williamr@2
|
63 |
static void relink(
|
williamr@2
|
64 |
sequenced_index_node_impl* position,
|
williamr@2
|
65 |
sequenced_index_node_impl* x,sequenced_index_node_impl* y)
|
williamr@2
|
66 |
{
|
williamr@2
|
67 |
/* position is assumed not to be in [x,y) */
|
williamr@2
|
68 |
|
williamr@2
|
69 |
if(x!=y){
|
williamr@2
|
70 |
sequenced_index_node_impl* z=y->prior();
|
williamr@2
|
71 |
x->prior()->next()=y;
|
williamr@2
|
72 |
y->prior()=x->prior();
|
williamr@2
|
73 |
x->prior()=position->prior();
|
williamr@2
|
74 |
z->next()=position;
|
williamr@2
|
75 |
x->prior()->next()=x;
|
williamr@2
|
76 |
z->next()->prior()=z;
|
williamr@2
|
77 |
}
|
williamr@2
|
78 |
}
|
williamr@2
|
79 |
|
williamr@2
|
80 |
static void reverse(sequenced_index_node_impl* header)
|
williamr@2
|
81 |
{
|
williamr@2
|
82 |
sequenced_index_node_impl* x=header;
|
williamr@2
|
83 |
do{
|
williamr@2
|
84 |
sequenced_index_node_impl* y=x->next();
|
williamr@2
|
85 |
std::swap(x->prior(),x->next());
|
williamr@2
|
86 |
x=y;
|
williamr@2
|
87 |
}while(x!=header);
|
williamr@2
|
88 |
}
|
williamr@2
|
89 |
|
williamr@2
|
90 |
static void swap(sequenced_index_node_impl* x,sequenced_index_node_impl* y)
|
williamr@2
|
91 |
{
|
williamr@2
|
92 |
/* This swap function does not exchange the header nodes,
|
williamr@2
|
93 |
* but rather their pointers. This is *not* used for implementing
|
williamr@2
|
94 |
* sequenced_index::swap.
|
williamr@2
|
95 |
*/
|
williamr@2
|
96 |
|
williamr@2
|
97 |
if(x->next()!=x){
|
williamr@2
|
98 |
if(y->next()!=y){
|
williamr@2
|
99 |
std::swap(x->next(),y->next());
|
williamr@2
|
100 |
std::swap(x->prior(),y->prior());
|
williamr@2
|
101 |
x->next()->prior()=x->prior()->next()=x;
|
williamr@2
|
102 |
y->next()->prior()=y->prior()->next()=y;
|
williamr@2
|
103 |
}
|
williamr@2
|
104 |
else{
|
williamr@2
|
105 |
y->next()=x->next();
|
williamr@2
|
106 |
y->prior()=x->prior();
|
williamr@2
|
107 |
x->next()=x->prior()=x;
|
williamr@2
|
108 |
y->next()->prior()=y->prior()->next()=y;
|
williamr@2
|
109 |
}
|
williamr@2
|
110 |
}
|
williamr@2
|
111 |
else if(y->next()!=y){
|
williamr@2
|
112 |
x->next()=y->next();
|
williamr@2
|
113 |
x->prior()=y->prior();
|
williamr@2
|
114 |
y->next()=y->prior()=y;
|
williamr@2
|
115 |
x->next()->prior()=x->prior()->next()=x;
|
williamr@2
|
116 |
}
|
williamr@2
|
117 |
}
|
williamr@2
|
118 |
|
williamr@2
|
119 |
private:
|
williamr@2
|
120 |
sequenced_index_node_impl* prior_;
|
williamr@2
|
121 |
sequenced_index_node_impl* next_;
|
williamr@2
|
122 |
};
|
williamr@2
|
123 |
|
williamr@2
|
124 |
template<typename Super>
|
williamr@2
|
125 |
struct sequenced_index_node_trampoline:sequenced_index_node_impl{};
|
williamr@2
|
126 |
|
williamr@2
|
127 |
template<typename Super>
|
williamr@2
|
128 |
struct sequenced_index_node:Super,sequenced_index_node_trampoline<Super>
|
williamr@2
|
129 |
{
|
williamr@2
|
130 |
sequenced_index_node_impl*& prior(){return impl_type::prior();}
|
williamr@2
|
131 |
sequenced_index_node_impl* prior()const{return impl_type::prior();}
|
williamr@2
|
132 |
sequenced_index_node_impl*& next(){return impl_type::next();}
|
williamr@2
|
133 |
sequenced_index_node_impl* next()const{return impl_type::next();}
|
williamr@2
|
134 |
|
williamr@2
|
135 |
sequenced_index_node_impl* impl()
|
williamr@2
|
136 |
{return static_cast<impl_type*>(this);}
|
williamr@2
|
137 |
const sequenced_index_node_impl* impl()const
|
williamr@2
|
138 |
{return static_cast<const impl_type*>(this);}
|
williamr@2
|
139 |
|
williamr@2
|
140 |
static sequenced_index_node* from_impl(sequenced_index_node_impl *x)
|
williamr@2
|
141 |
{return static_cast<sequenced_index_node*>(static_cast<impl_type*>(x));}
|
williamr@2
|
142 |
static const sequenced_index_node* from_impl(
|
williamr@2
|
143 |
const sequenced_index_node_impl* x)
|
williamr@2
|
144 |
{
|
williamr@2
|
145 |
return static_cast<const sequenced_index_node*>(
|
williamr@2
|
146 |
static_cast<const impl_type*>(x));
|
williamr@2
|
147 |
}
|
williamr@2
|
148 |
|
williamr@2
|
149 |
/* interoperability with bidir_node_iterator */
|
williamr@2
|
150 |
|
williamr@2
|
151 |
static void increment(sequenced_index_node*& x)
|
williamr@2
|
152 |
{
|
williamr@2
|
153 |
sequenced_index_node_impl* xi=x->impl();
|
williamr@2
|
154 |
impl_type::increment(xi);
|
williamr@2
|
155 |
x=from_impl(xi);
|
williamr@2
|
156 |
}
|
williamr@2
|
157 |
|
williamr@2
|
158 |
static void decrement(sequenced_index_node*& x)
|
williamr@2
|
159 |
{
|
williamr@2
|
160 |
sequenced_index_node_impl* xi=x->impl();
|
williamr@2
|
161 |
impl_type::decrement(xi);
|
williamr@2
|
162 |
x=from_impl(xi);
|
williamr@2
|
163 |
}
|
williamr@2
|
164 |
|
williamr@2
|
165 |
private:
|
williamr@2
|
166 |
typedef sequenced_index_node_trampoline<Super> impl_type;
|
williamr@2
|
167 |
};
|
williamr@2
|
168 |
|
williamr@2
|
169 |
} /* namespace multi_index::detail */
|
williamr@2
|
170 |
|
williamr@2
|
171 |
} /* namespace multi_index */
|
williamr@2
|
172 |
|
williamr@2
|
173 |
} /* namespace boost */
|
williamr@2
|
174 |
|
williamr@2
|
175 |
#endif
|