source: trunk/lib/Vector.h @ 1187

Last change on this file since 1187 was 1187, checked in by Peter Johansson, 12 years ago

new Vector class. refs #475

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 3.8 KB
Line 
1#ifndef _theplu_svndigest_vector_
2#define _theplu_svndigest_vector_
3
4// $Id: Vector.h 1187 2010-08-28 21:58:37Z 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 <subversion-1/svn_types.h>
26
27#include <map>
28
29namespace theplu {
30namespace svndigest {
31
32  /**
33     \brief Sparse Vector
34  */
35  template<typename T, class Policy>
36  class Vector {
37    typedef typename std::map<svn_revnum_t, T> Map;
38  public:
39    // iterator to underlying container, used in begin() and end()
40    typedef typename Map::const_iterator const_iterator;
41
42    /**
43       \brief default constructor
44     */
45    Vector(void) {}
46
47    /**
48       \return first non-trivial element
49
50       The iterator iterates only over non-trivial element, e.g.,
51       non-zero in SparseVector. If you need to iterate over all
52       elements you can use operator[] and size().
53     */
54    const_iterator begin(void) const { return map_.begin(); }
55
56    /**
57       \brief make container empty
58     */
59    void clear(void) { map_.clear(); }
60
61    /*
62      \return end of Vector
63     */
64    const_iterator end(void) const { return map_.end(); }
65
66    /**
67       works as vec[revision] = count
68     */
69    void set(svn_revnum_t revision, T count)
70    {
71      // FIXME: we should let policy collaps map, if possible
72      map_[revision] = count;
73    }
74
75    /**
76       \return value of revision \a rev
77
78       If revision \a rev is non-trivial, i.e., directly stored in
79       underlying container, its value is returned. Otherwise, return
80       value is decided by the policy class.
81     */
82    T operator[](svn_revnum_t rev) const
83    {
84      const_iterator i = map_.lower_bound(rev);
85      if (i!=map_.end() && i->first == rev)
86        return i->second;
87      return policy_.get(map_, i);
88    }
89
90    /**
91       \return 0 if Vector is empty; otherwise the largest_rev + 1
92     */
93    size_t size(void) const
94    {
95      if (map_.empty())
96        return 0;
97      return map_.rbegin()->first + 1;
98    }
99
100  private:
101    Map map_;
102    Policy policy_;
103
104    // using compiler generated copy constructor
105    // Vector(const Vector&)
106    // Vector& operator=(const Vector&);
107  };
108
109  template<typename T>
110  class SparsePolicy
111  {
112    typedef typename std::map<svn_revnum_t, T> M;
113  public:
114    T get(const M&, typename M::const_iterator) const
115    { return 0; }
116
117  };
118
119  typedef Vector<unsigned int, SparsePolicy<unsigned int> > SparseVector;
120
121  template<typename T>
122  class SumPolicy
123  {
124    typedef typename std::map<svn_revnum_t, T> M;
125  public:
126    /*
127      iter points to first element after rev, while we wanna return
128      the value of the first element before rev, so we iterate one
129      step back and return its value;
130
131      The exception is when there is no value before rev in which case
132      we return 0, i.e., all revs up to the first element is 0.
133     */
134    T get(const M& map, typename M::const_iterator iter) const
135    { 
136      if (iter==map.begin())
137        return 0;
138      return (--iter)->second;
139    }
140  };
141
142  typedef Vector<unsigned int, SumPolicy<unsigned int> > SumVector;
143
144  /**
145     create a SumVector from a ParseVector
146
147     result[i] = result[i-1] + vec[i];
148  */
149  void accumulate(const SparseVector& vec, SumVector& result)
150  {
151    result.clear();
152    unsigned int value = 0;
153    for (SumVector::const_iterator iter = vec.begin(); iter!=vec.end();++iter) {
154      value += iter->second;
155      result.set(iter->first, value);
156    }
157  }
158
159}} // end of namespace svndigest and namespace theplu
160
161#endif
Note: See TracBrowser for help on using the repository browser.