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
|
#pragma once
#include <vector>
#include <algorithm>
#include <utility>
#include <type_traits>
#include <cassert>
#include <iostream>
namespace Gudhi_laplacian
{
template <typename T>
class Sparse_vector
{
public:
Sparse_vector() : compressed(true), data()
{
static_assert(std::is_arithmetic<T>::value, "Only arithmetic types are supported.");
}
// Default destructor.
// Default copy-constructor.
// Default assignment operator.
// Default moves.
void compress()
{
if (compressed)
return;
std::vector<std::pair<unsigned int, T> > tmp(data);
data.clear();
std::sort(tmp.begin(), tmp.end());
for (auto it = tmp.cbegin(); it != tmp.cend(); ++it)
{
if (data.empty())
{
if (it->second != T())
{
data.push_back(*it);
}
}
else if (it->first == data.back().first)
{
T x = data.back().second + it->second;
if (x == T())
{
data.pop_back();
}
else
{
data.back().second = x;
}
}
else if (it->second != T())
{
data.push_back(*it);
}
}
compressed = true;
}
inline void add(unsigned int i, T x)
{
data.push_back(std::make_pair(i, x));
compressed = false;
}
static std::vector<Sparse_vector<T> > transpose(const std::vector<Sparse_vector<T> > & x, unsigned int n)
{
unsigned int m = x.size();
std::vector<Sparse_vector<T> > ret(n);
for (unsigned int i = 0; i < m; ++i)
{
const Sparse_vector<T> & a = x[i];
for (auto it = a.cbegin(); it != a.cend(); ++it)
{
assert(it->first < n);
ret[it->first].data.push_back(std::make_pair(i, it->second)); // Avoid add to keep compressed = true.
}
}
return ret;
}
inline const T & operator[](typename std::vector<std::pair<unsigned int, T> >::size_type i)
{
std::cerr << "UNTESTED FUNCTION" << std::endl;
assert(compressed);
auto it = std::lower_bound(data.cbegin(), data.cend(), std::make_pair(i, T()),
[](const std::pair<unsigned int, T> & x, const std::pair<unsigned int, T> & y)
{ return x.first < y.first; });
if (it == data.cend() || it->first != i)
return T();
else
return it->second;
}
inline typename std::vector<std::pair<unsigned int, T> >::size_type size() const { return data.size(); }
inline typename std::vector<std::pair<unsigned int, T> >::size_type nnz() const { return data.size(); }
using Const_iterator = typename std::vector<std::pair<unsigned int, T> >::const_iterator;
inline Const_iterator cbegin() const { return data.cbegin(); }
inline Const_iterator cend() const { return data.cend(); }
inline Const_iterator begin() const { return data.cbegin(); }
inline Const_iterator end() const { return data.cend(); }
private:
bool compressed;
std::vector<std::pair<unsigned int, T> > data;
};
}
|
