author | hgs |
Thu, 14 Oct 2010 14:15:50 +0530 | |
changeset 72 | 403e7f6ed6c5 |
parent 0 | e4d67989cc36 |
permissions | -rw-r--r-- |
0
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
1 |
// |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
2 |
//======================================================================= |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
3 |
// Copyright 1997-2001 University of Notre Dame. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
4 |
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
5 |
// |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
6 |
// Distributed under the Boost Software License, Version 1.0. (See |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
7 |
// accompanying file LICENSE_1_0.txt or copy at |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
8 |
// http://www.boost.org/LICENSE_1_0.txt) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
9 |
//======================================================================= |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
10 |
// |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
11 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
12 |
#ifndef BOOST_INCREMENTAL_COMPONENTS_HPP |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
13 |
#define BOOST_INCREMENTAL_COMPONENTS_HPP |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
14 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
15 |
#include <boost/detail/iterator.hpp> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
16 |
#include <boost/graph/detail/incremental_components.hpp> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
17 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
18 |
namespace boost { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
19 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
20 |
// A connected component algorithm for the case when dynamically |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
21 |
// adding (but not removing) edges is common. The |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
22 |
// incremental_components() function is a preparing operation. Call |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
23 |
// same_component to check whether two vertices are in the same |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
24 |
// component, or use disjoint_set::find_set to determine the |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
25 |
// representative for a vertex. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
26 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
27 |
// This version of connected components does not require a full |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
28 |
// Graph. Instead, it just needs an edge list, where the vertices of |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
29 |
// each edge need to be of integer type. The edges are assumed to |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
30 |
// be undirected. The other difference is that the result is stored in |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
31 |
// a container, instead of just a decorator. The container should be |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
32 |
// empty before the algorithm is called. It will grow during the |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
33 |
// course of the algorithm. The container must be a model of |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
34 |
// BackInsertionSequence and RandomAccessContainer |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
35 |
// (std::vector is a good choice). After running the algorithm the |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
36 |
// index container will map each vertex to the representative |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
37 |
// vertex of the component to which it belongs. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
38 |
// |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
39 |
// Adapted from an implementation by Alex Stepanov. The disjoint |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
40 |
// sets data structure is from Tarjan's "Data Structures and Network |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
41 |
// Algorithms", and the application to connected components is |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
42 |
// similar to the algorithm described in Ch. 22 of "Intro to |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
43 |
// Algorithms" by Cormen, et. all. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
44 |
// |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
45 |
// RankContainer is a random accessable container (operator[] is |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
46 |
// defined) with a value type that can represent an integer part of |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
47 |
// a binary log of the value type of the corresponding |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
48 |
// ParentContainer (char is always enough) its size_type is no less |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
49 |
// than the size_type of the corresponding ParentContainer |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
50 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
51 |
// An implementation of disjoint sets can be found in |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
52 |
// boost/pending/disjoint_sets.hpp |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
53 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
54 |
template <class EdgeListGraph, class DisjointSets> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
55 |
void incremental_components(EdgeListGraph& g, DisjointSets& ds) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
56 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
57 |
typename graph_traits<EdgeListGraph>::edge_iterator e, end; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
58 |
for (tie(e,end) = edges(g); e != end; ++e) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
59 |
ds.union_set(source(*e,g),target(*e,g)); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
60 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
61 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
62 |
template <class ParentIterator> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
63 |
void compress_components(ParentIterator first, ParentIterator last) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
64 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
65 |
for (ParentIterator current = first; current != last; ++current) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
66 |
detail::find_representative_with_full_compression(first, current-first); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
67 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
68 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
69 |
template <class ParentIterator> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
70 |
typename boost::detail::iterator_traits<ParentIterator>::difference_type |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
71 |
component_count(ParentIterator first, ParentIterator last) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
72 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
73 |
std::ptrdiff_t count = 0; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
74 |
for (ParentIterator current = first; current != last; ++current) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
75 |
if (*current == current - first) ++count; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
76 |
return count; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
77 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
78 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
79 |
// This algorithm can be applied to the result container of the |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
80 |
// connected_components algorithm to normalize |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
81 |
// the components. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
82 |
template <class ParentIterator> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
83 |
void normalize_components(ParentIterator first, ParentIterator last) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
84 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
85 |
for (ParentIterator current = first; current != last; ++current) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
86 |
detail::normalize_node(first, current - first); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
87 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
88 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
89 |
template <class VertexListGraph, class DisjointSets> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
90 |
void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
91 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
92 |
typename graph_traits<VertexListGraph> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
93 |
::vertex_iterator v, vend; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
94 |
for (tie(v, vend) = vertices(G); v != vend; ++v) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
95 |
ds.make_set(*v); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
96 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
97 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
98 |
template <class Vertex, class DisjointSet> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
99 |
inline bool same_component(Vertex u, Vertex v, DisjointSet& ds) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
100 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
101 |
return ds.find_set(u) == ds.find_set(v); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
102 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
103 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
104 |
// considering changing the so that it initializes with a pair of |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
105 |
// vertex iterators and a parent PA. |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
106 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
107 |
template <class IndexT> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
108 |
class component_index |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
109 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
110 |
public://protected: (avoid friends for now) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
111 |
typedef std::vector<IndexT> MyIndexContainer; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
112 |
MyIndexContainer header; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
113 |
MyIndexContainer index; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
114 |
typedef typename MyIndexContainer::size_type SizeT; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
115 |
typedef typename MyIndexContainer::const_iterator IndexIter; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
116 |
public: |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
117 |
typedef detail::component_iterator<IndexIter, IndexT, SizeT> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
118 |
component_iterator; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
119 |
class component { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
120 |
friend class component_index; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
121 |
protected: |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
122 |
IndexT number; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
123 |
const component_index<IndexT>* comp_ind_ptr; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
124 |
component(IndexT i, const component_index<IndexT>* p) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
125 |
: number(i), comp_ind_ptr(p) {} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
126 |
public: |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
127 |
typedef component_iterator iterator; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
128 |
typedef component_iterator const_iterator; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
129 |
typedef IndexT value_type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
130 |
iterator begin() const { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
131 |
return iterator( comp_ind_ptr->index.begin(), |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
132 |
(comp_ind_ptr->header)[number] ); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
133 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
134 |
iterator end() const { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
135 |
return iterator( comp_ind_ptr->index.begin(), |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
136 |
comp_ind_ptr->index.size() ); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
137 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
138 |
}; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
139 |
typedef SizeT size_type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
140 |
typedef component value_type; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
141 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
142 |
#if defined(BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
143 |
template <class Iterator> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
144 |
component_index(Iterator first, Iterator last) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
145 |
: index(std::distance(first, last)) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
146 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
147 |
std::copy(first, last, index.begin()); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
148 |
detail::construct_component_index(index, header); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
149 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
150 |
#else |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
151 |
template <class Iterator> |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
152 |
component_index(Iterator first, Iterator last) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
153 |
: index(first, last) |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
154 |
{ |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
155 |
detail::construct_component_index(index, header); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
156 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
157 |
#endif |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
158 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
159 |
component operator[](IndexT i) const { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
160 |
return component(i, this); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
161 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
162 |
SizeT size() const { |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
163 |
return header.size(); |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
164 |
} |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
165 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
166 |
}; |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
167 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
168 |
} // namespace boost |
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
169 |
|
e4d67989cc36
Revision: 201002
Dremov Kirill (Nokia-D-MSW/Tampere) <kirill.dremov@nokia.com>
parents:
diff
changeset
|
170 |
#endif // BOOST_INCREMENTAL_COMPONENTS_HPP |