]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright 2005 The Trustees of Indiana University. |
2 | ||
3 | // Distributed under the Boost Software License, Version 1.0. | |
4 | // (See accompanying file LICENSE_1_0.txt or copy at | |
5 | // http://www.boost.org/LICENSE_1_0.txt) | |
6 | ||
7 | // Authors: Jeremiah Willcock | |
8 | // Douglas Gregor | |
9 | // Andrew Lumsdaine | |
10 | ||
11 | // Indexed properties -- used for CSR and CSR-like graphs | |
12 | ||
13 | #ifndef BOOST_GRAPH_INDEXED_PROPERTIES_HPP | |
14 | #define BOOST_GRAPH_INDEXED_PROPERTIES_HPP | |
15 | ||
16 | #include <vector> | |
17 | #include <utility> | |
18 | #include <algorithm> | |
19 | #include <climits> | |
20 | #include <iterator> | |
21 | #include <boost/graph/graph_traits.hpp> | |
22 | #include <boost/graph/properties.hpp> | |
23 | #include <boost/iterator/counting_iterator.hpp> | |
24 | #include <boost/integer.hpp> | |
25 | #include <boost/iterator/iterator_facade.hpp> | |
26 | #include <boost/property_map/property_map.hpp> | |
27 | #include <boost/mpl/if.hpp> | |
28 | ||
29 | namespace boost { | |
30 | namespace detail { | |
31 | ||
32 | template<typename Derived, typename Property, typename Descriptor, typename IndexMap> | |
33 | class indexed_vertex_properties | |
34 | { | |
35 | public: | |
36 | typedef no_property vertex_property_type; | |
37 | typedef Property vertex_bundled; | |
38 | typedef iterator_property_map< | |
39 | typename std::vector<Property>::iterator, | |
40 | IndexMap> vertex_map_type; | |
41 | typedef iterator_property_map< | |
42 | typename std::vector<Property>::const_iterator, | |
43 | IndexMap> const_vertex_map_type; | |
44 | ||
45 | // Directly access a vertex or edge bundle | |
46 | Property& operator[](Descriptor v) | |
47 | { return m_vertex_properties[get(vertex_index, derived(), v)]; } | |
48 | ||
49 | const Property& operator[](Descriptor v) const | |
50 | { return m_vertex_properties[get(vertex_index, derived(), v)]; } | |
51 | ||
52 | vertex_map_type get_vertex_bundle(const IndexMap& index_map = IndexMap()) { | |
53 | return vertex_map_type(m_vertex_properties.begin(), index_map); | |
54 | } | |
55 | ||
56 | const_vertex_map_type get_vertex_bundle(const IndexMap& index_map = IndexMap()) const { | |
57 | return const_vertex_map_type(m_vertex_properties.begin(), index_map); | |
58 | } | |
59 | ||
60 | protected: | |
61 | // Default-construct with no property values | |
62 | indexed_vertex_properties() {} | |
63 | ||
64 | // Initialize with n default-constructed property values | |
65 | indexed_vertex_properties(std::size_t n) : m_vertex_properties(n) { } | |
66 | ||
67 | public: | |
68 | // Clear the properties vector | |
69 | void clear() | |
70 | { | |
71 | m_vertex_properties.clear(); | |
72 | } | |
73 | ||
74 | // Resize the properties vector | |
75 | void resize(std::size_t n) | |
76 | { | |
77 | m_vertex_properties.resize(n); | |
78 | } | |
79 | ||
80 | // Reserve space in the vector of properties | |
81 | void reserve(std::size_t n) | |
82 | { | |
83 | m_vertex_properties.reserve(n); | |
84 | } | |
85 | ||
86 | // Add a new property value to the back | |
87 | void push_back(const Property& prop) | |
88 | { | |
89 | m_vertex_properties.push_back(prop); | |
90 | } | |
91 | ||
92 | // Write an element by raw index | |
93 | void write_by_index(std::size_t idx, const Property& prop) | |
94 | { | |
95 | m_vertex_properties[idx] = prop; | |
96 | } | |
97 | ||
98 | // Access to the derived object | |
99 | Derived& derived() { return *static_cast<Derived*>(this); } | |
100 | ||
101 | const Derived& derived() const | |
102 | { return *static_cast<const Derived*>(this); } | |
103 | ||
104 | public: // should be private, but friend templates not portable | |
105 | std::vector<Property> m_vertex_properties; | |
106 | }; | |
107 | ||
108 | template<typename Derived, typename Descriptor, typename IndexMap> | |
109 | class indexed_vertex_properties<Derived, void, Descriptor, IndexMap> | |
110 | { | |
111 | struct secret {}; | |
112 | ||
113 | public: | |
114 | typedef no_property vertex_property_type; | |
115 | typedef void vertex_bundled; | |
116 | typedef secret vertex_map_type; | |
117 | typedef secret const_vertex_map_type; | |
118 | ||
119 | secret operator[](secret) { return secret(); } | |
120 | ||
121 | vertex_map_type get_vertex_bundle() const { | |
122 | return vertex_map_type(); | |
123 | } | |
124 | ||
125 | protected: | |
126 | // All operations do nothing. | |
127 | indexed_vertex_properties() { } | |
128 | indexed_vertex_properties(std::size_t) { } | |
129 | ||
130 | public: | |
131 | void clear() { } | |
132 | void resize(std::size_t) { } | |
133 | void reserve(std::size_t) { } | |
134 | }; | |
135 | ||
136 | template<typename Derived, typename Property, typename Descriptor, typename IndexMap> | |
137 | class indexed_edge_properties | |
138 | { | |
139 | public: | |
140 | typedef no_property edge_property_type; | |
141 | typedef Property edge_bundled; | |
142 | typedef Property edge_push_back_type; | |
143 | typedef iterator_property_map< | |
144 | typename std::vector<Property>::iterator, | |
145 | IndexMap> edge_map_type; | |
146 | typedef iterator_property_map< | |
147 | typename std::vector<Property>::const_iterator, | |
148 | IndexMap> const_edge_map_type; | |
149 | ||
150 | // Directly access a edge or edge bundle | |
151 | Property& operator[](Descriptor v) | |
152 | { return m_edge_properties[get(edge_index, derived(), v)]; } | |
153 | ||
154 | const Property& operator[](Descriptor v) const | |
155 | { return m_edge_properties[get(edge_index, derived(), v)]; } | |
156 | ||
157 | edge_map_type get_edge_bundle(const IndexMap& index_map = IndexMap()) { | |
158 | return edge_map_type(m_edge_properties.begin(), index_map); | |
159 | } | |
160 | ||
161 | const_edge_map_type get_edge_bundle(const IndexMap& index_map = IndexMap()) const { | |
162 | return const_edge_map_type(m_edge_properties.begin(), index_map); | |
163 | } | |
164 | ||
165 | protected: | |
166 | // Default-construct with no property values | |
167 | indexed_edge_properties() {} | |
168 | ||
169 | // Initialize with n default-constructed property values | |
170 | indexed_edge_properties(std::size_t n) : m_edge_properties(n) { } | |
171 | ||
172 | // Get the size of the properties vector | |
173 | std::size_t size() const | |
174 | { | |
175 | return m_edge_properties.size(); | |
176 | } | |
177 | ||
178 | // Clear the properties vector | |
179 | void clear() | |
180 | { | |
181 | m_edge_properties.clear(); | |
182 | } | |
183 | ||
184 | // Resize the properties vector | |
185 | void resize(std::size_t n) | |
186 | { | |
187 | m_edge_properties.resize(n); | |
188 | } | |
189 | ||
190 | // Reserve space in the vector of properties | |
191 | void reserve(std::size_t n) | |
192 | { | |
193 | m_edge_properties.reserve(n); | |
194 | } | |
195 | ||
196 | // Write an element by raw index | |
197 | void write_by_index(std::size_t idx, const Property& prop) | |
198 | { | |
199 | m_edge_properties[idx] = prop; | |
200 | } | |
201 | ||
202 | public: | |
203 | // Add a new property value to the back | |
204 | void push_back(const Property& prop) | |
205 | { | |
206 | m_edge_properties.push_back(prop); | |
207 | } | |
208 | ||
209 | // Move range of properties backwards | |
210 | void move_range(std::size_t src_begin, std::size_t src_end, std::size_t dest_begin) { | |
211 | std::copy_backward( | |
212 | m_edge_properties.begin() + src_begin, | |
213 | m_edge_properties.begin() + src_end, | |
214 | m_edge_properties.begin() + dest_begin + (src_end - src_begin)); | |
215 | } | |
216 | ||
217 | typedef typename std::vector<Property>::iterator iterator; | |
218 | iterator begin() {return m_edge_properties.begin();} | |
219 | iterator end() {return m_edge_properties.end();} | |
220 | ||
221 | private: | |
222 | // Access to the derived object | |
223 | Derived& derived() { return *static_cast<Derived*>(this); } | |
224 | ||
225 | const Derived& derived() const | |
226 | { return *static_cast<const Derived*>(this); } | |
227 | ||
228 | public: // should be private, but friend templates not portable | |
229 | std::vector<Property> m_edge_properties; | |
230 | }; | |
231 | ||
232 | struct dummy_no_property_iterator | |
233 | : public boost::iterator_facade<dummy_no_property_iterator, no_property, std::random_access_iterator_tag> { | |
234 | mutable no_property prop; | |
235 | no_property& dereference() const {return prop;} | |
236 | bool equal(const dummy_no_property_iterator&) const {return true;} | |
237 | void increment() {} | |
238 | void decrement() {} | |
239 | void advance(std::ptrdiff_t) {} | |
240 | std::ptrdiff_t distance_to(const dummy_no_property_iterator) const {return 0;} | |
241 | }; | |
242 | ||
243 | template<typename Derived, typename Descriptor, typename IndexMap> | |
244 | class indexed_edge_properties<Derived, void, Descriptor, IndexMap> | |
245 | { | |
246 | struct secret {}; | |
247 | ||
248 | public: | |
249 | typedef no_property edge_property_type; | |
250 | typedef void edge_bundled; | |
251 | typedef void* edge_push_back_type; | |
252 | typedef secret edge_map_type; | |
253 | typedef secret const_edge_map_type; | |
254 | ||
255 | secret operator[](secret) { return secret(); } | |
256 | void write_by_index(std::size_t /*idx*/, const no_property& /*prop*/) {} | |
257 | ||
258 | edge_map_type get_edge_bundle(const IndexMap& = IndexMap()) const { | |
259 | return edge_map_type(); | |
260 | } | |
261 | ||
262 | protected: | |
263 | // All operations do nothing. | |
264 | indexed_edge_properties() { } | |
265 | indexed_edge_properties(std::size_t) { } | |
266 | std::size_t size() const {return 0;} | |
267 | void clear() { } | |
268 | void resize(std::size_t) { } | |
269 | void reserve(std::size_t) { } | |
270 | ||
271 | public: | |
272 | void push_back(const edge_push_back_type&) { } | |
273 | void move_range(std::size_t /*src_begin*/, std::size_t /*src_end*/, std::size_t /*dest_begin*/) {} | |
274 | ||
275 | typedef dummy_no_property_iterator iterator; | |
276 | iterator begin() {return dummy_no_property_iterator();} | |
277 | iterator end() {return dummy_no_property_iterator();} | |
278 | ||
279 | }; | |
280 | ||
281 | } | |
282 | } | |
283 | ||
284 | #endif // BOOST_GRAPH_INDEXED_PROPERTIES_HPP |