predicate_iterator.h

Go to the documentation of this file.

// -*- mode: c++; -*-
//
//The Biomolecule Toolkit (BTK) is a C++ library for use in the
//modeling, analysis, and design of biological macromolecules.
//Copyright (C) 2002, 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.

//@file predicate_iterator.h

#ifndef PREDICATE_ITERATOR_H
#define PREDICATE_ITERATOR_H

#include "boost/shared_ptr.hpp"
#include <iterator>
#include <vector>
#include <cassert>

namespace BTK {

template <class Predicate, class Iterator>  
class MatchListStrategy {
public:
  typedef typename Iterator::value_type value_type;
  typedef value_type & reference;
  typedef Iterator iterator_type;
  typedef Predicate predicate_type;

  MatchListStrategy(Iterator const & begin,
        Iterator const & end,
        Predicate const & pred = Predicate()) :
    _iterator(begin), _end(end), 
    _match_list(new std::vector<bool>()), _cur(0)
  {
    Iterator i(begin);

    // if the the range is empty, put a single false in
    // the match list
    if (begin == end) {
      _match_list->push_back(false);
    } else {

      // fill up the match list
      while (i != end) {
  if (pred(*i++)) 
    _match_list->push_back(true);
  else
    _match_list->push_back(false);
      }
      
      // advance to the first selected element.
      if (!(*_match_list)[0]) advance();
    }
  };

  void advance() 
  {
    // only iterate over the matching elements in the tested range.
    // (no iteration past-the-end).
    while (_iterator != _end) {
      ++_cur;
      ++_iterator;
      
      if (!(*_match_list)[_cur]) continue;
      else return;
    }
  }
  
  reference dereference() const { return *_iterator; }
  const Iterator base() const { return _iterator; }

  MatchListStrategy & operator=(MatchListStrategy const & rhs) 
  {
    _iterator = rhs._iterator;
    _end = rhs._end;
    _match_list = rhs._match_list;
    _cur = rhs._cur;
  }
  
private:
  Iterator _iterator;
  Iterator _end;
  boost::shared_ptr<std::vector<bool> > _match_list;
  std::vector<bool>::size_type _cur;
};

template <class Predicate, class Iterator>
class PointerListStrategy {
public:
  typedef typename Iterator::value_type value_type;
  typedef typename Iterator::reference reference;
  typedef Iterator iterator_type;
  typedef Predicate predicate_type;

  
  PointerListStrategy(Iterator const & begin,
          Iterator const & end,
          Predicate const & pred = Predicate()) :
    _match_list(new std::vector<Iterator>()), _cur()
  {
    // fill the match list with pointers to matching elements.
    for (Iterator i(begin); i != end; ++i) {
      if (pred(*i)) {
  _match_list->push_back(i);
      }
    }

    // push the end iterator on the list, in order to guarantee
    // that the end iterator is returned during iteration.
    _match_list->push_back(end);

    _cur = _match_list->begin();
  }

  void advance() { ++_cur; }

  reference dereference() const { return **_cur; }

  Iterator base() const { return *_cur; }

  PointerListStrategy & operator=(PointerListStrategy const & rhs)
  {
    _match_list = rhs._match_list;
    _cur = rhs._cur;  // this is only safe because _match_list is a shared_ptr
  }

private:
  boost::shared_ptr<std::vector<Iterator> > _match_list;
  typename std::vector<Iterator>::iterator _cur;
};

template <class Predicate, class Iterator, 
    class Strategy = PointerListStrategy<Predicate,Iterator> > 
class PredicateIterator
{
 public:

  typedef std::forward_iterator_tag iterator_category;

  typedef typename std::iterator_traits<Iterator>::value_type
  value_type;

  typedef typename std::iterator_traits<Iterator>::difference_type
  difference_type;

  typedef typename std::iterator_traits<Iterator>::pointer
  pointer;

  typedef typename std::iterator_traits<Iterator>::reference
  reference;

  typedef PredicateIterator<Predicate,Iterator,Strategy> self_type;
  typedef Iterator iterator_type;
  typedef Predicate predicate_type;
  typedef Strategy strategy_type;

  PredicateIterator(Iterator const & begin, 
        Iterator const & end,
        Predicate const & p = Predicate()) :
    _predicate(p), _strategy(begin,end,p) {}

  PredicateIterator(Iterator const & end,
        Predicate const & p = Predicate()) :
    _predicate(p), _strategy(end,end,p) {}

  inline self_type & operator++()
  {  
    _strategy.advance();
    return *this;
  } 

  inline self_type operator++(int)
  {
    self_type tmp(*this);
    _strategy.advance();
    return tmp;
  }
  
  bool inline operator==(self_type const & rhs) const
  {
    return (_strategy.base() == rhs._strategy.base());
  }

  bool inline operator!=(self_type const & rhs) const
  {
    return (_strategy.base() != rhs._strategy.base());
  }

  bool inline operator==(Iterator const & rhs) const
  {
    return _strategy.base() == rhs;
  }

  bool inline operator!=(Iterator const & rhs) const
  {
    return _strategy.base() != rhs;
  }

  friend bool operator==(Iterator const & lhs,
       self_type const & rhs) 
  {
    return (lhs == rhs._iterator);
  }

  friend bool operator!=(Iterator const & lhs,
       self_type const & rhs)
  {
    return (lhs != rhs._iterator);
  }

  inline reference operator*() const
  {
    return _strategy.dereference();
  }

  inline pointer operator->() const
  {
    // this is unintuitive, i know, but it has to be
    // done this way to ensure that a pointer is returned,
    // and not some iterator-intermediate thing.
    return &(_strategy.dereference());
  }

  inline self_type & operator=(self_type const & rhs) 
  {
    _predicate = rhs._predicate;
    _strategy = rhs._strategy;
    return *this;
  }

 private:
  Predicate _predicate;
  Strategy _strategy;
};

template <class Predicate, class Iterator>
inline PredicateIterator<Predicate,Iterator> 
make_predicate_iterator(Iterator const & begin,
      Iterator const & end,
      Predicate const & p) 
{
  return PredicateIterator<Predicate,Iterator>(begin,end,p);
}

template <class Predicate, class Iterator>
inline PredicateIterator<Predicate,Iterator>
make_predicate_iterator(Iterator const & end,
      Predicate const & p)
{
  return PredicateIterator<Predicate,Iterator>(end,p);
}

}; // namespace BTK

#endif // PREDICATE_ITERATOR_H

---