mstl_iterator.hpp

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

/*
The young Library
Copyright (c) 2005 by 杨桓

Permission to use, copy, modify, distribute and sell this software for any
purpose is hereby granted without fee, provided that the above copyright
notice appear in all copies and that both that copyright notice and this
permission notice appear in supporting documentation.
The author make no representations about the suitability of this software
for any purpose. It is provided "as is" without express or implied warranty.
*/

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_MINI_STL_ITERATOR_HEADER_FILE__
#define __MACRO_CPLUSPLUS_MINI_STL_ITERATOR_HEADER_FILE__
//-----------------------------------------------------------------------------
#include <iterator>
#include "mstl_define.hpp"
#include "mstl_pair.hpp"
#include "mstl_type_traits.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

/*
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag,
                              public output_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};
*/

typedef  std::input_iterator_tag          input_iterator_tag;
typedef  std::output_iterator_tag         output_iterator_tag;
typedef  std::forward_iterator_tag        forward_iterator_tag;
typedef  std::bidirectional_iterator_tag  bidirectional_iterator_tag;
typedef  std::random_access_iterator_tag  random_access_iterator_tag;

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename Iterator >
struct iterator_traits
{
    typedef  false_type  is_pointer;
    typedef  typename Iterator::iterator_category  iterator_category;
    typedef  typename Iterator::value_type         value_type;
    typedef  typename Iterator::reference          reference;
    typedef  typename Iterator::pointer            pointer;
    typedef  typename Iterator::size_type          size_type;
    typedef  typename Iterator::difference_type    difference_type;
};

template< typename T >
struct iterator_traits<T*>
{
    typedef  true_type  is_pointer;
    typedef  random_access_iterator_tag  iterator_category;
    typedef  T                           value_type;
    typedef  value_type&                 reference;
    typedef  value_type*                 pointer;
    typedef  def_size_t                  size_type;
    typedef  def_ptrdiff_t               difference_type;
};

template< typename T >
struct iterator_traits<const T*>
{
    typedef  true_type  is_pointer;
    typedef  random_access_iterator_tag  iterator_category;
    typedef  T                           value_type;
    typedef  value_type&                 reference;
    typedef  value_type*                 pointer;
    typedef  def_size_t                  size_type;
    typedef  def_ptrdiff_t               difference_type;
};



template< typename T >
inline T* const_iter_cast( const T* cptr )
{
    return const_cast<T*>( cptr );
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

//必须是双向迭代器以上的迭代器
template< typename Iterator >
class Reverse_Iterator
{
public:
    typedef  typename iterator_traits<Iterator>::iterator_category  iterator_category;
    typedef  typename iterator_traits<Iterator>::value_type         value_type;
    typedef  typename iterator_traits<Iterator>::reference          reference;
    typedef  typename iterator_traits<Iterator>::pointer            pointer;
    typedef  typename iterator_traits<Iterator>::size_type          size_type;
    typedef  typename iterator_traits<Iterator>::difference_type    difference_type;
    typedef  const pointer    const_pointer;
    typedef  const reference  const_reference;

    typedef  Reverse_Iterator<Iterator>  self;
    typedef  Iterator                    iterator_type;

    Reverse_Iterator()  {}
    Reverse_Iterator( iterator_type it ) : current(it)  {}

    iterator_type base() const  {  return current;  }

    reference operator*() const
    {      	
    	iterator_type result = current;
    	return *(--result);
    }
    pointer operator->() const
    {
        return &( operator*() );
    }

    self& operator++()     {  --current;  return this;  }
    self& operator--()     {  ++current;  return this;  }
    self operator++(int)   {  self temp = *this;  --current;  return temp;  }
    self operator--(int)   {  self temp = *this;  ++current;  return temp;  }

    self& operator+=( difference_type n )  {  current -= n;  return *this;  }
    self& operator-=( difference_type n )  {  current += n;  return *this;  }

    self operator+( difference_type n ) const {  return self( current - n );  }
    self operator-( difference_type n ) const {  return self( current + n );  }

    reference operator[]( difference_type n ) const
    {  return *( *this + n );  }

protected:
    iterator_type current;

};  //end class



template< typename Iterator >
inline typename Reverse_Iterator<Iterator>::difference_type
operator-( const Reverse_Iterator<Iterator>& lhs, 
           const Reverse_Iterator<Iterator>& rhs )
{
    return rhs.base() - lhs.base();
}

template< typename Iterator >
inline Reverse_Iterator<Iterator>
operator+( typename Reverse_Iterator<Iterator>::difference_type n,
           const Reverse_Iterator<Iterator>& rhs )
{
    return Reverse_Iterator<Iterator>( rhs.base() - n );
}

template< typename Iterator >
inline bool operator==( const Reverse_Iterator<Iterator>& lhs,
                        const Reverse_Iterator<Iterator>& rhs )
{
    return ( lhs.base() == rhs.base() );
}

template< typename Iterator >
inline bool operator!=( const Reverse_Iterator<Iterator>& lhs,
                        const Reverse_Iterator<Iterator>& rhs )
{
    return ( lhs.base() != rhs.base() );
}

template< typename Iterator >
inline bool operator<( const Reverse_Iterator<Iterator>& lhs,
                       const Reverse_Iterator<Iterator>& rhs )
{
    return ( rhs.base() < lhs.base() );
}

template< typename Iterator >
inline bool operator>( const Reverse_Iterator<Iterator>& lhs,
                       const Reverse_Iterator<Iterator>& rhs )
{
    return ( rhs < lhs );
}

template< typename Iterator >
inline bool operator<=( const Reverse_Iterator<Iterator>& lhs,
                        const Reverse_Iterator<Iterator>& rhs )
{
    return !( rhs < lhs );
}

template< typename Iterator >
inline bool operator>=( const Reverse_Iterator<Iterator>& lhs,
                        const Reverse_Iterator<Iterator>& rhs )
{
    return !( lhs < rhs );
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename ForwardIterator >
inline typename iterator_traits<ForwardIterator>::difference_type
distance( ForwardIterator first, ForwardIterator last )
{
    typedef  typename iterator_traits<ForwardIterator>::iterator_category  cate;
    typedef  typename iterator_traits<ForwardIterator>::difference_type  diff_t;
    return distance_aux( first, last, cate() );
}

template< typename ForwardIterator >
typename iterator_traits<ForwardIterator>::difference_type
distance_aux( ForwardIterator first, ForwardIterator last,
              input_iterator_tag )
{
    typedef  typename iterator_traits<ForwardIterator>::difference_type  diff_t;

    diff_t len = 0;
    while( first != last )
    {
    	++first;
        ++len;
    }
    return len;
}

template< typename ForwardIterator >
inline typename iterator_traits<ForwardIterator>::difference_type
distance_aux( ForwardIterator first, ForwardIterator last,
              random_access_iterator_tag )
{
    return ( last - first );
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename InputIterator, typename Integer >
inline void advance( InputIterator& iter, Integer n )
{
    typedef  typename iterator_traits<InputIterator>::iterator_category  cate;
    advance_aux( iter, n, cate() );
}

template< typename InputIterator, typename Integer >
void advance_aux( InputIterator& iter, Integer n, input_iterator_tag )
{
    while( n-- )
    	++iter;
}

template< typename InputIterator, typename Integer >
void advance_aux( InputIterator& iter, Integer n, bidirectional_iterator_tag )
{
    if( n >= 0 )
    {
    	while( n-- )
    	    ++iter;
    }
    else
    {
    	while( n++ )
    	    --iter;
    }
}

template< typename InputIterator, typename Integer >
inline void advance_aux( InputIterator& iter, Integer n,
                         random_access_iterator_tag )
{
    iter += n;
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename InputIterator, typename Integer >
inline
Integer range_length( InputIterator first, InputIterator last, Integer length )
{
    typedef  typename iterator_traits<InputIterator>::iterator_category  cate;
    return range_len_aux( first, last, length, cate() );
}

template< typename InputIterator, typename Integer >
inline Integer range_len_aux( InputIterator first, InputIterator last,
                              Integer length, input_iterator_tag tag )
{
    if( length < 1 )
        length = distance_aux( first, last, tag );
    return length;
}

template< typename InputIterator, typename Integer >
inline Integer range_len_aux( InputIterator first, InputIterator last,
                              Integer length, random_access_iterator_tag )
{
    return ( last - first );
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

//返回值为最后一个有效的迭带器和区间长度
template< typename InputIterator >
inline
pair<InputIterator, typename iterator_traits<InputIterator>::difference_type>
pair_iter_len( InputIterator first, InputIterator last )
{
    typedef  typename iterator_traits<InputIterator>::iterator_category  cate;
    return iter_len_aux( first, last, cate() );
}

template< typename InputIterator >
pair<InputIterator, typename iterator_traits<InputIterator>::difference_type>
iter_len_aux( InputIterator first, InputIterator last,
              input_iterator_tag )
{
    typedef  typename iterator_traits<InputIterator>::difference_type  diff_t;

    if( first == last )
        return pair<InputIterator, diff_t>( first, 0 );

    diff_t len = 1;
    InputIterator result = first;
    ++first;
    while( first != last )
    {
    	++first;
    	++result;
        ++len;
    }
    return pair<InputIterator, diff_t>( result, len );
}

template< typename InputIterator >
pair<InputIterator, typename iterator_traits<InputIterator>::difference_type>
iter_len_aux( InputIterator first, InputIterator last,
              random_access_iterator_tag )
{
    typedef  typename iterator_traits<InputIterator>::difference_type  diff_t;

    diff_t len = last - first;
    if( len == 0 )
        return pair<InputIterator, diff_t>( first, 0 );
    else
        return pair<InputIterator, diff_t>( first + (len - 1), len );
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_END_NAMESPACE__
#endif
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------