35 #ifndef OPENMS_DATASTRUCTURES_SPARSEVECTOR_H
36 #define OPENMS_DATASTRUCTURES_SPARSEVECTOR_H
59 template <
typename Value>
80 typedef typename std::map<size_t, Value>::size_type
size_type;
101 std::cout << std::endl;
104 std::cout << it->first <<
": " << it->second << std::endl;
130 i =
values_.insert(i, std::make_pair(s, value));
215 return (Value)ValueProxy(const_cast<SparseVector &>(*
this), pos);
222 return ValueProxy(*
this, pos);
241 if (mit->first >= newsize)
263 if (it.position() >=
size_)
281 mit_next =
values_.lower_bound(it.position());
286 if (update)
update_(mit_next, 1);
295 void erase(SparseVectorIterator first, SparseVectorIterator last)
297 if (first.position() >=
size_ || last.position() >
size_ || last.position() < first.position())
302 size_type amount_deleted = last.position() - first.position();
317 update_(start_it, amount_deleted);
320 size_ -= amount_deleted;
342 bool first_sparse_found =
false;
349 if (lowest->first > 0)
351 first_sparse_found =
true;
354 while (second != last)
356 if (second->second < lowest->second)
362 if ((second->first) - (first->first) > 1)
364 pos = first->first + 1;
365 first_sparse_found =
true;
373 return SparseVectorIterator(*
this, lowest->first);
377 if (!first_sparse_found)
379 return SparseVectorIterator(*
this, first->first + 1);
381 return SparseVectorIterator(*
this, pos);
392 return SparseVectorIterator(*
this, 0);
398 return SparseVectorIterator(*
this, this->
size());
404 return SparseVectorReverseIterator(*
this, this->
size());
410 return SparseVectorReverseIterator(*
this, 0);
416 return SparseVectorConstIterator(*
this, 0);
422 return SparseVectorConstIterator(*
this, this->
size());
428 return SparseVectorConstIterator(*
this, this->
size());
434 return SparseVectorConstIterator(*
this, 0);
455 Value tmp_value = it->second;
462 it =
values_.insert(tmp_it, std::make_pair(tmp_index - amount_deleted, tmp_value));
468 it =
values_.insert(std::make_pair(tmp_index - amount_deleted, tmp_value)).first;
500 value = cmit->second;
512 value = cmit->second;
518 operator float()
const
524 value = cmit->second;
534 if ((
this != &rhs) && (
vec_ == rhs.
vec_))
584 return !(
this != other);
590 return (Value) *
this < (Value)other;
596 return (Value) *
this > (Value)other;
602 return (Value) *
this <= (Value)other;
608 return (Value) *
this >= (Value)other;
756 return !(*
this != other);
970 return !(*
this != other);
1089 if (
this != &source)
1182 return !(*
this != other);
1295 if (
this != &source)
1411 #endif //OPENMS_DATASTRUCTURES_SPARSEVECTOR_H
SparseVectorIterator(const SparseVectorIterator &source)
copy constructor
Definition: SparseVector.h:633
ValueProxy & operator=(const ValueProxy &rhs)
assignment operator, ditches the sparse elements
Definition: SparseVector.h:532
SparseVector(Value se)
constructor with chosen sparse element
Definition: SparseVector.h:115
SparseVectorConstIterator operator+(const size_type rhs) const
binary arithmetic +
Definition: SparseVector.h:1162
reverse_iterator rend()
rend iterator
Definition: SparseVector.h:408
size_type position() const
find out at what position the iterator is; useful in combination with hop()
Definition: SparseVector.h:809
SparseVectorConstReverseIterator(const SparseVectorConstIterator &source)
copy constructor
Definition: SparseVector.h:1272
SparseVectorConstReverseIterator & operator++()
postincrement operator
Definition: SparseVector.h:1305
SparseVectorIterator operator+(const size_type rhs) const
binary arithmetic +
Definition: SparseVector.h:724
map_const_iterator valit_
the position in the underlying map of SparseVector
Definition: SparseVector.h:1260
bool operator!=(const SparseVectorIterator &other)
inequality operator
Definition: SparseVector.h:748
SparseVectorReverseIterator & operator++()
prefix increment
Definition: SparseVector.h:877
const ValueProxy & const_reference
Definition: SparseVector.h:85
ValueProxy operator*()
dereference operator
Definition: SparseVector.h:688
SparseVectorConstIterator operator--(int)
immidiate increment operator
Definition: SparseVector.h:1124
size_type position() const
find out at what position the iterator is, useful in combination with hop()
Definition: SparseVector.h:1372
std::map< size_t, Value >::const_iterator map_const_iterator
Definition: SparseVector.h:88
size_type position_
the position in the referred SparseVector
Definition: SparseVector.h:825
void clear()
removes all elements
Definition: SparseVector.h:226
SparseVectorReverseIterator operator+(const size_type rhs) const
binary arithmetic +
Definition: SparseVector.h:937
SparseVector(const SparseVector &source)
copy constructor
Definition: SparseVector.h:136
SparseVectorConstIterator & operator++()
postincrement operator
Definition: SparseVector.h:1099
bool empty() const
true if the container is empty
Definition: SparseVector.h:183
Out of range exception.
Definition: Exception.h:320
ValueProxy & operator=(Value val)
assignment operator, ditches the sparse elements
Definition: SparseVector.h:557
SparseVectorIterator & operator++()
prefix increment
Definition: SparseVector.h:658
ValueProxy operator[](size_type pos)
ValueProxy handles the conversion and the writing ( if != sparseElement )
Definition: SparseVector.h:219
ValueProxy operator*()
derefence operator
Definition: SparseVector.h:1339
class ValueProxy allows the SparseVector to differentiate between writing and reading, so zeros can be ignored See "more effective c++" section 30
Definition: SparseVector.h:480
SparseVectorConstReverseIterator()
default constructor
bool operator<(const SparseVector &rhs) const
less than operator
Definition: SparseVector.h:165
ValueProxy & reference
Definition: SparseVector.h:84
SparseVector implementation. The container will not actually store a specified type of element - the ...
Definition: SparseVector.h:60
SparseVectorIterator operator-(const size_type rhs) const
binary arithmetic -
Definition: SparseVector.h:736
SparseVectorReverseIterator operator-(const size_type rhs) const
binary arithmetic -
Definition: SparseVector.h:949
SparseVectorReverseIterator operator--(int)
postfix decrement
Definition: SparseVector.h:899
std::map< size_t, Value >::reverse_iterator reverse_map_iterator
Definition: SparseVector.h:91
std::map< size_t, Value >::iterator map_iterator
Definition: SparseVector.h:89
Value operator*()
dereference operator
Definition: SparseVector.h:907
bool operator==(const ValueProxy &other)
equality operator
Definition: SparseVector.h:582
SparseVectorIterator & operator-=(const size_type rhs)
compound assignment -
Definition: SparseVector.h:717
const_reverse_iterator rend() const
const end reverse_iterator
Definition: SparseVector.h:432
bool operator<(const ValueProxy &other)
less than operator
Definition: SparseVector.h:588
SparseVectorConstReverseIterator(const SparseVectorReverseIterator &source)
copy constructor from SparseVector::SparseVectorIterator
Definition: SparseVector.h:1280
SparseVectorConstReverseIterator operator++(int)
immidiate increment operator
Definition: SparseVector.h:1313
const_iterator for SparseVector
Definition: SparseVector.h:1058
SparseVectorReverseIterator & operator-=(const size_type rhs)
compound assignment -
Definition: SparseVector.h:930
map_const_iterator valit_
the position in the underlying map of SparseVector
Definition: SparseVector.h:831
bool operator>=(const SparseVectorConstIterator &other)
greater or equal than operator
Definition: SparseVector.h:1204
SparseVectorConstIterator & operator=(const SparseVectorConstIterator &source)
assignment operator
Definition: SparseVector.h:1087
SparseVectorConstReverseIterator & operator=(const SparseVectorConstReverseIterator &source)
assignment operator
Definition: SparseVector.h:1293
const_iterator end() const
const end iterator
Definition: SparseVector.h:420
SparseVectorReverseIterator reverse_iterator
Definition: SparseVector.h:76
bool operator!=(const SparseVectorReverseIterator &other)
inequality operator
Definition: SparseVector.h:962
ValueProxy(SparseVector &vec, size_type index)
public constructor
Definition: SparseVector.h:486
const Value operator*() const
derefence operator
Definition: SparseVector.h:1133
difference_type operator-(const SparseVectorReverseIterator rhs) const
binary arithmetic -
Definition: SparseVector.h:955
SparseVectorIterator & operator+=(const size_type rhs)
compound assignment +
Definition: SparseVector.h:710
ValueProxy operator[](size_type n)
indexing
Definition: SparseVector.h:915
bool operator!=(const SparseVectorConstReverseIterator &other)
inequality operator
Definition: SparseVector.h:1378
bool operator>=(const SparseVectorReverseIterator &other)
greater or equal than operator
Definition: SparseVector.h:992
SparseVector & vector_
reffered sparseVector
Definition: SparseVector.h:1045
SparseVectorConstIterator(const SparseVectorIterator &source)
copy constructor from SparseVector::SparseVectorIterator
Definition: SparseVector.h:1074
bool operator==(const SparseVector &rhs) const
equality operator
Definition: SparseVector.h:159
SparseVectorReverseIterator & rhop()
go to the next nonempty position
Definition: SparseVector.h:998
void push_back(Value value)
push_back (see stl vector docs)
Definition: SparseVector.h:189
bool operator<=(const SparseVectorIterator &other)
less or equal than operator
Definition: SparseVector.h:772
SparseVectorReverseIterator(const SparseVectorReverseIterator &source)
copy constructor
Definition: SparseVector.h:852
void resize(size_type newsize)
resizes the the vector to param newsize
Definition: SparseVector.h:233
size_type size_
size including sparse elements
Definition: SparseVector.h:442
random access iterator for SparseVector including the hop() function to jump to the next non-sparse e...
Definition: SparseVector.h:625
size_type position_
position in reffered SparseVector
Definition: SparseVector.h:1254
const_iterator begin() const
const begin iterator
Definition: SparseVector.h:414
size_type nonzero_size() const
number of nonzero elements, i.e. the space actually used
Definition: SparseVector.h:171
size_type size() const
size of the represented vector
Definition: SparseVector.h:177
bool operator!=(const ValueProxy &other)
inequality operator
Definition: SparseVector.h:575
SparseVectorConstIterator(const SparseVectorConstIterator &source)
copy constructor
Definition: SparseVector.h:1066
virtual ~SparseVectorIterator()
destructor
Definition: SparseVector.h:641
SparseVectorConstIterator(const SparseVector &vector, size_type position)
detailed constructor
Definition: SparseVector.h:1245
std::map< size_t, Value >::size_type size_type
Definition: SparseVector.h:80
iterator end()
end iterator
Definition: SparseVector.h:396
SparseVectorConstIterator & operator-=(const size_type rhs)
compound assignment -
Definition: SparseVector.h:1155
SparseVectorIterator getMinElement()
gets an Iterator to the element (including sparseElements) with the minimal value ...
Definition: SparseVector.h:324
bool operator<(const SparseVectorConstIterator &other)
less than operator
Definition: SparseVector.h:1186
const_reverse_iterator rbegin() const
const begin reverse_iterator
Definition: SparseVector.h:426
const SparseVector & vector_
referenc to the vector operating on
Definition: SparseVector.h:1400
const_reverse_iterator for SparseVector
Definition: SparseVector.h:1265
SparseVectorConstIterator()
default constructor
bool operator>(const SparseVectorReverseIterator &other)
greater than operator
Definition: SparseVector.h:980
Value at(size_type pos) const
Definition: SparseVector.h:199
difference_type operator+(const SparseVectorIterator rhs) const
binary arithmetic +
Definition: SparseVector.h:730
size_type position() const
find out at what position the iterator is, useful in combination with hop()
Definition: SparseVector.h:1235
size_type position_
Definition: SparseVector.h:1397
SparseVectorIterator & operator=(const SparseVectorIterator &source)
assignment operator
Definition: SparseVector.h:646
void erase(SparseVectorIterator it)
Definition: SparseVector.h:261
virtual ~SparseVectorConstReverseIterator()
destructor
Definition: SparseVector.h:1288
SparseVectorConstReverseIterator(const SparseVector &vector, size_type position)
detailed constructor
Definition: SparseVector.h:1389
void erase(SparseVectorIterator first, SparseVectorIterator last)
Definition: SparseVector.h:295
const SparseVector & vector_
referring to this SparseVector
Definition: SparseVector.h:1257
bool operator==(const SparseVectorReverseIterator &other)
equality operator
Definition: SparseVector.h:968
SparseVectorIterator & hop()
go to the next nonempty position
Definition: SparseVector.h:784
bool operator==(const SparseVectorConstIterator &other)
equality operator
Definition: SparseVector.h:1180
bool operator>(const SparseVectorConstIterator &other)
greater than operator
Definition: SparseVector.h:1192
SparseVector & operator=(const SparseVector &source)
assignment operator
Definition: SparseVector.h:142
SparseVectorConstIterator const_iterator
Definition: SparseVector.h:70
SparseVectorConstReverseIterator operator--(int)
immidiate decrement operator
Definition: SparseVector.h:1330
SparseVectorIterator iterator
Definition: SparseVector.h:75
iterator begin()
begin iterator
Definition: SparseVector.h:390
SparseVectorConstReverseIterator & rhop()
go to the next nonempty position
Definition: SparseVector.h:1347
const ValueProxy operator[](size_type n) const
Definition: SparseVector.h:1140
bool operator>=(const ValueProxy &other)
greater or equal than operator
Definition: SparseVector.h:606
SparseVector()
default constructor
Definition: SparseVector.h:109
SparseVectorReverseIterator & operator+=(const size_type rhs)
compound assignment +
Definition: SparseVector.h:923
SparseVectorIterator(SparseVector &vector, size_type position)
Definition: SparseVector.h:817
bool operator>=(const SparseVectorIterator &other)
greater or equal than operator
Definition: SparseVector.h:778
SparseVectorReverseIterator ReverseIterator
Definition: SparseVector.h:96
SparseVectorConstReverseIterator const_reverse_iterator
Definition: SparseVector.h:74
bool operator==(const SparseVectorIterator &other)
equality operator
Definition: SparseVector.h:754
SparseVectorIterator operator++(int)
postfix increment
Definition: SparseVector.h:665
SparseVectorConstIterator operator++(int)
immidiate increment operator
Definition: SparseVector.h:1107
SparseVectorConstReverseIterator ConstReverseIterator
Definition: SparseVector.h:94
SparseVectorConstIterator & hop()
go to the next nonempty position
Definition: SparseVector.h:1210
SparseVectorIterator()
Not implemented => private.
reverse_map_const_iterator valrit_
Definition: SparseVector.h:1403
size_type position_
the position in the referred SparseVector
Definition: SparseVector.h:1041
SparseVector & vec_
the referring SparseVector
Definition: SparseVector.h:614
Value * pointer
Definition: SparseVector.h:83
const Value operator*() const
const dereference operator
Definition: SparseVector.h:695
Value value_type
Definition: SparseVector.h:82
SparseVectorIterator Iterator
Definition: SparseVector.h:95
SparseVectorReverseIterator & operator=(const SparseVectorReverseIterator &source)
assignment operator
Definition: SparseVector.h:865
bool operator<=(const ValueProxy &other)
less or equal than operator
Definition: SparseVector.h:600
const Value operator[](size_type pos) const
ValueProxy handles the conversion to int and ,the writing ( if != sparseElement ) ...
Definition: SparseVector.h:212
difference_type operator+(const SparseVectorReverseIterator rhs) const
binary arithmetic +
Definition: SparseVector.h:943
void update_(map_iterator it, Size amount_deleted)
Updates position of it and all larger elements.
Definition: SparseVector.h:450
size_t Size
Size type e.g. used as variable which can hold result of size()
Definition: Types.h:144
size_type position() const
find out at what position the iterator is; useful in combination with hop()
Definition: SparseVector.h:1023
bool operator<(const SparseVectorIterator &other)
less than operator
Definition: SparseVector.h:760
bool operator<=(const SparseVectorConstIterator &other)
less or equal than operator
Definition: SparseVector.h:1198
virtual ~SparseVectorConstIterator()
destructor
Definition: SparseVector.h:1082
size_type index_
the reference into the SparseVector
Definition: SparseVector.h:617
reverse_map_const_iterator valrit_
the position in the underlying map of SparseVector
Definition: SparseVector.h:1048
bool operator>(const ValueProxy &other)
greater than operator
Definition: SparseVector.h:594
SparseVector(size_type size, Value value, Value se=0)
detailed constructor, use with filling element value is discouraged unless it is the same as sparse e...
Definition: SparseVector.h:121
SparseVectorConstIterator ConstIterator
Definition: SparseVector.h:93
SparseVectorReverseIterator(SparseVector &vector, size_type position)
detailed constructor
Definition: SparseVector.h:1031
bool operator<(const SparseVectorReverseIterator &other)
less than operator
Definition: SparseVector.h:974
SparseVectorConstIterator operator-(const size_type rhs) const
binary arithmetic -
Definition: SparseVector.h:1168
std::map< size_t, Value >::allocator_type allocator_type
Definition: SparseVector.h:81
void print() const
Definition: SparseVector.h:99
ValueProxy operator[](size_type n)
indexing
Definition: SparseVector.h:702
SparseVectorConstIterator & operator--()
postincrement operator
Definition: SparseVector.h:1116
SparseVectorIterator & operator--()
prefix decrement
Definition: SparseVector.h:673
std::map< size_type, Value > values_
underlying map
Definition: SparseVector.h:439
std::map< size_t, Value >::const_reverse_iterator reverse_map_const_iterator
Definition: SparseVector.h:90
SparseVectorReverseIterator()
Not implemented => private.
SparseVectorConstIterator & operator+=(const size_type rhs)
compound assignment +
Definition: SparseVector.h:1148
SparseVectorIterator operator--(int)
postfix decrement
Definition: SparseVector.h:680
SparseVectorConstReverseIterator & operator--()
postdecrement operator
Definition: SparseVector.h:1322
Value sparse_element_
sparse element
Definition: SparseVector.h:447
reverse_iterator rbegin()
rbegin iterator
Definition: SparseVector.h:402
random access reverse iterator for SparseVector including the hop() function to jump to the next non-...
Definition: SparseVector.h:844
virtual ~SparseVectorReverseIterator()
destructor
Definition: SparseVector.h:860
SparseVector & vector_
the referred SparseVector
Definition: SparseVector.h:828
bool operator>(const SparseVectorIterator &other)
greater than operator
Definition: SparseVector.h:766
bool operator!=(const SparseVectorConstIterator &other)
inequality operator
Definition: SparseVector.h:1174
difference_type operator-(const SparseVectorIterator rhs) const
binary arithmetic -
Definition: SparseVector.h:742
SparseVectorReverseIterator & operator--()
prefix decrement
Definition: SparseVector.h:892
std::map< size_t, Value >::difference_type difference_type
Definition: SparseVector.h:79
SparseVectorReverseIterator operator++(int)
postfix increment
Definition: SparseVector.h:884
bool operator<=(const SparseVectorReverseIterator &other)
less or equal than operator
Definition: SparseVector.h:986
~SparseVector()
destructor
Definition: SparseVector.h:154