source: trunk/lib/Vector.h @ 1495

Last change on this file since 1495 was 1495, checked in by Peter Johansson, 9 years ago

merge patch release 0.9.6 into trunk

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