open_hash.h

很多二维 三维几何计算算法 C++ 类库

// Copyright (c) 2005  Tel-Aviv University (Israel).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/Arrangement_2/include/CGAL/Arrangement_2/Open_hash.h $
// $Id: Open_hash.h 28567 2006-02-16 14:30:13Z lsaboret $
// 
//
// Author(s)     : Ron Wein          <[e-mail]>
#ifndef CGAL_OPEN_HASH_H
#define CGAL_OPEN_HASH_H

/*! \file
 * Definition of the Open_hash and the Hash_map class-templates.
 */

#include <vector>
#include <list>

CGAL_BEGIN_NAMESPACE

/*! \class
 * A default equality functor.
 * The parameter Type must support the equality operator. 
 */
template <class Type>
class Default_is_equal_functor
{
public:

  bool operator() (const Type& t1, const Type& t2) const
  {
    return (t1 == t2);
  }
};

/*! \class
 * An implementation of an open-addressing hash.
 */
template <class Key_,
          class Hash_functor_,
          class EqualKey_ = Default_is_equal_functor<Key_> >
class Open_hash
{
public:

  // Type definitions (for STL compatibility):
  typedef Key_               value_type;
  typedef Key_               key_type;
  typedef Hash_functor_      hasher;
  typedef EqualKey_          key_equal;
  typedef value_type*        pointer;
  typedef value_type&        reference;
  typedef const value_type*  const_pointer;
  typedef const value_type&  const_reference;
  typedef size_t             size_type;
  typedef size_t             difference_type;

protected:

  enum
  {
    DEFAULT_NUMBER_OF_BUCKETS = 1000
  };

  typedef std::list<Key_>                  Bucket;
  typedef typename Bucket::iterator        Bucket_iterator;
  typedef typename Bucket::const_iterator  Bucket_const_iterator;
  
  size_type            n_buckets;   // Number of buckets in the hash.
  size_type            n_objects;   // Number of objects stored in the hash.
  std::vector<Bucket>  buckets;     // The buckets (linked lists of objects).
  hasher               hash_func;   // The hashing functor.
  key_equal            equal_func;  // The equality functor.

private:

  // Copy constructor and assignment operator - not supported.
  Open_hash (const Open_hash& );
  Open_hash& operator= (const Open_hash& );

public:

  /// \name Construction and destruction methods.
  //@{

  /*! Default constructor. */
  Open_hash () :
    n_objects (0),
    buckets (DEFAULT_NUMBER_OF_BUCKETS),
    hash_func (),
    equal_func ()
  {
    n_buckets = buckets.size();
  }

  /*! Constructor with an initial number of buckets. */
  Open_hash (size_type n,
             hasher hash_f = hasher(),
             key_equal equal_f = key_equal()) :
    n_objects (0),
    buckets (n),
    hash_func (hash_f),
    equal_func (equal_f)
  {
    n_buckets = buckets.size();
  }

  /*! Destructor. */
  virtual ~Open_hash ()
  {}
  //@}

  /// \number Access the hash properties.
  //@{

  /*! Get the number of buckets in the hash. */
  size_type bucket_count () const
  {
    return (n_buckets);
  }

  /*! Get the number of objects stored in the hash. */
  size_type size () const
  {
    return (n_objects);
  }

  /*! Check whether the hash is empty. */
  bool empty () const
  {
    return (n_objects == 0);
  }

  /*! Get the hasher object used by the hash. */ 
  const hasher& hash_funct () const
  {
    return (hash_func);
  }

  /*! Get the key_equal object used by the hash. */
  const key_equal& key_eq () const
  {
    return (equal_func);
  }
  //@}

  /*! \class
   * An iterator for the open-addressing hash.
   */
  class iterator
  {
    friend class Open_hash<Key_, Hash_functor_, EqualKey_>;

  private:
  
    Open_hash<Key_, Hash_functor_, EqualKey_>  *p_hash;  // The scanned hash.
    int                           index;  // The index of the current bucket.
    Bucket_iterator               iter;   // Iterator for the current bucket.

    /*! Private constructor. */
    iterator (const Open_hash<Key_, Hash_functor_, EqualKey_>& hash,
              size_type ind) :
      p_hash (const_cast<Open_hash<Key_,Hash_functor_,EqualKey_>* >(&hash))
    {
      // Find the next non-empty bucket and get an iterator for it.
      index = p_hash->_next_non_empty_bucket (static_cast<int> (ind));

      if (index < static_cast<int>(p_hash->n_buckets))
        iter = (p_hash->buckets[index]).begin();
    }

    /*! Private constructor. */
    iterator (const Open_hash<Key_, Hash_functor_, EqualKey_>& hash,
              size_type ind,
              Bucket_iterator it) :
      p_hash (const_cast<Open_hash<Key_,Hash_functor_,EqualKey_>* >(&hash)),
      index (static_cast<int> (ind)),
      iter (it)
    {}

  public:

    /*! Default constructor. */
    iterator () :
      p_hash (NULL),
      index (0)
    {}

    /*! Equality operator. */
    bool operator== (const iterator& it)
    {
      if (p_hash != it.p_hash)
        return (false);
      
      if (p_hash == NULL)
        return (true);

      if ((index < 0 || index >= static_cast<int>(p_hash->n_buckets)) &&
          (it.index < 0 || it.index >= static_cast<int>(p_hash->n_buckets)))
        return (true);

      return (index == it.index && iter == it.iter);
    }

    /*! Inequality operator. */
    bool operator!= (const iterator& it)
    {
      return (! (*this == it));
    }

    /*! Get the current object the iterator points on. */
    const_reference operator* () const
    {
      CGAL_precondition (p_hash != NULL &&
                         index >= 0 && index < static_cast<int>(p_hash->n_buckets));

      return (*iter);
    }

    /*! Get a pointer for the current object the iterator points on. */
    const_pointer operator-> () const
    {
      CGAL_precondition (p_hash != NULL &&
                         index >= 0 && index < static_cast<int>(p_hash->n_buckets));

      return (&(*iter));
    }

    /* Increment the iterator (prefix notation). */
    iterator& operator++ ()
    {
      // Check end conditions.
      CGAL_precondition (p_hash != NULL);

      if (index >= static_cast<int>(p_hash->n_buckets))
        return (*this);

      if (index < 0)
      {
        // Find the first non-empty bucket and get an iterator for it.
        index = p_hash->_next_non_empty_bucket (0);

        if (index < static_cast<int>(p_hash->n_buckets))
          iter = (p_hash->buckets[index]).begin();

        return (*this);
      }
      
      // Try to increment the current list iterator.
      ++iter;

      if (iter == (p_hash->buckets[index]).end())
      {
        // Find the next non-empty bucket and get an iterator for it.
        index = p_hash->_next_non_empty_bucket (index + 1);

        if (index < static_cast<int>(p_hash->n_buckets))
          iter = (p_hash->buckets[index]).begin();
      }
        
      return (*this);
    }

    /* Increment the iterator (postfix notation). */
    iterator operator++ (int )
    {
      iterator   temp = *this;

      ++(*this);
      return (temp);
    }

    /* Decrement the iterator (prefix notation). */
    iterator& operator-- ()
    {
      // Check end conditions.
      CGAL_precondition (p_hash != NULL);

      if (index >= static_cast<int>(p_hash->n_buckets))
      {
        // Find the last non-empty bucket and get an iterator for it.
        index = p_hash->_prev_non_empty_bucket 
                           (static_cast<int>(p_hash->n_buckets) - 1);

        if (index >= 0)
        {
          iter = (p_hash->buckets[index]).end();
          --iter;
        }

        return (*this);
      }

      if (index < 0)
        return (*this);
      
      // Try to decrement the current list iterator.
      if (iter != (p_hash->buckets[index]).begin())
      {
        --iter;
      }
      else
      {
        // Find the nprevious non-empty bucket and get an iterator for it.
        index = p_hash->_prev_non_empty_bucket (index - 1);

        if (index >= 0)
        {
          iter = (p_hash->buckets[index]).end();
          --iter;
        }
      }
        
      return (*this);
    }

    /* Decrement the iterator (postfix notation). */
    iterator operator-- (int )
    {
      iterator   temp = *this;

      --(*this);
      return (temp);
    }

  };

  friend class iterator;

  /// \name Scan the objects in the hash.
  //@{

  /*! Get an iterator for the first object in the hash. */
  iterator begin () const
  {
    return (iterator (*this, 0));
  }

  /*! Get a past-the end iterator for the objects. */
  iterator end () const
  {
    return (iterator (*this, n_buckets));
  }

  //@}

  /// \name Hash operations.
  //@{

  /*!
   * Check if an object with the given key exists in the map.
   * \param ket The key to look for.
   * \return An iterator for an objects having the given key,
   *         or a past-the-end iterator if no such object was found.
   */
  iterator find (const key_type& key) const
  {
    // Look for the object in the approriate bucket.
    const size_type           index = hash_func (key) % n_buckets;
    Bucket&                   my_bucket = const_cast<Bucket&>(buckets[index]);
    Bucket_iterator           bucket_it = _find_in_bucket (index, key);

    if (bucket_it == my_bucket.end())
      // The object was not found.
      return (end());

    // Create an iterator pointing to the object.
    return (iterator (*this, index, bucket_it));
  }

  /*!
   * Insert an object into the hash.
   * \param val The object to insert.
   * \return A pair comprised of an iterator for the inserted object,
   *         and a flag indicating whether the insertion tool place
   *         (false if the object had already existed in the hash).
   */
  std::pair<iterator,bool> insert (const value_type& val)
  {
    // Look for the object in the approriate bucket.
    const size_type           index = hash_func (val) % n_buckets;
    Bucket_iterator           bucket_it = _find_in_bucket (index, val);
    std::pair<iterator,bool>  res;

    // Check if the object already exists.
    if (bucket_it != buckets[index].end())
    {
      // In case the object already exists:
      res.first = iterator (*this, index, bucket_it);
      res.second = false;
    }
    else