Home  · Classes  · Annotated Classes  · Modules  · Members  · Namespaces  · Related Pages
SparseVector.h
Go to the documentation of this file.
1 // --------------------------------------------------------------------------
2 // OpenMS -- Open-Source Mass Spectrometry
3 // --------------------------------------------------------------------------
4 // Copyright The OpenMS Team -- Eberhard Karls University Tuebingen,
5 // ETH Zurich, and Freie Universitaet Berlin 2002-2017.
6 //
7 // This software is released under a three-clause BSD license:
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above copyright
11 // notice, this list of conditions and the following disclaimer in the
12 // documentation and/or other materials provided with the distribution.
13 // * Neither the name of any author or any participating institution
14 // may be used to endorse or promote products derived from this software
15 // without specific prior written permission.
16 // For a full list of authors, refer to the file AUTHORS.
17 // --------------------------------------------------------------------------
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 // ARE DISCLAIMED. IN NO EVENT SHALL ANY OF THE AUTHORS OR THE CONTRIBUTING
22 // INSTITUTIONS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
25 // OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
26 // WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
27 // OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
28 // ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // --------------------------------------------------------------------------
31 // $Maintainer: Mathias Walzer $
32 // $Authors: $
33 // --------------------------------------------------------------------------
34 //
35 #ifndef OPENMS_DATASTRUCTURES_SPARSEVECTOR_H
36 #define OPENMS_DATASTRUCTURES_SPARSEVECTOR_H
37 
38 #include <OpenMS/CONCEPT/Types.h>
40 #include <OpenMS/config.h>
41 
42 #include <algorithm>
43 #include <cassert>
44 #include <cmath>
45 #include <iostream>
46 #include <map>
47 #include <sstream>
48 #include <stdexcept>
49 
50 namespace OpenMS
51 {
61  template <typename Value>
63  {
64 
65 public:
66 
67  //forward declarations
72  class ValueProxy;
73 
74  //made available from this classes
75  typedef SparseVectorConstIterator const_iterator;
76  typedef SparseVectorConstReverseIterator const_reverse_iterator;
77  typedef SparseVectorIterator iterator;
78  typedef SparseVectorReverseIterator reverse_iterator;
79 
80  //remapping
81  typedef typename std::map<size_t, Value>::difference_type difference_type; //needed?
82  typedef typename std::map<size_t, Value>::size_type size_type;
83  typedef typename std::map<size_t, Value>::allocator_type allocator_type; //needed?
84  typedef Value value_type;
85  typedef Value* pointer; //needed?
86  typedef ValueProxy& reference;
87  typedef const ValueProxy& const_reference;
88 
89  //internal use
90  typedef typename std::map<size_t, Value>::const_iterator map_const_iterator;
91  typedef typename std::map<size_t, Value>::iterator map_iterator;
92  typedef typename std::map<size_t, Value>::const_reverse_iterator reverse_map_const_iterator;
93  typedef typename std::map<size_t, Value>::reverse_iterator reverse_map_iterator;
94 
95  typedef SparseVectorConstIterator ConstIterator;
96  typedef SparseVectorConstReverseIterator ConstReverseIterator;
97  typedef SparseVectorIterator Iterator;
98  typedef SparseVectorReverseIterator ReverseIterator;
99 
100 
101  void print() const
102  {
103  std::cout << std::endl;
104  for (map_const_iterator it = values_.begin(); it != values_.end(); ++it)
105  {
106  std::cout << it->first << ": " << it->second << std::endl;
107  }
108  }
109 
112  values_(), size_(0), sparse_element_(0)
113  {
114  }
115 
117  SparseVector(Value se) :
118  values_(), size_(0), sparse_element_(se)
119  {
120  }
121 
123  SparseVector(size_type size, Value value, Value se = 0) :
124  values_(), size_(size), sparse_element_(se)
125  {
126 #pragma clang diagnostic push
127 #pragma clang diagnostic ignored "-Wfloat-equal"
128  if (value != sparse_element_) //change, if sparse element is another
129 #pragma clang diagnostic pop
130  {
131  map_iterator i = values_.begin();
132  for (size_type s = 0; s < size; ++s)
133  {
134  //makes each insertion in amortized constant time inserted direct after last one
135  i = values_.insert(i, std::make_pair(s, value));
136  }
137  }
138  }
139 
141  SparseVector(const SparseVector& source) :
142  values_(source.values_), size_(source.size_), sparse_element_(source.sparse_element_)
143  {
144  }
145 
148  {
149  if (this != &source)
150  {
151  values_ = source.values_;
152  size_ = source.size_;
154  }
155  return *this;
156  }
157 
160  {
161  }
162 
164  bool operator==(const SparseVector& rhs) const
165  {
166  return (values_ == rhs.values_) && (size_ == rhs.size_) && (sparse_element_ == rhs.sparse_element_);
167  }
168 
170  bool operator<(const SparseVector& rhs) const
171  {
172  return values_ < rhs.values_;
173  }
174 
176  size_type nonzero_size() const
177  {
178  return values_.size();
179  }
180 
182  size_type size() const
183  {
184  return size_;
185  }
186 
188  bool empty() const
189  {
190  return size() == 0;
191  }
192 
194  void push_back(Value value)
195  {
196  operator[](size_++) = value;
197  }
198 
204  Value at(size_type pos) const
205  {
206  if (pos >= size_)
207  {
208  throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
209  }
210  else
211  {
212  return operator[](pos);
213  }
214  }
215 
217  const Value /*Proxy*/ operator[](size_type pos) const
218  {
219  assert(pos < size_);
220  return (Value)ValueProxy(const_cast<SparseVector&>(*this), pos);
221  }
222 
224  ValueProxy operator[](size_type pos)
225  {
226  assert(pos < size_);
227  return ValueProxy(*this, pos);
228  }
229 
231  void clear()
232  {
233  values_.clear();
234  size_ = 0;
235  }
236 
238  void resize(size_type newsize)
239  {
240  // if the vector is to be smaller
241  // delete all invalid entries
242  if (newsize < size_)
243  {
244  for (map_iterator mit = values_.begin(); mit != values_.end(); )
245  {
246  if (mit->first >= newsize)
247  {
248  size_type nextvalue = (++mit)->first;
249  values_.erase(--mit);
250  mit = values_.find(nextvalue);
251  }
252  else
253  {
254  ++mit;
255  }
256  }
257  }
258  size_ = newsize;
259  }
260 
266  void erase(SparseVectorIterator it)
267  {
268  if (it.position() >= size_)
269  {
270  throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
271  }
272  //store pointer to the element after the current element
273  //erase element
274  bool update = false;
275  map_iterator mit = values_.find(it.position());
276  map_iterator mit_next;
277  if (mit != values_.end()) //element exists => erase it and update indices of elements after it
278  {
279  mit_next = mit;
280  ++mit_next;
281  values_.erase(mit);
282  update = true;
283  }
284  else //element does not exists => update indices of elements after it
285  {
286  mit_next = values_.lower_bound(it.position());
287  update = true;
288  }
289 
290  //update indices if necessary
291  if (update) update_(mit_next, 1);
292 
293  --size_;
294  }
295 
300  void erase(SparseVectorIterator first, SparseVectorIterator last)
301  {
302  if (first.position() >= size_ || last.position() > size_ || last.position() < first.position())
303  {
304  throw Exception::OutOfRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
305  }
306 
307  size_type amount_deleted = last.position() - first.position();
308  map_iterator mfirst = values_.lower_bound(first.position());
309  map_iterator mlast = values_.lower_bound(last.position());
310 
311  if (mfirst == values_.begin())
312  {
313  values_.erase(mfirst, mlast);
314  update_(values_.begin(), amount_deleted);
315  }
316  else
317  {
318  map_iterator start_it = mfirst;
319  --start_it;
320  values_.erase(mfirst, mlast);
321  ++start_it;
322  update_(start_it, amount_deleted);
323  }
324 
325  size_ -= amount_deleted;
326  }
327 
329  SparseVectorIterator getMinElement()
330  {
331  switch (size_)
332  {
333  case 0:
334  break;
335 
336  case 1:
337  return begin();
338 
339  break;
340 
341  default:
342  if (values_.empty())
343  {
344  //only sparse elements left
345  return begin();
346  }
347  bool first_sparse_found = false;
348  size_type pos = 0;
349  map_iterator lowest = values_.begin();
350  map_iterator second = values_.begin();
351  map_iterator first = second++;
352  map_iterator last = values_.end();
353 
354  if (lowest->first > 0)
355  {
356  first_sparse_found = true;
357  }
358 
359  while (second != last)
360  {
361  if (second->second < lowest->second) //the first element is covered by initial lowest == first
362  {
363  lowest = second;
364  }
365  if (size_ > values_.size() && !first_sparse_found)
366  {
367  if ((second->first) - (first->first) > 1)
368  {
369  pos = first->first + 1;
370  first_sparse_found = true;
371  }
372  }
373  ++first; ++second;
374  }
375 
376  if (size_ == values_.size() || lowest->second < SparseVector::sparse_element_)
377  {
378  return SparseVectorIterator(*this, lowest->first);
379  }
380  else //lowest->second >(=) sparseElement
381  {
382  if (!first_sparse_found)
383  {
384  return SparseVectorIterator(*this, first->first + 1);
385  }
386  return SparseVectorIterator(*this, pos);
387  }
388  break;
389  }
390  return end();
391  //map_iterator pos = min_element(values_.begin(), values_.end()); //sorts by map.key :(
392  }
393 
395  iterator begin()
396  {
397  return SparseVectorIterator(*this, 0);
398  }
399 
401  iterator end()
402  {
403  return SparseVectorIterator(*this, this->size());
404  }
405 
407  reverse_iterator rbegin()
408  {
409  return SparseVectorReverseIterator(*this, this->size());
410  }
411 
413  reverse_iterator rend()
414  {
415  return SparseVectorReverseIterator(*this, 0);
416  }
417 
419  const_iterator begin() const
420  {
421  return SparseVectorConstIterator(*this, 0);
422  }
423 
425  const_iterator end() const
426  {
427  return SparseVectorConstIterator(*this, this->size());
428  }
429 
431  const_reverse_iterator rbegin() const
432  {
433  return SparseVectorConstIterator(*this, this->size());
434  }
435 
437  const_reverse_iterator rend() const
438  {
439  return SparseVectorConstIterator(*this, 0);
440  }
441 
442 private:
444  std::map<size_type, Value> values_;
445 
447  size_type size_;
448 
449 protected:
450 
453 
455  void update_(map_iterator it, Size amount_deleted)
456  {
457  while (it != values_.end())
458  {
459  size_type tmp_index = it->first;
460  Value tmp_value = it->second;
461  if (it != values_.begin())
462  {
463  //makes insertion in amortized constant time if really inserted directly after mit
464  map_iterator tmp_it = it;
465  --tmp_it;
466  values_.erase(it);
467  it = values_.insert(tmp_it, std::make_pair(tmp_index - amount_deleted, tmp_value));
468  }
469  else
470  {
471  //simply insert, as we have no element to insert after
472  values_.erase(it);
473  it = values_.insert(std::make_pair(tmp_index - amount_deleted, tmp_value)).first;
474  }
475  ++it;
476  }
477  }
478 
479 public:
480 
486  {
487 
488 public:
489 
491  ValueProxy(SparseVector& vec, size_type index) :
492  vec_(vec), index_(index)
493  {
494  }
495 
496  // if there is a entry in the map from SparseVector, return that
497  // if not it is a zero, so return sparseElement
499  operator double() const
500  {
501  double value = vec_.sparse_element_;
502  map_const_iterator cmit = vec_.values_.find(index_);
503  if (cmit != vec_.values_.end())
504  {
505  value = cmit->second;
506  }
507  return value;
508  }
509 
511  operator int() const
512  {
513  int value = vec_.sparse_element_;
514  map_const_iterator cmit = vec_.values_.find(index_);
515  if (cmit != vec_.values_.end())
516  {
517  value = cmit->second;
518  }
519  return value;
520  }
521 
523  operator float() const
524  {
525  float value = vec_.sparse_element_;
526  map_const_iterator cmit = vec_.values_.find(index_);
527  if (cmit != vec_.values_.end())
528  {
529  value = cmit->second;
530  }
531  return value;
532  }
533 
534  // maybe more cast-operators for other types
535 
538  {
539  if ((this != &rhs) && (vec_ == rhs.vec_))
540  {
541  //if rhs' value != sparseElement, cmit!=rhs.vec_.values_.end()
542  map_const_iterator cmit = rhs.vec_.values_.find(rhs.index_);
543  if (cmit != rhs.vec_.values_.end())
544  {
545  vec_.values_[rhs.index_] = cmit->second;
546  }
547  //instead of setting value to zero erase it
548  else
549  {
550  map_iterator mit = vec_.values_.find(rhs.index_);
551  if (mit != vec_.values_.end())
552  {
553  vec_.values_.erase(mit);
554  }
555  }
556  index_ = rhs.index_;
557  }
558  return *this;
559  }
560 
562  ValueProxy& operator=(Value val)
563  {
564  if (val != vec_.sparse_element_) //if (fabs(val) > 1e-8)
565  {
566  vec_.values_[index_] = val;
567  }
568  else
569  {
570  map_iterator mit = vec_.values_.find(index_);
571  if (mit != vec_.values_.end())
572  {
573  vec_.values_.erase(mit);
574  }
575  }
576  return *this;
577  }
578 
580  bool operator!=(const ValueProxy& other)
581  {
582 
583  return (index_ != other.index_) || (&vec_ != &other.vec_);
584  }
585 
587  bool operator==(const ValueProxy& other)
588  {
589  return !(this != other);
590  }
591 
593  bool operator<(const ValueProxy& other)
594  {
595  return (Value) * this < (Value)other;
596  }
597 
599  bool operator>(const ValueProxy& other)
600  {
601  return (Value) * this > (Value)other;
602  }
603 
605  bool operator<=(const ValueProxy& other)
606  {
607  return (Value) * this <= (Value)other;
608  }
609 
611  bool operator>=(const ValueProxy& other)
612  {
613  return (Value) * this >= (Value)other;
614  }
615 
616 private:
617 
620 
622  size_type index_;
623 
624  }; //end of class ValueProxy
625 
631  {
632  friend class SparseVector<Value>;
634 
635 public:
636 
639  position_(source.position_),
640  vector_(source.vector_),
641  valit_(source.valit_)
642  {
643  }
644 
647  {
648  }
649 
652  {
653  if (this != &source)
654  {
655  position_ = source.position_;
656  vector_ = source.vector_;
657  valit_ = source.valit_;
658  }
659  return *this;
660  }
661 
664  {
665  ++position_;
666  return *this;
667  }
668 
671  {
672  SparseVectorIterator tmp(*this);
673  ++position_;
674  return tmp;
675  }
676 
679  {
680  --position_;
681  return *this;
682  }
683 
686  {
687  SparseVectorIterator tmp(*this);
688  --position_;
689  return tmp;
690  }
691 
694  {
695  assert(position_ < vector_.size_);
696  return ValueProxy(this->vector_, position_);
697  }
698 
700  const Value operator*() const
701  {
702  assert(position_ < vector_.size_);
703  return (Value)ValueProxy(this->vector_, position_);
704  }
705 
707  ValueProxy operator[](size_type n)
708  {
709  position_ += n;
710  assert(position_ < vector_.size_);
711  return ValueProxy(this->vector_, position_);
712  }
713 
715  SparseVectorIterator& operator+=(const size_type rhs)
716  {
717  position_ += rhs;
718  return *this;
719  }
720 
722  SparseVectorIterator& operator-=(const size_type rhs)
723  {
724  position_ -= rhs;
725  return *this;
726  }
727 
729  SparseVectorIterator operator+(const size_type rhs) const
730  {
731  return SparseVectorIterator(vector_, position_ + rhs);
732  }
733 
735  difference_type operator+(const SparseVectorIterator rhs) const
736  {
737  return position_ + rhs.position();
738  }
739 
741  SparseVectorIterator operator-(const size_type rhs) const
742  {
743  return SparseVectorIterator(vector_, position_ - rhs);
744  }
745 
747  difference_type operator-(const SparseVectorIterator rhs) const
748  {
749  return position_ - rhs.position();
750  }
751 
753  bool operator!=(const SparseVectorIterator& other)
754  {
755  return position_ != other.position_ || &vector_ != &other.vector_;
756  }
757 
759  bool operator==(const SparseVectorIterator& other)
760  {
761  return !(*this != other);
762  }
763 
765  bool operator<(const SparseVectorIterator& other)
766  {
767  return position_ < other.position();
768  }
769 
771  bool operator>(const SparseVectorIterator& other)
772  {
773  return position_ > other.position();
774  }
775 
777  bool operator<=(const SparseVectorIterator& other)
778  {
779  return position_ <= other.position();
780  }
781 
783  bool operator>=(const SparseVectorIterator& other)
784  {
785  return position_ >= other.position();
786  }
787 
790  {
791  //assert(valit_ != vector_.values_.end() );
792  //look for first entry if this is the first call. Go one step otherwise
793  if (position_ != valit_->first) //first call
794  {
795  valit_ = vector_.values_.upper_bound(position_);
796  }
797  else
798  {
799  ++valit_;
800  }
801  //check if we are at the end
802  if (valit_ == vector_.values_.end())
803  {
804  position_ = vector_.size_;
805  }
806  else
807  {
808  position_ = valit_->first;
809  }
810  return *this;
811  }
812 
814  size_type position() const
815  {
816  return position_;
817  }
818 
819 protected:
820 
822  SparseVectorIterator(SparseVector& vector, size_type position) :
823  position_(position),
824  vector_(vector),
825  valit_(vector.values_.begin())
826  {
827  }
828 
830  size_type position_;
831 
834 
836  map_const_iterator valit_;
837 
838 private:
839 
842 
843  }; //end of class SparseVectorIterator
844 
850  {
851  friend class SparseVector<Value>;
853 
854 public:
855 
858  position_(source.position_),
859  vector_(source.vector_),
860  valrit_(source.valrit_)
861  {
862  }
863 
866  {
867  }
868 
871  {
872  if (this != &source)
873  {
874  position_ = source.position_;
875  vector_ = source.vector_;
876  valrit_ = source.valrit_;
877  }
878  return *this;
879  }
880 
883  {
884  --position_;
885  return *this;
886  }
887 
890  {
891  SparseVectorReverseIterator tmp(*this);
892  --position_;
893  return tmp;
894  }
895 
898  {
899  ++position_;
900  return *this;
901  }
902 
905  {
906  SparseVectorReverseIterator tmp(*this);
907  ++position_;
908  return tmp;
909  }
910 
912  Value operator*()
913  {
914  assert(position_ <= vector_.size_);
915  assert(position_ != 0);
916  return ValueProxy(this->vector_, position_ - 1);
917  }
918 
920  ValueProxy operator[](size_type n)
921  {
922  position_ -= n;
923  assert(position_ < vector_.size_);
924  return ValueProxy(this->vector_, position_);
925  }
926 
929  {
930  position_ -= rhs;
931  return *this;
932  }
933 
936  {
937  position_ += rhs;
938  return *this;
939  }
940 
942  SparseVectorReverseIterator operator+(const size_type rhs) const
943  {
944  return SparseVectorReverseIterator(vector_, position_ - rhs);
945  }
946 
948  difference_type operator+(const SparseVectorReverseIterator rhs) const
949  {
950  return position_ + rhs.position();
951  }
952 
954  SparseVectorReverseIterator operator-(const size_type rhs) const
955  {
956  return SparseVectorReverseIterator(vector_, position_ + rhs);
957  }
958 
960  difference_type operator-(const SparseVectorReverseIterator rhs) const
961  {
962  //what about negatives?
963  return -1 * (position_ - rhs.position());
964  }
965 
968  {
969  return position_ != other.position_ || &vector_ != &other.vector_;
970  }
971 
974  {
975  return !(*this != other);
976  }
977 
980  {
981  return !(this->position() < other.position());
982  }
983 
986  {
987  return !(this->position() > other.position());
988  }
989 
992  {
993  return !(this->position() <= other.position());
994  }
995 
998  {
999  return !(this->position() >= other.position());
1000  }
1001 
1004  {
1005  assert(valrit_ != reverse_map_const_iterator(vector_.values_.rend()));
1006  //look for first entry if this is the first call. Go one step otherwise
1007  if (position_ - 1 != valrit_->first)
1008  {
1009  valrit_ = reverse_map_const_iterator(--(vector_.values_.find(position_ - 1)));
1010  }
1011  else
1012  {
1013  ++valrit_;
1014  }
1015  //check if we are at the end(begin)
1016  if (valrit_ == reverse_map_const_iterator(vector_.values_.rend()))
1017  {
1018  position_ = 0;
1019  }
1020  else
1021  {
1022  position_ = valrit_->first + 1;
1023  }
1024  return *this;
1025  }
1026 
1028  size_type position() const
1029  {
1030  return position_;
1031  }
1032 
1033 public:
1034 
1036  SparseVectorReverseIterator(SparseVector& vector, size_type position) :
1037  position_(position),
1038  vector_(vector),
1039  valrit_(vector.values_.rbegin())
1040  {
1041  }
1042 
1043 protected:
1044 
1046  size_type position_;
1047 
1048 private:
1051 
1053  reverse_map_const_iterator valrit_;
1054 
1057 
1058 
1059 
1060  }; //end of class SparseVectorReverseIterator
1061 
1064  {
1065  friend class SparseVector<Value>;
1066  friend class SparseVectorIterator;
1067 
1068 public:
1069 
1072  position_(source.position_),
1073  vector_(source.vector_),
1074  valit_(source.valit_)
1075  {
1076  }
1077 
1080  position_(source.position_),
1081  vector_(source.vector_),
1082  valit_(source.valit_)
1083  {
1084  }
1085 
1088  {
1089  }
1090 
1093  {
1094  if (this != &source)
1095  {
1096  position_ = source.position_;
1097  const_cast<SparseVector&>(this->vector_) = source.vector_;
1098  valit_ = source.valit_;
1099  }
1100  return *this;
1101  }
1102 
1105  {
1106  assert(position_ <= vector_.size_);
1107  ++position_;
1108  return *this;
1109  }
1110 
1113  {
1114  SparseVectorConstIterator tmp(*this);
1115  ++position_;
1116  assert(position_ <= vector_.size_);
1117  return tmp;
1118  }
1119 
1122  {
1123  assert(position_ <= vector_.size_);
1124  --position_;
1125  return *this;
1126  }
1127 
1130  {
1131  SparseVectorConstIterator tmp(*this);
1132  --position_;
1133  assert(position_ <= vector_.size_);
1134  return tmp;
1135  }
1136 
1138  const Value operator*() const
1139  {
1140  assert(position_ < vector_.size_);
1141  return (Value)ValueProxy(const_cast<SparseVector&>(this->vector_), position_);
1142  }
1143 
1144  // indexing
1145  const ValueProxy operator[](size_type n) const
1146  {
1147  position_ += n;
1148  assert(position_ < vector_.size_);
1149  return ValueProxy(const_cast<SparseVector&>(this->vector_), position_);
1150  }
1151 
1154  {
1155  position_ += rhs;
1156  return *this;
1157  }
1158 
1161  {
1162  position_ -= rhs;
1163  return *this;
1164  }
1165 
1167  SparseVectorConstIterator operator+(const size_type rhs) const
1168  {
1169  return SparseVectorConstIterator(const_cast<SparseVector&>(this->vector_), position_ + rhs);
1170  }
1171 
1173  SparseVectorConstIterator operator-(const size_type rhs) const
1174  {
1175  return SparseVectorConstIterator(const_cast<SparseVector&>(this->vector_), position_ - rhs);
1176  }
1177 
1180  {
1181  return position_ != other.position_ || &vector_ != &other.vector_;
1182  }
1183 
1186  {
1187  return !(*this != other);
1188  }
1189 
1192  {
1193  return this->position() < other.position();
1194  }
1195 
1198  {
1199  return this->position() > other.position();
1200  }
1201 
1204  {
1205  return this->position() <= other.position();
1206  }
1207 
1210  {
1211  return this->position() >= other.position();
1212  }
1213 
1216  {
1217  assert(valit_ != vector_.values_.end());
1218  //look for first entry if this is the first call. Go one step otherwise
1219  if (position_ != valit_->first) //first call
1220  {
1221  valit_ = vector_.values_.upper_bound(position_);
1222  }
1223  else
1224  {
1225  ++valit_;
1226  }
1227  //check if we are at the end
1228  if (valit_ == vector_.values_.end())
1229  {
1230  position_ = vector_.size_;
1231  }
1232  else
1233  {
1234  position_ = valit_->first;
1235  }
1236  return *this;
1237  }
1238 
1240  size_type position() const
1241  {
1242  return position_;
1243  }
1244 
1245 protected:
1248 
1250  SparseVectorConstIterator(const SparseVector& vector, size_type position) :
1251  position_(position),
1252  vector_(vector),
1253  valit_(vector.values_.begin())
1254  {
1255  }
1256 
1257 private:
1259  mutable size_type position_;
1260 
1263 
1265  map_const_iterator valit_;
1266 
1267  }; //end of class SparseVectorConstIterator
1268 
1271  {
1272  friend class SparseVector<Value>;
1273 
1274 public:
1275 
1278  position_(source.position_),
1279  vector_(source.vector_),
1280  valrit_(source.valrit_)
1281  {
1282  }
1283 
1286  position_(source.position_),
1287  vector_(source.vector_),
1288  valrit_(source.valrit_)
1289  {
1290  }
1291 
1294  {
1295  }
1296 
1299  {
1300  if (this != &source)
1301  {
1302  position_ = source.position_;
1303  const_cast<SparseVector&>(this->vector_) = source.vector_;
1304  valrit_ = source.valrit_;
1305  }
1306  return *this;
1307  }
1308 
1311  {
1312  //assert(position_ < 0);
1313  --position_;
1314  return *this;
1315  }
1316 
1319  {
1320  SparseVectorConstIterator tmp(*this);
1321  --position_;
1322  //assert(position_ < 0);
1323  return tmp;
1324  }
1325 
1328  {
1329  //assert(position_ < 0);
1330  ++position_;
1331  return *this;
1332  }
1333 
1336  {
1337  SparseVectorConstIterator tmp(*this);
1338  ++position_;
1339  //assert(position_ < 0);
1340  return tmp;
1341  }
1342 
1345  {
1346  assert(position_ <= vector_.size_);
1347  assert(position_ != 0);
1348  return ValueProxy(const_cast<SparseVector&>(this->vector_), position_ - 1);
1349  }
1350 
1353  {
1354  assert(valrit_ != vector_.values_.rend());
1355  //look for first entry if this is the first call. Go one step otherwise
1356  if (position_ - 1 != valrit_->first)
1357  {
1358  valrit_ = reverse_map_const_iterator(--(vector_.values_.find(position_ - 1)));
1359  }
1360  else
1361  {
1362  ++valrit_;
1363  }
1364  //check if we are at the end(begin)
1365  if (valrit_ == reverse_map_const_iterator(vector_.values_.rend()))
1366  {
1367  position_ = 0;
1368  }
1369  else
1370  {
1371  position_ = valrit_->first + 1;
1372  }
1373  return *this;
1374  }
1375 
1377  size_type position() const
1378  {
1379  return position_;
1380  }
1381 
1384  {
1385  return position_ != other.position_ || &vector_ != &other.vector_;
1386  }
1387 
1388 protected:
1389 
1392 
1394  SparseVectorConstReverseIterator(const SparseVector& vector, size_type position) :
1395  position_(position), vector_(vector), valrit_(vector.values_.rbegin())
1396  {
1397  }
1398 
1399 private:
1400 
1401  // the position in SparseVector
1402  mutable size_type position_;
1403 
1406 
1407  // the position in the underlying map of SparseVector
1408  reverse_map_const_iterator valrit_;
1409 
1410  }; //end of class SparseVectorConstReverseIterator
1411 
1412 
1413  }; //end of class SparseVector
1414 
1415 }
1416 #endif //OPENMS_DATASTRUCTURES_SPARSEVECTOR_H
SparseVectorIterator(const SparseVectorIterator &source)
copy constructor
Definition: SparseVector.h:638
ValueProxy & operator=(const ValueProxy &rhs)
assignment operator, ditches the sparse elements
Definition: SparseVector.h:537
size_type position() const
find out at what position the iterator is; useful in combination with hop()
Definition: SparseVector.h:814
SparseVector(Value se)
constructor with chosen sparse element
Definition: SparseVector.h:117
reverse_iterator rend()
rend iterator
Definition: SparseVector.h:413
SparseVectorConstReverseIterator(const SparseVectorConstIterator &source)
copy constructor
Definition: SparseVector.h:1277
SparseVectorConstReverseIterator & operator++()
postincrement operator
Definition: SparseVector.h:1310
map_const_iterator valit_
the position in the underlying map of SparseVector
Definition: SparseVector.h:1265
bool operator!=(const SparseVectorIterator &other)
inequality operator
Definition: SparseVector.h:753
SparseVectorReverseIterator & operator++()
prefix increment
Definition: SparseVector.h:882
const ValueProxy & const_reference
Definition: SparseVector.h:87
ValueProxy operator*()
dereference operator
Definition: SparseVector.h:693
SparseVectorConstIterator operator--(int)
immediate increment operator
Definition: SparseVector.h:1129
std::map< size_t, Value >::const_iterator map_const_iterator
Definition: SparseVector.h:90
size_type position_
the position in the referred SparseVector
Definition: SparseVector.h:830
void clear()
removes all elements
Definition: SparseVector.h:231
SparseVector(const SparseVector &source)
copy constructor
Definition: SparseVector.h:141
SparseVectorConstIterator & operator++()
postincrement operator
Definition: SparseVector.h:1104
Out of range exception.
Definition: Exception.h:320
const_iterator end() const
const end iterator
Definition: SparseVector.h:425
ValueProxy & operator=(Value val)
assignment operator, ditches the sparse elements
Definition: SparseVector.h:562
SparseVectorIterator & operator++()
prefix increment
Definition: SparseVector.h:663
ValueProxy operator[](size_type pos)
ValueProxy handles the conversion and the writing ( if != sparseElement )
Definition: SparseVector.h:224
ValueProxy operator*()
dereference operator
Definition: SparseVector.h:1344
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:485
ValueProxy & reference
Definition: SparseVector.h:86
SparseVectorConstIterator operator+(const size_type rhs) const
binary arithmetic +
Definition: SparseVector.h:1167
SparseVector implementation. The container will not actually store a specified type of element - the ...
Definition: SparseVector.h:62
const_reverse_iterator rend() const
const end reverse_iterator
Definition: SparseVector.h:437
SparseVectorReverseIterator operator--(int)
postfix decrement
Definition: SparseVector.h:904
SparseVectorIterator operator+(const size_type rhs) const
binary arithmetic +
Definition: SparseVector.h:729
difference_type operator+(const SparseVectorIterator rhs) const
binary arithmetic +
Definition: SparseVector.h:735
std::map< size_t, Value >::reverse_iterator reverse_map_iterator
Definition: SparseVector.h:93
SparseVectorConstIterator operator-(const size_type rhs) const
binary arithmetic -
Definition: SparseVector.h:1173
std::map< size_t, Value >::iterator map_iterator
Definition: SparseVector.h:91
Value operator*()
dereference operator
Definition: SparseVector.h:912
bool operator==(const ValueProxy &other)
equality operator
Definition: SparseVector.h:587
SparseVectorIterator & operator-=(const size_type rhs)
compound assignment -
Definition: SparseVector.h:722
bool operator<(const ValueProxy &other)
less than operator
Definition: SparseVector.h:593
bool empty() const
true if the container is empty
Definition: SparseVector.h:188
SparseVectorConstReverseIterator(const SparseVectorReverseIterator &source)
copy constructor from SparseVector::SparseVectorIterator
Definition: SparseVector.h:1285
SparseVectorConstReverseIterator operator++(int)
immediate increment operator
Definition: SparseVector.h:1318
size_type position() const
find out at what position the iterator is, useful in combination with hop()
Definition: SparseVector.h:1240
const_iterator for SparseVector
Definition: SparseVector.h:1063
Main OpenMS namespace.
Definition: FeatureDeconvolution.h:47
SparseVectorReverseIterator & operator-=(const size_type rhs)
compound assignment -
Definition: SparseVector.h:935
map_const_iterator valit_
the position in the underlying map of SparseVector
Definition: SparseVector.h:836
bool operator>=(const SparseVectorConstIterator &other)
greater or equal than operator
Definition: SparseVector.h:1209
SparseVectorConstIterator & operator=(const SparseVectorConstIterator &source)
assignment operator
Definition: SparseVector.h:1092
const_iterator begin() const
const begin iterator
Definition: SparseVector.h:419
SparseVectorConstReverseIterator & operator=(const SparseVectorConstReverseIterator &source)
assignment operator
Definition: SparseVector.h:1298
SparseVectorReverseIterator reverse_iterator
Definition: SparseVector.h:78
bool operator!=(const SparseVectorReverseIterator &other)
inequality operator
Definition: SparseVector.h:967
ValueProxy(SparseVector &vec, size_type index)
public constructor
Definition: SparseVector.h:491
SparseVectorIterator & operator+=(const size_type rhs)
compound assignment +
Definition: SparseVector.h:715
ValueProxy operator[](size_type n)
indexing
Definition: SparseVector.h:920
size_type nonzero_size() const
number of nonzero elements, i.e. the space actually used
Definition: SparseVector.h:176
bool operator!=(const SparseVectorConstReverseIterator &other)
inequality operator
Definition: SparseVector.h:1383
bool operator>=(const SparseVectorReverseIterator &other)
greater or equal than operator
Definition: SparseVector.h:997
SparseVector & vector_
referred sparseVector
Definition: SparseVector.h:1050
SparseVectorConstIterator(const SparseVectorIterator &source)
copy constructor from SparseVector::SparseVectorIterator
Definition: SparseVector.h:1079
difference_type operator+(const SparseVectorReverseIterator rhs) const
binary arithmetic +
Definition: SparseVector.h:948
SparseVectorReverseIterator & rhop()
go to the next nonempty position
Definition: SparseVector.h:1003
void push_back(Value value)
push_back (see stl vector docs)
Definition: SparseVector.h:194
bool operator<=(const SparseVectorIterator &other)
less or equal than operator
Definition: SparseVector.h:777
SparseVectorReverseIterator(const SparseVectorReverseIterator &source)
copy constructor
Definition: SparseVector.h:857
void resize(size_type newsize)
resizes the vector to param newsize
Definition: SparseVector.h:238
size_type size_
size including sparse elements
Definition: SparseVector.h:447
random access iterator for SparseVector including the hop() function to jump to the next non-sparse e...
Definition: SparseVector.h:630
size_type position_
position in referred SparseVector
Definition: SparseVector.h:1259
bool operator!=(const ValueProxy &other)
inequality operator
Definition: SparseVector.h:580
SparseVectorConstIterator(const SparseVectorConstIterator &source)
copy constructor
Definition: SparseVector.h:1071
virtual ~SparseVectorIterator()
destructor
Definition: SparseVector.h:646
SparseVectorConstIterator(const SparseVector &vector, size_type position)
detailed constructor
Definition: SparseVector.h:1250
std::map< size_t, Value >::size_type size_type
Definition: SparseVector.h:82
SparseVectorIterator operator-(const size_type rhs) const
binary arithmetic -
Definition: SparseVector.h:741
const Value operator*() const
const dereference operator
Definition: SparseVector.h:700
iterator end()
end iterator
Definition: SparseVector.h:401
SparseVectorConstIterator & operator-=(const size_type rhs)
compound assignment -
Definition: SparseVector.h:1160
SparseVectorIterator getMinElement()
gets an Iterator to the element (including sparseElements) with the minimal value ...
Definition: SparseVector.h:329
bool operator<(const SparseVectorConstIterator &other)
less than operator
Definition: SparseVector.h:1191
bool operator<(const SparseVector &rhs) const
less than operator
Definition: SparseVector.h:170
const_reverse_iterator rbegin() const
const begin reverse_iterator
Definition: SparseVector.h:431
const SparseVector & vector_
reference to the vector operating on
Definition: SparseVector.h:1405
const_reverse_iterator for SparseVector
Definition: SparseVector.h:1270
bool operator>(const SparseVectorReverseIterator &other)
greater than operator
Definition: SparseVector.h:985
size_type position_
Definition: SparseVector.h:1402
void print() const
Definition: SparseVector.h:101
SparseVectorIterator & operator=(const SparseVectorIterator &source)
assignment operator
Definition: SparseVector.h:651
size_type position() const
find out at what position the iterator is, useful in combination with hop()
Definition: SparseVector.h:1377
void erase(SparseVectorIterator it)
Definition: SparseVector.h:266
Value at(size_type pos) const
Definition: SparseVector.h:204
virtual ~SparseVectorConstReverseIterator()
destructor
Definition: SparseVector.h:1293
SparseVectorConstReverseIterator(const SparseVector &vector, size_type position)
detailed constructor
Definition: SparseVector.h:1394
void erase(SparseVectorIterator first, SparseVectorIterator last)
Definition: SparseVector.h:300
const SparseVector & vector_
referring to this SparseVector
Definition: SparseVector.h:1262
bool operator==(const SparseVectorReverseIterator &other)
equality operator
Definition: SparseVector.h:973
SparseVectorReverseIterator operator+(const size_type rhs) const
binary arithmetic +
Definition: SparseVector.h:942
SparseVectorIterator & hop()
go to the next nonempty position
Definition: SparseVector.h:789
bool operator==(const SparseVectorConstIterator &other)
equality operator
Definition: SparseVector.h:1185
bool operator>(const SparseVectorConstIterator &other)
greater than operator
Definition: SparseVector.h:1197
SparseVector & operator=(const SparseVector &source)
assignment operator
Definition: SparseVector.h:147
SparseVectorConstIterator const_iterator
Definition: SparseVector.h:72
SparseVectorConstReverseIterator operator--(int)
immediate decrement operator
Definition: SparseVector.h:1335
SparseVectorIterator iterator
Definition: SparseVector.h:77
SparseVectorReverseIterator operator-(const size_type rhs) const
binary arithmetic -
Definition: SparseVector.h:954
const ValueProxy operator[](size_type n) const
Definition: SparseVector.h:1145
iterator begin()
begin iterator
Definition: SparseVector.h:395
SparseVectorConstReverseIterator & rhop()
go to the next nonempty position
Definition: SparseVector.h:1352
bool operator>=(const ValueProxy &other)
greater or equal than operator
Definition: SparseVector.h:611
SparseVector()
default constructor
Definition: SparseVector.h:111
SparseVectorReverseIterator & operator+=(const size_type rhs)
compound assignment +
Definition: SparseVector.h:928
bool operator==(const SparseVector &rhs) const
equality operator
Definition: SparseVector.h:164
SparseVectorIterator(SparseVector &vector, size_type position)
Definition: SparseVector.h:822
bool operator>=(const SparseVectorIterator &other)
greater or equal than operator
Definition: SparseVector.h:783
SparseVectorReverseIterator ReverseIterator
Definition: SparseVector.h:98
SparseVectorConstReverseIterator const_reverse_iterator
Definition: SparseVector.h:76
bool operator==(const SparseVectorIterator &other)
equality operator
Definition: SparseVector.h:759
SparseVectorIterator operator++(int)
postfix increment
Definition: SparseVector.h:670
SparseVectorConstIterator operator++(int)
immediate increment operator
Definition: SparseVector.h:1112
SparseVectorConstReverseIterator ConstReverseIterator
Definition: SparseVector.h:96
size_type size() const
size of the represented vector
Definition: SparseVector.h:182
SparseVectorConstIterator & hop()
go to the next nonempty position
Definition: SparseVector.h:1215
reverse_map_const_iterator valrit_
Definition: SparseVector.h:1408
size_type position_
the position in the referred SparseVector
Definition: SparseVector.h:1046
const Value operator*() const
dereference operator
Definition: SparseVector.h:1138
size_type position() const
find out at what position the iterator is; useful in combination with hop()
Definition: SparseVector.h:1028
SparseVector & vec_
the referring SparseVector
Definition: SparseVector.h:619
Value * pointer
Definition: SparseVector.h:85
Value value_type
Definition: SparseVector.h:84
SparseVectorIterator Iterator
Definition: SparseVector.h:97
SparseVectorReverseIterator & operator=(const SparseVectorReverseIterator &source)
assignment operator
Definition: SparseVector.h:870
difference_type operator-(const SparseVectorReverseIterator rhs) const
binary arithmetic -
Definition: SparseVector.h:960
bool operator<=(const ValueProxy &other)
less or equal than operator
Definition: SparseVector.h:605
void update_(map_iterator it, Size amount_deleted)
Updates position of it and all larger elements.
Definition: SparseVector.h:455
size_t Size
Size type e.g. used as variable which can hold result of size()
Definition: Types.h:128
bool operator<(const SparseVectorIterator &other)
less than operator
Definition: SparseVector.h:765
bool operator<=(const SparseVectorConstIterator &other)
less or equal than operator
Definition: SparseVector.h:1203
virtual ~SparseVectorConstIterator()
destructor
Definition: SparseVector.h:1087
difference_type operator-(const SparseVectorIterator rhs) const
binary arithmetic -
Definition: SparseVector.h:747
size_type index_
the reference into the SparseVector
Definition: SparseVector.h:622
reverse_map_const_iterator valrit_
the position in the underlying map of SparseVector
Definition: SparseVector.h:1053
bool operator>(const ValueProxy &other)
greater than operator
Definition: SparseVector.h:599
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:123
SparseVectorConstIterator ConstIterator
Definition: SparseVector.h:95
SparseVectorReverseIterator(SparseVector &vector, size_type position)
detailed constructor
Definition: SparseVector.h:1036
bool operator<(const SparseVectorReverseIterator &other)
less than operator
Definition: SparseVector.h:979
std::map< size_t, Value >::allocator_type allocator_type
Definition: SparseVector.h:83
ValueProxy operator[](size_type n)
indexing
Definition: SparseVector.h:707
SparseVectorConstIterator & operator--()
postincrement operator
Definition: SparseVector.h:1121
SparseVectorIterator & operator--()
prefix decrement
Definition: SparseVector.h:678
std::map< size_type, Value > values_
underlying map
Definition: SparseVector.h:444
std::map< size_t, Value >::const_reverse_iterator reverse_map_const_iterator
Definition: SparseVector.h:92
SparseVectorConstIterator & operator+=(const size_type rhs)
compound assignment +
Definition: SparseVector.h:1153
SparseVectorIterator operator--(int)
postfix decrement
Definition: SparseVector.h:685
SparseVectorConstReverseIterator & operator--()
postdecrement operator
Definition: SparseVector.h:1327
Value sparse_element_
sparse element
Definition: SparseVector.h:452
reverse_iterator rbegin()
rbegin iterator
Definition: SparseVector.h:407
random access reverse iterator for SparseVector including the hop() function to jump to the next non-...
Definition: SparseVector.h:849
const Value operator[](size_type pos) const
ValueProxy handles the conversion to int and ,the writing ( if != sparseElement ) ...
Definition: SparseVector.h:217
virtual ~SparseVectorReverseIterator()
destructor
Definition: SparseVector.h:865
SparseVector & vector_
the referred SparseVector
Definition: SparseVector.h:833
bool operator>(const SparseVectorIterator &other)
greater than operator
Definition: SparseVector.h:771
bool operator!=(const SparseVectorConstIterator &other)
inequality operator
Definition: SparseVector.h:1179
SparseVectorReverseIterator & operator--()
prefix decrement
Definition: SparseVector.h:897
std::map< size_t, Value >::difference_type difference_type
Definition: SparseVector.h:81
SparseVectorReverseIterator operator++(int)
postfix increment
Definition: SparseVector.h:889
bool operator<=(const SparseVectorReverseIterator &other)
less or equal than operator
Definition: SparseVector.h:991
~SparseVector()
destructor
Definition: SparseVector.h:159

OpenMS / TOPP release 2.3.0 Documentation generated on Tue Jan 9 2018 18:22:04 using doxygen 1.8.13