SparseVector.h

Go to the documentation of this file.

// --------------------------------------------------------------------------
//                   OpenMS -- Open-Source Mass Spectrometry
// --------------------------------------------------------------------------
// Copyright The OpenMS Team -- Eberhard Karls University Tuebingen,
// ETH Zurich, and Freie Universitaet Berlin 2002-2012.
//
// This software is released under a three-clause BSD license:
//  * Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
//  * Redistributions in binary form must reproduce the above copyright
//    notice, this list of conditions and the following disclaimer in the
//    documentation and/or other materials provided with the distribution.
//  * Neither the name of any author or any participating institution
//    may be used to endorse or promote products derived from this software
//    without specific prior written permission.
// For a full list of authors, refer to the file AUTHORS.
// --------------------------------------------------------------------------
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL ANY OF THE AUTHORS OR THE CONTRIBUTING
// INSTITUTIONS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
// OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
// OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
// ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// --------------------------------------------------------------------------
// $Maintainer: Mathias Walzer $
// $Authors: $
// --------------------------------------------------------------------------
//
#ifndef OPENMS_DATASTRUCTURES_SPARSEVECTOR_H
#define OPENMS_DATASTRUCTURES_SPARSEVECTOR_H

#include <map>
#include <algorithm>
#include <stdexcept>
#include <cassert>
#include <cmath>
#include <sstream>
#include <OpenMS/CONCEPT/Exception.h>

#include <iostream>

namespace OpenMS
{
  template <typename Value>
  class SparseVector
  {

public:

    //forward declarations
    class SparseVectorConstIterator;
    class SparseVectorIterator;
    class SparseVectorReverseIterator;
    class SparseVectorConstReverseIterator;
    class ValueProxy;

    //made available from this classes
    typedef SparseVectorConstIterator const_iterator;
    typedef SparseVectorConstReverseIterator const_reverse_iterator;
    typedef SparseVectorIterator iterator;
    typedef SparseVectorReverseIterator reverse_iterator;

    //remapping
    typedef typename std::map<size_t, Value>::difference_type difference_type;        //needed?
    typedef typename std::map<size_t, Value>::size_type size_type;
    typedef typename std::map<size_t, Value>::allocator_type allocator_type;        //needed?
    typedef Value value_type;
    typedef Value * pointer;        //needed?
    typedef ValueProxy & reference;
    typedef const ValueProxy & const_reference;

    //internal use
    typedef typename std::map<size_t, Value>::const_iterator map_const_iterator;
    typedef typename std::map<size_t, Value>::iterator map_iterator;
    typedef typename std::map<size_t, Value>::const_reverse_iterator reverse_map_const_iterator;
    typedef typename std::map<size_t, Value>::reverse_iterator reverse_map_iterator;

    typedef SparseVectorConstIterator ConstIterator;
    typedef SparseVectorConstReverseIterator ConstReverseIterator;
    typedef SparseVectorIterator Iterator;
    typedef SparseVectorReverseIterator ReverseIterator;


    void print() const
    {
      std::cout << std::endl;
      for (map_const_iterator it = values_.begin(); it != values_.end(); ++it)
      {
        std::cout << it->first << ": " << it->second << std::endl;
      }
    }

    SparseVector() :
      values_(), size_(0), sparse_element_(0)
    {
    }

    SparseVector(Value se) :
      values_(), size_(0), sparse_element_(se)
    {
    }

    SparseVector(size_type size, Value value, Value se = 0) :
      values_(), size_(size), sparse_element_(se)
    {
      if (value != sparse_element_)          //change, if sparse element is another
      {
        map_iterator i = values_.begin();
        for (size_type s = 0; s < size; ++s)
        {
          //makes each insertion in amortized constant time inserted direct after last one
          i = values_.insert(i, std::make_pair(s, value));
        }
      }
    }

    SparseVector(const SparseVector & source) :
      values_(source.values_), size_(source.size_), sparse_element_(source.sparse_element_)
    {
    }

    SparseVector & operator=(const SparseVector & source)
    {
      if (this != &source)
      {
        values_ = source.values_;
        size_ = source.size_;
        sparse_element_ = source.sparse_element_;
      }
      return *this;
    }

    ~SparseVector()
    {
    }

    bool operator==(const SparseVector & rhs) const
    {
      return (values_ == rhs.values_) && (size_ == rhs.size_) && (sparse_element_ == rhs.sparse_element_);
    }

    bool operator<(const SparseVector & rhs) const
    {
      return values_ < rhs.values_;
    }

    size_type nonzero_size() const
    {
      return values_.size();
    }

    size_type size() const
    {
      return size_;
    }

    bool empty() const
    {
      return size() == 0;
    }

    void push_back(Value value)
    {
      operator[](size_++) = value;
    }

    Value at(size_type pos) const
    {
      if (pos >= size_)
      {
        throw Exception::OutOfRange(__FILE__, __LINE__, __PRETTY_FUNCTION__);
      }
      else
      {
        return operator[](pos);
      }
    }

    const Value /*Proxy*/ operator[](size_type pos) const
    {
      assert(pos < size_);
      return (Value)ValueProxy(const_cast<SparseVector &>(*this), pos);
    }

    ValueProxy operator[](size_type pos)
    {
      assert(pos < size_);
      return ValueProxy(*this, pos);
    }

    void clear()
    {
      values_.clear();
      size_ = 0;
    }

    void resize(size_type newsize)
    {
      // if the vector is to be smaller
      // delete all invalid entries
      if (newsize < size_)
      {
        for (map_iterator mit = values_.begin(); mit != values_.end(); )
        {
          if (mit->first >= newsize)
          {
            size_type nextvalue = (++mit)->first;
            values_.erase(--mit);
            mit = values_.find(nextvalue);
          }
          else
          {
            ++mit;
          }
        }
      }
      size_ = newsize;
    }

    void erase(SparseVectorIterator it)
    {
      if (it.position() >= size_)
      {
        throw Exception::OutOfRange(__FILE__, __LINE__, __PRETTY_FUNCTION__);
      }
      //store pointer to the element after the current element
      //erase element
      bool update = false;
      map_iterator mit = values_.find(it.position());
      map_iterator mit_next;
      if (mit != values_.end())             //element exists => erase it and update indices of elements after it
      {
        mit_next = mit;
        ++mit_next;
        values_.erase(mit);
        update = true;
      }
      else            //element does not exists => update indices of elements after it
      {
        mit_next = values_.lower_bound(it.position());
        update = true;
      }

      //update indices if necessary
      if (update) update_(mit_next, 1);

      --size_;
    }

    void erase(SparseVectorIterator first, SparseVectorIterator last)
    {
      if (first.position() >= size_ || last.position() > size_ || last.position() < first.position())
      {
        throw Exception::OutOfRange(__FILE__, __LINE__, __PRETTY_FUNCTION__);
      }

      size_type amount_deleted = last.position() - first.position();
      map_iterator mfirst = values_.lower_bound(first.position());
      map_iterator mlast = values_.lower_bound(last.position());

      if (mfirst == values_.begin())
      {
        values_.erase(mfirst, mlast);
        update_(values_.begin(), amount_deleted);
      }
      else
      {
        map_iterator start_it = mfirst;
        --start_it;
        values_.erase(mfirst, mlast);
        ++start_it;
        update_(start_it, amount_deleted);
      }

      size_ -= amount_deleted;
    }

    SparseVectorIterator getMinElement()
    {
      switch (size_)
      {
      case 0:
        break;

      case 1:
        return begin();

        break;

      default:
        if (values_.empty())
        {
          //only sparse elements left
          return begin();
        }
        bool first_sparse_found = false;
        size_type pos = 0;
        map_iterator lowest = values_.begin();
        map_iterator second = values_.begin();
        map_iterator first = second++;
        map_iterator last = values_.end();

        if (lowest->first > 0)
        {
          first_sparse_found = true;
        }

        while (second != last)
        {
          if (second->second < lowest->second)                 //the first element is covered by initial lowest == frst
          {
            lowest = second;
          }
          if (size_ > values_.size() && !first_sparse_found)
          {
            if ((second->first) - (first->first) > 1)
            {
              pos = first->first + 1;
              first_sparse_found = true;
            }
          }
          ++first; ++second;
        }

        if (size_ == values_.size() || lowest->second < SparseVector::sparse_element_)
        {
          return SparseVectorIterator(*this, lowest->first);
        }
        else                 //lowest->second >(=) sparseElement
        {
          if (!first_sparse_found)
          {
            return SparseVectorIterator(*this, first->first + 1);
          }
          return SparseVectorIterator(*this, pos);
        }
        break;
      }
      return end();
      //map_iterator pos = min_element(values_.begin(), values_.end()); //sorts by map.key :(
    }

    iterator begin()
    {
      return SparseVectorIterator(*this, 0);
    }

    iterator end()
    {
      return SparseVectorIterator(*this, this->size());
    }

    reverse_iterator rbegin()
    {
      return SparseVectorReverseIterator(*this, this->size());
    }

    reverse_iterator rend()
    {
      return SparseVectorReverseIterator(*this, 0);
    }

    const_iterator begin() const
    {
      return SparseVectorConstIterator(*this, 0);
    }

    const_iterator end() const
    {
      return SparseVectorConstIterator(*this, this->size());
    }

    const_reverse_iterator rbegin() const
    {
      return SparseVectorConstIterator(*this, this->size());
    }

    const_reverse_iterator rend() const
    {
      return SparseVectorConstIterator(*this, 0);
    }

private:
    std::map<size_type, Value> values_;

    size_type size_;

protected:

    Value sparse_element_;

    void update_(map_iterator it, Size amount_deleted)
    {
      while (it != values_.end())
      {
        size_type tmp_index = it->first;
        Value tmp_value = it->second;
        if (it != values_.begin())
        {
          //makes insertion in amortized constant time if really inserted directly after mit
          map_iterator tmp_it = it;
          --tmp_it;
          values_.erase(it);
          it = values_.insert(tmp_it, std::make_pair(tmp_index - amount_deleted, tmp_value));
        }
        else
        {
          //simply insert, as we have no element to insert after
          values_.erase(it);
          it = values_.insert(std::make_pair(tmp_index - amount_deleted, tmp_value)).first;
        }
        ++it;
      }
    }

public:

    class ValueProxy
    {

public:

      ValueProxy(SparseVector & vec, size_type index) :
        vec_(vec), index_(index)
      {
      }

      // if there is a entry in the map from SparseVector, return that
      // if not it is a zero, so return sparseElement
      operator double() const
      {
        double value = vec_.sparse_element_;
        map_const_iterator cmit = vec_.values_.find(index_);
        if (cmit != vec_.values_.end())
        {
          value = cmit->second;
        }
        return value;
      }

      operator int() const
      {
        int value = vec_.sparse_element_;
        map_const_iterator cmit = vec_.values_.find(index_);
        if (cmit != vec_.values_.end())
        {
          value = cmit->second;
        }
        return value;
      }

      operator float() const
      {
        float value = vec_.sparse_element_;
        map_const_iterator cmit = vec_.values_.find(index_);
        if (cmit != vec_.values_.end())
        {
          value = cmit->second;
        }
        return value;
      }

      // maybe more cast-operators for other types

      ValueProxy & operator=(const ValueProxy & rhs)
      {
        if ((this != &rhs) && (vec_ == rhs.vec_))
        {
          //if rhs' value != sparseElement, cmit!=rhs.vec_.values_.end()
          map_const_iterator cmit = rhs.vec_.values_.find(rhs.index_);
          if (cmit != rhs.vec_.values_.end())
          {
            vec_.values_[rhs.index_] = cmit->second;
          }
          //instead of setting value to zero erase it
          else
          {
            map_iterator mit = vec_.values_.find(rhs.index_);
            if (mit != vec_.values_.end())
            {
              vec_.values_.erase(mit);
            }
          }
          index_ = rhs.index_;
        }
        return *this;
      }

      ValueProxy & operator=(Value val)
      {
        if (val != vec_.sparse_element_)             //if (fabs(val) > 1e-8)
        {
          vec_.values_[index_] = val;
        }
        else
        {
          map_iterator mit = vec_.values_.find(index_);
          if (mit != vec_.values_.end())
          {
            vec_.values_.erase(mit);
          }
        }
        return *this;
      }

      bool operator!=(const ValueProxy & other)
      {

        return (index_ != other.index_) || (&vec_ != &other.vec_);
      }

      bool operator==(const ValueProxy & other)
      {
        return !(this != other);
      }

      bool operator<(const ValueProxy & other)
      {
        return (Value) * this < (Value)other;
      }

      bool operator>(const ValueProxy & other)
      {
        return (Value) * this > (Value)other;
      }

      bool operator<=(const ValueProxy & other)
      {
        return (Value) * this <= (Value)other;
      }

      bool operator>=(const ValueProxy & other)
      {
        return (Value) * this >= (Value)other;
      }

private:

      SparseVector & vec_;

      size_type index_;

    };      //end of class ValueProxy

    class SparseVectorIterator
    {
      friend class SparseVector<Value>;
      friend class SparseVectorConstIterator;

public:

      SparseVectorIterator(const SparseVectorIterator & source) :
        position_(source.position_),
        vector_(source.vector_),
        valit_(source.valit_)
      {
      }

      virtual ~SparseVectorIterator()
      {
      }

      SparseVectorIterator & operator=(const SparseVectorIterator & source)
      {
        if (this != &source)
        {
          position_ = source.position_;
          vector_ = source.vector_;
          valit_ = source.valit_;
        }
        return *this;
      }

      SparseVectorIterator & operator++()
      {
        ++position_;
        return *this;
      }

      SparseVectorIterator operator++(int)
      {
        SparseVectorIterator tmp(*this);
        ++position_;
        return tmp;
      }

      SparseVectorIterator & operator--()
      {
        --position_;
        return *this;
      }

      SparseVectorIterator operator--(int)
      {
        SparseVectorIterator tmp(*this);
        --position_;
        return tmp;
      }

      ValueProxy operator*()
      {
        assert(position_ < vector_.size_);
        return ValueProxy(this->vector_, position_);
      }

      const Value operator*() const
      {
        assert(position_ < vector_.size_);
        return (Value)ValueProxy(this->vector_, position_);
      }

      ValueProxy operator[](size_type n)
      {
        position_ += n;
        assert(position_ < vector_.size_);
        return ValueProxy(this->vector_, position_);
      }

      SparseVectorIterator & operator+=(const size_type rhs)
      {
        position_ += rhs;
        return *this;
      }

      SparseVectorIterator & operator-=(const size_type rhs)
      {
        position_ -= rhs;
        return *this;
      }

      SparseVectorIterator operator+(const size_type rhs) const
      {
        return SparseVectorIterator(vector_, position_ + rhs);
      }

      difference_type operator+(const SparseVectorIterator rhs) const
      {
        return position_ + rhs.position();
      }

      SparseVectorIterator operator-(const size_type rhs) const
      {
        return SparseVectorIterator(vector_, position_ - rhs);
      }

      difference_type operator-(const SparseVectorIterator rhs) const
      {
        return position_ - rhs.position();
      }

      bool operator!=(const SparseVectorIterator & other)
      {
        return position_ != other.position_ || &vector_ != &other.vector_;
      }

      bool operator==(const SparseVectorIterator & other)
      {
        return !(*this != other);
      }

      bool operator<(const SparseVectorIterator & other)
      {
        return position_ < other.position();
      }

      bool operator>(const SparseVectorIterator & other)
      {
        return position_ > other.position();
      }

      bool operator<=(const SparseVectorIterator & other)
      {
        return position_ <= other.position();
      }

      bool operator>=(const SparseVectorIterator & other)
      {
        return position_ >= other.position();
      }

      SparseVectorIterator & hop()
      {
        //assert(valit_ != vector_.values_.end() );
        //look for first entry if this is the first call. Go one step otherwise
        if (position_ != valit_->first)             //first call
        {
          valit_ = vector_.values_.upper_bound(position_);
        }
        else
        {
          ++valit_;
        }
        //check if we are at the end
        if (valit_ == vector_.values_.end())
        {
          position_ = vector_.size_;
        }
        else
        {
          position_ = valit_->first;
        }
        return *this;
      }

      size_type position() const
      {
        return position_;
      }

protected:

      SparseVectorIterator(SparseVector & vector, size_type position) :
        position_(position),
        vector_(vector),
        valit_(vector.values_.begin())
      {
      }

      size_type position_;

      SparseVector & vector_;

      map_const_iterator valit_;

private:

      SparseVectorIterator();

    };    //end of class SparseVectorIterator

    class SparseVectorReverseIterator
    {
      friend class SparseVector<Value>;
      friend class SparseVectorConstReverseIterator;

public:

      SparseVectorReverseIterator(const SparseVectorReverseIterator & source) :
        position_(source.position_),
        vector_(source.vector_),
        valrit_(source.valrit_)
      {
      }

      virtual ~SparseVectorReverseIterator()
      {
      }

      SparseVectorReverseIterator & operator=(const SparseVectorReverseIterator & source)
      {
        if (this != &source)
        {
          position_ = source.position_;
          vector_ = source.vector_;
          valrit_ = source.valrit_;
        }
        return *this;
      }

      SparseVectorReverseIterator & operator++()
      {
        --position_;
        return *this;
      }

      SparseVectorReverseIterator operator++(int)
      {
        SparseVectorReverseIterator tmp(*this);
        --position_;
        return tmp;
      }

      SparseVectorReverseIterator & operator--()
      {
        ++position_;
        return *this;
      }

      SparseVectorReverseIterator operator--(int)
      {
        SparseVectorReverseIterator tmp(*this);
        ++position_;
        return tmp;
      }

      Value operator*()
      {
        assert(position_ <= vector_.size_);
        assert(position_ != 0);
        return ValueProxy(this->vector_, position_ - 1);
      }

      ValueProxy operator[](size_type n)
      {
        position_ -= n;
        assert(position_ < vector_.size_);
        return ValueProxy(this->vector_, position_);
      }

      SparseVectorReverseIterator & operator+=(const size_type rhs)
      {
        position_ -= rhs;
        return *this;
      }

      SparseVectorReverseIterator & operator-=(const size_type rhs)
      {
        position_ += rhs;
        return *this;
      }

      SparseVectorReverseIterator operator+(const size_type rhs) const
      {
        return SparseVectorReverseIterator(vector_, position_ - rhs);
      }

      difference_type operator+(const SparseVectorReverseIterator rhs) const
      {
        return position_ + rhs.position();
      }

      SparseVectorReverseIterator operator-(const size_type rhs) const
      {
        return SparseVectorReverseIterator(vector_, position_ + rhs);
      }

      difference_type operator-(const SparseVectorReverseIterator rhs) const
      {
        //what about negatives?
        return -1 * (position_ - rhs.position());
      }

      bool operator!=(const SparseVectorReverseIterator & other)
      {
        return position_ != other.position_ || &vector_ != &other.vector_;
      }

      bool operator==(const SparseVectorReverseIterator & other)
      {
        return !(*this != other);
      }

      bool operator<(const SparseVectorReverseIterator & other)
      {
        return !(this->position() < other.position());
      }

      bool operator>(const SparseVectorReverseIterator & other)
      {
        return !(this->position() > other.position());
      }

      bool operator<=(const SparseVectorReverseIterator & other)
      {
        return !(this->position() <= other.position());
      }

      bool operator>=(const SparseVectorReverseIterator & other)
      {
        return !(this->position() >= other.position());
      }

      SparseVectorReverseIterator & rhop()
      {
        assert(valrit_ != reverse_map_const_iterator(vector_.values_.rend()));
        //look for first entry if this is the first call. Go one step otherwise
        if (position_ - 1 != valrit_->first)
        {
          valrit_ = reverse_map_const_iterator(--(vector_.values_.find(position_ - 1)));
        }
        else
        {
          ++valrit_;
        }
        //check if we are at the end(begin)
        if (valrit_ == reverse_map_const_iterator(vector_.values_.rend()))
        {
          position_ = 0;
        }
        else
        {
          position_ = valrit_->first + 1;
        }
        return *this;
      }

      size_type position() const
      {
        return position_;
      }

public:

      SparseVectorReverseIterator(SparseVector & vector, size_type position) :
        position_(position),
        vector_(vector),
        valrit_(vector.values_.rbegin())
      {
      }

protected:

      size_type position_;

private:
      SparseVector & vector_;

      reverse_map_const_iterator valrit_;

      SparseVectorReverseIterator();



    };    //end of class SparseVectorReverseIterator

    class SparseVectorConstIterator
    {
      friend class SparseVector<Value>;
      friend class SparseVectorIterator;

public:

      SparseVectorConstIterator(const SparseVectorConstIterator & source) :
        position_(source.position_),
        vector_(source.vector_),
        valit_(source.valit_)
      {
      }

      SparseVectorConstIterator(const SparseVectorIterator & source) :
        position_(source.position_),
        vector_(source.vector_),
        valit_(source.valit_)
      {
      }

      virtual ~SparseVectorConstIterator()
      {
      }

      SparseVectorConstIterator & operator=(const SparseVectorConstIterator & source)
      {
        if (this != &source)
        {
          position_ = source.position_;
          const_cast<SparseVector &>(this->vector_) = source.vector_;
          valit_ = source.valit_;
        }
        return *this;
      }

      SparseVectorConstIterator & operator++()
      {
        assert(position_ <= vector_.size_);
        ++position_;
        return *this;
      }

      SparseVectorConstIterator operator++(int)
      {
        SparseVectorConstIterator tmp(*this);
        ++position_;
        assert(position_ <= vector_.size_);
        return tmp;
      }

      SparseVectorConstIterator & operator--()
      {
        assert(position_ <= vector_.size_);
        --position_;
        return *this;
      }

      SparseVectorConstIterator operator--(int)
      {
        SparseVectorConstIterator tmp(*this);
        --position_;
        assert(position_ <= vector_.size_);
        return tmp;
      }

      const Value operator*() const
      {
        assert(position_ < vector_.size_);
        return (Value)ValueProxy(const_cast<SparseVector &>(this->vector_), position_);
      }

      // indexing
      const ValueProxy operator[](size_type n) const
      {
        position_ += n;
        assert(position_ < vector_.size_);
        return ValueProxy(const_cast<SparseVector &>(this->vector_), position_);
      }

      SparseVectorConstIterator & operator+=(const size_type rhs)
      {
        position_ += rhs;
        return *this;
      }

      SparseVectorConstIterator & operator-=(const size_type rhs)
      {
        position_ -= rhs;
        return *this;
      }

      SparseVectorConstIterator operator+(const size_type rhs) const
      {
        return SparseVectorConstIterator(const_cast<SparseVector &>(this->vector_), position_ + rhs);
      }

      SparseVectorConstIterator operator-(const size_type rhs) const
      {
        return SparseVectorConstIterator(const_cast<SparseVector &>(this->vector_), position_ - rhs);
      }

      bool operator!=(const SparseVectorConstIterator & other)
      {
        return position_ != other.position_ || &vector_ != &other.vector_;
      }

      bool operator==(const SparseVectorConstIterator & other)
      {
        return !(*this != other);
      }

      bool operator<(const SparseVectorConstIterator & other)
      {
        return this->position() < other.position();
      }

      bool operator>(const SparseVectorConstIterator & other)
      {
        return this->position() > other.position();
      }

      bool operator<=(const SparseVectorConstIterator & other)
      {
        return this->position() <= other.position();
      }

      bool operator>=(const SparseVectorConstIterator & other)
      {
        return this->position() >= other.position();
      }

      SparseVectorConstIterator & hop()
      {
        assert(valit_ != vector_.values_.end());
        //look for first entry if this is the first call. Go one step otherwise
        if (position_ != valit_->first)             //first call
        {
          valit_ = vector_.values_.upper_bound(position_);
        }
        else
        {
          ++valit_;
        }
        //check if we are at the end
        if (valit_ == vector_.values_.end())
        {
          position_ = vector_.size_;
        }
        else
        {
          position_ = valit_->first;
        }
        return *this;
      }

      size_type position() const
      {
        return position_;
      }

protected:
      SparseVectorConstIterator();

      SparseVectorConstIterator(const SparseVector & vector, size_type position) :
        position_(position),
        vector_(vector),
        valit_(vector.values_.begin())
      {
      }

private:
      mutable size_type position_;

      const SparseVector & vector_;

      map_const_iterator valit_;

    };      //end of class SparseVectorConstIterator

    class SparseVectorConstReverseIterator
    {
      friend class SparseVector<Value>;

public:

      SparseVectorConstReverseIterator(const SparseVectorConstIterator & source) :
        position_(source.position_),
        vector_(source.vector_),
        valrit_(source.valrit_)
      {
      }

      SparseVectorConstReverseIterator(const SparseVectorReverseIterator & source) :
        position_(source.position_),
        vector_(source.vector_),
        valrit_(source.valrit_)
      {
      }

      virtual ~SparseVectorConstReverseIterator()
      {
      }

      SparseVectorConstReverseIterator & operator=(const SparseVectorConstReverseIterator & source)
      {
        if (this != &source)
        {
          position_ = source.position_;
          const_cast<SparseVector &>(this->vector_) = source.vector_;
          valrit_ = source.valrit_;
        }
        return *this;
      }

      SparseVectorConstReverseIterator & operator++()
      {
        //assert(position_ < 0);
        --position_;
        return *this;
      }

      SparseVectorConstReverseIterator operator++(int)
      {
        SparseVectorConstIterator tmp(*this);
        --position_;
        //assert(position_ < 0);
        return tmp;
      }

      SparseVectorConstReverseIterator & operator--()
      {
        //assert(position_ < 0);
        ++position_;
        return *this;
      }

      SparseVectorConstReverseIterator operator--(int)
      {
        SparseVectorConstIterator tmp(*this);
        ++position_;
        //assert(position_ < 0);
        return tmp;
      }

      ValueProxy operator*()
      {
        assert(position_ <= vector_.size_);
        assert(position_ != 0);
        return ValueProxy(const_cast<SparseVector &>(this->vector_), position_ - 1);
      }

      SparseVectorConstReverseIterator & rhop()
      {
        assert(valrit_ != vector_.values_.rend());
        //look for first entry if this is the first call. Go one step otherwise
        if (position_ - 1 != valrit_->first)
        {
          valrit_ = reverse_map_const_iterator(--(vector_.values_.find(position_ - 1)));
        }
        else
        {
          ++valrit_;
        }
        //check if we are at the end(begin)
        if (valrit_ == reverse_map_const_iterator(vector_.values_.rend()))
        {
          position_ = 0;
        }
        else
        {
          position_ = valrit_->first + 1;
        }
        return *this;
      }

      size_type position() const
      {
        return position_;
      }

      bool operator!=(const SparseVectorConstReverseIterator & other)
      {
        return position_ != other.position_ || &vector_ != &other.vector_;
      }

protected:

      SparseVectorConstReverseIterator();

      SparseVectorConstReverseIterator(const SparseVector & vector, size_type position) :
        position_(position), vector_(vector), valrit_(vector.values_.rbegin())
      {
      }

private:

      // the position in SparseVector
      mutable size_type position_;

      const SparseVector & vector_;

      // the position in the underlying map of SparseVector
      reverse_map_const_iterator valrit_;

    };      //end of class SparseVectorConstReverseIterator


  };  //end of class SparseVector

}
#endif //OPENMS_DATASTRUCTURES_SPARSEVECTOR_H