node_collection.h

Go to the documentation of this file.

/*
 *  node_collection.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 NODE_COLLECTION_H
#define NODE_COLLECTION_H
 
// C++ includes:
#include <memory>
#include <ostream>
#include <stdexcept>  // out_of_range
#include <vector>
 
// Includes from libnestuil:
#include "dictionary.h"
 
// Includes from nestkernel:
#include "exceptions.h"
 
 
// Includes from thirdparty:
#include "compose.hpp"
 
namespace nest
{
class Node;
class NodeCollection;
class NodeCollectionPrimitive;
class NodeCollectionComposite;
class NodeCollectionMetadata;
 
using NodeCollectionPTR = std::shared_ptr< NodeCollection >;
using NodeCollectionMetadataPTR = std::shared_ptr< NodeCollectionMetadata >;
 
class NodeCollectionMetadata
{
public:
  NodeCollectionMetadata() = default;
  virtual ~NodeCollectionMetadata() = default;
 
  virtual void set_status( const Dictionary&, bool ) = 0;
 
  virtual void get_status( Dictionary&, NodeCollection const* const ) const = 0;
  virtual void get_status( Dictionary&, const NodeCollectionPTR ) const = 0;
 
  virtual void set_first_node_id( size_t ) = 0;
  virtual size_t get_first_node_id() const = 0;
  virtual std::string get_type() const = 0;
 
  virtual bool operator==( const NodeCollectionMetadataPTR ) const = 0;
};
 
class NodeIDTriple
{
public:
  size_t node_id { 0 };   
  size_t model_id { 0 };  
  size_t nc_index { 0 };  
  NodeIDTriple() = default;
};
 
class nc_const_iterator
{
  friend class NodeCollectionPrimitive;
  friend class NodeCollectionComposite;
 
public:
  enum class NCIteratorKind
  {
    GLOBAL,        
    RANK_LOCAL,    
    THREAD_LOCAL,  
    END            
  };
 
private:
  NodeCollectionPTR coll_ptr_;  
  size_t element_idx_;          
  size_t part_idx_;             
  size_t step_;                 
  const NCIteratorKind kind_;   
  const size_t rank_or_vp_;     
 
  NodeCollectionPrimitive const* const primitive_collection_;
 
  NodeCollectionComposite const* const composite_collection_;
 
  explicit nc_const_iterator( NodeCollectionPTR collection_ptr,
    const NodeCollectionPrimitive& collection,
    size_t offset,
    size_t stride,
    NCIteratorKind kind = NCIteratorKind::GLOBAL );
 
  explicit nc_const_iterator( NodeCollectionPTR collection_ptr,
    const NodeCollectionComposite& collection,
    size_t part,
    size_t offset,
    size_t stride,
    NCIteratorKind kind = NCIteratorKind::GLOBAL );
 
  size_t find_next_within_part_( size_t n ) const;
 
  void advance_global_iter_to_new_part_( size_t n );
 
  void advance_local_iter_to_new_part_( size_t n );
 
public:
  using iterator_category = std::forward_iterator_tag;
  using difference_type = long;
  using value_type = NodeIDTriple;
  using pointer = NodeIDTriple*;
  using reference = NodeIDTriple&;
 
  nc_const_iterator( const nc_const_iterator& nci ) = default;
  std::pair< size_t, size_t > get_part_offset() const;
 
  NodeIDTriple operator*() const;
  bool operator==( const nc_const_iterator& rhs ) const;
  bool operator!=( const nc_const_iterator& rhs ) const;
  bool operator<( const nc_const_iterator& rhs ) const;
  bool operator<=( const nc_const_iterator& rhs ) const;
  bool operator>( const nc_const_iterator& rhs ) const;
  bool operator>=( const nc_const_iterator& rhs ) const;
 
  nc_const_iterator& operator++();
  nc_const_iterator operator++( int );  // postfix
  nc_const_iterator& operator+=( const size_t );
  nc_const_iterator operator+( const size_t ) const;
 
  size_t get_step_size() const;
};
 
 
class NodeCollection
{
  friend class nc_const_iterator;
 
public:
  using const_iterator = nc_const_iterator;
 
 
  NodeCollection();
 
  virtual ~NodeCollection() = default;
 
  static NodeCollectionPTR create( const size_t node_id );
 
  static NodeCollectionPTR create( const Node* node );
 
  static NodeCollectionPTR create( const std::vector< size_t >& node_ids );
 
  bool valid() const;
 
  virtual std::ostream& print_me( std::ostream& ) const = 0;
 
  virtual size_t operator[]( size_t ) const = 0;
 
  virtual NodeCollectionPTR operator+( NodeCollectionPTR ) const = 0;
  virtual bool operator==( NodeCollectionPTR ) const = 0;
 
  virtual bool operator!=( NodeCollectionPTR ) const;
 
  virtual const_iterator begin( NodeCollectionPTR = NodeCollectionPTR( nullptr ) ) const = 0;
 
  virtual const_iterator thread_local_begin( NodeCollectionPTR = NodeCollectionPTR( nullptr ) ) const = 0;
 
  virtual const_iterator rank_local_begin( NodeCollectionPTR = NodeCollectionPTR( nullptr ) ) const = 0;
 
  virtual const_iterator end( NodeCollectionPTR = NodeCollectionPTR( nullptr ) ) const = 0;
 
  std::vector< size_t > to_array( const std::string& selection ) const;
 
  virtual size_t size() const = 0;
 
  virtual size_t stride() const = 0;
 
  virtual bool contains( const size_t node_id ) const = 0;
 
  virtual NodeCollectionPTR slice( size_t start, size_t end, size_t stride ) const = 0;
 
  virtual void set_metadata( NodeCollectionMetadataPTR ) = 0;
 
  virtual NodeCollectionMetadataPTR get_metadata() const = 0;
 
  virtual bool is_range() const = 0;
 
  virtual bool empty() const = 0;
 
  virtual long get_nc_index( const size_t ) const = 0;
 
  virtual bool has_proxies() const = 0;
 
  void get_metadata_status( Dictionary& ) const;
 
  size_t get_first() const;
 
  size_t get_last() const;
 
 
private:
  unsigned long fingerprint_;  
  static NodeCollectionPTR create_();
  static NodeCollectionPTR create_( const std::vector< size_t >& );
};
 
class NodeCollectionPrimitive : public NodeCollection
{
  friend class nc_const_iterator;
 
private:
  // Even though all members are logically const, we cannot declare them const because
  // sorting or merging the parts_ array requires assignment.
  size_t first_;                        
  size_t last_;                         
  size_t model_id_;                     
  NodeCollectionMetadataPTR metadata_;  
  bool nodes_have_no_proxies_;          
 
  void assert_consistent_model_ids_( const size_t ) const;
 
public:
  NodeCollectionPrimitive( size_t first, size_t last, size_t model_id, NodeCollectionMetadataPTR );
 
  NodeCollectionPrimitive( size_t first, size_t last, size_t model_id );
 
  NodeCollectionPrimitive( size_t first, size_t last );
 
  NodeCollectionPrimitive( const NodeCollectionPrimitive& ) = default;
 
  NodeCollectionPrimitive& operator=( const NodeCollectionPrimitive& ) = default;
 
  NodeCollectionPrimitive();
 
  std::ostream& print_me( std::ostream& ) const override;
  void print_primitive( std::ostream& ) const;
 
  size_t operator[]( const size_t ) const override;
  NodeCollectionPTR operator+( NodeCollectionPTR rhs ) const override;
  bool operator==( const NodeCollectionPTR rhs ) const override;
  bool operator==( const NodeCollectionPrimitive& rhs ) const;
 
  const_iterator begin( NodeCollectionPTR = NodeCollectionPTR( nullptr ) ) const override;
  const_iterator thread_local_begin( NodeCollectionPTR = NodeCollectionPTR( nullptr ) ) const override;
  const_iterator rank_local_begin( NodeCollectionPTR = NodeCollectionPTR( nullptr ) ) const override;
  const_iterator end( NodeCollectionPTR = NodeCollectionPTR( nullptr ) ) const override;
 
  size_t size() const override;
 
  size_t stride() const override;
 
  bool contains( const size_t node_id ) const override;
  NodeCollectionPTR slice( size_t start, size_t end, size_t stride = 1 ) const override;
 
  void set_metadata( NodeCollectionMetadataPTR ) override;
 
  NodeCollectionMetadataPTR get_metadata() const override;
 
  bool is_range() const override;
  bool empty() const override;
 
  long get_nc_index( const size_t ) const override;
 
  bool has_proxies() const override;
 
  bool is_contiguous_ascending( const NodeCollectionPrimitive& other ) const;
 
  bool overlapping( const NodeCollectionPrimitive& rhs ) const;
};
 
NodeCollectionPTR operator+( NodeCollectionPTR lhs, NodeCollectionPTR rhs );
 
class NodeCollectionComposite : public NodeCollection
{
  friend class nc_const_iterator;
 
private:
  std::vector< NodeCollectionPrimitive > parts_;  
  size_t size_;                                   
  size_t stride_;                                 
  size_t first_part_;                             
  size_t first_elem_;                             
  size_t last_part_;                              
  size_t last_elem_;                              
  bool is_sliced_;                                
  std::vector< size_t > cumul_abs_size_;          
  std::vector< size_t >
    first_in_part_;  
 
  void merge_parts_( std::vector< NodeCollectionPrimitive >& parts ) const;
 
  typedef size_t ( *gid_to_phase_fcn_ )( size_t );
 
  std::pair< size_t, size_t > specific_local_begin_( size_t period,
    size_t phase,
    size_t start_part,
    size_t start_offset,
    gid_to_phase_fcn_ period_first_node ) const;
 
  bool valid_idx_( const size_t part_idx, const size_t element_idx ) const;
 
  std::pair< size_t, size_t > find_next_part_( size_t part_idx, size_t element_idx, size_t n = 1 ) const;
 
  static size_t gid_to_vp_( size_t gid );
 
  static size_t gid_to_rank_( size_t gid );
 
 
public:
  NodeCollectionComposite( const NodeCollectionPrimitive&, size_t, size_t, size_t );
 
  NodeCollectionComposite( const NodeCollectionComposite&, size_t, size_t, size_t );
 
  explicit NodeCollectionComposite( const std::vector< NodeCollectionPrimitive >& );
 
  NodeCollectionComposite( const NodeCollectionComposite& ) = default;
 
  std::ostream& print_me( std::ostream& ) const override;
 
  size_t operator[]( const size_t ) const override;
 
  NodeCollectionPTR operator+( NodeCollectionPTR rhs ) const override;
  NodeCollectionPTR operator+( const NodeCollectionPrimitive& rhs ) const;
  bool operator==( const NodeCollectionPTR rhs ) const override;
 
  const_iterator begin( NodeCollectionPTR = NodeCollectionPTR( nullptr ) ) const override;
  const_iterator thread_local_begin( NodeCollectionPTR = NodeCollectionPTR( nullptr ) ) const override;
  const_iterator rank_local_begin( NodeCollectionPTR = NodeCollectionPTR( nullptr ) ) const override;
  const_iterator end( NodeCollectionPTR = NodeCollectionPTR( nullptr ) ) const override;
 
  size_t size() const override;
 
  size_t stride() const override;
 
  bool contains( const size_t node_id ) const override;
  NodeCollectionPTR slice( size_t start, size_t end, size_t step = 1 ) const override;
 
  void set_metadata( NodeCollectionMetadataPTR ) override;
 
  NodeCollectionMetadataPTR get_metadata() const override;
 
  bool is_range() const override;
  bool empty() const override;
 
  long get_nc_index( const size_t ) const override;
 
  bool has_proxies() const override;
};
 
inline std::ostream&
operator<<( std::ostream& out, const NodeCollectionPTR nc )
{
  return nc->print_me( out );
}
 
 
inline bool
NodeCollection::operator!=( NodeCollectionPTR rhs ) const
{
  return not( *this == rhs );
}
 
inline void
NodeCollection::set_metadata( NodeCollectionMetadataPTR )
{
  throw KernelException( "Cannot set Metadata on this type of NodeCollection." );
}
 
inline size_t
NodeCollection::get_first() const
{
  return ( *begin() ).node_id;
}
 
inline size_t
NodeCollection::get_last() const
{
  assert( size() > 0 );
  return ( *( begin() + ( size() - 1 ) ) ).node_id;
}
 
inline nc_const_iterator&
nc_const_iterator::operator+=( const size_t n )
{
  assert( kind_ != NCIteratorKind::END );
 
  if ( n == 0 )
  {
    return *this;
  }
 
  const auto new_element_idx = find_next_within_part_( n );
 
  // For a primitive collection, we either have a new element or are at the end
  // For a composite collection, we may need to search through further parts,
  // which is signalled by new_element_idx == element_idx_
  if ( primitive_collection_ or new_element_idx != element_idx_ )
  {
    element_idx_ = new_element_idx;
  }
  else
  {
    // We did not find a new element in the current part and have not exhausted the collection
    if ( kind_ == NCIteratorKind::GLOBAL )
    {
      advance_global_iter_to_new_part_( n );
    }
    else
    {
      advance_local_iter_to_new_part_( n );
    }
  }
 
  return *this;
}
 
inline nc_const_iterator
nc_const_iterator::operator+( const size_t n ) const
{
  nc_const_iterator it = *this;
  return it += n;
}
 
inline nc_const_iterator&
nc_const_iterator::operator++()
{
  ( *this ) += 1;
  return *this;
}
 
inline nc_const_iterator
nc_const_iterator::operator++( int )
{
  nc_const_iterator tmp = *this;
  ++( *this );
  return tmp;
}
 
inline bool
nc_const_iterator::operator==( const nc_const_iterator& rhs ) const
{
  return part_idx_ == rhs.part_idx_ and element_idx_ == rhs.element_idx_;
}
 
inline bool
nc_const_iterator::operator!=( const nc_const_iterator& rhs ) const
{
  return not( *this == rhs );
}
 
inline bool
nc_const_iterator::operator<( const nc_const_iterator& rhs ) const
{
  return ( part_idx_ < rhs.part_idx_ or ( part_idx_ == rhs.part_idx_ and element_idx_ < rhs.element_idx_ ) );
}
 
inline bool
nc_const_iterator::operator<=( const nc_const_iterator& rhs ) const
{
  return ( *this < rhs or *this == rhs );
}
 
inline bool
nc_const_iterator::operator>( const nc_const_iterator& rhs ) const
{
  return not( *this <= rhs );
}
 
inline bool
nc_const_iterator::operator>=( const nc_const_iterator& rhs ) const
{
  return not( *this < rhs );
}
 
inline std::pair< size_t, size_t >
nc_const_iterator::get_part_offset() const
{
  return { part_idx_, element_idx_ };
}
 
inline size_t
nc_const_iterator::get_step_size() const
{
  return step_;
}
 
inline NodeCollectionPTR
operator+( NodeCollectionPTR lhs, NodeCollectionPTR rhs )
{
  return lhs->operator+( rhs );
}
 
inline size_t
NodeCollectionPrimitive::operator[]( const size_t idx ) const
{
  // throw exception if outside of NodeCollection
  if ( first_ + idx > last_ )
  {
    throw std::out_of_range( String::compose( "pos %1 points outside of the NodeCollection", idx ) );
  }
  return first_ + idx;
}
 
inline bool
NodeCollectionPrimitive::operator==( NodeCollectionPTR rhs ) const
{
  auto const* const rhs_ptr = dynamic_cast< NodeCollectionPrimitive const* >( rhs.get() );
  // Checking that rhs_ptr is valid first, to avoid segfaults. If rhs is a NodeCollectionComposite,
  // rhs_ptr will be a null pointer.
  if ( not rhs_ptr )
  {
    return false;
  }
 
  // We know we have a primitive collection, so forward
  return *this == *rhs_ptr;
}
 
inline bool
NodeCollectionPrimitive::operator==( const NodeCollectionPrimitive& rhs ) const
{
  // Not dereferencing rhs_ptr->metadata_ in the equality comparison because we want to avoid overloading
  // operator==() of *metadata_, and to let it handle typechecking.
  const bool eq_metadata =
    ( not metadata_ and not rhs.metadata_ ) or ( metadata_ and rhs.metadata_ and *metadata_ == rhs.metadata_ );
 
  return first_ == rhs.first_ and last_ == rhs.last_ and model_id_ == rhs.model_id_ and eq_metadata;
}
 
inline NodeCollection::const_iterator
NodeCollectionPrimitive::begin( NodeCollectionPTR cp ) const
{
  return nc_const_iterator( cp, *this, /* offset */ 0, /* stride */ 1 );
}
 
inline NodeCollection::const_iterator
NodeCollectionPrimitive::end( NodeCollectionPTR cp ) const
{
  // The unique end() element of a primitive NC is given by (part 0, element size()) )
  return nc_const_iterator( cp, *this, /* offset */ size(), /* stride */ 1, nc_const_iterator::NCIteratorKind::END );
}
 
inline size_t
NodeCollectionPrimitive::size() const
{
  // empty NC has first_ == last_ == 0, need to handle that special
  return std::min( last_, last_ - first_ + 1 );
}
 
inline size_t
NodeCollectionPrimitive::stride() const
{
  return 1;
}
 
inline bool
NodeCollectionPrimitive::contains( const size_t node_id ) const
{
  return first_ <= node_id and node_id <= last_;
}
 
inline void
NodeCollectionPrimitive::set_metadata( NodeCollectionMetadataPTR meta )
{
  metadata_ = meta;
}
 
inline NodeCollectionMetadataPTR
NodeCollectionPrimitive::get_metadata() const
{
  return metadata_;
}
 
inline bool
NodeCollectionPrimitive::is_range() const
{
  return true;
}
 
inline bool
NodeCollectionPrimitive::empty() const
{
  return last_ == 0;
}
 
inline long
NodeCollectionPrimitive::get_nc_index( const size_t neuron_id ) const
{
  if ( neuron_id < first_ or last_ < neuron_id )
  {
    return -1;
  }
  else
  {
    return neuron_id - first_;
  }
}
 
inline bool
NodeCollectionPrimitive::has_proxies() const
{
  return not nodes_have_no_proxies_;
}
 
inline NodeCollection::const_iterator
NodeCollectionComposite::begin( NodeCollectionPTR cp ) const
{
  return nc_const_iterator( cp, *this, first_part_, first_elem_, stride_ );
}
 
inline NodeCollection::const_iterator
NodeCollectionComposite::end( NodeCollectionPTR cp ) const
{
  // The unique end() element of a composite NC is given by one past the last element
  // This is the (potentially non-existing) next element irrespective of stride and step
  return nc_const_iterator(
    cp, *this, last_part_, last_elem_ + 1, /* stride */ 1, nc_const_iterator::NCIteratorKind::END );
}
 
inline size_t
NodeCollectionComposite::size() const
{
  return size_;
}
 
inline size_t
NodeCollectionComposite::stride() const
{
  return stride_;
}
 
inline void
NodeCollectionComposite::set_metadata( NodeCollectionMetadataPTR meta )
{
  for ( auto& part : parts_ )
  {
    part.set_metadata( meta );
  }
}
 
inline NodeCollectionMetadataPTR
NodeCollectionComposite::get_metadata() const
{
  return parts_[ 0 ].get_metadata();
}
 
inline bool
NodeCollectionComposite::is_range() const
{
  return false;
}
 
inline bool
NodeCollectionComposite::empty() const
{
  // Composite NodeCollections can never be empty.
  return false;
}
 
inline bool
NodeCollectionComposite::contains( const size_t node_id ) const
{
  return get_nc_index( node_id ) != -1;
}
 
inline bool
NodeCollectionComposite::valid_idx_( const size_t part_idx, const size_t element_idx ) const
{
  return part_idx < last_part_ or ( part_idx == last_part_ and element_idx <= last_elem_ );
}
 
}  // namespace nest
 
#endif /* #ifndef NODE_COLLECTION_H */