SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Arrangement_2/Open_hash.h

Go to the documentation of this file.

// 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.5-branch/Arrangement_on_surface_2/include/CGAL/Arrangement_2/Open_hash.h $
// $Id: Open_hash.h 33290 2006-08-14 06:28:19Z wein $
// 
//
// Author(s)     : Ron Wein          <wein@post.tau.ac.il>
#ifndef CGAL_OPEN_HASH_H
#define CGAL_OPEN_HASH_H

#include <vector>
#include <list>

CGAL_BEGIN_NAMESPACE

template <class Type>
class Default_is_equal_functor
{
public:

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

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:



  Open_hash () :
    n_objects (0),
    buckets (DEFAULT_NUMBER_OF_BUCKETS),
    hash_func (),
    equal_func ()
  {
    n_buckets = buckets.size();
  }

  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();
  }

  virtual ~Open_hash ()
  {}



  size_type bucket_count () const
  {
    return (n_buckets);
  }

  size_type size () const
  {
    return (n_objects);
  }

  bool empty () const
  {
    return (n_objects == 0);
  }

  const hasher& hash_funct () const
  {
    return (hash_func);
  }

  const key_equal& key_eq () const
  {
    return (equal_func);
  }

  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.

    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();
    }

    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:

    iterator () :
      p_hash (NULL),
      index (0)
    {}

    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);
    }

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

    const_reference operator* () const
    {
      CGAL_precondition (p_hash != NULL &&
                         index >= 0 && index < static_cast<int>(p_hash->n_buckets));

      return (*iter);
    }

    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;



  iterator begin () const
  {
    return (iterator (*this, 0));
  }

  iterator end () const
  {
    return (iterator (*this, n_buckets));
  }




  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));
  }

  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
    {
      // 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);
  }

  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;
  }

  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);
  }

  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;
  }



  void resize (size_type n)
  {
    rehash (n, hash_func);
  };

  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:

  int _prev_non_empty_bucket (int index) const
  {
    while (index >= 0 && buckets[index].empty())
      index--;

    return (index);
  }

  int _next_non_empty_bucket (int index) const
  {
    while (index < static_cast<int>(n_buckets) && buckets[index].empty())
      index++;

    return (index);
  }

  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);
  }
};

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 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 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:



  Hash_map () :
    vt_hash_func (hasher()),
    vt_equal_func (key_equal()),
    hash ()
  {}

  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)
  {}

  virtual ~Hash_map ()
  {}



  size_type bucket_count () const
  {
    return (hash.bucket_count());
  }

  size_type size () const
  {
    return (hash.size());
  }

  bool empty () const
  {
    return (hash.empty());
  }

  typedef typename Hash::iterator    iterator;



  iterator begin () const
  {
    return (hash.begin());
  }

  iterator end () const
  {
    return (hash.end());
  }




  iterator find (const key_type& key) const
  {
    value_type    vt (key, data_type());
    return (hash.find (vt));
  }

  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));
  }

  std::pair<iterator,bool> insert (const value_type& val)
  {
    return (hash.insert (val));
  }

  void erase (iterator pos)
  {
    hash.erase (pos);
    return;
  }

  bool erase (const key_type& key)
  {
    value_type    vt (key, data_type());
    return (hash.erase (vt));
  }

  void clear ()
  {
    hash.clear();
  }



  void resize (size_type n)
  {
    hash.resize (n);
  };

  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