35#include <itpp/itexports.h>
41template <
class T>
class Vec;
43template <
class T>
class Sparse_Vec;
49Sparse_Vec<T>
operator+(
const Sparse_Vec<T> &v1,
const Sparse_Vec<T> &v2);
53T
operator*(
const Sparse_Vec<T> &v1,
const Sparse_Vec<T> &v2);
57T
operator*(
const Sparse_Vec<T> &v1,
const Vec<T> &v2);
61T
operator*(
const Vec<T> &v1,
const Sparse_Vec<T> &v2);
65Sparse_Vec<T>
elem_mult(
const Sparse_Vec<T> &v1,
const Sparse_Vec<T> &v2);
69Vec<T>
elem_mult(
const Sparse_Vec<T> &v1,
const Vec<T> &v2);
73Sparse_Vec<T>
elem_mult_s(
const Sparse_Vec<T> &v1,
const Vec<T> &v2);
77Vec<T>
elem_mult(
const Vec<T> &v1,
const Sparse_Vec<T> &v2);
81Sparse_Vec<T>
elem_mult_s(
const Vec<T> &v1,
const Sparse_Vec<T> &v2);
87 template <
typename NumT>
struct Sparse_Eps_Type_Selector;
88 template <>
struct Sparse_Eps_Type_Selector<double> {
typedef double eps_type;};
89 template <>
struct Sparse_Eps_Type_Selector<
std::complex<double> > {
typedef double eps_type;};
90 template <>
struct Sparse_Eps_Type_Selector<int> {
typedef int eps_type;};
91 template <>
struct Sparse_Eps_Type_Selector<short> {
typedef short eps_type;};
92 template <>
struct Sparse_Eps_Type_Selector<
itpp::bin> {
typedef int eps_type;};
155 int size()
const {
return v_size; }
159 if (check_small_elems_flag) {
231 if (check_small_elems_flag) {
239 if (check_small_elems_flag) {
247 if (check_small_elems_flag) {
255 if (check_small_elems_flag) {
329 int v_size, used_size, data_size;
332 typename details::Sparse_Eps_Type_Selector<T>::eps_type eps;
333 bool check_small_elems_flag;
366 check_small_elems_flag =
true;
372 if (data_size != 0) {
373 data =
new T[data_size];
374 index =
new int[data_size];
379void Sparse_Vec<T>::free()
408 used_size =
v.used_size;
409 data_size =
v.data_size;
411 check_small_elems_flag =
v.check_small_elems_flag;
414 for (
int i = 0;
i < used_size;
i++) {
416 index[
i] =
v.index[
i];
426 data_size = std::min(
v.
size(), 10000);
429 for (
int i = 0;
i < v_size;
i++) {
431 if (used_size == data_size)
432 resize_data(data_size*2);
434 index[used_size] =
i;
447 data_size = std::min(
v.
size(), 10000);
448 eps = std::abs(epsilon);
451 for (
int i = 0;
i < v_size;
i++) {
452 if (std::abs(
v(
i)) >
eps) {
453 if (used_size == data_size)
454 resize_data(data_size*2);
456 index[used_size] =
i;
484 if (check_small_elems_flag) {
485 remove_small_elements();
488 return double(used_size) / v_size;
494 eps = std::abs(epsilon);
495 remove_small_elements();
505 for (
i = 0;
i < used_size;
i++) {
519 check_small_elems_flag =
false;
526 it_assert(
new_size >= used_size,
"Sparse_Vec<T>::resize_data(int new_size): New size is to small");
536 for (
int p = 0; p < used_size; p++) {
549 if (check_small_elems_flag) {
550 remove_small_elements();
552 resize_data(used_size);
561 for (
int p = 0; p < used_size; p++)
562 v(index[p]) =
data[p];
577 it_assert_debug(
i >= 0 &&
i < v_size,
"The index of the element is out of range");
581 for (p = 0; p < used_size; p++) {
593 it_assert_debug(
i >= 0 &&
i < v_size,
"The index of the element is out of range");
599 for (p = 0; p < used_size; p++) {
611 if (used_size == data_size)
612 resize_data(data_size*2 + 100);
614 index[used_size] =
i;
619 if (std::abs(
v) <=
eps) {
620 remove_small_elements();
628 it_assert_debug(v_size >
i,
"The index of the element exceeds the size of the sparse vector");
631 if (std::abs(
v) >
eps) {
632 if (used_size == data_size)
633 resize_data(data_size*2 + 100);
635 index[used_size] =
i;
646 it_assert_debug(v_size >
i,
"The index of the element exceeds the size of the sparse vector");
648 for (p = 0; p < used_size; p++) {
657 if (used_size == data_size)
658 resize_data(data_size*2 + 100);
660 index[used_size] =
i;
664 check_small_elems_flag =
true;
678 for (q = 0; q <
nrof_nz; q++) {
680 for (p = 0; p < used_size; p++) {
689 if (used_size == data_size)
690 resize_data(data_size*2 + 100);
691 data[used_size] =
v(q);
692 index[used_size] =
i;
698 check_small_elems_flag =
true;
706 check_small_elems_flag =
false;
715 it_assert_debug(v_size >
i,
"The index of the element exceeds the size of the sparse vector");
717 for (p = 0; p < used_size; p++) {
725 index[p] = index[used_size-1];
734 check_small_elems_flag =
false;
743 it_assert_debug(v_size >
i,
"The index of the element exceeds the size of the sparse vector");
745 for (p = 0; p < used_size; p++) {
753 index[p] = index[used_size-1];
781 for (q = 0; q <
nrof_nz; q++) {
782 if (std::abs(
v[q]) >
eps) {
783 if (used_size == data_size)
784 resize_data(data_size*2 + 100);
785 data[used_size] =
v(q);
797 for (
int i = 0;
i < n;
i++) {
798 r(
i) = get_nz_index(
i);
810 for (
int p = 0; p < used_size; p++) {
811 if (index[p] >=
i1 && index[p] <=
i2) {
812 if (r.used_size == r.data_size)
813 r.resize_data(r.data_size*2 + 100);
815 r.index[r.used_size] = index[p] -
i1;
820 r.check_small_elems_flag = check_small_elems_flag;
830 for (
int p = 0; p < used_size; p++)
841 used_size =
v.used_size;
842 data_size =
v.data_size;
844 check_small_elems_flag =
v.check_small_elems_flag;
847 for (
int i = 0;
i < used_size;
i++) {
849 index[
i] =
v.index[
i];
859 data_size = std::min(
v.
size(), 10000);
860 eps = std::abs(T(0));
861 check_small_elems_flag =
false;
864 for (
int i = 0;
i < v_size;
i++) {
866 if (used_size == data_size)
867 resize_data(data_size*2);
869 index[used_size] =
i;
881 for (
int p = 0; p < used_size; p++) {
882 r.data[p] = -
data[p];
883 r.index[p] = index[p];
885 r.used_size = used_size;
897 if (check_small_elems_flag)
898 remove_small_elements();
900 if (v_size !=
v.v_size) {
905 for (p = 0;p < used_size;p++) {
906 for (q = 0;q <
v.used_size;q++) {
907 if (index[p] ==
v.index[q]) {
926 if (used_size !=
v.used_size) {
927 if (used_size >
v.used_size) {
934 for (q = 0;q <
v.used_size;q++) {
935 if (std::abs(
v.
data[q]) <=
v.eps)
964 check_small_elems_flag =
true;
978 check_small_elems_flag =
true;
998 check_small_elems_flag =
true;
1012 check_small_elems_flag =
true;
1020 for (p = 0; p < used_size; p++) {
1024 check_small_elems_flag =
true;
1031 for (p = 0; p < used_size; p++) {
1036 check_small_elems_flag =
true;
1048 for (
int p = 0; p <
v2.used_size; p++) {
1049 if (
v1f[
v2.index[p]] != T(0))
1062 for (
int p1 = 0;
p1 <
v1.used_size;
p1++)
1074 for (
int p2 = 0;
p2 <
v2.used_size;
p2++)
1086 ivec pos(
v1.v_size);
1088 for (
int p1 = 0;
p1 <
v1.used_size;
p1++)
1090 for (
int p2 = 0;
p2 <
v2.used_size;
p2++) {
1091 if (pos[
v2.index[
p2]] != -1) {
1092 if (r.used_size == r.data_size)
1093 r.resize_data(r.used_size*2 + 100);
1095 r.index[r.used_size] =
v2.index[
p2];
1111 for (
int p1 = 0;
p1 <
v1.used_size;
p1++)
1123 for (
int p1 = 0;
p1 <
v1.used_size;
p1++) {
1124 if (
v2[
v1.index[
p1]] != T(0)) {
1125 if (r.used_size == r.data_size)
1126 r.resize_data(r.used_size*2 + 100);
1128 r.index[r.used_size] =
v1.index[
p1];
1144 for (
int p2 = 0;
p2 <
v2.used_size;
p2++)
1156 for (
int p2 = 0;
p2 <
v2.used_size;
p2++) {
1157 if (
v1[
v2.index[
p2]] != T(0)) {
1158 if (r.used_size == r.data_size)
1159 r.resize_data(r.used_size*2 + 100);
1161 r.index[r.used_size] =
v2.index[
p2];
1176 ivec pos(
v1.v_size);
1178 for (
int p1 = 0;
p1 <
v1.used_size;
p1++)
1180 for (
int p2 = 0;
p2 <
v2.used_size;
p2++) {
1181 if (pos[
v2.index[
p2]] == -1) {
1182 if (r.used_size == r.data_size)
1183 r.resize_data(r.used_size*2 + 100);
1185 r.index[r.used_size] =
v2.index[
p2];
1191 r.check_small_elems_flag =
true;
1228ITPP_EXPORT_TEMPLATE
template class ITPP_EXPORT Sparse_Vec<int>;
1229ITPP_EXPORT_TEMPLATE
template class ITPP_EXPORT Sparse_Vec<double>;
1230ITPP_EXPORT_TEMPLATE
template class ITPP_EXPORT Sparse_Vec<std::complex<double> >;
1232ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT sparse_ivec
operator+(
const sparse_ivec &,
1233 const sparse_ivec &);
1234ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT sparse_vec
operator+(
const sparse_vec &,
1235 const sparse_vec &);
1236ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT sparse_cvec
operator+(
const sparse_cvec &,
1237 const sparse_cvec &);
1239ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT
int operator*(
const sparse_ivec &,
const sparse_ivec &);
1240ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT
double operator*(
const sparse_vec &,
const sparse_vec &);
1241ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT std::complex<double>
operator*(
const sparse_cvec &,
1242 const sparse_cvec &);
1244ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT
int operator*(
const sparse_ivec &,
const ivec &);
1245ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT
double operator*(
const sparse_vec &,
const vec &);
1246ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT std::complex<double>
operator*(
const sparse_cvec &,
1249ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT
int operator*(
const ivec &,
const sparse_ivec &);
1250ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT
double operator*(
const vec &,
const sparse_vec &);
1251ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT std::complex<double>
operator*(
const cvec &,
1252 const sparse_cvec &);
1254ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT sparse_ivec
elem_mult(
const sparse_ivec &,
1255 const sparse_ivec &);
1256ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT sparse_vec
elem_mult(
const sparse_vec &,
const sparse_vec &);
1257ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT sparse_cvec
elem_mult(
const sparse_cvec &,
1258 const sparse_cvec &);
1260ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT ivec
elem_mult(
const sparse_ivec &,
const ivec &);
1261ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT vec
elem_mult(
const sparse_vec &,
const vec &);
1262ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT cvec
elem_mult(
const sparse_cvec &,
const cvec &);
1264ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT sparse_ivec
elem_mult_s(
const sparse_ivec &,
const ivec &);
1265ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT sparse_vec
elem_mult_s(
const sparse_vec &,
const vec &);
1266ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT sparse_cvec
elem_mult_s(
const sparse_cvec &,
const cvec &);
1268ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT ivec
elem_mult(
const ivec &,
const sparse_ivec &);
1269ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT vec
elem_mult(
const vec &,
const sparse_vec &);
1270ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT cvec
elem_mult(
const cvec &,
const sparse_cvec &);
1272ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT sparse_ivec
elem_mult_s(
const ivec &,
const sparse_ivec &);
1273ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT sparse_vec
elem_mult_s(
const vec &,
const sparse_vec &);
1274ITPP_EXPORT_TEMPLATE
template ITPP_EXPORT sparse_cvec
elem_mult_s(
const cvec &,
const sparse_cvec &);
void alloc(int n)
Allocate storage for an array of length n.
void free()
Free the storage space allocated by the array.
int size() const
Returns the number of data elements in the array object.
T * data
A pointer to the data area.
void set_size(int n, bool copy=false)
Resizing an Array<T>.
Templated sparse vector class.
void set(int i, T v)
Set element i equal to v.
void operator-=(const Vec< T > &v)
Subtract vector v from all non-zero elements of the sparse vector.
Sparse_Vec(const Vec< T > &v, T epsilon)
Initiate a new sparse vector from a dense vector. Elements of v larger than epsilon are copied into t...
Sparse_Vec< T > get_subvector(int i1, int i2) const
Return sparse subvector from index i1 to index i2.
void operator/=(const T &v)
Divide all non-zero elements of the sparse vector with the scalar v.
void set_size(int sz, int data_init=-1)
Set the size sz of the sparse vector. Default value data_init=-1 => allocated size for the data is no...
void zeros()
Set the sparse vector to the all zero vector (removes all non-zero elements)
Sparse_Vec()
Default constructor.
T get_nz_data(int p)
Returns the p-th non-zero data element.
bool operator==(const Sparse_Vec< T > &v)
Compare two sparse vectors. False if wrong sizes or different values.
ivec get_nz_indices()
Return the indices of non-zero values.
void set_new(int i, T v)
Set a new element with index i equal to v.
int nnz()
Number of non-zero elements in the sparse vector.
T operator()(int i) const
Returns the element with index i.
void add_elem(const int i, const T v)
Add element i with v.
void operator-=(const Sparse_Vec< T > &v)
Subtract sparse vector v from all non-zero elements of the sparse vector.
void set_small_element(const T &epsilon)
Set that all elements smaller than epsilon should be set to zero.
void operator*=(const T &v)
Multiply the scalar v to all non-zero elements of the sparse vector.
void clear_elem(const int i)
Clear the i-th element (if it contains a non-zero value)
void zero_elem(const int i)
Set the i-th element to zero (i.e. clear that element if it contains a non-zero value)
void get_nz_data(int p, T &data_out)
Extract the reference to the p-th non-zero data element.
Sparse_Vec< int > sparse_ivec
Type definition of an integer sparse vector.
double density()
Returns the density of the sparse vector: (number of non-zero elements)/(size of the vector)
void add(const ivec &index_vec, const Vec< T > &v)
Add v to the elements specified by index_vec with v.
Sparse_Vec(const Sparse_Vec< T > &v)
Initiate a new sparse vector.
Sparse_Vec(int sz, int data_init=200)
Initiate an empty sparse vector.
int get_nz_index(int p)
Returns the vector index of the p-th non-zero element.
Sparse_Vec< std::complex< double > > sparse_cvec
Type definition of a complex<double> sparse vector.
void operator+=(const Vec< T > &v)
Add vector v to all non-zero elements of the sparse vector.
void get_nz(int p, int &idx, T &dat)
Returns the p-th non-zero value in dat and the corresponding vector index in idx.
void set_new(const ivec &index_vec, const Vec< T > &v)
Set new elements with indices index_vec equal to the values in v (no check whether the same index is ...
void operator=(const Sparse_Vec< T > &v)
Assign sparse vector the value and length of the sparse vector v.
Sparse_Vec(const Vec< T > &v)
Initiate a new sparse vector from a dense vector.
void full(Vec< T > &v) const
Returns a full, dense vector in v.
T sqr() const
Returns the sum of all values squared.
void resize_data(int new_size)
Set the maximum number of non-zero elements to new_size.
void clear()
Clear all non-zero elements of the sparse vector.
int size() const
Returns the size of the sparse vector.
Vec< T > full() const
Returns a full, dense vector.
void set(const ivec &index_vec, const Vec< T > &v)
Set the elements of the sparse vector with indices index_vec to the values in v.
void compact()
Set the maximum number of non-zero elements equal to the actual number of non-zero elements.
void operator=(const Vec< T > &v)
Assign sparse vector the value and length of the dense vector v.
void remove_small_elements()
void operator+=(const Sparse_Vec< T > &v)
Add sparse vector v to all non-zero elements of the sparse vector.
Sparse_Vec< double > sparse_vec
Type definition of a double sparse vector.
Sparse_Vec< T > operator-() const
Returns the sign inverse of all elements in the sparse vector.
#define it_assert_debug(t, s)
Abort if t is not true and NDEBUG is not defined.
#define it_assert(t, s)
Abort if t is not true.
T sum(const Vec< T > &v)
Sum of all elements in the vector.
T max(const Vec< T > &v)
Maximum value of vector.
Minimum and maximum functions on vectors and matrices.
Sparse_Mat< T > sparse(const Mat< T > &m, T epsilon)
Convert a dense matrix m into its sparse representation.
Mat< T > full(const Sparse_Mat< T > &s)
Convert a sparse matrix s into its dense representation.
GF2mat operator*(const GF2mat &X, const GF2mat &Y)
GF(2) matrix multiplication.
const double eps
Constant eps.
Sparse_Vec< T > elem_mult_s(const Sparse_Vec< T > &v1, const Vec< T > &v2)
Elementwise multiplication of a sparse vector and a dense vector returning a sparse vector.
GF2mat operator+(const GF2mat &X, const GF2mat &Y)
GF(2) matrix addition.
Mat< Num_T > elem_mult(const Mat< Num_T > &m1, const Mat< Num_T > &m2)
Element wise multiplication of two matrices.
Templated Vector Class Definitions.