source: trunk/lib/Vector.h @ 1187

#ifndef _theplu_svndigest_vector_
#define _theplu_svndigest_vector_

// $Id: Vector.h 1187 2010-08-28 21:58:37Z peter $

/*
  Copyright (C) 2010 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 <subversion-1/svn_types.h>

#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;

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

    /**
       \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(); }

    /*
      \return end of Vector
     */
    const_iterator end(void) const { return 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;
    }

    /**
       \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);
    }

    /**
       \return 0 if Vector is empty; otherwise the largest_rev + 1
     */
    size_t size(void) const
    {
      if (map_.empty())
        return 0;
      return map_.rbegin()->first + 1;
    }

  private:
    Map map_;
    Policy policy_;

    // 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<unsigned int, SparsePolicy<unsigned 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)
  {
    result.clear();
    unsigned int value = 0;
    for (SumVector::const_iterator iter = vec.begin(); iter!=vec.end();++iter) {
      value += iter->second;
      result.set(iter->first, value);
    }
  }

}} // end of namespace svndigest and namespace theplu

#endif