-
Notifications
You must be signed in to change notification settings - Fork 1
/
array.cpp
162 lines (131 loc) · 4.83 KB
/
array.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <cslibs_indexed_storage/storage.hpp>
#include <cslibs_indexed_storage/backend/array/array.hpp>
#include <cslibs_indexed_storage/operations/clustering.hpp>
#include <vector>
#include <iostream>
#include <map>
using namespace cslibs_indexed_storage;
using namespace cslibs_indexed_storage::backend;
using namespace cslibs_indexed_storage::operations;
namespace
{
//! we simuate 2D points, discreticed by their integer value
using Index = std::array<int, 2>;
//! define the data
struct Data
{
Index index;
int cluster = -1; //!< cluster index of this chunk
std::vector<int> indices; //!< indices of the points stored in this chunk
Data() = default; //!< \todo Data type must be default constructbile
Data(Index index, int id) : //!< Actual data constructor
index(index)
{
indices.push_back(id);
}
void merge(const Data& other) //!< merge operation between old and to-be-inserted data
{
indices.insert(indices.end(), other.indices.begin(), other.indices.end());
}
};
//! clustering method we are using
struct ClusterOp
{
//! called when a new cluster should be started
bool start(const Index&, Data& data)
{
if (data.cluster != -1)
return false;
current_cluster +=1;
data.cluster = current_cluster;
return true;
}
//! called when a cluster is extended due to found neighbors
bool extend(const Index&, const Index&, Data& data)
{
if (data.cluster != -1)
return false;
data.cluster = current_cluster;
return true;
}
//! used neighborhood, look at direct neighbors only
using neighborhood_t = operations::clustering::GridNeighborhoodStatic<std::tuple_size<Index>::value, 3>;
using visitor_index_t = neighborhood_t::offset_t; //!< currently needed by the clustering API
//! vistor implementation for neighbors
template<typename visitor_t>
void visit_neighbours(const Index&, const visitor_t& visitior)
{
static constexpr auto neighborhood = neighborhood_t{};
neighborhood.visit(visitior);
}
int current_cluster = -1; //!< keep track of the current cluster index
};
}
namespace cslibs_indexed_storage
{
template<>
struct auto_index<Data>
{
using index_t = std::array<int, 2>;
inline index_t index(const Data& data) const
{
return data.index;
}
};
}
int main()
{
std::vector<Data> datas;
{
int i = 0;
// 3 points at (0, 0)
datas.emplace_back(Index{0, 0}, i++);
datas.emplace_back(Index{0, 0}, i++);
datas.emplace_back(Index{0, 0}, i++);
// 2 points at (0, 1), should be joined to (0,0)
datas.emplace_back(Index{0, 1}, i++);
datas.emplace_back(Index{0, 1}, i++);
// 3 points at (2, 0), should be separted
datas.emplace_back(Index{2, 0}, i++);
datas.emplace_back(Index{2, 0}, i++);
datas.emplace_back(Index{2, 0}, i++);
// 1 point at (3, -1), should be joined to (2, 0)
datas.emplace_back(Index{3, -1}, i++);
}
using StorageType = AutoIndexStorage<interface::non_owning<Data>, array::Array>;
// generate some test data
StorageType storage;
// dynamically calculate index bounds with storage.get_indexer();
storage.set<option::tags::array_size>(10ul, 10ul);
storage.set<option::tags::array_offset>(-5, -5);
{
for (auto& data : datas)
storage.insert(&data);
}
// do the actual clustering
ClusterOp clusters;
{
clustering::Clustering<StorageType> clusterer(storage);
clusterer.cluster(clusters);
}
// print clustering results
{
std::cout << "Clusters Found: " << clusters.current_cluster + 1 << std::endl;
// this map may be also generated in ClusterOp during start(...) and extend(...)
std::map<int, std::vector<int>> cluster_indices;
storage.traverse([&cluster_indices](const Index& index, const Data& data)
{
std::cout << "Entry at (" << index[0] << ", " << index[1] << "): indices = ";
std::copy(data.indices.begin(), data.indices.end(), std::ostream_iterator<int>(std::cout, ", "));
std::cout << " cluster = " << data.cluster << std::endl;
auto& cluster_idxs = cluster_indices[data.cluster];
cluster_idxs.insert(cluster_idxs.end(), data.indices.begin(), data.indices.end());
});
for (const auto& entry : cluster_indices)
{
std::cout << "Cluster: index = " << entry.first << ", indices = ";
std::copy(entry.second.begin(), entry.second.end(), std::ostream_iterator<int>(std::cout, ", "));
std::cout << std::endl;
}
}
}