source: trunk/lib/Vector.h @ 1481

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

avoid logN lookup and insertion

  • 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 1481 2012-06-03 11:29:54Z 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    }
188
189    /**
190       \return size of vector
191     */
192    svn_revnum_t size(void) const
193    {
194      return size_;
195    }
196
197  private:
198    Map map_;
199    Policy policy_;
200    svn_revnum_t size_;
201
202    // using compiler generated copy constructor
203    // Vector(const Vector&)
204    // Vector& operator=(const Vector&);
205  };
206
207  template<typename T>
208  class SparsePolicy
209  {
210    typedef typename std::map<svn_revnum_t, T> M;
211  public:
212    T get(const M&, typename M::const_iterator) const
213    { return 0; }
214
215  };
216
217  typedef Vector<int, SparsePolicy<int> > SparseVector;
218
219  template<typename T>
220  class SumPolicy
221  {
222    typedef typename std::map<svn_revnum_t, T> M;
223  public:
224    /*
225      iter points to first element after rev, while we wanna return
226      the value of the first element before rev, so we iterate one
227      step back and return its value;
228
229      The exception is when there is no value before rev in which case
230      we return 0, i.e., all revs up to the first element is 0.
231     */
232    T get(const M& map, typename M::const_iterator iter) const
233    { 
234      if (iter==map.begin())
235        return 0;
236      return (--iter)->second;
237    }
238  };
239
240  typedef Vector<unsigned int, SumPolicy<unsigned int> > SumVector;
241
242  /**
243     create a SumVector from a ParseVector
244
245     result[i] = result[i-1] + vec[i];
246  */
247  void accumulate(const SparseVector& vec, SumVector& result);
248
249}} // end of namespace svndigest and namespace theplu
250
251#endif
Note: See TracBrowser for help on using the repository browser.