1 /*========================================================================= 2 3 Program: Visualization Toolkit 4 Module: vtkSparseArray.h 5 6 ------------------------------------------------------------------------- 7 Copyright 2008 Sandia Corporation. 8 Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation, 9 the U.S. Government retains certain rights in this software. 10 ------------------------------------------------------------------------- 11 12 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen 13 All rights reserved. 14 See Copyright.txt or http://www.kitware.com/Copyright.htm for details. 15 16 This software is distributed WITHOUT ANY WARRANTY; without even 17 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 18 PURPOSE. See the above copyright notice for more information. 19 20 =========================================================================*/ 21 22 /** 23 * @class vtkSparseArray 24 * @brief Sparse, independent coordinate storage for N-way arrays. 25 * 26 * 27 * vtkSparseArray is a concrete vtkArray implementation that stores values using 28 * sparse independent coordinate storage. This means that the array stores the 29 * complete set of coordinates and the value for each non-null value in the array. 30 * While this approach requires slightly more storage than other sparse storage 31 * schemes (such as Compressed-Row or Compressed-Column), it is easier and more 32 * efficient to work with when implementing algorithms, and it generalizes well 33 * for arbitrary numbers of dimensions. 34 * 35 * In addition to the value retrieval and update methods provided by vtkTypedArray, 36 * vtkSparseArray provides methods to: 37 * 38 * Get and set a special 'null' value that will be returned when retrieving values 39 * for undefined coordinates. 40 * 41 * Clear the contents of the array so that every set of coordinates is undefined. 42 * 43 * Sort the array contents so that value coordinates can be visited in a specific order. 44 * 45 * Retrieve pointers to the value- and coordinate-storage memory blocks. 46 * 47 * Reserve storage for a specific number of non-null values, for efficiency when the 48 * number of non-null values is known in advance. 49 * 50 * Recompute the array extents so that they bound the largest set of non-nullptr values 51 * along each dimension. 52 * 53 * Specify arbitrary array extents. 54 * 55 * Add values to the array in amortized-constant time. 56 * 57 * Validate that the array does not contain duplicate coordinates. 58 * 59 * @sa 60 * vtkArray, vtkTypedArray, vtkDenseArray 61 * 62 * @par Thanks: 63 * Developed by Timothy M. Shead (tshead@sandia.gov) at Sandia National Laboratories. 64 */ 65 66 #ifndef vtkSparseArray_h 67 #define vtkSparseArray_h 68 69 #include "vtkArrayCoordinates.h" 70 #include "vtkArraySort.h" 71 #include "vtkObjectFactory.h" 72 #include "vtkTypedArray.h" 73 74 template <typename T> 75 class vtkSparseArray : public vtkTypedArray<T> 76 { 77 public: 78 vtkTemplateTypeMacro(vtkSparseArray<T>, vtkTypedArray<T>); 79 static vtkSparseArray<T>* New(); 80 void PrintSelf(ostream& os, vtkIndent indent) override; 81 82 typedef typename vtkArray::CoordinateT CoordinateT; 83 typedef typename vtkArray::DimensionT DimensionT; 84 typedef typename vtkArray::SizeT SizeT; 85 86 // vtkArray API 87 bool IsDense() override; 88 const vtkArrayExtents& GetExtents() override; 89 SizeT GetNonNullSize() override; 90 void GetCoordinatesN(const SizeT n, vtkArrayCoordinates& coordinates) override; 91 vtkArray* DeepCopy() override; 92 93 // vtkTypedArray API 94 const T& GetValue(CoordinateT i) override; 95 const T& GetValue(CoordinateT i, CoordinateT j) override; 96 const T& GetValue(CoordinateT i, CoordinateT j, CoordinateT k) override; 97 const T& GetValue(const vtkArrayCoordinates& coordinates) override; 98 const T& GetValueN(const SizeT n) override; 99 void SetValue(CoordinateT i, const T& value) override; 100 void SetValue(CoordinateT i, CoordinateT j, const T& value) override; 101 void SetValue(CoordinateT i, CoordinateT j, CoordinateT k, const T& value) override; 102 void SetValue(const vtkArrayCoordinates& coordinates, const T& value) override; 103 void SetValueN(const SizeT n, const T& value) override; 104 105 // vtkSparseArray API 106 107 /** 108 * Set the value that will be returned by GetValue() for nullptr areas of the array. 109 */ 110 void SetNullValue(const T& value); 111 112 /** 113 * Returns the value that will be returned by GetValue() for nullptr areas of the array. 114 */ 115 const T& GetNullValue(); 116 117 /** 118 * Remove all non-null elements from the array, leaving the number of dimensions, the 119 * extent of each dimension, and the label for each dimension unchanged. 120 */ 121 void Clear(); 122 123 /** 124 * Sorts array values so that their coordinates appear in some well-defined order. 125 * The supplied vtkArraySort object controls which dimensions are sorted, and in what 126 * order, and should contain one-or-more sort dimensions, up to the number of dimensions 127 * stored in the array. 128 */ 129 void Sort(const vtkArraySort& sort); 130 131 /** 132 * Returns the set of unique coordinates along the given dimension. 133 */ 134 std::vector<CoordinateT> GetUniqueCoordinates(DimensionT dimension); 135 136 /** 137 * Return a read-only reference to the underlying coordinate storage. Coordinates 138 * for each dimension are stored contiguously as a one-dimensional array. The ordering 139 * of coordinates within the array depends on the order in which values were added to 140 * the array. 141 */ 142 const CoordinateT* GetCoordinateStorage(DimensionT dimension) const; 143 144 /** 145 * Return a mutable reference to the underlying coordinate storage. Coordinates 146 * for each dimension are stored contiguously as a one-dimensional array. The ordering 147 * of coordinates within the array depends on the order in which values were added to 148 * the array, and any subsequent sorting. Use at your own risk! 149 */ 150 CoordinateT* GetCoordinateStorage(DimensionT dimension); 151 152 /** 153 * Return a read-only reference to the underlying value storage. Values are stored 154 * contiguously, but in arbitrary order. Use GetCoordinateStorage() if you need to 155 * get the corresponding coordinates for a value. 156 */ 157 const T* GetValueStorage() const; 158 159 /** 160 * Return a mutable reference to the underlying value storage. Values are stored 161 * contiguously, but in arbitrary order. Use GetCoordinateStorage() if you need to 162 * get the corresponding coordinates for a value. Use at your own risk! 163 */ 164 T* GetValueStorage(); 165 166 /** 167 * Reserve storage for a specific number of values. This is useful for reading external 168 * data using GetCoordinateStorage() and GetValueStorage(), when the total 169 * number of non-nullptr values in the array can be determined in advance. Note that after 170 * calling ReserveStorage(), all coordinates and values will be undefined, so you must 171 * ensure that every set of coordinates and values is overwritten. It is the caller's 172 * responsibility to ensure that duplicate coordinates are not inserted into the array. 173 */ 174 void ReserveStorage(const SizeT value_count); 175 176 /** 177 * Update the array extents to match its contents, so that the extent along each dimension 178 * matches the maximum index value along that dimension. 179 */ 180 void SetExtentsFromContents(); 181 /** 182 * Specify arbitrary array extents, without altering the contents of the array. Note 183 * that the extents must be as-large-or-larger-than the extents of the actual values 184 * stored in the array. The number of dimensions in the supplied extents must match the 185 * number of dimensions currently stored in the array. 186 */ 187 void SetExtents(const vtkArrayExtents& extents); 188 189 ///@{ 190 /** 191 * Adds a new non-null element to the array. Does not test to see if an element with 192 * matching coordinates already exists. Useful for providing fast initialization of the 193 * array as long as the caller is prepared to guarantee that no duplicate coordinates are 194 * ever used. 195 */ 196 inline void AddValue(CoordinateT i, const T& value); 197 inline void AddValue(CoordinateT i, CoordinateT j, const T& value); 198 inline void AddValue(CoordinateT i, CoordinateT j, CoordinateT k, const T& value); 199 void AddValue(const vtkArrayCoordinates& coordinates, const T& value); 200 ///@} 201 202 /** 203 * Validate the contents of the array, returning false if there are any problems. 204 * Potential problems include duplicate coordinates, which can be introduced into the 205 * array either through AddValue() or direct access to coordinates storage; and coordinates 206 * out-of-bounds given the current array extents. 207 208 * Note that Validate() is a heavyweight O(N log N) operation that is intended for 209 * temporary use during debugging. 210 */ 211 bool Validate(); 212 213 protected: 214 vtkSparseArray(); 215 ~vtkSparseArray() override; 216 217 private: 218 vtkSparseArray(const vtkSparseArray&) = delete; 219 void operator=(const vtkSparseArray&) = delete; 220 221 void InternalResize(const vtkArrayExtents& extents) override; 222 void InternalSetDimensionLabel(DimensionT i, const vtkStdString& label) override; 223 vtkStdString InternalGetDimensionLabel(DimensionT i) override; 224 225 typedef vtkSparseArray<T> ThisT; 226 227 /** 228 * Stores the current array extents (size along each dimension) 229 */ 230 vtkArrayExtents Extents; 231 232 /** 233 * Stores a label for each array dimension 234 */ 235 std::vector<vtkStdString> DimensionLabels; 236 237 /** 238 * Stores the coordinates of each non-null element within the array, 239 * using one contiguous array to store the coordinates for each dimension. 240 */ 241 std::vector<std::vector<CoordinateT>> Coordinates; 242 243 /** 244 * Stores the value of each non-null element within the array 245 */ 246 std::vector<T> Values; 247 248 ///@{ 249 /** 250 * Stores the value that will be returned when accessing nullptr areas 251 * of the array. 252 */ 253 T NullValue; 254 ///@} 255 }; 256 257 #include "vtkSparseArray.txx" 258 259 #endif 260 // VTK-HeaderTest-Exclude: vtkSparseArray.h 261