Field3D
SparseField.h
Go to the documentation of this file.
00001 //----------------------------------------------------------------------------//
00002 
00003 /*
00004  * Copyright (c) 2009 Sony Pictures Imageworks Inc
00005  *
00006  * All rights reserved.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions
00010  * are met:
00011  *
00012  * Redistributions of source code must retain the above copyright
00013  * notice, this list of conditions and the following disclaimer.
00014  * Redistributions in binary form must reproduce the above copyright
00015  * notice, this list of conditions and the following disclaimer in the
00016  * documentation and/or other materials provided with the
00017  * distribution.  Neither the name of Sony Pictures Imageworks nor the
00018  * names of its contributors may be used to endorse or promote
00019  * products derived from this software without specific prior written
00020  * permission.
00021  *
00022  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00023  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00024  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
00025  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
00026  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
00027  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
00028  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
00029  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00030  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
00031  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
00032  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
00033  * OF THE POSSIBILITY OF SUCH DAMAGE.
00034  */
00035 
00036 //----------------------------------------------------------------------------//
00037 
00042 //----------------------------------------------------------------------------//
00043 
00044 #ifndef _INCLUDED_Field3D_SparseField_H_
00045 #define _INCLUDED_Field3D_SparseField_H_
00046 
00047 //----------------------------------------------------------------------------//
00048 
00049 #include <vector>
00050 
00051 #include <boost/lexical_cast.hpp>
00052 
00053 #include "Field.h"
00054 #include "SparseFile.h"
00055 
00056 #define BLOCK_ORDER 4 // 2^BLOCK_ORDER is the block size along each axis
00057 
00058 //----------------------------------------------------------------------------//
00059 
00060 #include "ns.h"
00061 
00062 FIELD3D_NAMESPACE_OPEN
00063 
00064 //----------------------------------------------------------------------------//
00065 // Forward declarations 
00066 //----------------------------------------------------------------------------//
00067 
00068 template <class Field_T>
00069 class LinearGenericFieldInterp;
00070 template <class Field_T>
00071 class CubicGenericFieldInterp; 
00072 
00073 //----------------------------------------------------------------------------//
00074 // SparseBlock
00075 //----------------------------------------------------------------------------//
00076 
00079 namespace Sparse {
00080 
00084 template <typename Data_T>
00085 struct SparseBlock 
00086 {
00087   // Constructors --------------------------------------------------------------
00088 
00090   SparseBlock()
00091     : isAllocated(false),
00092       emptyValue(static_cast<Data_T>(0))
00093   { /* Empty */ }
00094 
00095   // Main methods --------------------------------------------------------------
00096 
00098   Data_T& value(int i, int j, int k, int blockOrder)
00100   { return data[(k << blockOrder << blockOrder) + (j << blockOrder) + i]; }
00101 
00104   const Data_T& value(int i, int j, int k, int blockOrder) const
00105   { return data[(k << blockOrder << blockOrder) + (j << blockOrder) + i]; }
00106 
00108   void resize(int n)
00109   { this->data.resize(n); }
00110 
00112   void clear()
00113   { std::vector<Data_T>().swap(data); }
00114 
00116   Data_T& dataRef()
00117   { return data[0]; }
00118 
00119   // Data members --------------------------------------------------------------
00120 
00122   bool isAllocated;
00123 
00127   Data_T emptyValue;
00128 
00130   std::vector<Data_T> data;
00131 
00132 private:
00133 
00136 
00137 };
00138 
00139 } // namespace Sparse
00140 
00141 //----------------------------------------------------------------------------//
00142 // SparseField
00143 //----------------------------------------------------------------------------//
00144 
00157 //----------------------------------------------------------------------------//
00158 
00159 template <class Data_T>
00160 class SparseField
00161   : public ResizableField<Data_T>
00162 {
00163 public:
00164 
00165   // Typedefs ------------------------------------------------------------------
00166   
00167   typedef boost::intrusive_ptr<SparseField> Ptr;
00168   typedef std::vector<Ptr> Vec;
00169 
00170   typedef LinearGenericFieldInterp<SparseField<Data_T> > LinearInterp;
00171   typedef CubicGenericFieldInterp<SparseField<Data_T> > CubicInterp;
00172 
00173   // Constructors --------------------------------------------------------------
00174 
00177 
00179   SparseField();
00180 
00182   SparseField(const SparseField &o);
00183 
00185   ~SparseField();
00186 
00189   SparseField & operator=(const SparseField &o);
00190 
00191   // \}
00192 
00193   // Main methods --------------------------------------------------------------
00194 
00196   virtual void clear(const Data_T &value);
00197 
00200   void setBlockOrder(int order);
00201 
00203   int blockOrder() const;
00204 
00206   int blockSize() const;
00207 
00209   bool voxelIsInAllocatedBlock(int i, int j, int k) const;
00210 
00212   bool blockIsAllocated(int bi, int bj, int bk) const;
00213   
00216   const Data_T getBlockEmptyValue(int bi, int bj, int bk) const;
00217 
00220   void setBlockEmptyValue(int bi, int bj, int bk, const Data_T &val);
00221 
00223   bool blockIndexIsValid(int bi, int bj, int bk) const;
00224 
00226   V3i blockRes() const;
00227 
00233   template <typename Functor_T>
00234   int releaseBlocks(Functor_T func);
00235 
00237   int blockId(int blockI, int blockJ, int blockK) const;
00238 
00242   void getBlockCoord(int i, int j, int k, int &bi, int &bj, int &bk) const;
00243   
00247   void getVoxelInBlock(int i, int j, int k, int &vi, int &vj, int &vk) const;
00248 
00250   void applyDataWindowOffset(int &i, int &j, int &k) const
00251   {
00252     i -= base::m_dataWindow.min.x;
00253     j -= base::m_dataWindow.min.y;
00254     k -= base::m_dataWindow.min.z;
00255   }
00256   
00257   // From Field base class -----------------------------------------------------
00258 
00261   virtual Data_T value(int i, int j, int k) const;
00262   virtual long long int memSize() const;
00264 
00265   // RTTI replacement ----------------------------------------------------------
00266 
00267   typedef SparseField<Data_T> class_type;
00268   DEFINE_FIELD_RTTI_CONCRETE_CLASS;
00269 
00270   // From WritableField base class ---------------------------------------------
00271 
00274   virtual Data_T& lvalue(int i, int j, int k);
00276 
00277   // Concrete voxel access -----------------------------------------------------
00278 
00280   Data_T fastValue(int i, int j, int k) const;
00282   Data_T& fastLValue(int i, int j, int k);
00283 
00284   // From FieldBase ------------------------------------------------------------
00285 
00288   virtual std::string className() const
00289     { return std::string("SparseField"); }
00290 
00291   virtual FieldBase::Ptr clone() const
00292     { return Ptr(new SparseField(*this)); }
00293 
00295   
00296   // Iterators -----------------------------------------------------------------
00297 
00300 
00302   class const_iterator;
00303 
00305   const_iterator cbegin() const;
00307   const_iterator cbegin(const Box3i &subset) const;
00309   const_iterator cend() const;
00312   const_iterator cend(const Box3i &subset) const;
00313 
00317   class iterator;
00318 
00320   iterator begin();
00322   iterator begin(const Box3i &subset);
00324   iterator end();
00327   iterator end(const Box3i &subset);
00328 
00332   class block_iterator;
00333 
00334   block_iterator blockBegin() const;
00336   block_iterator blockEnd() const;
00337 
00339 
00340   // Internal utility functions ------------------------------------------------
00341 
00344   void addReference(const std::string &filename, const std::string &layerPath,
00345                     int valuesPerBlock, int occupiedBlocks);
00348   void setupReferenceBlocks();
00349 
00350  protected:
00351 
00352   friend class SparseFieldIO;
00353 
00354   // Typedefs ------------------------------------------------------------------
00355 
00356   typedef ResizableField<Data_T> base;
00357   typedef Sparse::SparseBlock<Data_T> Block;
00358 
00359   // From ResizableField class -------------------------------------------------
00360 
00361   virtual void sizeChanged()
00362   { 
00363     // Call base class
00364     base::sizeChanged();
00365     setupBlocks(); 
00366   }
00367 
00368   // Convenience methods -------------------------------------------------------
00369 
00372 
00374   void setupBlocks();
00375 
00377   void deallocBlock(Block &block, const Data_T &emptyValue);
00378 
00380 
00381   // Data members --------------------------------------------------------------
00382 
00384   int m_blockOrder;
00386   V3i m_blockRes;
00388   int m_blockXYSize;
00390   std::vector<Block> m_blocks;
00391 
00394   SparseFileManager *m_fileManager;
00396   int m_fileId;
00397 
00399   Data_T m_dummy;
00400 
00401 private:
00402 
00405   void copySparseField(const SparseField &o);
00406 
00409   void copyBlockStates(const SparseField<Data_T> &o);
00410 
00411 };
00412 
00413 //----------------------------------------------------------------------------//
00414 // Typedefs
00415 //----------------------------------------------------------------------------//
00416 
00417 typedef SparseField<half>   SparseFieldh;
00418 typedef SparseField<float>  SparseFieldf;
00419 typedef SparseField<double> SparseFieldd;
00420 typedef SparseField<V3h>    SparseField3h;
00421 typedef SparseField<V3f>    SparseField3f;
00422 typedef SparseField<V3d>    SparseField3d;
00423 
00424 //----------------------------------------------------------------------------//
00425 // Helper functors
00426 //----------------------------------------------------------------------------//
00427 
00428 namespace Sparse {
00429 
00432 template <typename Data_T>
00433 struct CheckAllEqual
00434 {
00443   bool check(const SparseBlock<Data_T> &block, Data_T &retEmptyValue,
00444              const V3i &validSize, const V3i &blockSize)
00445   {
00446     // Store first value
00447     Data_T first = block.data[0];
00448     // Iterate over rest
00449     bool match = true;
00450     if (validSize == blockSize) {
00451       // interior block so look at all voxels
00452       for (typename std::vector<Data_T>::const_iterator i = block.data.begin();
00453            i != block.data.end(); ++i) {
00454         if (*i != first) {
00455           match = false;
00456           break;
00457         }
00458       }
00459     } else {
00460       // only look at valid voxels
00461       int x=0, y=0, z=0;
00462       for (typename std::vector<Data_T>::const_iterator i = block.data.begin();
00463            i != block.data.end(); ++i, ++x) {
00464         if (x >= blockSize.x) {
00465           x = 0;
00466           ++y;
00467           if (y >= blockSize.y) {
00468             y = 0;
00469             ++z;
00470           }
00471         }
00472         if (x >= validSize.x || y >= validSize.y || z >= validSize.z) {
00473           continue;
00474         }
00475 
00476         if (*i != first) {
00477           match = false;
00478           break;
00479         }
00480       }
00481     } // end of interior block test
00482 
00483     if (match) {
00484       retEmptyValue = first;
00485       return true;
00486     } else {
00487       return false;
00488     }
00489   }
00490 };
00491 
00492 //----------------------------------------------------------------------------//
00493 
00494 template <typename Data_T>
00495 inline bool isAnyLess(const Data_T &left, const Data_T &right)
00496 {
00497   return (std::abs(left) < right);
00498 }
00499 
00500 //----------------------------------------------------------------------------//
00501 
00502 template <>
00503 inline bool isAnyLess(const V3h &left, const V3h &right)
00504 {
00505   return (std::abs(left.x) < right.x || 
00506           std::abs(left.y) < right.y || 
00507           std::abs(left.z) < right.z );
00508 }
00509 
00510 //----------------------------------------------------------------------------//
00511 
00512 template <>
00513 inline bool isAnyLess(const V3f &left, const V3f &right)
00514 {
00515   return (std::abs(left.x) < right.x || 
00516           std::abs(left.y) < right.y || 
00517           std::abs(left.z) < right.z );
00518 }
00519 
00520 //----------------------------------------------------------------------------//
00521 
00522 template <>
00523 inline bool isAnyLess(const V3d &left, const V3d &right)
00524 {
00525   return (std::abs(left.x) < right.x || 
00526           std::abs(left.y) < right.y || 
00527           std::abs(left.z) < right.z );
00528 }
00529 
00530 //----------------------------------------------------------------------------//
00531 
00535 template <typename Data_T>
00536 struct CheckMaxAbs
00537 {
00539   CheckMaxAbs(Data_T maxValue)
00540     : m_maxValue(maxValue)
00541   { }
00550   bool check(const SparseBlock<Data_T> &block, Data_T &retEmptyValue,
00551              const V3i &validSize, const V3i &blockSize)
00552   {
00553     // Store first value
00554     Data_T first = block.data[0];
00555     // Iterate over rest
00556     bool allGreater = true;
00557     if (validSize == blockSize) {
00558       // interior block so look at all voxels
00559       for (typename std::vector<Data_T>::const_iterator i = block.data.begin();
00560            i != block.data.end(); ++i) {
00561         if (isAnyLess<Data_T>(*i, m_maxValue)) {
00562           allGreater = false;
00563           break;
00564         }
00565       }
00566     } else {
00567       // only look at valid voxels
00568       int x=0, y=0, z=0;
00569       for (typename std::vector<Data_T>::const_iterator i = block.data.begin();
00570            i != block.data.end(); ++i, ++x) {
00571         if (x >= blockSize.x) {
00572           x = 0;
00573           ++y;
00574           if (y >= blockSize.y) {
00575             y = 0;
00576             ++z;
00577           }
00578         }
00579         if (x >= validSize.x || y >= validSize.y || z >= validSize.z) {
00580           continue;
00581         }
00582         if (isAnyLess<Data_T>(*i, m_maxValue)) {
00583           allGreater = false;
00584           break;
00585         }
00586       }
00587     } // end of interior block test
00588 
00589     if (allGreater) {
00590       retEmptyValue = first;
00591       return true;
00592     } else {
00593       return false;
00594     }
00595   }
00596 private:
00597   Data_T m_maxValue;
00598 };
00599 
00600 } // namespace Sparse
00601 
00602 //----------------------------------------------------------------------------//
00603 // SparseField::const_iterator
00604 //----------------------------------------------------------------------------//
00605 
00607 template <class Data_T>
00608 class SparseField<Data_T>::const_iterator
00609 {
00610  public:
00611   typedef SparseField<Data_T> class_type;
00612   const_iterator(const class_type &field,
00613                  const Box3i &window,
00614                  const V3i &currentPos, int blockOrder)
00615     : x(currentPos.x), y(currentPos.y), z(currentPos.z), 
00616       m_p(NULL), m_blockIsActivated(false), 
00617       m_blockStepsTicker(0), m_blockOrder(blockOrder), 
00618       m_blockId(-1), m_window(window), m_field(&field)
00619   {
00620     m_manager = m_field->m_fileManager;
00621     setupNextBlock(x, y, z);
00622   }
00623   ~const_iterator() {
00624     if (m_manager && m_blockId >= 0 && 
00625         m_blockId < static_cast<int>(m_field->m_blocks.size())) {
00626       if (m_field->m_blocks[m_blockId].isAllocated)
00627         m_manager->decBlockRef<Data_T>(m_field->m_fileId, m_blockId);
00628     }
00629   }
00630   const const_iterator& operator ++ ()
00631   {
00632     bool resetPtr = false;
00633     // Check against end of data window
00634     if (x == m_window.max.x) {
00635       if (y == m_window.max.y) {
00636         x = m_window.min.x;
00637         y = m_window.min.y;
00638         ++z;
00639         resetPtr = true;
00640       } else {
00641         x = m_window.min.x;
00642         ++y;
00643         resetPtr = true;
00644       }
00645     } else {
00646       ++x;
00647     }
00648     // These can both safely be incremented here
00649     ++m_blockStepsTicker;
00650     // ... but only step forward if we're in a non-empty block
00651     if (!m_isEmptyBlock && (!m_manager || m_blockIsActivated))
00652       ++m_p;   
00653     // Check if we've reached the end of this block
00654     if (m_blockStepsTicker == (1 << m_blockOrder))
00655       resetPtr = true;
00656     if (resetPtr) {
00657       // If we have, we need to reset the current block, etc.
00658       m_blockStepsTicker = 0;
00659       setupNextBlock(x, y, z);
00660     }
00661     return *this;
00662   }
00663   template <class Iter_T>
00664   inline bool operator == (const Iter_T &rhs) const
00665   {
00666     return x == rhs.x && y == rhs.y && z == rhs.z;
00667   }
00668   template <class Iter_T>
00669   inline bool operator != (const Iter_T &rhs) const
00670   {
00671     return x != rhs.x || y != rhs.y || z != rhs.z;
00672   }
00673   inline const Data_T& operator * () const
00674   {
00675     if (!m_isEmptyBlock && m_manager && !m_blockIsActivated) {
00676       m_manager->activateBlock<Data_T>(m_field->m_fileId, m_blockId);
00677       m_blockIsActivated = true;
00678       const Block &block = m_field->m_blocks[m_blockId];
00679       int vi, vj, vk;
00680       m_field->getVoxelInBlock(x, y, z, vi, vj, vk);
00681       m_p = &block.value(vi, vj, vk, m_blockOrder);
00682     }
00683     return *m_p;
00684   }
00685   inline const Data_T* operator -> () const
00686   {
00687     if (!m_isEmptyBlock && m_manager && !m_blockIsActivated) {
00688       SparseFileManager *manager = m_field->m_fileManager;
00689       manager->activateBlock<Data_T>(m_field->m_fileId, m_blockId);
00690       m_blockIsActivated = true;
00691       const Block &block = m_field->m_blocks[m_blockId];
00692       int vi, vj, vk;
00693       m_field->getVoxelInBlock(x, y, z, vi, vj, vk);
00694       m_p = &block.value(vi, vj, vk, m_blockOrder);
00695     }
00696     return m_p;
00697   }
00698 
00699   // Public data members -------------------------------------------------------
00700 
00702   int x, y, z;
00703 
00704 private:
00705 
00706   // Typedefs ------------------------------------------------------------------
00707 
00708   typedef Sparse::SparseBlock<Data_T> Block;
00709 
00710   // Convenience methods -------------------------------------------------------
00711 
00712   void setupNextBlock(int i, int j, int k) 
00713   {
00714     m_field->applyDataWindowOffset(i, j, k);
00715     m_field->getBlockCoord(i, j, k, m_blockI, m_blockJ, m_blockK);
00716     int oldBlockId = m_blockId;
00717     m_blockId = m_field->blockId(m_blockI, m_blockJ, m_blockK);
00718     if (m_manager && oldBlockId != m_blockId &&
00719         oldBlockId >= 0 && 
00720         oldBlockId < static_cast<int>(m_field->m_blocks.size()) &&
00721         m_field->m_blocks[oldBlockId].isAllocated) {
00722       m_manager->decBlockRef<Data_T>(m_field->m_fileId, oldBlockId);
00723     }
00724     if (m_blockId >= m_field->m_blockXYSize * m_field->m_blockRes.z) {
00725       m_isEmptyBlock = true;
00726       return;
00727     }
00728 
00729     const Block &block = m_field->m_blocks[m_blockId];
00730     int vi, vj, vk;
00731     m_field->getVoxelInBlock(i, j, k, vi, vj, vk);      
00732     m_blockStepsTicker = vi;
00733     if (block.isAllocated) {
00734       if (m_manager && oldBlockId != m_blockId && m_blockId >= 0) {
00735         m_manager->incBlockRef<Data_T>(m_field->m_fileId, m_blockId);
00736         // this is a managed field, so the block may not be loaded
00737         // yet, so don't bother setting m_p yet (it'll get set in the
00738         // * and -> operators when the block is activated)
00739       } else {
00740         // only set m_p to the voxel's address if this is not a
00741         // managed field, i.e., if the data is already in memory.
00742         m_p = &block.value(vi, vj, vk, m_blockOrder);
00743       }
00744       m_isEmptyBlock = false;
00745     } else {
00746       m_p = &block.emptyValue;
00747       m_isEmptyBlock = true;
00748     }
00749     if (m_field->m_fileManager) {
00750       m_blockIsActivated = false;
00751     }
00752   }
00753 
00755   mutable const Data_T *m_p;
00757   bool m_isEmptyBlock;
00760   mutable bool m_blockIsActivated;
00762   int m_blockStepsTicker;
00764   int m_blockOrder;
00766   int m_blockI, m_blockJ, m_blockK, m_blockId;
00768   Box3i m_window;
00770   const class_type *m_field;
00772   SparseFileManager *m_manager;
00773 };
00774 
00775 //----------------------------------------------------------------------------//
00776 // SparseField::iterator
00777 //----------------------------------------------------------------------------/
00778 
00780 template <class Data_T>
00781 class SparseField<Data_T>::iterator
00782 {
00783  public:
00784   typedef SparseField<Data_T> class_type;
00785   iterator(class_type &field,
00786            const Box3i &window,
00787            const V3i &currentPos, int blockOrder)
00788     : x(currentPos.x), y(currentPos.y), z(currentPos.z),
00789       m_p(NULL), m_blockStepsTicker(0), m_blockOrder(blockOrder), 
00790       m_blockId(-1), m_window(window), m_field(&field)
00791   {
00792     setupNextBlock(x, y, z);
00793   }
00794   const iterator& operator ++ ()
00795   {
00796     bool resetPtr = false;
00797     // Check against end of data window
00798     if (x == m_window.max.x) {
00799       if (y == m_window.max.y) {
00800         x = m_window.min.x;
00801         y = m_window.min.y;
00802         ++z;
00803         resetPtr = true;
00804       } else {
00805         x = m_window.min.x;
00806         ++y;
00807         resetPtr = true;
00808       }
00809     } else {
00810       ++x;
00811     }
00812     // These can both safely be incremented here
00813     ++m_blockStepsTicker;
00814     // ... but only step forward if we're in a non-empty block
00815     if (!m_isEmptyBlock)
00816       ++m_p;   
00817     // Check if we've reached the end of this block
00818     if (m_blockStepsTicker == (1 << m_blockOrder))
00819       resetPtr = true;
00820     if (resetPtr) {
00821       // If we have, we need to reset the current block, etc.
00822       m_blockStepsTicker = 0;
00823       setupNextBlock(x, y, z);
00824     }
00825     return *this;
00826   }
00827   inline bool operator == (const iterator &rhs) const
00828   {
00829     return x == rhs.x && y == rhs.y && z == rhs.z;
00830   }
00831   inline bool operator != (const iterator &rhs) const
00832   {
00833     return x != rhs.x || y != rhs.y || z != rhs.z;
00834   }
00835   inline Data_T& operator * ()
00836   {
00837     if (m_field->m_fileManager) {
00838       assert(false && "Dereferencing iterator on a dynamic-read sparse field");
00839       Msg::print(Msg::SevWarning, "Dereferencing iterator on a dynamic-read "
00840                 "sparse field");
00841       return *m_p;      
00842     }
00843     // If the block is currently empty, we must allocate it
00844     if (m_isEmptyBlock) {
00845       // Touch the voxel to allocate the block
00846       m_field->lvalue(x, y, z);
00847       // Set up the block again
00848       setupNextBlock(x, y, z);
00849     }
00850     return *m_p;
00851   }
00852   inline Data_T* operator -> ()
00853   {
00854     if (m_field->m_fileManager) {
00855       assert(false && "Dereferencing iterator on a dynamic-read sparse field");
00856       Msg::print(Msg::SevWarning, "Dereferencing iterator on a dynamic-read "
00857                 "sparse field");
00858       return m_p;      
00859     }
00860     // If the block is currently empty, we must allocate it
00861     if (m_isEmptyBlock) {
00862       // Touch the voxel to allocate the block
00863       m_field->lvalue(x, y, z);
00864       // Set up the block again
00865       setupNextBlock(x, y, z);
00866     }
00867     return m_p;
00868   }
00869   // Public data members
00870   int x, y, z;
00871 private:
00872   typedef Sparse::SparseBlock<Data_T> Block;
00874   void setupNextBlock(int i, int j, int k) 
00875   {
00876     m_field->applyDataWindowOffset(i, j, k);
00877     m_field->getBlockCoord(i, j, k, m_blockI, m_blockJ, m_blockK);
00878     m_blockId = m_field->blockId(m_blockI, m_blockJ, m_blockK);
00879     if (m_blockId >= m_field->m_blockXYSize * m_field->m_blockRes.z) {
00880       m_isEmptyBlock = true;
00881       return;
00882     }
00883     Block &block = m_field->m_blocks[m_blockId];
00884     int vi, vj, vk;
00885     m_field->getVoxelInBlock(i, j, k, vi, vj, vk);      
00886     m_blockStepsTicker = vi;
00887     if (block.isAllocated) {
00888       m_p = &block.value(vi, vj, vk, m_blockOrder);
00889       m_isEmptyBlock = false;
00890     } else {
00891       m_p = &block.emptyValue;
00892       m_isEmptyBlock = true;
00893     }
00894   }
00896   Data_T *m_p;
00898   bool m_isEmptyBlock;
00900   int m_blockStepsTicker;
00902   int m_blockOrder;
00904   int m_blockI, m_blockJ, m_blockK, m_blockId;
00906   Box3i m_window;
00908   class_type *m_field;
00909 };
00910 
00911 //----------------------------------------------------------------------------//
00912 // SparseField::block_iterator
00913 //----------------------------------------------------------------------------/
00914 
00917 template <class Data_T>
00918 class SparseField<Data_T>::block_iterator
00919 {
00920  public:
00922   typedef SparseField<Data_T> class_type;
00924   block_iterator(const class_type &field, const Box3i &window,
00925                  const V3i &currentPos)
00926     : x(currentPos.x), y(currentPos.y), z(currentPos.z), 
00927       m_window(window), m_field(field)
00928   {
00929     recomputeBlockBoundingBox();
00930   }
00932   const block_iterator& operator ++ ()
00933   {
00934     if (x == m_window.max.x) {
00935       if (y == m_window.max.y) {
00936         x = m_window.min.x;
00937         y = m_window.min.y;
00938         ++z;
00939       } else {
00940         x = m_window.min.x; 
00941         ++y;
00942       }
00943     } else {
00944       ++x;
00945     }
00946     recomputeBlockBoundingBox();
00947     return *this;
00948   }
00950   inline bool operator == (const block_iterator &rhs) const
00951   {
00952     return x == rhs.x && y == rhs.y && z == rhs.z;
00953   }
00955   inline bool operator != (const block_iterator &rhs) const
00956   {
00957     return x != rhs.x || y != rhs.y || z != rhs.z;
00958   }
00960   const Box3i& blockBoundingBox()
00961   {
00962     return m_currentBlockWindow;
00963   }
00965   int x, y, z;
00966 private:
00967   void recomputeBlockBoundingBox()
00968   {
00969     Box3i box;
00970     int blockSize = m_field.blockSize();
00971     box.min = V3i(x * blockSize, y * blockSize, z * blockSize);
00972     box.max = box.min + V3i(blockSize - 1, blockSize - 1, blockSize - 1);
00973     // Clamp the box 
00974     box.min = FIELD3D_CLIP(box.min, m_field.dataWindow());
00975     box.max = FIELD3D_CLIP(box.max, m_field.dataWindow());
00976     // Set the member variable
00977     m_currentBlockWindow = box;
00978   }
00980   Box3i m_window;
00982   const class_type& m_field;
00984   Box3i m_currentBlockWindow;
00985 };
00986 
00987 //----------------------------------------------------------------------------//
00988 // SparseField implementations
00989 //----------------------------------------------------------------------------//
00990 
00991 template <class Data_T>
00992 SparseField<Data_T>::SparseField()
00993   : base(),
00994     m_blockOrder(BLOCK_ORDER),
00995     m_fileManager(NULL)
00996 { 
00997   setupBlocks();
00998 }
00999 
01000 //----------------------------------------------------------------------------//
01001 
01002 template <class Data_T>
01003 SparseField<Data_T>::SparseField(const SparseField<Data_T> &o) :
01004   base(o)
01005 {
01006   copySparseField(o);
01007 }
01008 
01009 //----------------------------------------------------------------------------//
01010 
01011 template <class Data_T>
01012 SparseField<Data_T>::~SparseField()
01013 {
01014   if (m_fileManager) {
01015     // this file is dynamically managed, so we need to ensure the
01016     // cache doesn't point to this field's blocks because they are
01017     // about to be deleted
01018     m_fileManager->removeFieldFromCache<Data_T>(m_fileId);
01019   }
01020 }
01021 
01022 //----------------------------------------------------------------------------//
01023 
01024 template <class Data_T>
01025 SparseField<Data_T> &
01026 SparseField<Data_T>::operator=(const SparseField<Data_T> &o)
01027 {
01028   if (this != &o) {
01029     this->base::operator=(o);
01030     copySparseField(o);
01031   }
01032   return *this;
01033 }
01034 
01035 //----------------------------------------------------------------------------//
01036 
01037 template <class Data_T>
01038 void
01039 SparseField<Data_T>::copySparseField(const SparseField<Data_T> &o)
01040 {
01041   m_blockOrder = o.m_blockOrder;
01042   if (o.m_fileManager) {
01043     // allocate m_blocks, sets m_blockRes, m_blockXYSize, m_blocks
01044     setupBlocks();
01045 
01046     m_fileManager = o.m_fileManager;
01047     SparseFile::Reference<Data_T> &oldReference = 
01048       m_fileManager->reference<Data_T>(o.m_fileId);
01049     addReference(oldReference.filename, oldReference.layerPath,
01050                  oldReference.valuesPerBlock,
01051                  oldReference.occupiedBlocks);
01052     copyBlockStates(o);
01053     setupReferenceBlocks();
01054   } else {
01055     // directly copy all values and blocks from the source, no extra setup
01056     m_blockRes = o.m_blockRes;
01057     m_blockXYSize = o.m_blockXYSize;
01058     m_blocks = o.m_blocks;
01059     m_fileId = -1;
01060     m_fileManager = NULL;
01061   }
01062 }
01063 
01064 //----------------------------------------------------------------------------//
01065 
01066 template <class Data_T>
01067 void SparseField<Data_T>::addReference(const std::string &filename,
01068                                        const std::string &layerPath,
01069                                        int valuesPerBlock,
01070                                        int occupiedBlocks)
01071 {
01072   m_fileManager = &SparseFileManager::singleton();
01073   m_fileId = m_fileManager->getNextId<Data_T>(filename, layerPath);
01074   // Set up the manager data
01075   SparseFile::Reference<Data_T> &reference = 
01076     m_fileManager->reference<Data_T>(m_fileId);
01077   reference.valuesPerBlock = valuesPerBlock;
01078   reference.occupiedBlocks = occupiedBlocks;
01079   reference.setNumBlocks(m_blocks.size());
01080 }
01081 
01082 //----------------------------------------------------------------------------//
01083 
01084 template <class Data_T>
01085 void SparseField<Data_T>::copyBlockStates(const SparseField<Data_T> &o)
01086 {
01087   if (m_blocks.size() != o.m_blocks.size()) return;
01088 
01089   typename std::vector<Sparse::SparseBlock<Data_T> >::iterator b =
01090     m_blocks.begin();
01091   typename std::vector<Sparse::SparseBlock<Data_T> >::iterator bend = 
01092     m_blocks.end();
01093   typename std::vector<Sparse::SparseBlock<Data_T> >::const_iterator ob =
01094     o.m_blocks.begin();
01095 
01096   for (; b != bend; ++b, ++ob) {
01097     b->isAllocated = ob->isAllocated;
01098     b->emptyValue = ob->emptyValue;
01099     b->clear();
01100   }
01101 }
01102 
01103 //----------------------------------------------------------------------------//
01104 
01105 template <class Data_T>
01106 void SparseField<Data_T>::setupReferenceBlocks()
01107 {
01108   if (!m_fileManager || m_fileId < 0) return;
01109 
01110   SparseFile::Reference<Data_T> &reference = 
01111     m_fileManager->reference<Data_T>(m_fileId);
01112 
01113   std::vector<int>::iterator fb = reference.fileBlockIndices.begin();
01114   typename SparseFile::Reference<Data_T>::BlockPtrs::iterator bp = 
01115     reference.blocks.begin();
01116   typename std::vector<Sparse::SparseBlock<Data_T> >::iterator b =
01117     m_blocks.begin();
01118   typename std::vector<Sparse::SparseBlock<Data_T> >::iterator bend =
01119     m_blocks.end();
01120   int nextBlockIdx = 0;
01121 
01122   for (; b != bend; ++b, ++fb, ++bp) {
01123     if (b->isAllocated) {
01124       *fb = nextBlockIdx;
01125       *bp = &(*b);
01126       nextBlockIdx++;
01127     } else {
01128       *fb = -1;
01129     }
01130   }
01131 }
01132 
01133 //----------------------------------------------------------------------------//
01134 
01135 template <class Data_T>
01136 void SparseField<Data_T>::clear(const Data_T &value)
01137 {
01138   // If we're clearing, we can get rid of all current blocks
01139   setupBlocks();
01140   // Then just fill in the default values
01141   typename std::vector<Block>::iterator i;
01142   for (i = m_blocks.begin(); i != m_blocks.end(); ++i) {
01143     i->emptyValue = value;
01144   }
01145 }
01146 
01147 //----------------------------------------------------------------------------//
01148 
01149 template <class Data_T>
01150 void SparseField<Data_T>::setBlockOrder(int order)
01151 {
01152   m_blockOrder = order;
01153   setupBlocks();
01154 }
01155 
01156 //----------------------------------------------------------------------------//
01157 
01158 template <class Data_T>
01159 int SparseField<Data_T>::blockOrder() const 
01160 {
01161   return m_blockOrder;
01162 }
01163 
01164 //----------------------------------------------------------------------------//
01165 
01166 template <class Data_T>
01167 int SparseField<Data_T>::blockSize() const
01168 { 
01169   return 1 << m_blockOrder;
01170 }
01171 
01172 //----------------------------------------------------------------------------//
01173 
01174 template <class Data_T>
01175 bool SparseField<Data_T>::voxelIsInAllocatedBlock(int i, int j, int k) const
01176 {
01177   int bi, bj, bk;
01178   applyDataWindowOffset(i, j, k);
01179   getBlockCoord(i, j, k, bi, bj, bk);
01180   return blockIsAllocated(bi, bj, bk);
01181 }
01182 
01183 //----------------------------------------------------------------------------//
01184 
01185 template <class Data_T>
01186 bool SparseField<Data_T>::blockIsAllocated(int bi, int bj, int bk) const
01187 {
01188   const Block &block = m_blocks[blockId(bi, bj, bk)];
01189   return block.isAllocated;
01190 }
01191   
01192 //----------------------------------------------------------------------------//
01193 
01194 template <class Data_T>
01195 const Data_T SparseField<Data_T>::getBlockEmptyValue(int bi, int bj, int bk) const
01196 {
01197   return m_blocks[blockId(bi, bj, bk)].emptyValue;
01198 }
01199 
01200 //----------------------------------------------------------------------------//
01201 
01202 template <class Data_T>
01203 void SparseField<Data_T>::setBlockEmptyValue(int bi, int bj, int bk, 
01204                                              const Data_T &val)
01205 {
01206   Block &block = m_blocks[blockId(bi, bj, bk)];
01207   if (block.isAllocated) {
01208     deallocBlock(block, val);
01209   } else {
01210     block.emptyValue = val;
01211   }
01212 }
01213 
01214 //----------------------------------------------------------------------------//
01215 
01216 template <class Data_T>
01217 bool SparseField<Data_T>::blockIndexIsValid(int bi, int bj, int bk) const
01218 {
01219   return bi >= 0 && bj >= 0 && bk >= 0 && 
01220     bi < m_blockRes.x && bj < m_blockRes.y && bk < m_blockRes.z;
01221 }
01222 
01223 //----------------------------------------------------------------------------//
01224 
01225 template <class Data_T>
01226 V3i SparseField<Data_T>::blockRes() const
01227 {
01228   return m_blockRes;
01229 }
01230 
01231 //----------------------------------------------------------------------------//
01232 
01233 template <class Data_T>
01234 template <typename Functor_T>
01235 int SparseField<Data_T>::releaseBlocks(Functor_T func)
01236 {
01237   Data_T emptyValue;
01238   int numDeallocs = 0;
01239   typename std::vector<Block>::iterator i;
01240 
01241   // If the block is on the edge of the field, it may have unused
01242   // voxels, with undefined values.  We need to pass the range of
01243   // valid voxels into the check function, so it only looks at valid
01244   // voxels.
01245   V3i dataRes = FieldRes::dataResolution();
01246   V3i validSize;
01247   V3i blockAllocSize(blockSize());
01248   int bx, by, bz;
01249 
01250   for (i = m_blocks.begin(), bx=0, by=0, bz=0; i != m_blocks.end(); ++i, ++bx) {
01251     if (bx >= m_blockRes.x) {
01252       bx = 0;
01253       ++by;
01254       if (by >= m_blockRes.y) {
01255         by = 0;
01256         ++bz;
01257       }
01258     }
01259     validSize = blockAllocSize;
01260     if (bx == m_blockRes.x-1) {
01261       validSize.x = dataRes.x - bx * blockAllocSize.x;
01262     }
01263     if (by == m_blockRes.y-1) {
01264       validSize.y = dataRes.y - by * blockAllocSize.y;
01265     }
01266     if (bz == m_blockRes.z-1) {
01267       validSize.z = dataRes.z - bz * blockAllocSize.z;
01268     }
01269 
01270     if (i->isAllocated) {
01271       if (func.check(*i, emptyValue, validSize, blockAllocSize)) {
01272         deallocBlock(*i, emptyValue);
01273         numDeallocs++;
01274       }
01275     }
01276   }
01277   return numDeallocs;
01278 }
01279 
01280 //----------------------------------------------------------------------------//
01281 
01282 template <class Data_T>
01283 Data_T SparseField<Data_T>::value(int i, int j, int k) const
01284 {
01285   return fastValue(i, j, k);
01286 }
01287 
01288 //----------------------------------------------------------------------------//
01289 
01290 template <class Data_T>
01291 Data_T& SparseField<Data_T>::lvalue(int i, int j, int k)
01292 {
01293   return fastLValue(i, j, k);
01294 }
01295 
01296 //----------------------------------------------------------------------------//
01297 
01298 template <class Data_T>
01299 Data_T SparseField<Data_T>::fastValue(int i, int j, int k) const
01300 {
01301   assert (i >= base::m_dataWindow.min.x);
01302   assert (i <= base::m_dataWindow.max.x);
01303   assert (j >= base::m_dataWindow.min.y);
01304   assert (j <= base::m_dataWindow.max.y);
01305   assert (k >= base::m_dataWindow.min.z);
01306   assert (k <= base::m_dataWindow.max.z);
01307   // Add crop window offset
01308   applyDataWindowOffset(i, j, k);
01309   // Find block coord
01310   int bi, bj, bk;
01311   getBlockCoord(i, j, k, bi, bj, bk);
01312   // Find coord in block
01313   int vi, vj, vk;
01314   getVoxelInBlock(i, j, k, vi, vj, vk);
01315   // Get the actual block
01316   int id = blockId(bi, bj, bk);
01317 
01318   const Block &block = m_blocks[id];
01319   // Check if block data is allocated
01320   if (block.isAllocated) {
01321     if (m_fileManager) {
01322       m_fileManager->incBlockRef<Data_T>(m_fileId, id);
01323       m_fileManager->activateBlock<Data_T>(m_fileId, id);
01324       Data_T tmpValue = block.value(vi, vj, vk, m_blockOrder);
01325       m_fileManager->decBlockRef<Data_T>(m_fileId, id);
01326       return tmpValue;
01327     } else {
01328       return block.value(vi, vj, vk, m_blockOrder);
01329     }
01330   } else {
01331     return block.emptyValue;
01332   }
01333 }
01334 
01335 //----------------------------------------------------------------------------//
01336 
01338 template <class Data_T>
01339 Data_T& SparseField<Data_T>::fastLValue(int i, int j, int k)
01340 {
01341   assert (i >= base::m_dataWindow.min.x);
01342   assert (i <= base::m_dataWindow.max.x);
01343   assert (j >= base::m_dataWindow.min.y);
01344   assert (j <= base::m_dataWindow.max.y);
01345   assert (k >= base::m_dataWindow.min.z);
01346   assert (k <= base::m_dataWindow.max.z);
01347 
01348   if (m_fileManager) {
01349     assert(false && "Called fastLValue() on a dynamic-read sparse field");
01350     Msg::print(Msg::SevWarning, "Called fastLValue() on a dynamic-read "
01351               "sparse field");
01352     return m_dummy;
01353   }
01354 
01355   // Add crop window offset
01356   applyDataWindowOffset(i, j, k);
01357   // Find block coord
01358   int bi, bj, bk;
01359   getBlockCoord(i, j, k, bi, bj, bk);
01360   // Find coord in block
01361   int vi, vj, vk;
01362   getVoxelInBlock(i, j, k, vi, vj, vk);
01363   // Get the actual block
01364   int id = blockId(bi, bj, bk);
01365   Block &block = m_blocks[id];
01366   // If block is allocated, return a reference to the data
01367   if (block.isAllocated) {
01368     return block.value(vi, vj, vk, m_blockOrder);
01369   } else {
01370     // ... Otherwise, allocate block
01371     block.isAllocated = true;
01372     block.data.resize(1 << m_blockOrder << m_blockOrder << m_blockOrder);
01373     std::fill(block.data.begin(), block.data.end(), block.emptyValue);
01374     return block.value(vi, vj, vk, m_blockOrder);
01375   }
01376 }
01377 
01378 //----------------------------------------------------------------------------//
01379 
01380 template <class Data_T>
01381 long long int SparseField<Data_T>::memSize() const
01382 {
01383   long long int blockSize = m_blocks.capacity() * sizeof(Block);
01384   long long int dataSize = 0;
01385   typename std::vector<Block>::const_iterator i;
01386   for (i = m_blocks.begin(); i != m_blocks.end(); ++i) {
01387     if (i->isAllocated) {
01388       dataSize += i->data.capacity() * sizeof(Data_T);
01389     }
01390   }
01391   return sizeof(*this) + dataSize + blockSize;
01392 }
01393 
01394 //----------------------------------------------------------------------------//
01395 
01396 template <class Data_T>
01397 typename SparseField<Data_T>::const_iterator 
01398 SparseField<Data_T>::cbegin() const
01399 { 
01400   if (FieldRes::dataResolution() == V3i(0))
01401     return cend();
01402   return const_iterator(*this, base::m_dataWindow, base::m_dataWindow.min,
01403                         m_blockOrder); 
01404 }
01405 
01406 //----------------------------------------------------------------------------//
01407 
01408 template <class Data_T>
01409 typename SparseField<Data_T>::const_iterator 
01410 SparseField<Data_T>::cbegin(const Box3i &subset) const
01411 { 
01412   if (subset.isEmpty())
01413     return cend(subset);
01414   return const_iterator(*this, subset, subset.min, m_blockOrder); 
01415 }
01416 
01417 //----------------------------------------------------------------------------//
01418 
01419 template <class Data_T>
01420 typename SparseField<Data_T>::const_iterator 
01421 SparseField<Data_T>::cend() const
01422 { 
01423   return const_iterator(*this, base::m_dataWindow, 
01424                         V3i(base::m_dataWindow.min.x, 
01425                                    base::m_dataWindow.min.y,
01426                                    base::m_dataWindow.max.z + 1),
01427                         m_blockOrder);
01428 }
01429 
01430 //----------------------------------------------------------------------------//
01431 
01432 template <class Data_T>
01433 typename SparseField<Data_T>::const_iterator 
01434 SparseField<Data_T>::cend(const Box3i &subset) const
01435 { 
01436   return const_iterator(*this, subset, 
01437                         V3i(subset.min.x, 
01438                                    subset.min.y,
01439                                    subset.max.z + 1), m_blockOrder);
01440 }
01441 
01442 //----------------------------------------------------------------------------//
01443 
01444 template <class Data_T>
01445 typename SparseField<Data_T>::iterator 
01446 SparseField<Data_T>::begin()
01447 { 
01448   if (FieldRes::dataResolution() == V3i(0))
01449     return end();
01450   return iterator(*this, base::m_dataWindow, 
01451                   base::m_dataWindow.min, m_blockOrder); }
01452 
01453 //----------------------------------------------------------------------------//
01454 
01455 template <class Data_T>
01456 typename SparseField<Data_T>::iterator 
01457 SparseField<Data_T>::begin(const Box3i &subset)
01458 { 
01459   if (subset.isEmpty())
01460     return end(subset);
01461   return iterator(*this, subset, subset.min, m_blockOrder); 
01462 }
01463 
01464 //----------------------------------------------------------------------------//
01465 
01466 template <class Data_T>
01467 typename SparseField<Data_T>::iterator 
01468 SparseField<Data_T>::end()
01469 { 
01470   return iterator(*this, base::m_dataWindow, 
01471                   V3i(base::m_dataWindow.min.x, 
01472                              base::m_dataWindow.min.y,
01473                              base::m_dataWindow.max.z + 1), m_blockOrder);
01474 }
01475 
01476 //----------------------------------------------------------------------------//
01477 
01478 template <class Data_T>
01479 typename SparseField<Data_T>::iterator 
01480 SparseField<Data_T>::end(const Box3i &subset)
01481 { 
01482   return iterator(*this, subset, 
01483                   V3i(subset.min.x, subset.min.y, subset.max.z + 1), 
01484                   m_blockOrder);
01485 }
01486 
01487 //----------------------------------------------------------------------------//
01488 
01489 template <class Data_T>
01490 typename SparseField<Data_T>::block_iterator 
01491 SparseField<Data_T>::blockBegin() const
01492 { 
01493   if (FieldRes::dataResolution() == V3i(0))
01494     return blockEnd();
01495   return block_iterator(*this, Box3i(V3i(0), m_blockRes - V3i(1)), 
01496                         V3i(0)); 
01497 }
01498 
01499 //----------------------------------------------------------------------------//
01500 
01501 template <class Data_T>
01502 typename SparseField<Data_T>::block_iterator 
01503 SparseField<Data_T>::blockEnd() const
01504 { 
01505   return block_iterator(*this, Box3i(V3i(0), m_blockRes - V3i(1)), 
01506                         V3i(0, 0, m_blockRes.z));
01507 }
01508 
01509 //----------------------------------------------------------------------------//
01510 
01511 template <class Data_T>
01512 void SparseField<Data_T>::setupBlocks()
01513 {
01514   // Do calculation in floating point so we can round up later
01515   V3f res(base::m_dataWindow.size() + V3i(1));
01516   V3f blockRes(res / (1 << m_blockOrder));
01517   blockRes.x = ceil(blockRes.x);
01518   blockRes.y = ceil(blockRes.y);
01519   blockRes.z = ceil(blockRes.z);
01520   V3i intBlockRes(static_cast<int>(blockRes.x),
01521                          static_cast<int>(blockRes.y),
01522                          static_cast<int>(blockRes.z));
01523   m_blockRes = intBlockRes;
01524   m_blockXYSize = m_blockRes.x * m_blockRes.y;
01526   m_blocks.clear();
01527   m_blocks.resize(intBlockRes.x * intBlockRes.y * intBlockRes.z);
01528 
01529 }
01530 
01531 //----------------------------------------------------------------------------//
01532 
01533 template <class Data_T>
01534 int SparseField<Data_T>::blockId(int blockI, int blockJ, int blockK) const
01535 {
01536   return blockK * m_blockXYSize + blockJ * m_blockRes.x + blockI;
01537 }
01538 
01539 //----------------------------------------------------------------------------//
01540 
01542 template <class Data_T>
01543 void SparseField<Data_T>::getBlockCoord(int i, int j, int k, 
01544                                         int &bi, int &bj, int &bk) const 
01545 {
01546   assert(i >= 0);
01547   assert(j >= 0);
01548   assert(k >= 0);
01549   bi = i >> m_blockOrder;
01550   bj = j >> m_blockOrder;
01551   bk = k >> m_blockOrder;
01552 }
01553 
01554 //----------------------------------------------------------------------------//
01555 
01557 template <class Data_T>
01558 void SparseField<Data_T>::getVoxelInBlock(int i, int j, int k, 
01559                                           int &vi, int &vj, int &vk) const
01560 {
01561   assert(i >= 0);
01562   assert(j >= 0);
01563   assert(k >= 0);
01564   vi = i & ((1 << m_blockOrder) - 1);
01565   vj = j & ((1 << m_blockOrder) - 1);
01566   vk = k & ((1 << m_blockOrder) - 1);
01567 }
01568 
01569 //----------------------------------------------------------------------------//
01570 
01571 template <class Data_T>
01572 void SparseField<Data_T>::deallocBlock(Block &block, const Data_T &emptyValue)
01573 {
01574   block.isAllocated = false;
01575   block.clear();
01576   block.emptyValue = emptyValue;
01577 }
01578 
01579 //----------------------------------------------------------------------------//
01580 
01581 FIELD3D_NAMESPACE_HEADER_CLOSE
01582 
01583 //----------------------------------------------------------------------------//
01584 
01585 #endif // Include guard