← Back to branch summary

~ubuntu-branches/ubuntu/saucy/blender/saucy-proposed

« back to all changes in this revision

Viewing changes to extern/Eigen3/Eigen/src/Sparse/CompressedStorage.h

  • Committer: Package Import Robot
  • Author(s): Jeremy Bicha
  • Date: 2013-03-06 12:08:47 UTC
  • mfrom: (1.5.1) (14.1.8 experimental)
  • Revision ID: package-import@ubuntu.com-20130306120847-frjfaryb2zrotwcg
Tags: 2.66a-1ubuntu1
https://launchpad.net/bugs/1076930
https://launchpad.net/bugs/1089256
https://launchpad.net/bugs/1052743
https://launchpad.net/bugs/999024
* Resynchronize with Debian (LP: #1076930, #1089256, #1052743, #999024,
  #1122888, #1147084)
* debian/control:
  - Lower build-depends on libavcodec-dev since we're not
    doing the libav9 transition in Ubuntu yet

Show diffs side-by-side

added added

removed removed

Lines of Context:
extern/Eigen3/Eigen/src/Sparse/CompressedStorage.h
1
 
// This file is part of Eigen, a lightweight C++ template library
2
 
// for linear algebra.
3
 
//
4
 
// Copyright (C) 2008 Gael Guennebaud <gael.guennebaud@inria.fr>
5
 
//
6
 
// Eigen is free software; you can redistribute it and/or
7
 
// modify it under the terms of the GNU Lesser General Public
8
 
// License as published by the Free Software Foundation; either
9
 
// version 3 of the License, or (at your option) any later version.
10
 
//
11
 
// Alternatively, you can redistribute it and/or
12
 
// modify it under the terms of the GNU General Public License as
13
 
// published by the Free Software Foundation; either version 2 of
14
 
// the License, or (at your option) any later version.
15
 
//
16
 
// Eigen is distributed in the hope that it will be useful, but WITHOUT ANY
17
 
// WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18
 
// FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License or the
19
 
// GNU General Public License for more details.
20
 
//
21
 
// You should have received a copy of the GNU Lesser General Public
22
 
// License and a copy of the GNU General Public License along with
23
 
// Eigen. If not, see <http://www.gnu.org/licenses/>.
24
 
 
25
 
#ifndef EIGEN_COMPRESSED_STORAGE_H
26
 
#define EIGEN_COMPRESSED_STORAGE_H
27
 
 
28
 
/** Stores a sparse set of values as a list of values and a list of indices.
29
 
  *
30
 
  */
31
 
template<typename _Scalar,typename _Index>
32
 
class CompressedStorage
33
 
{
34
 
  public:
35
 
 
36
 
    typedef _Scalar Scalar;
37
 
    typedef _Index Index;
38
 
 
39
 
  protected:
40
 
 
41
 
    typedef typename NumTraits<Scalar>::Real RealScalar;
42
 
 
43
 
  public:
44
 
 
45
 
    CompressedStorage()
46
 
      : m_values(0), m_indices(0), m_size(0), m_allocatedSize(0)
47
 
    {}
48
 
 
49
 
    CompressedStorage(size_t size)
50
 
      : m_values(0), m_indices(0), m_size(0), m_allocatedSize(0)
51
 
    {
52
 
      resize(size);
53
 
    }
54
 
 
55
 
    CompressedStorage(const CompressedStorage& other)
56
 
      : m_values(0), m_indices(0), m_size(0), m_allocatedSize(0)
57
 
    {
58
 
      *this = other;
59
 
    }
60
 
 
61
 
    CompressedStorage& operator=(const CompressedStorage& other)
62
 
    {
63
 
      resize(other.size());
64
 
      memcpy(m_values, other.m_values, m_size * sizeof(Scalar));
65
 
      memcpy(m_indices, other.m_indices, m_size * sizeof(Index));
66
 
      return *this;
67
 
    }
68
 
 
69
 
    void swap(CompressedStorage& other)
70
 
    {
71
 
      std::swap(m_values, other.m_values);
72
 
      std::swap(m_indices, other.m_indices);
73
 
      std::swap(m_size, other.m_size);
74
 
      std::swap(m_allocatedSize, other.m_allocatedSize);
75
 
    }
76
 
 
77
 
    ~CompressedStorage()
78
 
    {
79
 
      delete[] m_values;
80
 
      delete[] m_indices;
81
 
    }
82
 
 
83
 
    void reserve(size_t size)
84
 
    {
85
 
      size_t newAllocatedSize = m_size + size;
86
 
      if (newAllocatedSize > m_allocatedSize)
87
 
        reallocate(newAllocatedSize);
88
 
    }
89
 
 
90
 
    void squeeze()
91
 
    {
92
 
      if (m_allocatedSize>m_size)
93
 
        reallocate(m_size);
94
 
    }
95
 
 
96
 
    void resize(size_t size, float reserveSizeFactor = 0)
97
 
    {
98
 
      if (m_allocatedSize<size)
99
 
        reallocate(size + size_t(reserveSizeFactor*size));
100
 
      m_size = size;
101
 
    }
102
 
 
103
 
    void append(const Scalar& v, Index i)
104
 
    {
105
 
      Index id = static_cast<Index>(m_size);
106
 
      resize(m_size+1, 1);
107
 
      m_values[id] = v;
108
 
      m_indices[id] = i;
109
 
    }
110
 
 
111
 
    inline size_t size() const { return m_size; }
112
 
    inline size_t allocatedSize() const { return m_allocatedSize; }
113
 
    inline void clear() { m_size = 0; }
114
 
 
115
 
    inline Scalar& value(size_t i) { return m_values[i]; }
116
 
    inline const Scalar& value(size_t i) const { return m_values[i]; }
117
 
 
118
 
    inline Index& index(size_t i) { return m_indices[i]; }
119
 
    inline const Index& index(size_t i) const { return m_indices[i]; }
120
 
 
121
 
    static CompressedStorage Map(Index* indices, Scalar* values, size_t size)
122
 
    {
123
 
      CompressedStorage res;
124
 
      res.m_indices = indices;
125
 
      res.m_values = values;
126
 
      res.m_allocatedSize = res.m_size = size;
127
 
      return res;
128
 
    }
129
 
 
130
 
    /** \returns the largest \c k such that for all \c j in [0,k) index[\c j]\<\a key */
131
 
    inline Index searchLowerIndex(Index key) const
132
 
    {
133
 
      return searchLowerIndex(0, m_size, key);
134
 
    }
135
 
 
136
 
    /** \returns the largest \c k in [start,end) such that for all \c j in [start,k) index[\c j]\<\a key */
137
 
    inline Index searchLowerIndex(size_t start, size_t end, Index key) const
138
 
    {
139
 
      while(end>start)
140
 
      {
141
 
        size_t mid = (end+start)>>1;
142
 
        if (m_indices[mid]<key)
143
 
          start = mid+1;
144
 
        else
145
 
          end = mid;
146
 
      }
147
 
      return static_cast<Index>(start);
148
 
    }
149
 
 
150
 
    /** \returns the stored value at index \a key
151
 
      * If the value does not exist, then the value \a defaultValue is returned without any insertion. */
152
 
    inline Scalar at(Index key, Scalar defaultValue = Scalar(0)) const
153
 
    {
154
 
      if (m_size==0)
155
 
        return defaultValue;
156
 
      else if (key==m_indices[m_size-1])
157
 
        return m_values[m_size-1];
158
 
      // ^^  optimization: let's first check if it is the last coefficient
159
 
      // (very common in high level algorithms)
160
 
      const size_t id = searchLowerIndex(0,m_size-1,key);
161
 
      return ((id<m_size) && (m_indices[id]==key)) ? m_values[id] : defaultValue;
162
 
    }
163
 
 
164
 
    /** Like at(), but the search is performed in the range [start,end) */
165
 
    inline Scalar atInRange(size_t start, size_t end, Index key, Scalar defaultValue = Scalar(0)) const
166
 
    {
167
 
      if (start>=end)
168
 
        return Scalar(0);
169
 
      else if (end>start && key==m_indices[end-1])
170
 
        return m_values[end-1];
171
 
      // ^^  optimization: let's first check if it is the last coefficient
172
 
      // (very common in high level algorithms)
173
 
      const size_t id = searchLowerIndex(start,end-1,key);
174
 
      return ((id<end) && (m_indices[id]==key)) ? m_values[id] : defaultValue;
175
 
    }
176
 
 
177
 
    /** \returns a reference to the value at index \a key
178
 
      * If the value does not exist, then the value \a defaultValue is inserted
179
 
      * such that the keys are sorted. */
180
 
    inline Scalar& atWithInsertion(Index key, Scalar defaultValue = Scalar(0))
181
 
    {
182
 
      size_t id = searchLowerIndex(0,m_size,key);
183
 
      if (id>=m_size || m_indices[id]!=key)
184
 
      {
185
 
        resize(m_size+1,1);
186
 
        for (size_t j=m_size-1; j>id; --j)
187
 
        {
188
 
          m_indices[j] = m_indices[j-1];
189
 
          m_values[j] = m_values[j-1];
190
 
        }
191
 
        m_indices[id] = key;
192
 
        m_values[id] = defaultValue;
193
 
      }
194
 
      return m_values[id];
195
 
    }
196
 
 
197
 
    void prune(Scalar reference, RealScalar epsilon = NumTraits<RealScalar>::dummy_precision())
198
 
    {
199
 
      size_t k = 0;
200
 
      size_t n = size();
201
 
      for (size_t i=0; i<n; ++i)
202
 
      {
203
 
        if (!internal::isMuchSmallerThan(value(i), reference, epsilon))
204
 
        {
205
 
          value(k) = value(i);
206
 
          index(k) = index(i);
207
 
          ++k;
208
 
        }
209
 
      }
210
 
      resize(k,0);
211
 
    }
212
 
 
213
 
  protected:
214
 
 
215
 
    inline void reallocate(size_t size)
216
 
    {
217
 
      Scalar* newValues  = new Scalar[size];
218
 
      Index* newIndices = new Index[size];
219
 
      size_t copySize = (std::min)(size, m_size);
220
 
      // copy
221
 
      memcpy(newValues,  m_values,  copySize * sizeof(Scalar));
222
 
      memcpy(newIndices, m_indices, copySize * sizeof(Index));
223
 
      // delete old stuff
224
 
      delete[] m_values;
225
 
      delete[] m_indices;
226
 
      m_values = newValues;
227
 
      m_indices = newIndices;
228
 
      m_allocatedSize = size;
229
 
    }
230
 
 
231
 
  protected:
232
 
    Scalar* m_values;
233
 
    Index* m_indices;
234
 
    size_t m_size;
235
 
    size_t m_allocatedSize;
236
 
 
237
 
};
238
 
 
239
 
#endif // EIGEN_COMPRESSED_STORAGE_H