My Project
SparseVector.hpp
1 //===========================================================================
2 //
3 // File: SparseVector.hpp
4 //
5 // Created: Mon Jun 29 15:28:59 2009
6 //
7 // Author(s): Atgeirr F Rasmussen <atgeirr@sintef.no>
8 // Bård Skaflestad <bard.skaflestad@sintef.no>
9 //
10 // $Date$
11 //
12 // $Revision$
13 //
14 //===========================================================================
15 
16 /*
17  Copyright 2009, 2010 SINTEF ICT, Applied Mathematics.
18  Copyright 2009, 2010 Statoil ASA.
19 
20  This file is part of the Open Porous Media project (OPM).
21 
22  OPM is free software: you can redistribute it and/or modify
23  it under the terms of the GNU General Public License as published by
24  the Free Software Foundation, either version 3 of the License, or
25  (at your option) any later version.
26 
27  OPM is distributed in the hope that it will be useful,
28  but WITHOUT ANY WARRANTY; without even the implied warranty of
29  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30  GNU General Public License for more details.
31 
32  You should have received a copy of the GNU General Public License
33  along with OPM. If not, see <http://www.gnu.org/licenses/>.
34 */
35 
36 
37 #ifndef OPM_SPARSEVECTOR_HEADER
38 #define OPM_SPARSEVECTOR_HEADER
39 
40 #include <vector>
41 #include <numeric>
42 #include <algorithm>
43 #include <opm/common/ErrorMacros.hpp>
44 
45 namespace Opm
46 {
47 
53  template <typename T>
55  {
56  public:
59  : size_(0), default_elem_()
60  {
61  }
62 
65  explicit SparseVector(int sz)
66  : size_(sz), default_elem_()
67  {
68  }
69 
75  template <typename DataIter, typename IntegerIter>
76  SparseVector(int sz,
77  DataIter data_beg, DataIter data_end,
78  IntegerIter index_beg, IntegerIter index_end)
79  : size_(sz), data_(data_beg, data_end), indices_(index_beg, index_end),
80  default_elem_()
81  {
82 #ifndef NDEBUG
83  OPM_ERROR_IF(sz < 0, "The size of a SparseVector must be non-negative");
84  OPM_ERROR_IF(indices_.size() != data_.size(), "The number of indices of a SparseVector must equal to the number of entries");
85  int last_index = -1;
86  int num_ind = indices_.size();
87  for (int i = 0; i < num_ind; ++i) {
88  int index = indices_[i];
89  if (index <= last_index || index >= sz) {
90  OPM_THROW(std::logic_error, "Error in SparseVector construction, index is nonincreasing or out of range.");
91  }
92  last_index = index;
93  }
94 #endif
95  }
96 
97 
101  void addElement(const T& elem, int index)
102  {
103  assert(indices_.empty() || index > indices_.back());
104  assert(index < size_);
105  data_.push_back(elem);
106  indices_.push_back(index);
107  }
108 
110  bool empty() const
111  {
112  return size_ == 0;
113  }
114 
117  int size() const
118  {
119  return size_;
120  }
121 
123  int nonzeroSize() const
124  {
125  return data_.size();
126  }
127 
129  void clear()
130  {
131  data_.clear();
132  indices_.clear();
133  size_ = 0;
134  }
135 
137  bool operator==(const SparseVector& other) const
138  {
139  return size_ == other.size_ && data_ == other.data_ && indices_ == other.indices_;
140  }
141 
146  const T& element(int index) const
147  {
148 #ifndef NDEBUG
149  OPM_ERROR_IF(index < 0, "The index of a SparseVector must be non-negative (is " << index << ")");
150  OPM_ERROR_IF(index >= size_, "The index of a SparseVector must be smaller than the maximum value (is " << index << ", max value: " << size_ <<")");
151 #endif
152  std::vector<int>::const_iterator lb = std::lower_bound(indices_.begin(), indices_.end(), index);
153  if (lb != indices_.end() && *lb == index) {
154  return data_[lb - indices_.begin()];
155  } else {
156  return default_elem_;
157  }
158  }
159 
163  const T& nonzeroElement(int nzindex) const
164  {
165 #ifndef NDEBUG
166  OPM_ERROR_IF(nzindex < 0, "The index of a SparseVector must be non-negative (is " << nzindex << ")");
167  OPM_ERROR_IF(nzindex >= nonzeroSize(), "The index of a SparseVector must be smaller than the maximum value (is " << nzindex << ", max value: " << nonzeroSize() <<")");
168 #endif
169  return data_[nzindex];
170  }
171 
175  int nonzeroIndex(int nzindex) const
176  {
177  assert(nzindex >= 0);
178  assert(nzindex < nonzeroSize());
179  return indices_[nzindex];
180  }
181 
182  private:
183  // The vectors data_ and indices_ are always the same size.
184  // The indices are supposed to be stored in increasing order,
185  // to be unique, and to be in [0, size_ - 1].
186  // default_elem_ is returned when a default element is requested.
187  int size_;
188  std::vector<T> data_;
189  std::vector<int> indices_;
190  T default_elem_;
191  };
192 
193 } // namespace Opm
194 
195 
196 
197 
198 #endif // OPM_SPARSEVECTOR_HEADER
A SparseVector stores a vector with possibly many empty elements as efficiently as possible.
Definition: SparseVector.hpp:55
int size() const
Returns the size of the vector.
Definition: SparseVector.hpp:117
void clear()
Makes the vector empty().
Definition: SparseVector.hpp:129
void addElement(const T &elem, int index)
Appends an element to the vector.
Definition: SparseVector.hpp:101
const T & nonzeroElement(int nzindex) const
O(1) element access.
Definition: SparseVector.hpp:163
int nonzeroIndex(int nzindex) const
O(1) index access.
Definition: SparseVector.hpp:175
SparseVector(int sz, DataIter data_beg, DataIter data_end, IntegerIter index_beg, IntegerIter index_end)
A constructor taking all the element data for the vector and their indices.
Definition: SparseVector.hpp:76
int nonzeroSize() const
Returns the number of nonzero data elements.
Definition: SparseVector.hpp:123
bool empty() const
Definition: SparseVector.hpp:110
SparseVector()
Default constructor. Yields an empty SparseVector.
Definition: SparseVector.hpp:58
bool operator==(const SparseVector &other) const
Equality.
Definition: SparseVector.hpp:137
const T & element(int index) const
O(log n) element access.
Definition: SparseVector.hpp:146
SparseVector(int sz)
Constructs a SparseVector with a given size, but no nonzero elements.
Definition: SparseVector.hpp:65
This class implements a small container which holds the transmissibility mulitpliers for all the face...
Definition: Exceptions.hpp:29