source: trunk/lib/Vector.h @ 1481

#ifndef _theplu_svndigest_vector_
#define _theplu_svndigest_vector_

// $Id: Vector.h 1481 2012-06-03 11:29:54Z peter $

/*
  Copyright (C) 2010, 2012 Peter Johansson

  This file is part of svndigest, http://dev.thep.lu.se/svndigest

  svndigest is free software; you can redistribute it and/or modify it
  under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 3 of the License, or
  (at your option) any later version.

  svndigest is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with svndigest. If not, see <http://www.gnu.org/licenses/>.
*/

#include <iostream>

#include <subversion-1/svn_types.h>

#include <algorithm>
#include <cassert>
#include <map>

namespace theplu {
namespace svndigest {

  /**
     \brief Sparse Vector
  */
  template<typename T, class Policy>
  class Vector {
    typedef typename std::map<svn_revnum_t, T> Map;
  public:
    // iterator to underlying container, used in begin() and end()
    typedef typename Map::const_iterator const_iterator;
    // iterator to underlying container, used in begin() and end()
    typedef typename Map::const_reverse_iterator const_reverse_iterator;

    /**
       \brief default constructor
     */
    Vector(void) 
      : size_(0)
    {}

    /**
       \note Vector cannot be empty

       \return last element
     */
    T back(void) const
    { 
      assert(size()>0);
      if (map_.empty() || size()-1 > map_.rbegin()->first)
        return policy_.get(map_, map_.end());
      // check that size and elements are consistent
      assert(size()-1 == map_.rbegin()->first);
      return map_.rbegin()->second;
    }

    /**
       \return first non-trivial element

       The iterator iterates only over non-trivial element, e.g.,
       non-zero in SparseVector. If you need to iterate over all
       elements you can use operator[] and size().
     */
    const_iterator begin(void) const { return map_.begin(); }

    /**
       \brief make container empty
     */
    void clear(void) 
    { 
      map_.clear(); 
      size_ = 0;
    }

    /**
       \return true if Vector is empty
     */
    bool empty(void) const
    { return map_.empty(); }

    /*
      \return end of Vector
     */
    const_iterator end(void) const { return map_.end(); }

    /**
       same as begin() but reverse iterator 
     */
    const_reverse_iterator rbegin(void) const { return map_.rbegin(); }

    /**
       same as end() but reverse iterator 
     */
    const_reverse_iterator rend(void) const { return map_.rend(); }

    /*
      set size to \a size
     */
    void resize(svn_revnum_t size)
    {
      size_ = size;
      // remove elements with rev [size, inf)
      typename Map::iterator i = map_.lower_bound(size);
      map_.erase(i, map_.end());
    }

    /**
       works as vec[revision] = count
     */
    void set(svn_revnum_t revision, T count)
    {
      // FIXME: we should let policy collaps map, if possible
      map_[revision] = count;
      size_ = std::max(revision+1, size_);
    }

    /**
       \return value of revision \a rev

       If revision \a rev is non-trivial, i.e., directly stored in
       underlying container, its value is returned. Otherwise, return
       value is decided by the policy class.
     */
    T operator[](svn_revnum_t rev) const
    {
      const_iterator i = map_.lower_bound(rev);
      if (i!=map_.end() && i->first == rev)
        return i->second;
      return policy_.get(map_, i);
    }

    /**
       \brief add \a other to this
     */
    Vector& operator+=(const Vector& other)
    {
      // make a copy (of map_) whose iterators are not invalidated
      // when we insert values into map_.
      Map old;
      // Efficient way (constant time) to copy map_ into old and clear map_
      std::swap(old, map_);
      const_iterator first1 = old.begin();
      const_iterator last1 = old.end();
      const_iterator first2 = other.begin();
      const_iterator last2 = other.end();
      while (first1!=last1 || first2!=last2) {
        svn_revnum_t rev = 0;
        T value = 0;
        if (first1==last1) {
          rev = first2->first;
          value = policy_.get(old, first1) + first2->second;
          ++first2;
        }
        else if (first2==last2 || first1->first < first2->first) {
          rev = first1->first;
          value = first1->second + other.policy_.get(other.map_, first2);
          ++first1;
        }
        else if (first1->first == first2->first) {
          rev = first1->first;
          value = first1->second + first2->second;
          ++first1;
          ++first2;
        }
        else if (first1->first > first2->first) {
          rev = first2->first;
          value = policy_.get(old, first1) + first2->second;
          ++first2;
        }
        map_.insert(map_.end(), std::make_pair(rev, value));
      }
      size_ = std::max(size_, other.size());
      return *this;
    }

    /**
       \return size of vector
     */
    svn_revnum_t size(void) const
    {
      return size_;
    }

  private:
    Map map_;
    Policy policy_;
    svn_revnum_t size_;

    // using compiler generated copy constructor
    // Vector(const Vector&)
    // Vector& operator=(const Vector&);
  };

  template<typename T>
  class SparsePolicy
  {
    typedef typename std::map<svn_revnum_t, T> M;
  public:
    T get(const M&, typename M::const_iterator) const
    { return 0; }

  };

  typedef Vector<int, SparsePolicy<int> > SparseVector;

  template<typename T>
  class SumPolicy
  {
    typedef typename std::map<svn_revnum_t, T> M;
  public:
    /*
      iter points to first element after rev, while we wanna return
      the value of the first element before rev, so we iterate one
      step back and return its value;

      The exception is when there is no value before rev in which case
      we return 0, i.e., all revs up to the first element is 0.
     */
    T get(const M& map, typename M::const_iterator iter) const
    { 
      if (iter==map.begin())
        return 0;
      return (--iter)->second;
    }
  };

  typedef Vector<unsigned int, SumPolicy<unsigned int> > SumVector;

  /**
     create a SumVector from a ParseVector

     result[i] = result[i-1] + vec[i];
  */
  void accumulate(const SparseVector& vec, SumVector& result);

}} // end of namespace svndigest and namespace theplu

#endif