.. _program_listing_file__tmp_ws_src_octomap_octomap_include_octomap_OcTreeBaseImpl.h:

Program Listing for File OcTreeBaseImpl.h
=========================================

|exhale_lsh| :ref:`Return to documentation for file <file__tmp_ws_src_octomap_octomap_include_octomap_OcTreeBaseImpl.h>` (``/tmp/ws/src/octomap/octomap/include/octomap/OcTreeBaseImpl.h``)

.. |exhale_lsh| unicode:: U+021B0 .. UPWARDS ARROW WITH TIP LEFTWARDS

.. code-block:: cpp

   /*
    * OctoMap - An Efficient Probabilistic 3D Mapping Framework Based on Octrees
    * https://octomap.github.io/
    *
    * Copyright (c) 2009-2013, K.M. Wurm and A. Hornung, University of Freiburg
    * All rights reserved.
    * License: New BSD
    *
    * Redistribution and use in source and binary forms, with or without
    * modification, are permitted provided that the following conditions are met:
    *
    *     * Redistributions of source code must retain the above copyright
    *       notice, this list of conditions and the following disclaimer.
    *     * Redistributions in binary form must reproduce the above copyright
    *       notice, this list of conditions and the following disclaimer in the
    *       documentation and/or other materials provided with the distribution.
    *     * Neither the name of the University of Freiburg nor the names of its
    *       contributors may be used to endorse or promote products derived from
    *       this software without specific prior written permission.
    *
    * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
    * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    * POSSIBILITY OF SUCH DAMAGE.
    */
   
   #ifndef OCTOMAP_OCTREE_BASE_IMPL_H
   #define OCTOMAP_OCTREE_BASE_IMPL_H
   
   
   #include <list>
   #include <limits>
   #include <iterator>
   #include <stack>
   #include <bitset>
   
   #include "octomap_types.h"
   #include "OcTreeKey.h"
   #include "ScanGraph.h"
   
   
   namespace octomap {
     
     // forward declaration for NODE children array
     class AbstractOcTreeNode;
   
   
     template <class NODE,class INTERFACE>
     class OcTreeBaseImpl : public INTERFACE {
   
     public:
       typedef NODE NodeType;
   
       // the actual iterator implementation is included here
       // as a member from this file
       #include <octomap/OcTreeIterator.hxx>
       
       OcTreeBaseImpl(double resolution);
       virtual ~OcTreeBaseImpl();
   
       OcTreeBaseImpl(const OcTreeBaseImpl<NODE,INTERFACE>& rhs);
   
   
       void swapContent(OcTreeBaseImpl<NODE,INTERFACE>& rhs);
   
       bool operator== (const OcTreeBaseImpl<NODE,INTERFACE>& rhs) const;
   
       std::string getTreeType() const {return "OcTreeBaseImpl";}
   
       void setResolution(double r);
       inline double getResolution() const { return resolution; }
   
       inline unsigned int getTreeDepth () const { return tree_depth; }
   
       inline double getNodeSize(unsigned depth) const {assert(depth <= tree_depth); return sizeLookupTable[depth];}
       
       void clearKeyRays(){
         keyrays.clear();
       }
       
       // -- Tree structure operations formerly contained in the nodes ---
      
       NODE* createNodeChild(NODE* node, unsigned int childIdx);
       
       void deleteNodeChild(NODE* node, unsigned int childIdx);
       
       NODE* getNodeChild(NODE* node, unsigned int childIdx) const;
       
       const NODE* getNodeChild(const NODE* node, unsigned int childIdx) const;
       
       virtual bool isNodeCollapsible(const NODE* node) const;
       
       bool nodeChildExists(const NODE* node, unsigned int childIdx) const;
       
       bool nodeHasChildren(const NODE* node) const;
       
       virtual void expandNode(NODE* node);
       
       virtual bool pruneNode(NODE* node);
       
       
       // --------
   
       inline NODE* getRoot() const { return root; }
   
       NODE* search(double x, double y, double z, unsigned int depth = 0) const;
   
       NODE* search(const point3d& value, unsigned int depth = 0) const;
   
       NODE* search(const OcTreeKey& key, unsigned int depth = 0) const;
   
       bool deleteNode(double x, double y, double z, unsigned int depth = 0);
   
       bool deleteNode(const point3d& value, unsigned int depth = 0);
   
       bool deleteNode(const OcTreeKey& key, unsigned int depth = 0);
   
       void clear();
   
       virtual void prune();
   
       virtual void expand();
   
       // -- statistics  ----------------------
   
       virtual inline size_t size() const { return tree_size; }
   
       virtual size_t memoryUsage() const;
   
       virtual inline size_t memoryUsageNode() const {return sizeof(NODE); }
   
       unsigned long long memoryFullGrid() const;
   
       double volume();
   
       virtual void getMetricSize(double& x, double& y, double& z);
       virtual void getMetricSize(double& x, double& y, double& z) const;
       virtual void getMetricMin(double& x, double& y, double& z);
       void getMetricMin(double& x, double& y, double& z) const;
       virtual void getMetricMax(double& x, double& y, double& z);
       void getMetricMax(double& x, double& y, double& z) const;
   
       size_t calcNumNodes() const;
   
       size_t getNumLeafNodes() const;
   
   
       // -- access tree nodes  ------------------
   
       void getUnknownLeafCenters(point3d_list& node_centers, point3d pmin, point3d pmax, unsigned int depth = 0) const;
   
   
       // -- raytracing  -----------------------
   
       bool computeRayKeys(const point3d& origin, const point3d& end, KeyRay& ray) const;
   
   
       bool computeRay(const point3d& origin, const point3d& end, std::vector<point3d>& ray);
   
   
       // file IO
   
       std::istream& readData(std::istream &s);
   
       std::ostream& writeData(std::ostream &s) const;
   
       typedef leaf_iterator iterator;
   
       iterator begin(unsigned char maxDepth=0) const {return iterator(this, maxDepth);}
       const iterator end() const {return leaf_iterator_end;} // TODO: RVE?
   
       leaf_iterator begin_leafs(unsigned char maxDepth=0) const {return leaf_iterator(this, maxDepth);}
       const leaf_iterator end_leafs() const {return leaf_iterator_end;}
   
       leaf_bbx_iterator begin_leafs_bbx(const OcTreeKey& min, const OcTreeKey& max, unsigned char maxDepth=0) const {
         return leaf_bbx_iterator(this, min, max, maxDepth);
       }
       leaf_bbx_iterator begin_leafs_bbx(const point3d& min, const point3d& max, unsigned char maxDepth=0) const {
         return leaf_bbx_iterator(this, min, max, maxDepth);
       }
       const leaf_bbx_iterator end_leafs_bbx() const {return leaf_iterator_bbx_end;}
   
       tree_iterator begin_tree(unsigned char maxDepth=0) const {return tree_iterator(this, maxDepth);}
       const tree_iterator end_tree() const {return tree_iterator_end;}
   
       //
       // Key / coordinate conversion functions
       //
   
       inline key_type coordToKey(double coordinate) const{
         return ((int) floor(resolution_factor * coordinate)) + tree_max_val;
       }
   
       key_type coordToKey(double coordinate, unsigned depth) const;
   
   
       inline OcTreeKey coordToKey(const point3d& coord) const{
         return OcTreeKey(coordToKey(coord(0)), coordToKey(coord(1)), coordToKey(coord(2)));
       }
   
       inline OcTreeKey coordToKey(double x, double y, double z) const{
         return OcTreeKey(coordToKey(x), coordToKey(y), coordToKey(z));
       }
   
       inline OcTreeKey coordToKey(const point3d& coord, unsigned depth) const{
         if (depth == tree_depth)
           return coordToKey(coord);
         else
           return OcTreeKey(coordToKey(coord(0), depth), coordToKey(coord(1), depth), coordToKey(coord(2), depth));
       }
   
       inline OcTreeKey coordToKey(double x, double y, double z, unsigned depth) const{
         if (depth == tree_depth)
           return coordToKey(x,y,z);
         else
           return OcTreeKey(coordToKey(x, depth), coordToKey(y, depth), coordToKey(z, depth));
       }
   
       inline OcTreeKey adjustKeyAtDepth(const OcTreeKey& key, unsigned int depth) const{
         if (depth == tree_depth)
           return key;
   
         assert(depth <= tree_depth);
         return OcTreeKey(adjustKeyAtDepth(key[0], depth), adjustKeyAtDepth(key[1], depth), adjustKeyAtDepth(key[2], depth));
       }
   
       key_type adjustKeyAtDepth(key_type key, unsigned int depth) const;
   
       bool coordToKeyChecked(const point3d& coord, OcTreeKey& key) const;
   
       bool coordToKeyChecked(const point3d& coord, unsigned depth, OcTreeKey& key) const;
   
       bool coordToKeyChecked(double x, double y, double z, OcTreeKey& key) const;
   
       bool coordToKeyChecked(double x, double y, double z, unsigned depth, OcTreeKey& key) const;
   
       bool coordToKeyChecked(double coordinate, key_type& key) const;
   
       bool coordToKeyChecked(double coordinate, unsigned depth, key_type& key) const;
   
       double keyToCoord(key_type key, unsigned depth) const;
   
       inline double keyToCoord(key_type key) const{
         return (double( (int) key - (int) this->tree_max_val ) +0.5) * this->resolution;
       }
   
       inline point3d keyToCoord(const OcTreeKey& key) const{
         return point3d(float(keyToCoord(key[0])), float(keyToCoord(key[1])), float(keyToCoord(key[2])));
       }
   
       inline point3d keyToCoord(const OcTreeKey& key, unsigned depth) const{
         return point3d(float(keyToCoord(key[0], depth)), float(keyToCoord(key[1], depth)), float(keyToCoord(key[2], depth)));
       }
   
    protected:
       OcTreeBaseImpl(double resolution, unsigned int tree_depth, unsigned int tree_max_val);
   
       void init();
   
       void calcMinMax();
   
       void calcNumNodesRecurs(NODE* node, size_t& num_nodes) const;
       
       std::istream& readNodesRecurs(NODE*, std::istream &s);
       
       std::ostream& writeNodesRecurs(const NODE*, std::ostream &s) const;
       
       void deleteNodeRecurs(NODE* node);
   
       bool deleteNodeRecurs(NODE* node, unsigned int depth, unsigned int max_depth, const OcTreeKey& key);
   
       void pruneRecurs(NODE* node, unsigned int depth, unsigned int max_depth, unsigned int& num_pruned);
   
       void expandRecurs(NODE* node, unsigned int depth, unsigned int max_depth);
       
       size_t getNumLeafNodesRecurs(const NODE* parent) const;
   
     private:
       OcTreeBaseImpl<NODE,INTERFACE>& operator=(const OcTreeBaseImpl<NODE,INTERFACE>&);
   
     protected:  
       void allocNodeChildren(NODE* node);
   
       NODE* root; 
   
       // constants of the tree
       const unsigned int tree_depth; 
       const unsigned int tree_max_val;
       double resolution;  
       double resolution_factor; 
     
       size_t tree_size; 
       bool size_changed;
   
       point3d tree_center;  // coordinate offset of tree
   
       double max_value[3]; 
       double min_value[3]; 
       std::vector<double> sizeLookupTable;
   
       std::vector<KeyRay> keyrays;
   
       const leaf_iterator leaf_iterator_end;
       const leaf_bbx_iterator leaf_iterator_bbx_end;
       const tree_iterator tree_iterator_end;
   
   
     };
   
   }
   
   #include <octomap/OcTreeBaseImpl.hxx>
   
   #endif