ntree.h

Go to the documentation of this file.

/*
 *  ntree.h
 *
 *  This file is part of NEST.
 *
 *  Copyright (C) 2004 The NEST Initiative
 *
 *  NEST is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  NEST is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with NEST.  If not, see <http://www.gnu.org/licenses/>.
 *
 */
 
#ifndef NTREE_H
#define NTREE_H
 
// C++ includes:
#include <bitset>
#include <iterator>
#include <utility>
#include <vector>
 
// Includes from spatial:
#include "position.h"
 
namespace nest
{
 
class AbstractMask;
 
template < int D >
class Mask;
 
template < int D, class T, int max_capacity = 100, int max_depth = 10 >
class Ntree
{
public:
  static const int N = 1 << D;
 
  typedef Position< D > key_type;
  typedef T mapped_type;
  typedef std::pair< Position< D >, T > value_type;
  typedef value_type& reference;
  typedef const value_type& const_reference;
 
  class iterator
  {
  public:
    iterator()
      : ntree_( 0 )
      , top_( 0 )
      , node_( 0 )
    {
    }
 
    explicit iterator( Ntree& q );
 
    iterator( Ntree& q, size_t n );
 
    value_type&
    operator*()
    {
      return ntree_->nodes_[ node_ ];
    }
    value_type*
    operator->()
    {
      return &ntree_->nodes_[ node_ ];
    }
 
    iterator& operator++();
 
    iterator
    operator++( int )
    {
      iterator tmp = *this;
      ++*this;
      return tmp;
    }
 
    bool
    operator==( const iterator& other ) const
    {
      return other.ntree_ == ntree_ and ( other.node_ == node_ );
    }
    bool
    operator!=( const iterator& other ) const
    {
      return ( other.ntree_ != ntree_ ) or ( other.node_ != node_ );
    }
 
  protected:
    void next_leaf_();
 
    Ntree* ntree_;
    Ntree* top_;
    size_t node_;
  };
 
  class masked_iterator
  {
  public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = std::pair< Position< D >, T >;
    using pointer = value_type*;
    using reference = value_type&;
    using difference_type = long int;
    masked_iterator()
      : ntree_( 0 )
      , top_( 0 )
      , allin_top_( 0 )
      , node_( 0 )
      , mask_( 0 )
    {
    }
 
    masked_iterator( Ntree& q, const Mask< D >& mask, const Position< D >& anchor );
 
    value_type&
    operator*()
    {
      return ntree_->nodes_[ node_ ];
    }
    value_type*
    operator->()
    {
      return &ntree_->nodes_[ node_ ];
    }
 
    masked_iterator& operator++();
 
    masked_iterator
    operator++( int )
    {
      masked_iterator tmp = *this;
      ++*this;
      return tmp;
    }
 
    bool
    operator==( const masked_iterator& other ) const
    {
      return other.ntree_ == ntree_ and ( other.node_ == node_ );
    }
    bool
    operator!=( const masked_iterator& other ) const
    {
      return ( other.ntree_ != ntree_ ) or ( other.node_ != node_ );
    }
 
  protected:
    void init_();
 
    void next_leaf_();
 
    void first_leaf_();
 
    void first_leaf_inside_();
 
    void next_anchor_();
 
    bool
    anchored_position_inside_mask( const Position< D >& position )
    {
      // Create anchored position in two steps to avoid creating a new Position object.
      anchored_position_ = position;
      anchored_position_ -= anchor_;
      return mask_->inside( anchored_position_ );
    }
 
    Ntree* ntree_;
    Ntree* top_;
    Ntree* allin_top_;
    size_t node_;
    const Mask< D >* mask_;
    Position< D > anchor_;
    Position< D > anchored_position_;
    std::vector< Position< D > > anchors_;
    size_t current_anchor_;
  };
 
  Ntree( const Position< D >& lower_left,
    const Position< D >& extent,
    std::bitset< D > periodic = 0,
    Ntree* parent = 0,
    int subquad = 0 );
 
  ~Ntree();
 
  iterator insert( Position< D > pos, const T& node );
 
  iterator insert( const value_type& val );
 
  iterator insert( iterator, const value_type& val );
 
  void push_back( const value_type& val );
 
 
  std::vector< value_type > get_nodes();
 
  std::vector< value_type > get_nodes( const Mask< D >& mask, const Position< D >& anchor );
 
  iterator
  begin()
  {
    return iterator( *this );
  }
 
  iterator
  end()
  {
    return iterator();
  }
 
  masked_iterator
  masked_begin( const Mask< D >& mask, const Position< D >& anchor )
  {
    return masked_iterator( *this, mask, anchor );
  }
 
  masked_iterator
  masked_end()
  {
    return masked_iterator();
  }
 
  bool is_leaf() const;
 
protected:
  void split_();
 
  void append_nodes_( std::vector< value_type >& );
 
  void append_nodes_( std::vector< value_type >&, const Mask< D >&, const Position< D >& );
 
  int subquad_( const Position< D >& );
 
  Position< D > lower_left_;
  Position< D > extent_;
 
  bool leaf_;
 
  std::vector< value_type > nodes_;
 
  Ntree* parent_;
  int my_subquad_;  
  int my_depth_;    
  Ntree* children_[ N ];
  std::bitset< D > periodic_;  
 
  friend class iterator;
  friend class masked_iterator;
};
 
template < int D, class T, int max_capacity, int max_depth >
Ntree< D, T, max_capacity, max_depth >::Ntree( const Position< D >& lower_left,
  const Position< D >& extent,
  std::bitset< D > periodic,
  Ntree< D, T, max_capacity, max_depth >* parent,
  int subquad )
  : lower_left_( lower_left )
  , extent_( extent )
  , leaf_( true )
  , parent_( parent )
  , my_subquad_( subquad )
  , my_depth_( parent ? parent->my_depth_ + 1 : 0 )
  , periodic_( periodic )
{
}
 
template < int D, class T, int max_capacity, int max_depth >
Ntree< D, T, max_capacity, max_depth >::~Ntree()
{
  if ( leaf_ )
  {
    // if T is a vector class, we do not delete the pointees
    return;
  }
 
  for ( size_t n = 0; n < static_cast< size_t >( N ); ++n )
  {
    delete children_[ n ];  // calls destructor in child, thus recursing
  }
}
 
template < int D, class T, int max_capacity, int max_depth >
Ntree< D, T, max_capacity, max_depth >::iterator::iterator( Ntree& q, size_t n )
  : ntree_( &q )
  , top_( &q )
  , node_( n )
{
  assert( ntree_->leaf_ );
 
  // First ancestor
  while ( top_->parent_ )
  {
    top_ = top_->parent_;
  }
}
 
template < int D, class T, int max_capacity, int max_depth >
bool
Ntree< D, T, max_capacity, max_depth >::is_leaf() const
{
  return leaf_;
}
 
 
template < int D, class T, int max_capacity, int max_depth >
std::vector< std::pair< Position< D >, T > >
Ntree< D, T, max_capacity, max_depth >::get_nodes()
{
  std::vector< std::pair< Position< D >, T > > result;
  append_nodes_( result );
  return result;
}
 
template < int D, class T, int max_capacity, int max_depth >
std::vector< std::pair< Position< D >, T > >
Ntree< D, T, max_capacity, max_depth >::get_nodes( const Mask< D >& mask, const Position< D >& anchor )
{
  std::vector< std::pair< Position< D >, T > > result;
  append_nodes_( result, mask, anchor );
  return result;
}
 
template < int D, class T, int max_capacity, int max_depth >
typename Ntree< D, T, max_capacity, max_depth >::iterator
Ntree< D, T, max_capacity, max_depth >::insert( const std::pair< Position< D >, T >& val )
{
  return insert( val.first, val.second );
}
 
template < int D, class T, int max_capacity, int max_depth >
typename Ntree< D, T, max_capacity, max_depth >::iterator
Ntree< D, T, max_capacity, max_depth >::insert( iterator, const std::pair< Position< D >, T >& val )
{
  return insert( val.first, val.second );
}
 
template < int D, class T, int max_capacity, int max_depth >
void
Ntree< D, T, max_capacity, max_depth >::push_back( const value_type& val )
{
  insert( val );
}
 
 
}  // namespace nest
 
 
#endif