lib/Vector.h

Code
Comments
Other
Rev Date Author Line
1187 28 Aug 10 peter 1 #ifndef _theplu_svndigest_vector_
1187 28 Aug 10 peter 2 #define _theplu_svndigest_vector_
1187 28 Aug 10 peter 3
1187 28 Aug 10 peter 4 // $Id$
1187 28 Aug 10 peter 5
1187 28 Aug 10 peter 6 /*
1515 26 Sep 12 peter 7   Copyright (C) 2010, 2011, 2012 Peter Johansson
1187 28 Aug 10 peter 8
1187 28 Aug 10 peter 9   This file is part of svndigest, http://dev.thep.lu.se/svndigest
1187 28 Aug 10 peter 10
1187 28 Aug 10 peter 11   svndigest is free software; you can redistribute it and/or modify it
1187 28 Aug 10 peter 12   under the terms of the GNU General Public License as published by
1187 28 Aug 10 peter 13   the Free Software Foundation; either version 3 of the License, or
1187 28 Aug 10 peter 14   (at your option) any later version.
1187 28 Aug 10 peter 15
1187 28 Aug 10 peter 16   svndigest is distributed in the hope that it will be useful, but
1187 28 Aug 10 peter 17   WITHOUT ANY WARRANTY; without even the implied warranty of
1187 28 Aug 10 peter 18   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1187 28 Aug 10 peter 19   General Public License for more details.
1187 28 Aug 10 peter 20
1187 28 Aug 10 peter 21   You should have received a copy of the GNU General Public License
1187 28 Aug 10 peter 22   along with svndigest. If not, see <http://www.gnu.org/licenses/>.
1187 28 Aug 10 peter 23 */
1187 28 Aug 10 peter 24
1194 03 Oct 10 peter 25 #include <iostream>
1194 03 Oct 10 peter 26
1187 28 Aug 10 peter 27 #include <subversion-1/svn_types.h>
1187 28 Aug 10 peter 28
1194 03 Oct 10 peter 29 #include <algorithm>
1194 03 Oct 10 peter 30 #include <cassert>
1187 28 Aug 10 peter 31 #include <map>
1187 28 Aug 10 peter 32
1187 28 Aug 10 peter 33 namespace theplu {
1187 28 Aug 10 peter 34 namespace svndigest {
1187 28 Aug 10 peter 35
1187 28 Aug 10 peter 36   /**
1187 28 Aug 10 peter 37      \brief Sparse Vector
1187 28 Aug 10 peter 38   */
1187 28 Aug 10 peter 39   template<typename T, class Policy>
1187 28 Aug 10 peter 40   class Vector {
1187 28 Aug 10 peter 41     typedef typename std::map<svn_revnum_t, T> Map;
1187 28 Aug 10 peter 42   public:
1187 28 Aug 10 peter 43     // iterator to underlying container, used in begin() and end()
1187 28 Aug 10 peter 44     typedef typename Map::const_iterator const_iterator;
1194 03 Oct 10 peter 45     // iterator to underlying container, used in begin() and end()
1194 03 Oct 10 peter 46     typedef typename Map::const_reverse_iterator const_reverse_iterator;
1187 28 Aug 10 peter 47
1187 28 Aug 10 peter 48     /**
1187 28 Aug 10 peter 49        \brief default constructor
1187 28 Aug 10 peter 50      */
1513 23 Sep 12 peter 51     Vector(void)
1194 03 Oct 10 peter 52       : size_(0)
1194 03 Oct 10 peter 53     {}
1187 28 Aug 10 peter 54
1187 28 Aug 10 peter 55     /**
1194 03 Oct 10 peter 56        \note Vector cannot be empty
1194 03 Oct 10 peter 57
1194 03 Oct 10 peter 58        \return last element
1194 03 Oct 10 peter 59      */
1194 03 Oct 10 peter 60     T back(void) const
1513 23 Sep 12 peter 61     {
1194 03 Oct 10 peter 62       assert(size()>0);
1196 04 Oct 10 peter 63       if (map_.empty() || size()-1 > map_.rbegin()->first)
1196 04 Oct 10 peter 64         return policy_.get(map_, map_.end());
1196 04 Oct 10 peter 65       // check that size and elements are consistent
1196 04 Oct 10 peter 66       assert(size()-1 == map_.rbegin()->first);
1196 04 Oct 10 peter 67       return map_.rbegin()->second;
1194 03 Oct 10 peter 68     }
1194 03 Oct 10 peter 69
1194 03 Oct 10 peter 70     /**
1187 28 Aug 10 peter 71        \return first non-trivial element
1187 28 Aug 10 peter 72
1187 28 Aug 10 peter 73        The iterator iterates only over non-trivial element, e.g.,
1187 28 Aug 10 peter 74        non-zero in SparseVector. If you need to iterate over all
1187 28 Aug 10 peter 75        elements you can use operator[] and size().
1187 28 Aug 10 peter 76      */
1187 28 Aug 10 peter 77     const_iterator begin(void) const { return map_.begin(); }
1187 28 Aug 10 peter 78
1187 28 Aug 10 peter 79     /**
1187 28 Aug 10 peter 80        \brief make container empty
1187 28 Aug 10 peter 81      */
1513 23 Sep 12 peter 82     void clear(void)
1513 23 Sep 12 peter 83     {
1513 23 Sep 12 peter 84       map_.clear();
1194 03 Oct 10 peter 85       size_ = 0;
1194 03 Oct 10 peter 86     }
1187 28 Aug 10 peter 87
1194 03 Oct 10 peter 88     /**
1194 03 Oct 10 peter 89        \return true if Vector is empty
1194 03 Oct 10 peter 90      */
1194 03 Oct 10 peter 91     bool empty(void) const
1194 03 Oct 10 peter 92     { return map_.empty(); }
1194 03 Oct 10 peter 93
1187 28 Aug 10 peter 94     /*
1187 28 Aug 10 peter 95       \return end of Vector
1187 28 Aug 10 peter 96      */
1187 28 Aug 10 peter 97     const_iterator end(void) const { return map_.end(); }
1187 28 Aug 10 peter 98
1187 28 Aug 10 peter 99     /**
1513 23 Sep 12 peter 100        same as begin() but reverse iterator
1194 03 Oct 10 peter 101      */
1194 03 Oct 10 peter 102     const_reverse_iterator rbegin(void) const { return map_.rbegin(); }
1194 03 Oct 10 peter 103
1194 03 Oct 10 peter 104     /**
1513 23 Sep 12 peter 105        same as end() but reverse iterator
1194 03 Oct 10 peter 106      */
1194 03 Oct 10 peter 107     const_reverse_iterator rend(void) const { return map_.rend(); }
1194 03 Oct 10 peter 108
1194 03 Oct 10 peter 109     /*
1194 03 Oct 10 peter 110       set size to \a size
1194 03 Oct 10 peter 111      */
1194 03 Oct 10 peter 112     void resize(svn_revnum_t size)
1194 03 Oct 10 peter 113     {
1194 03 Oct 10 peter 114       size_ = size;
1195 04 Oct 10 peter 115       // remove elements with rev [size, inf)
1195 04 Oct 10 peter 116       typename Map::iterator i = map_.lower_bound(size);
1195 04 Oct 10 peter 117       map_.erase(i, map_.end());
1194 03 Oct 10 peter 118     }
1194 03 Oct 10 peter 119
1194 03 Oct 10 peter 120     /**
1187 28 Aug 10 peter 121        works as vec[revision] = count
1187 28 Aug 10 peter 122      */
1187 28 Aug 10 peter 123     void set(svn_revnum_t revision, T count)
1187 28 Aug 10 peter 124     {
1187 28 Aug 10 peter 125       // FIXME: we should let policy collaps map, if possible
1187 28 Aug 10 peter 126       map_[revision] = count;
1194 03 Oct 10 peter 127       size_ = std::max(revision+1, size_);
1187 28 Aug 10 peter 128     }
1187 28 Aug 10 peter 129
1187 28 Aug 10 peter 130     /**
1187 28 Aug 10 peter 131        \return value of revision \a rev
1187 28 Aug 10 peter 132
1187 28 Aug 10 peter 133        If revision \a rev is non-trivial, i.e., directly stored in
1187 28 Aug 10 peter 134        underlying container, its value is returned. Otherwise, return
1187 28 Aug 10 peter 135        value is decided by the policy class.
1187 28 Aug 10 peter 136      */
1187 28 Aug 10 peter 137     T operator[](svn_revnum_t rev) const
1187 28 Aug 10 peter 138     {
1187 28 Aug 10 peter 139       const_iterator i = map_.lower_bound(rev);
1187 28 Aug 10 peter 140       if (i!=map_.end() && i->first == rev)
1187 28 Aug 10 peter 141         return i->second;
1187 28 Aug 10 peter 142       return policy_.get(map_, i);
1187 28 Aug 10 peter 143     }
1187 28 Aug 10 peter 144
1187 28 Aug 10 peter 145     /**
1194 03 Oct 10 peter 146        \brief add \a other to this
1187 28 Aug 10 peter 147      */
1194 03 Oct 10 peter 148     Vector& operator+=(const Vector& other)
1187 28 Aug 10 peter 149     {
1481 03 Jun 12 peter 150       // make a copy (of map_) whose iterators are not invalidated
1481 03 Jun 12 peter 151       // when we insert values into map_.
1481 03 Jun 12 peter 152       Map old;
1481 03 Jun 12 peter 153       // Efficient way (constant time) to copy map_ into old and clear map_
1481 03 Jun 12 peter 154       std::swap(old, map_);
1481 03 Jun 12 peter 155       const_iterator first1 = old.begin();
1481 03 Jun 12 peter 156       const_iterator last1 = old.end();
1194 03 Oct 10 peter 157       const_iterator first2 = other.begin();
1194 03 Oct 10 peter 158       const_iterator last2 = other.end();
1194 03 Oct 10 peter 159       while (first1!=last1 || first2!=last2) {
1194 03 Oct 10 peter 160         svn_revnum_t rev = 0;
1481 03 Jun 12 peter 161         T value = 0;
1194 03 Oct 10 peter 162         if (first1==last1) {
1194 03 Oct 10 peter 163           rev = first2->first;
1481 03 Jun 12 peter 164           value = policy_.get(old, first1) + first2->second;
1194 03 Oct 10 peter 165           ++first2;
1194 03 Oct 10 peter 166         }
1481 03 Jun 12 peter 167         else if (first2==last2 || first1->first < first2->first) {
1194 03 Oct 10 peter 168           rev = first1->first;
1481 03 Jun 12 peter 169           value = first1->second + other.policy_.get(other.map_, first2);
1194 03 Oct 10 peter 170           ++first1;
1194 03 Oct 10 peter 171         }
1194 03 Oct 10 peter 172         else if (first1->first == first2->first) {
1194 03 Oct 10 peter 173           rev = first1->first;
1481 03 Jun 12 peter 174           value = first1->second + first2->second;
1194 03 Oct 10 peter 175           ++first1;
1194 03 Oct 10 peter 176           ++first2;
1194 03 Oct 10 peter 177         }
1194 03 Oct 10 peter 178         else if (first1->first > first2->first) {
1194 03 Oct 10 peter 179           rev = first2->first;
1481 03 Jun 12 peter 180           value = policy_.get(old, first1) + first2->second;
1194 03 Oct 10 peter 181           ++first2;
1194 03 Oct 10 peter 182         }
1481 03 Jun 12 peter 183         map_.insert(map_.end(), std::make_pair(rev, value));
1194 03 Oct 10 peter 184       }
1481 03 Jun 12 peter 185       size_ = std::max(size_, other.size());
1418 25 Oct 11 peter 186       return *this;
1495 27 Aug 12 peter 187       return *this;
1187 28 Aug 10 peter 188     }
1187 28 Aug 10 peter 189
1194 03 Oct 10 peter 190     /**
1194 03 Oct 10 peter 191        \return size of vector
1194 03 Oct 10 peter 192      */
1194 03 Oct 10 peter 193     svn_revnum_t size(void) const
1194 03 Oct 10 peter 194     {
1194 03 Oct 10 peter 195       return size_;
1194 03 Oct 10 peter 196     }
1194 03 Oct 10 peter 197
1187 28 Aug 10 peter 198   private:
1187 28 Aug 10 peter 199     Map map_;
1187 28 Aug 10 peter 200     Policy policy_;
1194 03 Oct 10 peter 201     svn_revnum_t size_;
1187 28 Aug 10 peter 202
1187 28 Aug 10 peter 203     // using compiler generated copy constructor
1187 28 Aug 10 peter 204     // Vector(const Vector&)
1187 28 Aug 10 peter 205     // Vector& operator=(const Vector&);
1187 28 Aug 10 peter 206   };
1187 28 Aug 10 peter 207
1187 28 Aug 10 peter 208   template<typename T>
1187 28 Aug 10 peter 209   class SparsePolicy
1187 28 Aug 10 peter 210   {
1187 28 Aug 10 peter 211     typedef typename std::map<svn_revnum_t, T> M;
1187 28 Aug 10 peter 212   public:
1187 28 Aug 10 peter 213     T get(const M&, typename M::const_iterator) const
1187 28 Aug 10 peter 214     { return 0; }
1187 28 Aug 10 peter 215
1187 28 Aug 10 peter 216   };
1187 28 Aug 10 peter 217
1208 07 Oct 10 peter 218   typedef Vector<int, SparsePolicy<int> > SparseVector;
1187 28 Aug 10 peter 219
1187 28 Aug 10 peter 220   template<typename T>
1187 28 Aug 10 peter 221   class SumPolicy
1187 28 Aug 10 peter 222   {
1187 28 Aug 10 peter 223     typedef typename std::map<svn_revnum_t, T> M;
1187 28 Aug 10 peter 224   public:
1187 28 Aug 10 peter 225     /*
1187 28 Aug 10 peter 226       iter points to first element after rev, while we wanna return
1187 28 Aug 10 peter 227       the value of the first element before rev, so we iterate one
1187 28 Aug 10 peter 228       step back and return its value;
1187 28 Aug 10 peter 229
1187 28 Aug 10 peter 230       The exception is when there is no value before rev in which case
1187 28 Aug 10 peter 231       we return 0, i.e., all revs up to the first element is 0.
1187 28 Aug 10 peter 232      */
1187 28 Aug 10 peter 233     T get(const M& map, typename M::const_iterator iter) const
1513 23 Sep 12 peter 234     {
1187 28 Aug 10 peter 235       if (iter==map.begin())
1187 28 Aug 10 peter 236         return 0;
1187 28 Aug 10 peter 237       return (--iter)->second;
1187 28 Aug 10 peter 238     }
1187 28 Aug 10 peter 239   };
1187 28 Aug 10 peter 240
1187 28 Aug 10 peter 241   typedef Vector<unsigned int, SumPolicy<unsigned int> > SumVector;
1187 28 Aug 10 peter 242
1187 28 Aug 10 peter 243   /**
1187 28 Aug 10 peter 244      create a SumVector from a ParseVector
1187 28 Aug 10 peter 245
1187 28 Aug 10 peter 246      result[i] = result[i-1] + vec[i];
1187 28 Aug 10 peter 247   */
1194 03 Oct 10 peter 248   void accumulate(const SparseVector& vec, SumVector& result);
1187 28 Aug 10 peter 249
1187 28 Aug 10 peter 250 }} // end of namespace svndigest and namespace theplu
1187 28 Aug 10 peter 251
1187 28 Aug 10 peter 252 #endif

Generated on Thu Jul 20 08:39:01 2023 (UTC) by svndigest 0.12pre (dev build 1672)