source: trunk/lib/Vector.h @ 1195

Last change on this file since 1195 was 1195, checked in by Peter Johansson, 11 years ago

refs #475, erase elements in underlying map (when possible) when resizing Vector.

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