Package: Sequence       

---

Container/bijective-mapping.h

Go to the documentation of this file.

#ifndef NMWR_GB_BIJECTIVE_MAPPING_H
#define NMWR_GB_BIJECTIVE_MAPPING_H



/* ------------------------------------------------------------

    Copyright (C) 1997 - 2009 Guntram Berti

    This file is part of the Grid Algorithms Library (GrAL),
    available at http://gral.berti-cmm.de

    GrAL is distributed under the MIT license,
    see the file LICENSE or http://gral.berti-cmm.de/license

--------------------------------------------------------------- */



#include "Container/my-hash-map.h" 
#include "Container/mapped-value-iterator.h"
#include "Utility/pre-post-conditions.h"

namespace GrAL {


  struct fail_if_undefined {};

  struct identity_if_undefined {};


  template<class T1, class T2, class Policy = fail_if_undefined>
  class bijective_mapping;

  template<class T1, class T2, class Policy = fail_if_undefined>
  class inverse_mapping;

  template<class T1, class T2, class Policy = fail_if_undefined>
  class domain_of_bijective_mapping;

  template<class T1, class T2, class Policy = fail_if_undefined>
  class range_of_bijective_mapping;

//----------------------------------------------------------------
//          [0] output facilities
//----------------------------------------------------------------

  template<class T1, class T2,  class Policy>
void write_bm(bijective_mapping<T1,T2,Policy> const& m, ::std::ostream& out);

  template<class T1, class T2, class Policy>
  void read_bm(bijective_mapping<T1,T2,Policy>       & m, ::std::istream& in);

template<class T1, class T2, class Policy>
class printer_of_bij_mapping {
private:
  bijective_mapping<T1,T2,Policy> const* mp;
public:
  printer_of_bij_mapping(bijective_mapping<T1,T2,Policy> const& m) : mp(&m) {}

  friend ::std::ostream& operator<<(::std::ostream& out, printer_of_bij_mapping<T1,T2,Policy> const& p)
    { write_bm(*(p.mp),out); return out;}

};

  template<class T1, class T2, class Policy>
inline printer_of_bij_mapping<T1,T2,Policy>
Printer(bijective_mapping<T1,T2,Policy> const& m)
{ return printer_of_bij_mapping<T1,T2,Policy>(m);}



  template<class T1, class T2, class MAP, class Policy> 
  struct map_accessor 
  {
    static T2 const& get(MAP const& m, T1 const& t1) { 
      REQUIRE(m.find(t1) != m.end(), "", 1);
      return m.find(t1)->second;
    }
  };

  template<class T1, class MAP> 
  struct map_accessor<T1,T1,MAP,identity_if_undefined>  
  {
    static T1 const& get(MAP const& m, T1 const& t1) { 
      return (m.find(t1) == m.end() ? t1 : m.find(t1)->second);
    }
  };

//----------------------------------------------------------------
//          [1] class bijective_mapping<T1,T2>
//----------------------------------------------------------------

  template<class T1, class T2, class Policy>
  class bijective_mapping {
public:
  typedef inverse_mapping<T1,T2,Policy>              inverse_type;
  typedef domain_of_bijective_mapping<T1,T2,Policy>  domain_type;
  typedef range_of_bijective_mapping <T1,T2,Policy>  range_type;

  template<class U, class R, class P> friend class bijective_mapping;
  template<class U, class R, class P> friend class inverse_mapping;
  template<class U, class R, class P> friend class domain_of_bijective_mapping;
  template<class U, class R, class P> friend class range_of_bijective_mapping;
  
  // STL unary function conformance
  typedef T1                         argument_type;
  typedef T2                         result_type;

private:
  // hash_map not yet in ::std::
  typedef STDHASH::hash_map<T1,T2>  map_table_type;
  typedef STDHASH::hash_map<T2,T1>  inv_table_type; 
  typedef map_accessor<T1,T2,map_table_type,Policy>  map_accessor_type;
  typedef map_accessor<T2,T1,inv_table_type,Policy>  inv_accessor_type;
  //--------------- DATA -------------------------

  map_table_type         the_map;
  mutable inv_table_type the_inverse_map;

  // flag if the_inverse_map really reflects the inverse mapping
  mutable bool                       inverse_ok;

  //-------  internal types ----------------

  typedef typename map_table_type::const_iterator map_iterator;
public:
    typedef bijective_mapping<T1,T2,Policy>   self;
  
  //---------- construction ----------------

  bijective_mapping() : inverse_ok(false) {}
  bijective_mapping(unsigned sz) : the_map(sz), the_inverse_map(sz), inverse_ok(false) {}
    bijective_mapping(inverse_mapping<T2,T1,Policy> const& inv);

  //---------- data access -----------------

  const T2& operator()(const T1& t1) const {
    /*
    REQUIRE( (the_map.find(t1) != the_map.end()), 
             "map not defined for item " << t1 << '\n',1);
    return (*(the_map.find(t1))).second;
    */
    return map_accessor_type::get(the_map,t1);
  }
  const T2& operator[](const T1& t1) const {
    /*
    REQUIRE( (the_map.find(t1) != the_map.end()), 
             "map not defined for item " << t1 << '\n',1);
    return (*(the_map.find(t1))).second;
    */
    return map_accessor_type::get(the_map,t1);
  }
  T2& operator[](const T1& t1) { inverse_ok = false; return the_map[t1];}

  bool defined  (const T1& t1) const { return (the_map.find(t1) != the_map.end());}
  bool undefined(const T1& t1) const { return !defined(t1); }


  //-------------- related functions and sets ----------------

  inverse_type inverse() const;

  domain_type domain() const;
  range_type  range()  const;

  typedef typename map_table_type::size_type  size_type;
  size_type size() const { return domain().size();}


private:
  //--------------- consistency -------------------------------

  void update_inverse() const {
    if(! inverse_ok) {
      calculate_inverse();
      inverse_ok = true;
    }

  }
  void calculate_inverse() const;
};


//-----------------------------------------------------------------
//          [2]  class inverse_mapping<T1,T2>
//-----------------------------------------------------------------

  template<class T1, class T2, class Policy>
class inverse_mapping {
private:
  typedef bijective_mapping<T1,T2, Policy>   mapping_type;
  typedef typename mapping_type::inv_accessor_type accessor_type;
  template<class U, class R, class P> friend class bijective_mapping;

  //-------- DATA ----------
  const  mapping_type*    bmap; // reference

public:
  typedef T1 result_type;
  typedef T2 argument_type;

  inverse_mapping(const mapping_type& tm) : bmap(&tm) {}

  const T1& operator()(const T2& t2) const { 
    bmap->update_inverse();
    REQUIRE( (defined(t2)),
            "inverse map not defined for item " << t2 << '\n',1);
    return (*(bmap->the_inverse_map.find(t2))).second;
    return accessor_type::get(bmap->the_inverse_map, t2);
  }

  bool defined(const T2& t2) const {
    bmap->update_inverse();
    return (bmap->the_inverse_map.find(t2) != bmap->the_inverse_map.end());
  }

  typedef typename mapping_type::domain_type range_type;
  inline range_type   range() const;
  typedef typename mapping_type::range_type  domain_type;
  inline domain_type  domain() const;
};

//-----------------------------------------------------------------
//           [3]  class domain_of_bijective_mapping<T1,T2>
//-----------------------------------------------------------------

  template<class T1, class T2, class Policy>
class domain_of_bijective_mapping {
public:
  typedef bijective_mapping<T1,T2, Policy>                 mapping_type;
  typedef typename mapping_type::map_table_type            map_table_type;
  typedef typename map_table_type::value_type              base_value_type;
  typedef typename map_table_type::const_iterator          base_iter_type;
  typedef mapped_value_const_iterator<base_iter_type,
                                      get_first<base_value_type> const> const_iterator;

  typedef T1                                                value_type;

private:
  const mapping_type*  bmap; // reference to mapping f
public:
  domain_of_bijective_mapping(const mapping_type& tm) : bmap(&tm) {}

  unsigned size() const { return bmap->the_map.size();}

  bool is_member(const value_type& x) const { return bmap->defined(x);}  

  const_iterator begin() const { return const_iterator(bmap->the_map.begin());}
  const_iterator end()   const { return const_iterator(bmap->the_map.end());}
  T1 const& front() const { return *begin();}
};

//-----------------------------------------------------------------
//          [4]   class range_of_bijective_mapping<T1,T2>
//-----------------------------------------------------------------

  template<class T1, class T2, class Policy>
class range_of_bijective_mapping {
public:
  typedef bijective_mapping<T1,T2, Policy>                 mapping_type;
  typedef typename mapping_type::map_table_type            map_table_type;
  typedef typename map_table_type::value_type              base_value_type;
  typedef typename map_table_type::const_iterator          base_iter_type;
  typedef mapped_value_const_iterator<base_iter_type,
                                      get_second<base_value_type> const> const_iterator;

  typedef T2                                                     value_type;

private:
  const mapping_type*  bmap; // reference
public:
  range_of_bijective_mapping(const mapping_type& tm)  : bmap(&tm) {}

  unsigned size() const { return bmap->the_map.size();}
  bool is_member(const value_type& x) const { 
    bmap->update_inverse();    
    return (bmap->the_inverse_map.find(x) != bmap->the_inverse_map.end());
  }  

  const_iterator begin() const { return const_iterator(bmap->the_map.begin());}
  const_iterator end()   const { return const_iterator(bmap->the_map.end());}
  T2 const& front() const { return *begin();}
};


//-----------------------------------------------------------------
//         inline functions of bijective_mapping<T1,T2>
//-----------------------------------------------------------------


  template<class T1, class T2, class Policy>
inline
  inverse_mapping<T1,T2, Policy> bijective_mapping<T1,T2, Policy>::inverse() const 
{ return inverse_type(*this);}

template<class T1, class T2, class Policy>
inline
domain_of_bijective_mapping<T1,T2,Policy> bijective_mapping<T1,T2,Policy >::domain() const 
{ return domain_type(*this);}
 
template<class T1, class T2, class Policy>
inline
range_of_bijective_mapping<T1,T2,Policy> bijective_mapping<T1,T2,Policy>::range() const 
{ return range_type(*this);}

template<class T1, class T2, class Policy>
inline
//domain_of_bijective_mapping<T1,T2>
typename inverse_mapping<T1,T2,Policy>::range_type
inverse_mapping<T1,T2,Policy>::range() const { return bmap->domain();}

template<class T1, class T2, class Policy>
inline
typename inverse_mapping<T1,T2,Policy>::domain_type //range_of_bijective_mapping<T1,T2>
inverse_mapping<T1,T2,Policy>::domain() const { return bmap->range();}


} // namespace GrAL 

#ifdef NMWR_INCLUDE_TEMPLATE_DEFS
#include "bijective-mapping.C"
#endif

#endif

---

©  Guntram Berti 1997-2009. See the GrAL Homepage for up-to-date information.

---