source: trunk/lib/Vector.h @ 1194

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

refs #475. First version using Sparse Vector class. This change is obviously quite invasive and thus the size of this commit is larger than what is preferred. I've tried to limit as much as possible and left optimization and style issues behind with a note 'FIXME'.

  • 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 1194 2010-10-03 23:39:12Z 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      // FIXME: avoid logN lookup time
63      assert(size()>0);
64      return (*this)[size()-1];
65    }
66
67    /**
68       \return first non-trivial element
69
70       The iterator iterates only over non-trivial element, e.g.,
71       non-zero in SparseVector. If you need to iterate over all
72       elements you can use operator[] and size().
73     */
74    const_iterator begin(void) const { return map_.begin(); }
75
76    /**
77       \brief make container empty
78     */
79    void clear(void) 
80    { 
81      map_.clear(); 
82      size_ = 0;
83    }
84
85    /**
86       \return true if Vector is empty
87     */
88    bool empty(void) const
89    { return map_.empty(); }
90
91    /*
92      \return end of Vector
93     */
94    const_iterator end(void) const { return map_.end(); }
95
96    /**
97       same as begin() but reverse iterator
98     */
99    const_reverse_iterator rbegin(void) const { return map_.rbegin(); }
100
101    /**
102       same as end() but reverse iterator
103     */
104    const_reverse_iterator rend(void) const { return map_.rend(); }
105
106    /*
107      set size to \a size
108     */
109    void resize(svn_revnum_t size)
110    {
111      size_ = size;
112    }
113
114    /**
115       works as vec[revision] = count
116     */
117    void set(svn_revnum_t revision, T count)
118    {
119      // FIXME: we should let policy collaps map, if possible
120      map_[revision] = count;
121      size_ = std::max(revision+1, size_);
122    }
123
124    /**
125       \return value of revision \a rev
126
127       If revision \a rev is non-trivial, i.e., directly stored in
128       underlying container, its value is returned. Otherwise, return
129       value is decided by the policy class.
130     */
131    T operator[](svn_revnum_t rev) const
132    {
133      const_iterator i = map_.lower_bound(rev);
134      if (i!=map_.end() && i->first == rev)
135        return i->second;
136      return policy_.get(map_, i);
137    }
138
139    /**
140       \brief add \a other to this
141     */
142    Vector& operator+=(const Vector& other)
143    {
144      Vector result;
145      typename Map::iterator first1 = map_.begin();
146      typename Map::iterator last1 = map_.end();
147      const_iterator first2 = other.begin();
148      const_iterator last2 = other.end();
149      while (first1!=last1 || first2!=last2) {
150        svn_revnum_t rev = 0;
151        if (first1==last1) {
152          rev = first2->first;
153          ++first2;
154        }
155        else if (first2==last2) {
156          rev = first1->first;
157          ++first1;
158        }
159        else if (first1->first < first2->first) {
160          rev = first1->first;
161          ++first1;
162        }
163        else if (first1->first == first2->first) {
164          rev = first1->first;
165          ++first1;
166          ++first2;
167        }
168        else if (first1->first > first2->first) {
169          rev = first2->first;
170          ++first2;
171        }
172        result.set(rev, (*this)[rev] + other[rev]); 
173      }
174      // assign result map to this
175      std::swap(map_, result.map_);
176      resize(std::max(size_, other.size()));
177    }
178
179    /**
180       \return size of vector
181     */
182    svn_revnum_t size(void) const
183    {
184      return size_;
185    }
186
187  private:
188    Map map_;
189    Policy policy_;
190    svn_revnum_t size_;
191
192    // using compiler generated copy constructor
193    // Vector(const Vector&)
194    // Vector& operator=(const Vector&);
195  };
196
197  template<typename T, class Policy>
198  Vector<T, Policy> operator+(const Vector<T, Policy>& lhs,
199                              const Vector<T, Policy>& rhs)
200  {
201    Vector<T, Policy> result(lhs);
202    result+=rhs;
203    assert(result.size()>=lhs.size());
204    assert(result.size()>=rhs.size());
205    return result;
206  }
207
208
209  template<typename T>
210  class SparsePolicy
211  {
212    typedef typename std::map<svn_revnum_t, T> M;
213  public:
214    T get(const M&, typename M::const_iterator) const
215    { return 0; }
216
217  };
218
219  typedef Vector<unsigned int, SparsePolicy<unsigned int> > SparseVector;
220
221  template<typename T>
222  class SumPolicy
223  {
224    typedef typename std::map<svn_revnum_t, T> M;
225  public:
226    /*
227      iter points to first element after rev, while we wanna return
228      the value of the first element before rev, so we iterate one
229      step back and return its value;
230
231      The exception is when there is no value before rev in which case
232      we return 0, i.e., all revs up to the first element is 0.
233     */
234    T get(const M& map, typename M::const_iterator iter) const
235    { 
236      if (iter==map.begin())
237        return 0;
238      return (--iter)->second;
239    }
240  };
241
242  typedef Vector<unsigned int, SumPolicy<unsigned int> > SumVector;
243
244  /**
245     create a SumVector from a ParseVector
246
247     result[i] = result[i-1] + vec[i];
248  */
249  void accumulate(const SparseVector& vec, SumVector& result);
250
251}} // end of namespace svndigest and namespace theplu
252
253#endif
Note: See TracBrowser for help on using the repository browser.