source: trunk/lib/Vector.h @ 1418

Last change on this file since 1418 was 1418, checked in by Peter Johansson, 10 years ago

avoid warnings (-Wall)

  • 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 1418 2011-10-25 01:00:49Z 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      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      Vector result;
151      typename Map::iterator first1 = map_.begin();
152      typename Map::iterator last1 = map_.end();
153      const_iterator first2 = other.begin();
154      const_iterator last2 = other.end();
155      while (first1!=last1 || first2!=last2) {
156        svn_revnum_t rev = 0;
157        if (first1==last1) {
158          rev = first2->first;
159          ++first2;
160        }
161        else if (first2==last2) {
162          rev = first1->first;
163          ++first1;
164        }
165        else if (first1->first < first2->first) {
166          rev = first1->first;
167          ++first1;
168        }
169        else if (first1->first == first2->first) {
170          rev = first1->first;
171          ++first1;
172          ++first2;
173        }
174        else if (first1->first > first2->first) {
175          rev = first2->first;
176          ++first2;
177        }
178        result.set(rev, (*this)[rev] + other[rev]); 
179      }
180      // assign result map to this
181      std::swap(map_, result.map_);
182      resize(std::max(size_, other.size()));
183      return *this;
184    }
185
186    /**
187       \return size of vector
188     */
189    svn_revnum_t size(void) const
190    {
191      return size_;
192    }
193
194  private:
195    Map map_;
196    Policy policy_;
197    svn_revnum_t size_;
198
199    // using compiler generated copy constructor
200    // Vector(const Vector&)
201    // Vector& operator=(const Vector&);
202  };
203
204  template<typename T>
205  class SparsePolicy
206  {
207    typedef typename std::map<svn_revnum_t, T> M;
208  public:
209    T get(const M&, typename M::const_iterator) const
210    { return 0; }
211
212  };
213
214  typedef Vector<int, SparsePolicy<int> > SparseVector;
215
216  template<typename T>
217  class SumPolicy
218  {
219    typedef typename std::map<svn_revnum_t, T> M;
220  public:
221    /*
222      iter points to first element after rev, while we wanna return
223      the value of the first element before rev, so we iterate one
224      step back and return its value;
225
226      The exception is when there is no value before rev in which case
227      we return 0, i.e., all revs up to the first element is 0.
228     */
229    T get(const M& map, typename M::const_iterator iter) const
230    { 
231      if (iter==map.begin())
232        return 0;
233      return (--iter)->second;
234    }
235  };
236
237  typedef Vector<unsigned int, SumPolicy<unsigned int> > SumVector;
238
239  /**
240     create a SumVector from a ParseVector
241
242     result[i] = result[i-1] + vec[i];
243  */
244  void accumulate(const SparseVector& vec, SumVector& result);
245
246}} // end of namespace svndigest and namespace theplu
247
248#endif
Note: See TracBrowser for help on using the repository browser.