grouped_element_iterator.hpp

Go to the documentation of this file.

// -*- mode: c++; indent-tabs-mode: nil; -*-
//
//The Biomolecule Toolkit (BTK) is a C++ library for use in the
//modeling, analysis, and design of biological macromolecules.
//Copyright (C) 2005-2006, Tim Robertson <kid50@users.sourceforge.net>
//
//This program is free software; you can redistribute it and/or modify
//it under the terms of the GNU Lesser General Public License as published
//by the Free Software Foundation; either version 2.1 of the License, or (at
//your option) any later version.
//
//This program 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
//Lesser General Public License for more details.
//
//You should have received a copy of the GNU Lesser General Public License
//along with this program; if not, write to the Free Software Foundation,
//Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.


#ifndef BTK_UTILITY_GROUPED_ELEMENT_ITERATOR_HPP
#define BTK_UTILITY_GROUPED_ELEMENT_ITERATOR_HPP

#include <boost/type_traits/is_convertible.hpp>
#include <boost/utility/enable_if.hpp>
#include <boost/iterator/iterator_facade.hpp>

#include <btk/core/common/debugging.hpp>
#include <btk/core/common/assertions.hpp>

namespace BTK {
namespace UTILITY {

template <typename GroupIterator,
          typename ElementIterator,
          typename GroupType,
          typename ElementType>
class GroupedElementIterator : public
 boost::iterator_facade<GroupedElementIterator<GroupIterator,
                                               ElementIterator,
                                               GroupType,
                                               ElementType>,
                          ElementType, boost::bidirectional_traversal_tag>
{

#ifndef DOXYGEN_SHOULD_SKIP_THIS
  // This template friend declaration is necessary to allow interoperation
  // with GroupedElementIterators that have const referent types.
  // (yes, this is the approach recommended in the docs for
  //  the boost::iterator_facade class!)
  template <typename A, typename B, typename C, typename D> 
  friend class GroupedElementIterator;

  // This is a reimplementation of std::mem_fun_ref_t, with the addition
  // of a default constructor, and debug checks for null-pointer dereferencing.
  //
  // This is necessary b/c iterators must be default constructible, and
  // it is impossible to default construct std::mem_fun_ref_t, making it
  // impossible to default construct a GroupedElementIterator when implemented
  // using std::mem_fun_ref_t.
  template <class Ret, class T>
  class dc_mem_fun_ref
  {
    typedef Ret (T::*func_ptr)();

  public:
    dc_mem_fun_ref() : func(static_cast<func_ptr>(0)) {}
    explicit dc_mem_fun_ref(func_ptr fp) : func(fp) {}
    Ret operator()(T & r) const
    {
      // If you get this error message, you are most likely trying to
      // increment/decrement an uninitialized GroupedElementIterator.
      BTK_ASSERT(func != static_cast<func_ptr>(0),
                 "Null ptr dereference in GroupedElementIterator::def_cons_mem_fun_ref");
      return (r.*func)();
    }

  private:
    func_ptr func;
  };
#endif // DOXYGEN_SHOULD_SKIP_THIS

 public:

  GroupedElementIterator()
  {
    // set sensible defaults to minimize the chance of NULL-ptr
    // dereferences if increment() or decrement() are called on
    // a default-constructed iterator.
    _cur_group = _group_container_end = _group_container_begin;
    _cur_element = _group_begin = _group_end;
  }


  GroupedElementIterator(GroupIterator begin,
                         GroupIterator end,
                         ElementIterator (GroupType::*group_begin_fun) (),
                         ElementIterator (GroupType::*group_end_fun) (),
                         bool at_end = false) :
    _cur_group(begin), _group_container_begin(begin), _group_container_end(end),
    _cur_element(), _group_begin(), _group_end(),
    _group_begin_fun(group_begin_fun),
    _group_end_fun(group_end_fun)
  {
    initialize(begin,end,at_end);
  }

  GroupedElementIterator(GroupIterator begin,
                         GroupIterator end,
                         bool at_end = false) :
    _cur_group(begin), _group_container_begin(begin), _group_container_end(end),
    _cur_element(), _group_begin(), _group_end(),
    _group_begin_fun(&GroupType::begin),
    _group_end_fun(&GroupType::end)
  {
    initialize(begin,end,at_end);
  }

  template <typename GI, typename EI, typename GT, typename ET>
  GroupedElementIterator(GroupedElementIterator<GI,EI,GT,ET> const & other,
                         ElementIterator (GroupType::*group_begin_fun) () =
                           &GroupType::begin,
                         ElementIterator (GroupType::*group_end_fun) () =
                           &GroupType::end,
                         typename boost::enable_if<
                           boost::is_convertible<GI,GroupIterator>
                         >::type * d1 = 0,
                         typename boost::enable_if<
                           boost::is_convertible<EI,ElementIterator>
                         >::type * d2 = 0,
                         typename boost::enable_if<
                           boost::is_convertible<GT,GroupType>
                         >::type * d3 = 0,
                         typename boost::enable_if<
                           boost::is_convertible<ET,ElementType>
                         >::type * d4 = 0) :
    _cur_group(other._cur_group),
    _group_container_begin(other._group_container_begin),
    _group_container_end(other._group_container_end),
    _cur_element(other._cur_element),
    _group_begin(other._group_begin),
    _group_end(other._group_end),
    _group_begin_fun(group_begin_fun),
    _group_end_fun(group_end_fun) {}

  friend std::ostream & operator<<(std::ostream & os,
                                   GroupedElementIterator<GroupIterator,
                                   ElementIterator,
                                   GroupType,
                                   ElementType> const & gei)
  {
    os << "GroupedElementIterator: " << std::endl
       << "  _cur_element: " << &*gei._cur_element << std::endl
       << "  _group_begin: " << &*gei._group_begin << std::endl
       << "  _group_end: " << &*gei._group_end << std::endl
       << "  _cur_group: " << &*gei._cur_group << std::endl
       << "  _group_container_begin: " << &*gei._group_container_begin << std::endl
       << "  _group_container_end: " << &*gei._group_container_end << std::endl;

    return os;
  }

 private:
  friend class boost::iterator_core_access;

  void initialize(GroupIterator begin,
                  GroupIterator end,
                  bool at_end)
  {
    BTK_ASSERT((begin != end),
               "Attempt to create GroupedElementIterator from 0-element range!");

    if (at_end) { // construct an "end" iterator.
      // set the current element, group begin/end to what they would be
      // had we iterated to the end-of-range.
      _cur_group = end;
      --_cur_group;
      _group_begin = _group_begin_fun(*_cur_group);
      _group_end = _group_end_fun(*_cur_group);
      _cur_element = _group_end;

      // set the current group to the true "end" group.
      _cur_group = end;
    } else { // construct a normal iterator (not at end)
      _cur_element = _group_begin_fun(*_cur_group);
      _group_begin = _cur_element;
      _group_end = _group_end_fun(*_cur_group);

      // if the current group is empty, advance to the first
      // element in a non-empty group.  This has to be done here,
      // because otherwise you can get the anomalous result of 1
      // successful increment for an empty list.
      if (_group_begin == _group_end) increment();
    }
  }

  void increment()
  {
    TRACE_OUT << "In GroupedElementIterator::increment():" << std::endl;

    // advance by 1 element
    if (_cur_element == _group_end || ++_cur_element == _group_end) {
      // advancing puts us at the end of the current group -- change groups

      TRACE_OUT << "  Advanced one element ("
                << "_cur_element=" << &*_cur_element
                << ", _group_end=" << &*_group_end
                << ")" << std::endl;

      if (_cur_group != _group_container_end &&
          ++_cur_group != _group_container_end) {
        // normal case: go to next group
        _group_begin = _group_begin_fun(*_cur_group);
        _group_end = _group_end_fun(*_cur_group);
        _cur_element = _group_begin;

        TRACE_OUT << "  Advanced one group ("
                  << "_cur_group=" <<  &*_cur_group
                  << ", _group_begin=" <<  &*_group_begin
                  << ", _group_end=" <<  &*_group_end
                  << ")" << std::endl;

        // if the new group is empty, advance again.
        if (_group_begin == _group_end) {
          TRACE_OUT << "  New group is empty! Re-calling increment()..." << std::endl;
          increment();
        }
      } else {
        // terminal case: next group (or current group) is the end
        _cur_group = _group_container_end;
        _cur_element = _group_end;

        TRACE_OUT << "  Can't move forward -- at last group ("
                  << "_cur_group=" << &*_cur_group
                  << ", _group_end=" << &*_group_end
                  << ")" << std::endl;
      }
    }
  }

  void decrement()
  {
    TRACE_OUT << "In GroupedElementIterator::decrement():" << std::endl;

    if (_cur_element == _group_begin) {
      // at the beginning of the current group.
      TRACE_OUT << "  At group beginning ("
                << "_cur_element=_group_begin="
                << &*_group_begin 
                << ", _cur_group=" << &*_cur_group 
                << ")" << std::endl;
      
      if (_cur_group != _group_container_begin) {
        // normal case: go to previous group.
        --_cur_group;
        _group_begin = _group_begin_fun(*_cur_group);
        _group_end = _group_end_fun(*_cur_group);
        
        TRACE_OUT << "  Moved one group back ("
                  << "_cur_group=" << &*_cur_group
                  << ", _group_begin=" << &*_group_begin
                  << ", _group_end=" << &*_group_end
                  << ")" << std::endl;
        
        // if new group is empty, decrement again.
        if (_group_begin == _group_end) {
          TRACE_OUT << "  New group is empty! Re-calling deccrement()..." << std::endl;
          decrement();
        } else {
          // group not empty -- go to last element in group.
          _cur_element = --(_group_end_fun(*_cur_group));
        }
      } else {
        // terminal case: previous group (or current group) is past the beginning
        _cur_group = _group_container_begin;
        _cur_element = _group_begin;

        TRACE_OUT << "  Can't move back -- at first group ("
                  << "_cur_group=" << &*_cur_group
                  << ", _group_begin=" << &*_group_begin
                  << ")" << std::endl;
      }
    } else {
      // not at beginning of current group -- OK to retreat by one element
      --_cur_element;

      // special case: current iterator is "end" iterator, and we're moving
      // it backwards.  Need to move the group iterator back by one.
      if (_cur_group == _group_container_end) --_cur_group;

      TRACE_OUT << "  Moved back one element ("
                << "_cur_element=" << &*_cur_element
                << ", _group_begin=" << &*_group_begin
                << ", _cur_group=" << &*_cur_group
                << ")" << std::endl;
    }
  }

  ElementType & dereference() const
  {
    return *_cur_element;
  }


  template <typename GI, typename EI, typename GT, typename ET>
  bool equal(GroupedElementIterator<GI,EI,GT,ET> const & rhs) const
  {
    TRACE_OUT << "In GroupedElementIterator::equal():" << std::endl
              << "  _cur_element: LHS=" << &*_cur_element
              << ", RHS=" << &*rhs._cur_element << std::endl
              << "  _cur_group: LHS=" << &*_cur_group
              << ", RHS=" << &*rhs._cur_group << std::endl;

    // "normal" equality test -- are element and group
    // iterators the same? if so, the iterator is equal.
    if (_cur_element == rhs._cur_element &&
        _cur_group == rhs._cur_group) return true;

    TRACE_OUT << "  NOT equal." << std::endl;

    return false;
  }

  GroupIterator _cur_group;
  GroupIterator _group_container_begin;
  GroupIterator _group_container_end;

  ElementIterator _cur_element;
  ElementIterator _group_begin;
  ElementIterator _group_end;

  dc_mem_fun_ref<ElementIterator,GroupType> _group_begin_fun;
  dc_mem_fun_ref<ElementIterator,GroupType> _group_end_fun;
};

} // namespace UTILITY
} // namespace BTK

#endif

---