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

#include <vector>
#include <utility>
#include <bitset>
#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) {}

      iterator(Ntree& q);

      iterator(Ntree& q, index 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_) && (other.node_==node_); }
      bool operator!=(const iterator &other) const
        { return (other.ntree_!=ntree_) || (other.node_!=node_); }

    protected:

      void next_leaf_();

      Ntree *ntree_;
      Ntree *top_;
      index node_;
    };

    class masked_iterator {
    public:
      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_) && (other.node_==node_); }
      bool operator!=(const masked_iterator &other) const
        { return (other.ntree_!=ntree_) || (other.node_!=node_); }

    protected:

      void init_();

      void next_leaf_();

      void first_leaf_();

      void first_leaf_inside_();

      void next_anchor_();

      Ntree *ntree_;
      Ntree *top_;
      Ntree *allin_top_;
      index node_;
      const Mask<D> *mask_;
      Position<D> anchor_;
      std::vector<Position<D> > anchors_;
      index 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);

    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_ )
      return;    // if T is a vector class, we do not delete the pointees

    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, index 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);
  }

} // namespace nest

#endif