sparse_array_n.h

mean-shift. pointer sample

/*! \file
  \verbatim
  
    Copyright (c) 2007, Sylvain Paris and Fr閐o Durand

    Permission is hereby granted, free of charge, to any person
    obtaining a copy of this software and associated documentation
    files (the "Software"), to deal in the Software without
    restriction, including without limitation the rights to use, copy,
    modify, merge, publish, distribute, sublicense, and/or sell copies
    of the Software, and to permit persons to whom the Software is
    furnished to do so, subject to the following conditions:

    The above copyright notice and this permission notice shall be
    included in all copies or substantial portions of the Software.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
    DEALINGS IN THE SOFTWARE.

  \endverbatim
*/

#ifndef __SPARSE_ARRAY_N__
#define __SPARSE_ARRAY_N__


#define STL_MAP      0
#define GNU_HASH_MAP 1

#ifndef SPARSE_ARRAY_UNDERLYING_STRUCTURE
#  define SPARSE_ARRAY_UNDERLYING_STRUCTURE STL_MAP
#endif

#include <limits>

#if SPARSE_ARRAY_UNDERLYING_STRUCTURE == STL_MAP
#  include <map>
#endif

#if SPARSE_ARRAY_UNDERLYING_STRUCTURE == GNU_HASH_MAP
#  include <ext/hash_map>
#endif


#include "geom.h"
#include "hash_tools.h"


template<unsigned int N,typename T,typename KEY_COEF = int>
class Sparse_array_ND{

public:
  typedef Geometry::Vec<N,KEY_COEF> key_type;
  typedef T                         value_type;

  typedef unsigned int size_type; 
  
private:

#if SPARSE_ARRAY_UNDERLYING_STRUCTURE == STL_MAP
  typedef std::map<key_type,value_type,
		   Geometry::Lexicographical_order<key_type> > storage_type;
#endif
  
#if SPARSE_ARRAY_UNDERLYING_STRUCTURE == GNU_HASH_MAP
  typedef __gnu_cxx::hash_map<key_type,value_type,
			      Hash_tools::hash<key_type> > storage_type;
#endif

  

public:
  static const size_type dimension = N;

  typedef typename storage_type::iterator       iterator;
  typedef typename storage_type::const_iterator const_iterator;
  
//   typedef typename storage_type::size_type       size_type;
  typedef typename storage_type::difference_type difference_type;

  typedef value_type&       reference;
  typedef const value_type& const_reference;
  
  //@{
  //! Classical constructor.
  
  inline Sparse_array_ND();

  inline Sparse_array_ND(const Sparse_array_ND<N,T,KEY_COEF>& a);
  
  //@}

  
  //@{
  //! Handle the array dimension.

  inline bool empty() const;

  inline key_type min_key() const;
  inline key_type max_key() const;
  
  template<typename Vector_ND>
  inline void all_sizes(Vector_ND* const size) const;

  template<typename Vector_ND>
  inline void all_actual_sizes(Vector_ND* const size) const;

  inline void resize(const key_type& s);
  
  inline size_type size() const;
  inline size_type max_size() const;
  //@}

  //! Efficient swapping of two 2D arrays.
  inline void swap(Sparse_array_ND<N,T,KEY_COEF>& a); /* A reference is used as in the STL. */

  //! Erase all of the elements.
  inline void clear();
  
  //@{
  //! Classical operator.
  
  inline Sparse_array_ND<N,T,KEY_COEF>&
  operator=(const Sparse_array_ND<N,T,KEY_COEF>& a);

  inline bool operator==(const Sparse_array_ND<N,T,KEY_COEF>& a);
  
  inline bool operator!=(const Sparse_array_ND<N,T,KEY_COEF>& a); 
  //@}


  //@{
  //! Access operator.

  inline value_type& operator[](const key_type& k);
  
  inline const value_type& operator[](const key_type& k) const;
  //@}


  //@{
  //! Iterator.

  inline iterator       begin();
  inline const_iterator begin() const;
  
  inline iterator       end();
  inline const_iterator end() const;
  //@}

private:
  storage_type storage;
};



/*
  
  #############################################
  #############################################
  #############################################
  ######                                 ######
  ######   I M P L E M E N T A T I O N   ######
  ######                                 ######
  #############################################
  #############################################
  #############################################
  
*/



template<unsigned int N,typename T,typename KEY_COEF>
Sparse_array_ND<N,T,KEY_COEF>::Sparse_array_ND(){}




template<unsigned int N,typename T,typename KEY_COEF>
Sparse_array_ND<N,T,KEY_COEF>::
Sparse_array_ND(const Sparse_array_ND<N,T,KEY_COEF>& a):
  storage(a.storage){}



template<unsigned int N,typename T,typename KEY_COEF>
bool Sparse_array_ND<N,T,KEY_COEF>::empty() const{
  return storage.empty();
}


/*! This function is computationally expensive. */
template<unsigned int N,typename T,typename KEY_COEF>
typename Sparse_array_ND<N,T,KEY_COEF>::key_type
Sparse_array_ND<N,T,KEY_COEF>::min_key() const{

  const_iterator i_begin = storage.begin();
  
  key_type k = i_begin->first;

  i_begin++;
  for(const_iterator
	i     = i_begin,
	i_end = storage.end();
      i != i_end;i++){

    for(size_type n = 0;n < dimension;n++){
      
      KEY_COEF& k_n = k[n];
      k_n = min(k_n,(i->first)[n]);
    }
  }

  return k;
}



/*! This function is computationally expensive. */
template<unsigned int N,typename T,typename KEY_COEF>
typename Sparse_array_ND<N,T,KEY_COEF>::key_type
Sparse_array_ND<N,T,KEY_COEF>::max_key() const{


  const_iterator i_begin = storage.begin();
  
  key_type k = i_begin->first;

  i_begin++;
  for(const_iterator
	i     = i_begin,
	i_end = storage.end();
      i != i_end;i++){

    for(size_type n = 0;n < dimension;n++){
      
      KEY_COEF& k_n = k[n];
      k_n = max(k_n,(i->first)[n]);
    }
  }

  return k;
}



template<unsigned int N,typename T,typename KEY_COEF>
template<typename Vector_ND>
void Sparse_array_ND<N,T,KEY_COEF>::
all_sizes(Vector_ND* const size) const{

  for(size_type n = 0;n < dimension;n++){
    (*size)[n] = std::numeric_limits<KEY_COEF>::max();
  }
}




/*! This function is computationally expensive. */
template<unsigned int N,typename T,typename KEY_COEF>
template<typename Vector_ND>
void Sparse_array_ND<N,T,KEY_COEF>::
all_actual_sizes(Vector_ND* const size) const{

  const key_type max_k = max_key();
  const key_type min_k = min_key();
  
  for(size_type n = 0;n < dimension;n++){
    (*size)[n] = max_k[n] - min_k[n];
  }
}


/*!
  Does nothing. Just to improve the similarity with a dense array
  for templates.
 */
template<unsigned int N,typename T,typename KEY_COEF>
void
Sparse_array_ND<N,T,KEY_COEF>::resize(const key_type& s){

}



template<unsigned int N,typename T,typename KEY_COEF>
typename Sparse_array_ND<N,T,KEY_COEF>::size_type
Sparse_array_ND<N,T,KEY_COEF>::size() const{

  return storage.size();
}



template<unsigned int N,typename T,typename KEY_COEF>
typename Sparse_array_ND<N,T,KEY_COEF>::size_type
Sparse_array_ND<N,T,KEY_COEF>::max_size() const{

  return storage.max_size();
}



template<unsigned int N,typename T,typename KEY_COEF>
void Sparse_array_ND<N,T,KEY_COEF>::
swap(Sparse_array_ND<N,T,KEY_COEF>& a){

  storage.swap(a.storage);
}



template<unsigned int N,typename T,typename KEY_COEF>
void Sparse_array_ND<N,T,KEY_COEF>::
clear(){
  storage.clear();
}


template<unsigned int N,typename T,typename KEY_COEF>
Sparse_array_ND<N,T,KEY_COEF>&
Sparse_array_ND<N,T,KEY_COEF>::
operator=(const Sparse_array_ND<N,T,KEY_COEF>& a){

  storage = a.storage;
  return *this;
}



template<unsigned int N,typename T,typename KEY_COEF>
bool Sparse_array_ND<N,T,KEY_COEF>::
operator==(const Sparse_array_ND<N,T,KEY_COEF>& a){

  return storage == a.storage;
}



template<unsigned int N,typename T,typename KEY_COEF>
bool Sparse_array_ND<N,T,KEY_COEF>::
operator!=(const Sparse_array_ND<N,T,KEY_COEF>& a){

  return !(*this == a);  
}



template<unsigned int N,typename T,typename KEY_COEF>
typename Sparse_array_ND<N,T,KEY_COEF>::reference
Sparse_array_ND<N,T,KEY_COEF>::operator[](const key_type& k){

  return storage[k];
}
  


template<unsigned int N,typename T,typename KEY_COEF>
typename Sparse_array_ND<N,T,KEY_COEF>::const_reference
Sparse_array_ND<N,T,KEY_COEF>::operator[](const key_type& k) const{

  const_iterator i = storage.find(k);

  if (i != storage.end()){
    return i->second;
  }

  static value_type default_value = value_type();
  
  return default_value;
}



template<unsigned int N,typename T,typename KEY_COEF>
typename Sparse_array_ND<N,T,KEY_COEF>::iterator
Sparse_array_ND<N,T,KEY_COEF>::begin(){
  
  return storage.begin();
}



template<unsigned int N,typename T,typename KEY_COEF>
typename Sparse_array_ND<N,T,KEY_COEF>::const_iterator
Sparse_array_ND<N,T,KEY_COEF>::begin() const{

  return storage.begin();
}



template<unsigned int N,typename T,typename KEY_COEF>
typename Sparse_array_ND<N,T,KEY_COEF>::iterator
Sparse_array_ND<N,T,KEY_COEF>::end(){

  return storage.end();
}



template<unsigned int N,typename T,typename KEY_COEF>
typename Sparse_array_ND<N,T,KEY_COEF>::const_iterator
Sparse_array_ND<N,T,KEY_COEF>::end() const{

  return storage.end();
}



#endif