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-2013.
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 <map>
39 #include <algorithm>
40 #include <stdexcept>
41 #include <cassert>
42 #include <cmath>
43 #include <sstream>
45 
46 #include <iostream>
47 
48 namespace OpenMS
49 {
59  template <typename Value>
61  {
62 
63 public:
64 
65  //forward declarations
70  class ValueProxy;
71 
72  //made available from this classes
73  typedef SparseVectorConstIterator const_iterator;
74  typedef SparseVectorConstReverseIterator const_reverse_iterator;
75  typedef SparseVectorIterator iterator;
76  typedef SparseVectorReverseIterator reverse_iterator;
77 
78  //remapping
79  typedef typename std::map<size_t, Value>::difference_type difference_type; //needed?
80  typedef typename std::map<size_t, Value>::size_type size_type;
81  typedef typename std::map<size_t, Value>::allocator_type allocator_type; //needed?
82  typedef Value value_type;
83  typedef Value * pointer; //needed?
84  typedef ValueProxy & reference;
85  typedef const ValueProxy & const_reference;
86 
87  //internal use
88  typedef typename std::map<size_t, Value>::const_iterator map_const_iterator;
89  typedef typename std::map<size_t, Value>::iterator map_iterator;
90  typedef typename std::map<size_t, Value>::const_reverse_iterator reverse_map_const_iterator;
91  typedef typename std::map<size_t, Value>::reverse_iterator reverse_map_iterator;
92 
93  typedef SparseVectorConstIterator ConstIterator;
94  typedef SparseVectorConstReverseIterator ConstReverseIterator;
95  typedef SparseVectorIterator Iterator;
96  typedef SparseVectorReverseIterator ReverseIterator;
97 
98 
99  void print() const
100  {
101  std::cout << std::endl;
102  for (map_const_iterator it = values_.begin(); it != values_.end(); ++it)
103  {
104  std::cout << it->first << ": " << it->second << std::endl;
105  }
106  }
107 
110  values_(), size_(0), sparse_element_(0)
111  {
112  }
113 
115  SparseVector(Value se) :
116  values_(), size_(0), sparse_element_(se)
117  {
118  }
119 
121  SparseVector(size_type size, Value value, Value se = 0) :
122  values_(), size_(size), sparse_element_(se)
123  {
124  if (value != sparse_element_) //change, if sparse element is another
125  {
126  map_iterator i = values_.begin();
127  for (size_type s = 0; s < size; ++s)
128  {
129  //makes each insertion in amortized constant time inserted direct after last one
130  i = values_.insert(i, std::make_pair(s, value));
131  }
132  }
133  }
134 
136  SparseVector(const SparseVector & source) :
137  values_(source.values_), size_(source.size_), sparse_element_(source.sparse_element_)
138  {
139  }
140 
143  {
144  if (this != &source)
145  {
146  values_ = source.values_;
147  size_ = source.size_;
149  }
150  return *this;
151  }
152 
155  {
156  }
157 
159  bool operator==(const SparseVector & rhs) const
160  {
161  return (values_ == rhs.values_) && (size_ == rhs.size_) && (sparse_element_ == rhs.sparse_element_);
162  }
163 
165  bool operator<(const SparseVector & rhs) const
166  {
167  return values_ < rhs.values_;
168  }
169 
172  {
173  return values_.size();
174  }
175 
177  size_type size() const
178  {
179  return size_;
180  }
181 
183  bool empty() const
184  {
185  return size() == 0;
186  }
187 
189  void push_back(Value value)
190  {
191  operator[](size_++) = value;
192  }
193 
199  Value at(size_type pos) const
200  {
201  if (pos >= size_)
202  {
203  throw Exception::OutOfRange(__FILE__, __LINE__, __PRETTY_FUNCTION__);
204  }
205  else
206  {
207  return operator[](pos);
208  }
209  }
210 
212  const Value /*Proxy*/ operator[](size_type pos) const
213  {
214  assert(pos < size_);
215  return (Value)ValueProxy(const_cast<SparseVector &>(*this), pos);
216  }
217 
219  ValueProxy operator[](size_type pos)
220  {
221  assert(pos < size_);
222  return ValueProxy(*this, pos);
223  }
224 
226  void clear()
227  {
228  values_.clear();
229  size_ = 0;
230  }
231 
233  void resize(size_type newsize)
234  {
235  // if the vector is to be smaller
236  // delete all invalid entries
237  if (newsize < size_)
238  {
239  for (map_iterator mit = values_.begin(); mit != values_.end(); )
240  {
241  if (mit->first >= newsize)
242  {
243  size_type nextvalue = (++mit)->first;
244  values_.erase(--mit);
245  mit = values_.find(nextvalue);
246  }
247  else
248  {
249  ++mit;
250  }
251  }
252  }
253  size_ = newsize;
254  }
255 
261  void erase(SparseVectorIterator it)
262  {
263  if (it.position() >= size_)
264  {
265  throw Exception::OutOfRange(__FILE__, __LINE__, __PRETTY_FUNCTION__);
266  }
267  //store pointer to the element after the current element
268  //erase element
269  bool update = false;
270  map_iterator mit = values_.find(it.position());
271  map_iterator mit_next;
272  if (mit != values_.end()) //element exists => erase it and update indices of elements after it
273  {
274  mit_next = mit;
275  ++mit_next;
276  values_.erase(mit);
277  update = true;
278  }
279  else //element does not exists => update indices of elements after it
280  {
281  mit_next = values_.lower_bound(it.position());
282  update = true;
283  }
284 
285  //update indices if necessary
286  if (update) update_(mit_next, 1);
287 
288  --size_;
289  }
290 
295  void erase(SparseVectorIterator first, SparseVectorIterator last)
296  {
297  if (first.position() >= size_ || last.position() > size_ || last.position() < first.position())
298  {
299  throw Exception::OutOfRange(__FILE__, __LINE__, __PRETTY_FUNCTION__);
300  }
301 
302  size_type amount_deleted = last.position() - first.position();
303  map_iterator mfirst = values_.lower_bound(first.position());
304  map_iterator mlast = values_.lower_bound(last.position());
305 
306  if (mfirst == values_.begin())
307  {
308  values_.erase(mfirst, mlast);
309  update_(values_.begin(), amount_deleted);
310  }
311  else
312  {
313  map_iterator start_it = mfirst;
314  --start_it;
315  values_.erase(mfirst, mlast);
316  ++start_it;
317  update_(start_it, amount_deleted);
318  }
319 
320  size_ -= amount_deleted;
321  }
322 
324  SparseVectorIterator getMinElement()
325  {
326  switch (size_)
327  {
328  case 0:
329  break;
330 
331  case 1:
332  return begin();
333 
334  break;
335 
336  default:
337  if (values_.empty())
338  {
339  //only sparse elements left
340  return begin();
341  }
342  bool first_sparse_found = false;
343  size_type pos = 0;
344  map_iterator lowest = values_.begin();
345  map_iterator second = values_.begin();
346  map_iterator first = second++;
347  map_iterator last = values_.end();
348 
349  if (lowest->first > 0)
350  {
351  first_sparse_found = true;
352  }
353 
354  while (second != last)
355  {
356  if (second->second < lowest->second) //the first element is covered by initial lowest == frst
357  {
358  lowest = second;
359  }
360  if (size_ > values_.size() && !first_sparse_found)
361  {
362  if ((second->first) - (first->first) > 1)
363  {
364  pos = first->first + 1;
365  first_sparse_found = true;
366  }
367  }
368  ++first; ++second;
369  }
370 
371  if (size_ == values_.size() || lowest->second < SparseVector::sparse_element_)
372  {
373  return SparseVectorIterator(*this, lowest->first);
374  }
375  else //lowest->second >(=) sparseElement
376  {
377  if (!first_sparse_found)
378  {
379  return SparseVectorIterator(*this, first->first + 1);
380  }
381  return SparseVectorIterator(*this, pos);
382  }
383  break;
384  }
385  return end();
386  //map_iterator pos = min_element(values_.begin(), values_.end()); //sorts by map.key :(
387  }
388 
391  {
392  return SparseVectorIterator(*this, 0);
393  }
394 
397  {
398  return SparseVectorIterator(*this, this->size());
399  }
400 
403  {
404  return SparseVectorReverseIterator(*this, this->size());
405  }
406 
409  {
410  return SparseVectorReverseIterator(*this, 0);
411  }
412 
415  {
416  return SparseVectorConstIterator(*this, 0);
417  }
418 
421  {
422  return SparseVectorConstIterator(*this, this->size());
423  }
424 
427  {
428  return SparseVectorConstIterator(*this, this->size());
429  }
430 
433  {
434  return SparseVectorConstIterator(*this, 0);
435  }
436 
437 private:
439  std::map<size_type, Value> values_;
440 
443 
444 protected:
445 
448 
450  void update_(map_iterator it, Size amount_deleted)
451  {
452  while (it != values_.end())
453  {
454  size_type tmp_index = it->first;
455  Value tmp_value = it->second;
456  if (it != values_.begin())
457  {
458  //makes insertion in amortized constant time if really inserted directly after mit
459  map_iterator tmp_it = it;
460  --tmp_it;
461  values_.erase(it);
462  it = values_.insert(tmp_it, std::make_pair(tmp_index - amount_deleted, tmp_value));
463  }
464  else
465  {
466  //simply insert, as we have no element to insert after
467  values_.erase(it);
468  it = values_.insert(std::make_pair(tmp_index - amount_deleted, tmp_value)).first;
469  }
470  ++it;
471  }
472  }
473 
474 public:
475 
481  {
482 
483 public:
484 
487  vec_(vec), index_(index)
488  {
489  }
490 
491  // if there is a entry in the map from SparseVector, return that
492  // if not it is a zero, so return sparseElement
494  operator double() const
495  {
496  double value = vec_.sparse_element_;
497  map_const_iterator cmit = vec_.values_.find(index_);
498  if (cmit != vec_.values_.end())
499  {
500  value = cmit->second;
501  }
502  return value;
503  }
504 
506  operator int() const
507  {
508  int value = vec_.sparse_element_;
509  map_const_iterator cmit = vec_.values_.find(index_);
510  if (cmit != vec_.values_.end())
511  {
512  value = cmit->second;
513  }
514  return value;
515  }
516 
518  operator float() const
519  {
520  float value = vec_.sparse_element_;
521  map_const_iterator cmit = vec_.values_.find(index_);
522  if (cmit != vec_.values_.end())
523  {
524  value = cmit->second;
525  }
526  return value;
527  }
528 
529  // maybe more cast-operators for other types
530 
533  {
534  if ((this != &rhs) && (vec_ == rhs.vec_))
535  {
536  //if rhs' value != sparseElement, cmit!=rhs.vec_.values_.end()
537  map_const_iterator cmit = rhs.vec_.values_.find(rhs.index_);
538  if (cmit != rhs.vec_.values_.end())
539  {
540  vec_.values_[rhs.index_] = cmit->second;
541  }
542  //instead of setting value to zero erase it
543  else
544  {
545  map_iterator mit = vec_.values_.find(rhs.index_);
546  if (mit != vec_.values_.end())
547  {
548  vec_.values_.erase(mit);
549  }
550  }
551  index_ = rhs.index_;
552  }
553  return *this;
554  }
555 
557  ValueProxy & operator=(Value val)
558  {
559  if (val != vec_.sparse_element_) //if (fabs(val) > 1e-8)
560  {
561  vec_.values_[index_] = val;
562  }
563  else
564  {
565  map_iterator mit = vec_.values_.find(index_);
566  if (mit != vec_.values_.end())
567  {
568  vec_.values_.erase(mit);
569  }
570  }
571  return *this;
572  }
573 
575  bool operator!=(const ValueProxy & other)
576  {
577 
578  return (index_ != other.index_) || (&vec_ != &other.vec_);
579  }
580 
582  bool operator==(const ValueProxy & other)
583  {
584  return !(this != other);
585  }
586 
588  bool operator<(const ValueProxy & other)
589  {
590  return (Value) * this < (Value)other;
591  }
592 
594  bool operator>(const ValueProxy & other)
595  {
596  return (Value) * this > (Value)other;
597  }
598 
600  bool operator<=(const ValueProxy & other)
601  {
602  return (Value) * this <= (Value)other;
603  }
604 
606  bool operator>=(const ValueProxy & other)
607  {
608  return (Value) * this >= (Value)other;
609  }
610 
611 private:
612 
615 
618 
619  }; //end of class ValueProxy
620 
626  {
627  friend class SparseVector<Value>;
629 
630 public:
631 
634  position_(source.position_),
635  vector_(source.vector_),
636  valit_(source.valit_)
637  {
638  }
639 
642  {
643  }
644 
647  {
648  if (this != &source)
649  {
650  position_ = source.position_;
651  vector_ = source.vector_;
652  valit_ = source.valit_;
653  }
654  return *this;
655  }
656 
659  {
660  ++position_;
661  return *this;
662  }
663 
666  {
667  SparseVectorIterator tmp(*this);
668  ++position_;
669  return tmp;
670  }
671 
674  {
675  --position_;
676  return *this;
677  }
678 
681  {
682  SparseVectorIterator tmp(*this);
683  --position_;
684  return tmp;
685  }
686 
689  {
690  assert(position_ < vector_.size_);
691  return ValueProxy(this->vector_, position_);
692  }
693 
695  const Value operator*() const
696  {
697  assert(position_ < vector_.size_);
698  return (Value)ValueProxy(this->vector_, position_);
699  }
700 
703  {
704  position_ += n;
705  assert(position_ < vector_.size_);
706  return ValueProxy(this->vector_, position_);
707  }
708 
711  {
712  position_ += rhs;
713  return *this;
714  }
715 
718  {
719  position_ -= rhs;
720  return *this;
721  }
722 
725  {
726  return SparseVectorIterator(vector_, position_ + rhs);
727  }
728 
731  {
732  return position_ + rhs.position();
733  }
734 
737  {
738  return SparseVectorIterator(vector_, position_ - rhs);
739  }
740 
743  {
744  return position_ - rhs.position();
745  }
746 
748  bool operator!=(const SparseVectorIterator & other)
749  {
750  return position_ != other.position_ || &vector_ != &other.vector_;
751  }
752 
754  bool operator==(const SparseVectorIterator & other)
755  {
756  return !(*this != other);
757  }
758 
760  bool operator<(const SparseVectorIterator & other)
761  {
762  return position_ < other.position();
763  }
764 
766  bool operator>(const SparseVectorIterator & other)
767  {
768  return position_ > other.position();
769  }
770 
772  bool operator<=(const SparseVectorIterator & other)
773  {
774  return position_ <= other.position();
775  }
776 
778  bool operator>=(const SparseVectorIterator & other)
779  {
780  return position_ >= other.position();
781  }
782 
785  {
786  //assert(valit_ != vector_.values_.end() );
787  //look for first entry if this is the first call. Go one step otherwise
788  if (position_ != valit_->first) //first call
789  {
790  valit_ = vector_.values_.upper_bound(position_);
791  }
792  else
793  {
794  ++valit_;
795  }
796  //check if we are at the end
797  if (valit_ == vector_.values_.end())
798  {
800  }
801  else
802  {
803  position_ = valit_->first;
804  }
805  return *this;
806  }
807 
810  {
811  return position_;
812  }
813 
814 protected:
815 
818  position_(position),
819  vector_(vector),
820  valit_(vector.values_.begin())
821  {
822  }
823 
826 
829 
832 
833 private:
834 
837 
838  }; //end of class SparseVectorIterator
839 
845  {
846  friend class SparseVector<Value>;
848 
849 public:
850 
853  position_(source.position_),
854  vector_(source.vector_),
855  valrit_(source.valrit_)
856  {
857  }
858 
861  {
862  }
863 
866  {
867  if (this != &source)
868  {
869  position_ = source.position_;
870  vector_ = source.vector_;
871  valrit_ = source.valrit_;
872  }
873  return *this;
874  }
875 
878  {
879  --position_;
880  return *this;
881  }
882 
885  {
886  SparseVectorReverseIterator tmp(*this);
887  --position_;
888  return tmp;
889  }
890 
893  {
894  ++position_;
895  return *this;
896  }
897 
900  {
901  SparseVectorReverseIterator tmp(*this);
902  ++position_;
903  return tmp;
904  }
905 
907  Value operator*()
908  {
909  assert(position_ <= vector_.size_);
910  assert(position_ != 0);
911  return ValueProxy(this->vector_, position_ - 1);
912  }
913 
916  {
917  position_ -= n;
918  assert(position_ < vector_.size_);
919  return ValueProxy(this->vector_, position_);
920  }
921 
924  {
925  position_ -= rhs;
926  return *this;
927  }
928 
931  {
932  position_ += rhs;
933  return *this;
934  }
935 
938  {
940  }
941 
944  {
945  return position_ + rhs.position();
946  }
947 
950  {
952  }
953 
956  {
957  //what about negatives?
958  return -1 * (position_ - rhs.position());
959  }
960 
963  {
964  return position_ != other.position_ || &vector_ != &other.vector_;
965  }
966 
969  {
970  return !(*this != other);
971  }
972 
975  {
976  return !(this->position() < other.position());
977  }
978 
981  {
982  return !(this->position() > other.position());
983  }
984 
987  {
988  return !(this->position() <= other.position());
989  }
990 
993  {
994  return !(this->position() >= other.position());
995  }
996 
999  {
1001  //look for first entry if this is the first call. Go one step otherwise
1002  if (position_ - 1 != valrit_->first)
1003  {
1005  }
1006  else
1007  {
1008  ++valrit_;
1009  }
1010  //check if we are at the end(begin)
1012  {
1013  position_ = 0;
1014  }
1015  else
1016  {
1017  position_ = valrit_->first + 1;
1018  }
1019  return *this;
1020  }
1021 
1024  {
1025  return position_;
1026  }
1027 
1028 public:
1029 
1032  position_(position),
1033  vector_(vector),
1034  valrit_(vector.values_.rbegin())
1035  {
1036  }
1037 
1038 protected:
1039 
1042 
1043 private:
1046 
1049 
1052 
1053 
1054 
1055  }; //end of class SparseVectorReverseIterator
1056 
1059  {
1060  friend class SparseVector<Value>;
1061  friend class SparseVectorIterator;
1062 
1063 public:
1064 
1067  position_(source.position_),
1068  vector_(source.vector_),
1069  valit_(source.valit_)
1070  {
1071  }
1072 
1075  position_(source.position_),
1076  vector_(source.vector_),
1077  valit_(source.valit_)
1078  {
1079  }
1080 
1083  {
1084  }
1085 
1088  {
1089  if (this != &source)
1090  {
1091  position_ = source.position_;
1092  const_cast<SparseVector &>(this->vector_) = source.vector_;
1093  valit_ = source.valit_;
1094  }
1095  return *this;
1096  }
1097 
1100  {
1101  assert(position_ <= vector_.size_);
1102  ++position_;
1103  return *this;
1104  }
1105 
1108  {
1109  SparseVectorConstIterator tmp(*this);
1110  ++position_;
1111  assert(position_ <= vector_.size_);
1112  return tmp;
1113  }
1114 
1117  {
1118  assert(position_ <= vector_.size_);
1119  --position_;
1120  return *this;
1121  }
1122 
1125  {
1126  SparseVectorConstIterator tmp(*this);
1127  --position_;
1128  assert(position_ <= vector_.size_);
1129  return tmp;
1130  }
1131 
1133  const Value operator*() const
1134  {
1135  assert(position_ < vector_.size_);
1136  return (Value)ValueProxy(const_cast<SparseVector &>(this->vector_), position_);
1137  }
1138 
1139  // indexing
1141  {
1142  position_ += n;
1143  assert(position_ < vector_.size_);
1144  return ValueProxy(const_cast<SparseVector &>(this->vector_), position_);
1145  }
1146 
1149  {
1150  position_ += rhs;
1151  return *this;
1152  }
1153 
1156  {
1157  position_ -= rhs;
1158  return *this;
1159  }
1160 
1163  {
1164  return SparseVectorConstIterator(const_cast<SparseVector &>(this->vector_), position_ + rhs);
1165  }
1166 
1169  {
1170  return SparseVectorConstIterator(const_cast<SparseVector &>(this->vector_), position_ - rhs);
1171  }
1172 
1175  {
1176  return position_ != other.position_ || &vector_ != &other.vector_;
1177  }
1178 
1181  {
1182  return !(*this != other);
1183  }
1184 
1187  {
1188  return this->position() < other.position();
1189  }
1190 
1193  {
1194  return this->position() > other.position();
1195  }
1196 
1199  {
1200  return this->position() <= other.position();
1201  }
1202 
1205  {
1206  return this->position() >= other.position();
1207  }
1208 
1211  {
1212  assert(valit_ != vector_.values_.end());
1213  //look for first entry if this is the first call. Go one step otherwise
1214  if (position_ != valit_->first) //first call
1215  {
1216  valit_ = vector_.values_.upper_bound(position_);
1217  }
1218  else
1219  {
1220  ++valit_;
1221  }
1222  //check if we are at the end
1223  if (valit_ == vector_.values_.end())
1224  {
1226  }
1227  else
1228  {
1229  position_ = valit_->first;
1230  }
1231  return *this;
1232  }
1233 
1236  {
1237  return position_;
1238  }
1239 
1240 protected:
1243 
1246  position_(position),
1247  vector_(vector),
1248  valit_(vector.values_.begin())
1249  {
1250  }
1251 
1252 private:
1255 
1258 
1261 
1262  }; //end of class SparseVectorConstIterator
1263 
1266  {
1267  friend class SparseVector<Value>;
1268 
1269 public:
1270 
1273  position_(source.position_),
1274  vector_(source.vector_),
1275  valrit_(source.valrit_)
1276  {
1277  }
1278 
1281  position_(source.position_),
1282  vector_(source.vector_),
1283  valrit_(source.valrit_)
1284  {
1285  }
1286 
1289  {
1290  }
1291 
1294  {
1295  if (this != &source)
1296  {
1297  position_ = source.position_;
1298  const_cast<SparseVector &>(this->vector_) = source.vector_;
1299  valrit_ = source.valrit_;
1300  }
1301  return *this;
1302  }
1303 
1306  {
1307  //assert(position_ < 0);
1308  --position_;
1309  return *this;
1310  }
1311 
1314  {
1315  SparseVectorConstIterator tmp(*this);
1316  --position_;
1317  //assert(position_ < 0);
1318  return tmp;
1319  }
1320 
1323  {
1324  //assert(position_ < 0);
1325  ++position_;
1326  return *this;
1327  }
1328 
1331  {
1332  SparseVectorConstIterator tmp(*this);
1333  ++position_;
1334  //assert(position_ < 0);
1335  return tmp;
1336  }
1337 
1340  {
1341  assert(position_ <= vector_.size_);
1342  assert(position_ != 0);
1343  return ValueProxy(const_cast<SparseVector &>(this->vector_), position_ - 1);
1344  }
1345 
1348  {
1349  assert(valrit_ != vector_.values_.rend());
1350  //look for first entry if this is the first call. Go one step otherwise
1351  if (position_ - 1 != valrit_->first)
1352  {
1354  }
1355  else
1356  {
1357  ++valrit_;
1358  }
1359  //check if we are at the end(begin)
1361  {
1362  position_ = 0;
1363  }
1364  else
1365  {
1366  position_ = valrit_->first + 1;
1367  }
1368  return *this;
1369  }
1370 
1373  {
1374  return position_;
1375  }
1376 
1379  {
1380  return position_ != other.position_ || &vector_ != &other.vector_;
1381  }
1382 
1383 protected:
1384 
1387 
1390  position_(position), vector_(vector), valrit_(vector.values_.rbegin())
1391  {
1392  }
1393 
1394 private:
1395 
1396  // the position in SparseVector
1398 
1401 
1402  // the position in the underlying map of SparseVector
1404 
1405  }; //end of class SparseVectorConstReverseIterator
1406 
1407 
1408  }; //end of class SparseVector
1409 
1410 }
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 &quot;more effective c++&quot; section 30
Definition: SparseVector.h:480
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
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 =&gt; 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 =&gt; 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

OpenMS / TOPP release 1.11.1 Documentation generated on Thu Nov 14 2013 11:19:21 using doxygen 1.8.5