find_iterators.hpp

linux下编程用 编译软件

// -*- C++ -*-

// Copyright (C) 2005 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library 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, 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
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// 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 GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice and
// this permission notice appear in supporting documentation. None of
// the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied warranty.

/**
 * @file find_iterators.hpp
 * Contains an implementation class for bin_search_tree_.
 */

#define PB_ASSOC_CONST_IT_C_DEC \
	const_it_< \
		Is_Forward_Iterator>

#define PB_ASSOC_CONST_ODIR_IT_C_DEC \
	const_it_< \
		!Is_Forward_Iterator>

#define PB_ASSOC_IT_C_DEC \
	it_< \
		Is_Forward_Iterator>

#define PB_ASSOC_ODIR_IT_C_DEC \
	it_< \
		!Is_Forward_Iterator>

template<bool Is_Forward_Iterator>
class const_it_
{

public:

  typedef std::bidirectional_iterator_tag iterator_category;

  typedef typename Allocator::difference_type difference_type;

  typedef mapped_value_type value_type;

  typedef mapped_pointer pointer;

  typedef const_mapped_pointer const_pointer;

  typedef mapped_reference reference;

  typedef const_mapped_reference const_reference;

public:

  inline
  const_it_(const node_pointer p_nd = NULL) : m_p_nd(const_cast<node_pointer>(p_nd))
  { }

  inline
  const_it_(const PB_ASSOC_CONST_ODIR_IT_C_DEC& 
	    r_other)

    : m_p_nd(r_other.m_p_nd)
  { }

  inline
  PB_ASSOC_CONST_IT_C_DEC& 
  operator=(const PB_ASSOC_CONST_IT_C_DEC& 
	    r_other)
  {
    m_p_nd = r_other.m_p_nd;

    return (*this);
  }

  inline
  PB_ASSOC_CONST_IT_C_DEC& 
  operator=(const PB_ASSOC_CONST_ODIR_IT_C_DEC& 
	    r_other)
  {
    m_p_nd = r_other.m_p_nd;

    return (*this);
  }

  inline const_pointer
  operator->() const
  {
    PB_ASSOC_DBG_ASSERT(m_p_nd != NULL);

    return (&m_p_nd->m_value);
  }

  inline const_reference
  operator*() const
  {
    PB_ASSOC_DBG_ASSERT(m_p_nd != NULL);

    return (m_p_nd->m_value);
  }

  inline bool
  operator==(const PB_ASSOC_CONST_IT_C_DEC
	     &r_other) const
  {
    return (m_p_nd == r_other.m_p_nd);
  }

  inline bool
  operator==(const PB_ASSOC_CONST_ODIR_IT_C_DEC
	     &r_other) const
  {
    return (m_p_nd == r_other.m_p_nd);
  }

  inline bool
  operator!=(const PB_ASSOC_CONST_IT_C_DEC& 
	     r_other) const
  {
    return (m_p_nd != r_other.m_p_nd);
  }

  inline bool
  operator!=(const PB_ASSOC_CONST_ODIR_IT_C_DEC& 
	     r_other) const
  {
    return (m_p_nd != r_other.m_p_nd);
  }

  inline PB_ASSOC_CONST_IT_C_DEC& 
  operator++()
  {
    PB_ASSOC_DBG_ASSERT(m_p_nd != NULL);

    inc(int_to_type<Is_Forward_Iterator>());

    return (*this);
  }

  inline PB_ASSOC_CONST_IT_C_DEC
  operator++(int)
  {
    PB_ASSOC_CONST_IT_C_DEC
      ret_it(m_p_nd);

    operator++();

    return (ret_it);
  }

  inline PB_ASSOC_CONST_IT_C_DEC& 
  operator--()
  {
    dec(int_to_type<Is_Forward_Iterator>());

    return (*this);
  }

  inline PB_ASSOC_CONST_IT_C_DEC
  operator--(int)
  {
    PB_ASSOC_CONST_IT_C_DEC
      ret_it(m_p_nd);

    operator--();

    return (ret_it);
  }

protected:
  inline void
  inc(int_to_type<false>)
  {
    dec(int_to_type<true>());
  }

  void
  inc(int_to_type<true>)
  {
    if (m_p_nd->m_p_right != NULL)
      {
	m_p_nd = m_p_nd->m_p_right;

	while (m_p_nd->m_p_left != NULL)
	  m_p_nd = m_p_nd->m_p_left;

	return;
      }

    node_pointer p_y = m_p_nd->m_p_parent;

    while (m_p_nd == p_y->m_p_right)
      {
	m_p_nd = p_y;

	p_y = p_y->m_p_parent;
      }

    if (m_p_nd->m_p_right != p_y)
      m_p_nd = p_y;
  }

  inline void
  dec(int_to_type<false>)
  {
    inc(int_to_type<true>());
  }

  void
  dec(int_to_type<true>)
  {
    if (m_p_nd->special_dec_check()&& 
	m_p_nd->m_p_parent->m_p_parent == m_p_nd)
      {
	m_p_nd = m_p_nd->m_p_right;

	return;
      }

    if (m_p_nd->m_p_left != NULL)
      {
	node_pointer p_y = m_p_nd->m_p_left;

	while (p_y->m_p_right != NULL)
	  p_y = p_y->m_p_right;

	m_p_nd = p_y;

	return;
      }

    node_pointer p_y = m_p_nd->m_p_parent;

    while (m_p_nd == p_y->m_p_left)
      {
	m_p_nd = p_y;

	p_y = p_y->m_p_parent;
      }

    /*
     * This seems to correct an apparent bug in the SGI STL
     * implementation. */
    if (m_p_nd->m_p_left != p_y)
      m_p_nd = p_y;
  }

  friend class PB_ASSOC_CLASS_C_DEC;

public:
  node_pointer m_p_nd;
};

template<bool Is_Forward_Iterator>
class it_ : 
  public PB_ASSOC_CONST_IT_C_DEC

{

public:

  inline
  it_(const node_pointer p_nd = NULL) : PB_ASSOC_CONST_IT_C_DEC((node_pointer)p_nd)
  { }

  inline
  it_(const PB_ASSOC_ODIR_IT_C_DEC& 
      r_other)

    : PB_ASSOC_CONST_IT_C_DEC(
			      r_other.m_p_nd)
  { }

  inline
  PB_ASSOC_IT_C_DEC& 
  operator=(const PB_ASSOC_IT_C_DEC& 
	    r_other)
  {
    my_base_it::m_p_nd = r_other.m_p_nd;

    return (*this);
  }

  inline
  PB_ASSOC_IT_C_DEC& 
  operator=(const PB_ASSOC_ODIR_IT_C_DEC& 
	    r_other)
  {
    my_base_it::m_p_nd = r_other.m_p_nd;

    return (*this);
  }

  inline pointer
  operator->()
  {
    PB_ASSOC_DBG_ASSERT(my_base_it::m_p_nd != NULL);

    return (&my_base_it::m_p_nd->m_value);
  }

  inline reference
  operator*()
  {
    PB_ASSOC_DBG_ASSERT(my_base_it::m_p_nd != NULL);

    return (my_base_it::m_p_nd->m_value);
  }

  inline PB_ASSOC_IT_C_DEC& 
  operator++()
  {
    PB_ASSOC_CONST_IT_C_DEC::
      operator++();

    return (*this);
  }

  inline PB_ASSOC_IT_C_DEC
  operator++(int)
  {
    PB_ASSOC_IT_C_DEC
      ret_it(my_base_it::m_p_nd);

    operator++();

    return (ret_it);
  }

  inline PB_ASSOC_IT_C_DEC& 
  operator--()
  {
    PB_ASSOC_CONST_IT_C_DEC::
      operator--();

    return (*this);
  }

  inline PB_ASSOC_IT_C_DEC
  operator--(int)
  {
    PB_ASSOC_IT_C_DEC
      ret_it(my_base_it::m_p_nd);

    operator--();

    return (ret_it);
  }

protected:
  typedef PB_ASSOC_CONST_IT_C_DEC my_base_it;

  friend class PB_ASSOC_CLASS_C_DEC;
};

#undef PB_ASSOC_CONST_IT_C_DEC

#undef PB_ASSOC_CONST_ODIR_IT_C_DEC

#undef PB_ASSOC_IT_C_DEC

#undef PB_ASSOC_ODIR_IT_C_DEC