vgtl_helpers.h

Go to the documentation of this file.

// Helper classes implementation -*- C++ -*-

// $Id: vgtl_helpers.h 347 2008-02-06 15:20:01Z schilly $
// Copyright (C) 2001-2003 Hermann Schichl
//
// This file is part of the Vienna Graph Template Library.  This library
// is free software; you can redistribute it and/or modify it under the
// terms of the Library GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library 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
// Library GNU General Public License for more details.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the Library GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the Library GNU General Public License.

#ifndef _VGTL_HELPERS_H_
#define _VGTL_HELPERS_H_

#include <vgtl_config.h>

__VGTL_BEGIN_NAMESPACE

template <class _BidirIter, class _Tp>
inline _BidirIter rfind(_BidirIter __first, _BidirIter __last,
                        const _Tp& __val,
                        std::bidirectional_iterator_tag)
{
  _BidirIter __c(__last);
  --__c;
  while (__c != __first && *__c != __val)
    --__c;
  if(__c == __first && *__c != __val)
    __c = __last;
  return __c;
}

template <class _BidirIter, class _Predicate>
inline _BidirIter rfind_if(_BidirIter __first, _BidirIter __last,
                           _Predicate __pred,
                           std::bidirectional_iterator_tag)
{
  _BidirIter __c(__last);
  --__c;
  while (__c != __first && !__pred(*__c))
    --__c;
  if(__c == __first && *__pred(*__c))
    __c = __last;
  return __c;
}

#ifdef __VGTL_CLASS_PARTIAL_SPECIALIZATION

template <class _RandomAccessIter, class _Tp>
_RandomAccessIter rfind(_RandomAccessIter __first, _RandomAccessIter __last,
                        const _Tp& __val,
                        std::random_access_iterator_tag)
{
  typename std::iterator_traits<_RandomAccessIter>::difference_type __trip_count
    = ((__last - __first)-1) >> 2;
  _RandomAccessIter __c(__last);
  --__c;

  for ( ; __trip_count > 0 ; --__trip_count) {
    if (*__c == __val) return __c;
    --__c;

    if (*__c == __val) return __c;
    --__c;

    if (*__c == __val) return __c;
    --__c;

    if (*__c == __val) return __c;
    --__c;
  }

  switch(__c - __first) {
  case 3:
    if (*__c == __val) return __c;
    --__c;
  case 2:
    if (*__c == __val) return __c;
    --__c;
  case 1:
    if (*__c == __val) return __c;
    --__c;
  case 0:
    if(*__c == __val)
      return __c;
    else
      return __last;
  default:
    return __last;
  }
}

template <class _RandomAccessIter, class _Predicate>
_RandomAccessIter rfind_if(_RandomAccessIter __first, _RandomAccessIter __last,
                           _Predicate __pred,
                           std::random_access_iterator_tag)
{
  typename std::iterator_traits<_RandomAccessIter>::difference_type __trip_count
    = (__last - __first) >> 2;
  _RandomAccessIter __c(__last);
  --__c;

  for ( ; __trip_count > 0 ; --__trip_count) {
    if (__pred(*__c)) return __c;
    --__c;

    if (__pred(*__c)) return __c;
    --__c;

    if (__pred(*__c)) return __c;
    --__c;

    if (__pred(*__c)) return __c;
    --__c;
  }

  switch(__c - __first) {
  case 3:
    if (__pred(*__c)) return __c;
    --__c;
  case 2:
    if (__pred(*__c)) return __c;
    --__c;
  case 1:
    if (__pred(*__c)) return __c;
    --__c;
  case 0:
    if(__pred(*__c))
      return __c;
    else
      return __last;
  default:
    return __last;
  }
}

#endif /* __VGTL_CLASS_PARTIAL_SPECIALIZATION */

template <class _BidirIter, class _Tp>
inline _BidirIter rfind(_BidirIter __first, _BidirIter __last,
                       const _Tp& __val)
{
  return rfind(__first, __last, __val, __ITERATOR_CATEGORY(__first));
}

template <class _BidirIter, class _Predicate>
inline _BidirIter rfind_if(_BidirIter __first, _BidirIter __last,
                          _Predicate __pred) {
  return rfind_if(__first, __last, __pred, __ITERATOR_CATEGORY(__first));
}

__VGTL_END_NAMESPACE

#endif /* _VGTL_HELPERS_H_ */

---