open_hash.h

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

    {
      // Insert a new object to the approriate bucket.
      buckets[index].push_front (val);

      n_objects++;

      res.first = iterator (*this, index, buckets[index].begin());
      res.second = true;
    }
      
    return (res);
  }

  /*!
   * Erase an object given an iterator pointing to it.
   * \param pos An iterator pointing at the object to be erased.
   */
  void erase (iterator pos)
  {
    // Erase the object from the approriate bucket.
    CGAL_precondition (pos.p_hash == this);

    const int        index = pos.index;
    Bucket_iterator  bucket_it = pos.iter;

    CGAL_assertion (index >= 0 && index < static_cast<int>(n_buckets));
    
    buckets[index].erase (bucket_it);
    n_objects--;

    return;
  }

  /*!
   * Erase an object with the given key.
   * \param key The key to delete.
   * \return Whether an object has been found and erased.
   */
  bool erase (const key_type& key)
  {
    // Look for the object in the approriate bucket.
    const size_type           index = hash_func (key) % n_buckets;
    Bucket_iterator           bucket_it = _find_in_bucket (index, key);

    if (bucket_it == buckets[index].end())
      // The object was not found.
      return (false);

    // Erase the object from the approriate bucket.
    buckets[index].erase (bucket_it);
    n_objects--;

    return (true);
  }

  /*!
   * Clear the contents of the hash.
   */
  void clear ()
  {
    // Clear all buckets.
    typename std::vector<Bucket>::iterator  it;

    for (it = buckets.begin(); it != buckets.end(); ++it)
      (*it).clear();

    n_objects = 0;
    return;
  }
  //@}

  /// \name Re-arranging the hash structure.
  //@{

  /*!
   * Resize the hash (takes time proporsional to the number of objects
   * stored in the hash).
   * \param n The new number of buckets.
   */
  void resize (size_type n)
  {
    rehash (n, hash_func);
  };

  /*! Rehash the structure.
   * \param n The new number of buckets.
   * \param hash_f The new hashing functor.
   */
  void rehash (size_type n, hasher hash_f)
  {
    // Set the hashing functor.
    hash_func = hash_f;

    // Rehash the structure.
    std::vector<Bucket>                     new_buckets (n);
    typename std::vector<Bucket>::iterator  it;
    Bucket_iterator                         bucket_it;
    size_type                               index;

    for (it = buckets.begin(); it != buckets.end(); ++it)
    {
      for (bucket_it = (*it).begin(); bucket_it != (*it).end(); ++bucket_it)
      {
        const value_type&  val = *bucket_it;
        
        index = hash_func (val) % n;
        new_buckets[index].push_back (val);
      }
    }

    // Set the new buckets.
    buckets = new_buckets;
    n_buckets = n;

    return;
  }
  //@}

private:

  /*! Get the index of the previous non-empty bucket. */
  int _prev_non_empty_bucket (int index) const
  {
    while (index >= 0 && buckets[index].empty())
      index--;

    return (index);
  }

  /*! Get the index of the next non-empty bucket. */
  int _next_non_empty_bucket (int index) const
  {
    while (index < static_cast<int>(n_buckets) && buckets[index].empty())
      index++;

    return (index);
  }

  /*! Find the given object in the given bucket. */
  Bucket_iterator _find_in_bucket (int index,
                                   const value_type& val) const
  {
    Bucket&             my_bucket = const_cast<Bucket&>(buckets[index]);
    Bucket_iterator     iter = my_bucket.begin();

    while (iter != my_bucket.end() && ! equal_func (val, *iter))
      ++iter;

    return (iter);
  }
};

/*! \class
 * An implementation of a hash-based map.
 */
template <class Key_, class Data_,
          class Hash_functor_,
          class EqualKey_ = Default_is_equal_functor<Key_> >
class Hash_map
{
public:

  // Type definitions (for STL compatibility):
  typedef Key_                   key_type;
  typedef Data_                  data_type;
  typedef std::pair<Key_,Data_>  value_type;
  typedef Hash_functor_          hasher;
  typedef EqualKey_              key_equal;
  typedef value_type*            pointer;
  typedef value_type&            reference;
  typedef const value_type&      const_reference;
  typedef size_t                 size_type;
  typedef size_t                 difference_type;

protected:

  /*! \class
   * A functor for the value_type pair.
   */
  class Value_type_hash_functor
  {
  private:

    Hash_functor_       hash_func;

  public:

    Value_type_hash_functor () :
      hash_func ()
    {}

    Value_type_hash_functor (Hash_functor_ func) :
      hash_func (func)
    {}

    size_type operator() (const value_type& vt) const
    {
      return (hash_func (vt.first));
    }
  };

  /*! \class
   * A functor for comparing value_type pairs.
   */
  class Value_type_equal
  {
  private:

    EqualKey_          equal_func;

  public:

    Value_type_equal () :
      equal_func ()
    {}

    Value_type_equal (EqualKey_ func) :
      equal_func (func)
    {}

    bool operator() (const value_type& vt1, const value_type& vt2) const
    {
      return (equal_func (vt1.first, vt2.first));
    }
  };

  typedef Open_hash<value_type, 
                    Value_type_hash_functor, Value_type_equal>    Hash;

  Value_type_hash_functor            vt_hash_func;
  Value_type_equal                   vt_equal_func;
  Hash                               hash;

public:

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

  /*! Default constructor. */
  Hash_map () :
    vt_hash_func (hasher()),
    vt_equal_func (key_equal()),
    hash ()
  {}

  /*! Constructor with an initial number of buckets. */
  Hash_map (size_type n,
            hasher hash_f = hasher(),
            key_equal equal_f = key_equal()) :
    vt_hash_func (hash_f),
    vt_equal_func (equal_f),
    hash (n, vt_hash_func, vt_equal_func)
  {}

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

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

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

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

  /*! Check whether the hash map is empty. */
  bool empty () const
  {
    return (hash.empty());
  }
  //@}

  typedef typename Hash::iterator    iterator;

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

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

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

  //@}

  /// \name Hash-map 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
  {
    value_type    vt (key, data_type());
    return (hash.find (vt));
  }

  /*!
   * Returns a reference to the object that is associated with the given key.
   * If the hash map does not contain such an object, it inserts an entry
   * corresponding to the given key.
   * \param key The key.
   * \return The data associated with this key.
   */
  data_type& operator[] (const key_type& key)
  {
    value_type                  vt (key, data_type());
    std::pair<iterator, bool>   res = hash.insert (vt);

    return (const_cast<data_type&> ((*(res.first)).second));
  }

  /*!
   * 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)
  {
    return (hash.insert (val));
  }

  /*!
   * Erase an object given an iterator pointing to it.
   * \param pos An iterator pointing at the object to be erased.
   */
  void erase (iterator pos)
  {
    hash.erase (pos);
    return;
  }

  /*!
   * Erase an object with the given key.
   * \param key The key to delete.
   * \return Whether an object has been found and erased.
   */
  bool erase (const key_type& key)
  {
    value_type    vt (key, data_type());
    return (hash.erase (vt));
  }

  /*!
   * Clear the contents of the hash map.
   */
  void clear ()
  {
    hash.clear();
  }
  //@}

  /// \name Re-arranging the hash structure.
  //@{

  /*!
   * Resize the hash map (takes time proporsional to the number of objects
   * stored in the hash).
   * \param n The new number of buckets.
   */
  void resize (size_type n)
  {
    hash.resize (n);
  };

  /*! Rehash the structure.
   * \param n The new number of buckets.
   * \param hash_f The new hashing functor.
   */
  void rehash (size_type n, hasher hash_f)
  {
    vt_hash_func = Value_type_hash_functor (hash_f);
    hash.rehash (n, vt_hash_func);
  }
  //@}

};

CGAL_END_NAMESPACE

#endif