Double_map.h
// Copyright (c) 2003-2007 INRIA Sophia-Antipolis (France).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org)
//
// $URL$
// $Id$
// SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial
//
//
// Author(s) : Laurent RINEAU
#ifndef CGAL_DOUBLE_MAP_H
#define CGAL_DOUBLE_MAP_H
#include <CGAL/disable_warnings.h>
#include <map>
#include <utility>
#include <algorithm>
#include <CGAL/assertions.h>
#include <CGAL/function_objects.h> // for CGAL::Identity
#include <boost/version.hpp>
# define CGAL_USE_BOOST_BIMAP
#ifdef CGAL_USE_BOOST_BIMAP
# if defined(BOOST_MSVC)
# pragma warning(push)
# pragma warning(disable: 4996)
# endif
#include <CGAL/boost/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
# if defined(BOOST_MSVC)
# pragma warning(pop)
# endif
#endif
namespace CGAL {
template <class _Key, class _Data, class _Direct_compare = std::less<_Key>,
class _Reverse_compare = std::less<_Data> >
class Double_map
{
public:
typedef _Key Key;
typedef _Data Data;
typedef _Direct_compare Direct_compare;
typedef _Reverse_compare Reverse_compare;
typedef Double_map<Key, Data, Direct_compare, Reverse_compare> Self;
#ifdef CGAL_USE_BOOST_BIMAP
typedef ::boost::bimap< ::boost::bimaps::set_of<Key, Direct_compare>,
::boost::bimaps::multiset_of<Data, Reverse_compare> > Boost_bimap;
typedef typename Boost_bimap::left_map Direct_func;
typedef typename Boost_bimap::right_map Reverse_func;
typedef typename Reverse_func::iterator reverse_iterator;
typedef typename Boost_bimap::relation relation;
typedef typename Boost_bimap::left_key_type left_key_type;
typedef typename Boost_bimap::left_value_type left_value_type;
typedef typename Boost_bimap::right_key_type right_key_type;
typedef typename Boost_bimap::right_value_type right_value_type;
#else
typedef std::multimap <Data, Key, Reverse_compare> Reverse_func;
typedef typename Reverse_func::iterator reverse_iterator;
typedef std::map <Key, reverse_iterator, Direct_compare> Direct_func;
typedef typename Self::Direct_func::key_type left_key_type;
typedef typename Self::Direct_func::value_type left_value_type;
typedef typename Self::Reverse_func::key_type right_key_type;
typedef typename Self::Reverse_func::value_type right_value_type;
#endif
typedef typename Direct_func::value_type Direct_entry;
// std::pair<Key, reverse_iterator>
typedef typename Reverse_func::value_type Reverse_entry;
// std::pair<Data, Key> ;
typedef typename Direct_func::size_type size_type;
typedef typename Direct_func::iterator direct_iterator;
typedef reverse_iterator iterator;
typedef typename Direct_func::const_iterator direct_const_iterator;
typedef direct_const_iterator const_iterator;
private:
// Private members
#ifdef CGAL_USE_BOOST_BIMAP
Boost_bimap boost_bimap;
const Direct_func& direct_func() const { return boost_bimap.left;}
const Reverse_func& reverse_func() const { return boost_bimap.right;}
Direct_func& direct_func() { return boost_bimap.left;}
Reverse_func& reverse_func() { return boost_bimap.right;}
#else
Direct_func direct_func_;
Reverse_func reverse_func_;
const Direct_func& direct_func() const { return direct_func_;}
const Reverse_func& reverse_func() const { return reverse_func_;}
Direct_func& direct_func() { return direct_func_;}
Reverse_func& reverse_func() { return reverse_func_;}
#endif
public :
// The default constructor
Double_map () {}
// The copy constructor
Double_map(const Self& dm)
{
copy(dm);
}
// Queries
bool empty() const
{
CGAL_assertion(is_valid());
return(direct_func().empty());
}
size_type size() const
{
return direct_func().size();
}
bool is_valid() const
{
return(direct_func().size()==reverse_func().size());
}
void clear()
{
#ifdef CGAL_USE_BOOST_BIMAP
boost_bimap.clear();
#else
direct_func().clear();
reverse_func().clear();
#endif
}
Self& operator=(const Self& dm)
{
if(&dm != this)
copy(dm);
return *this;
}
void copy(const Self& dm)
{
clear();
#ifdef CGAL_USE_BOOST_BIMAP
for(direct_const_iterator rit = dm.direct_func().begin();
rit != dm.direct_func().end();
++rit)
{
direct_func().insert(*rit);
}
#else
reverse_func() = dm.reverse_func();
for(reverse_iterator rit = reverse_func().begin();
rit != reverse_func().end();
++rit)
{
// Fix an error with -D_GLIBCXX_DEBUG -D_GLIBCPP_CONCEPT_CHECKS
// The following (commented) line triggered the error:
// direct_func()[rit->second] = rit;
// The new following line fixes the bug. Actually, it is even more
// efficient.
direct_func().insert(std::make_pair(rit->second, rit));
}
#endif
}
// Assignation
bool insert(const Key& k, const Data& d)
{
#ifdef CGAL_USE_BOOST_BIMAP
direct_iterator hint = boost_bimap.left.lower_bound(k);
if(hint != boost_bimap.left.end() && hint->first == k)
return false;
boost_bimap.left.insert(hint, Direct_entry(k, d));
return true;
#else
direct_iterator direct_hint = direct_func().lower_bound(k);
if(direct_hint != direct_func().end() &&
direct_hint->first == k)
return false;
reverse_iterator reverse_it = reverse_func().insert(Reverse_entry(d, k));
direct_func().insert(direct_hint, Direct_entry(k, reverse_it));
CGAL_assertion(is_valid());
return(true);
#endif
}
bool erase(const Key& k);
// Access
reverse_iterator front()
{
CGAL_assertion(is_valid() && !empty());
return(reverse_func().begin());
}
void pop_front()
{
#ifdef CGAL_USE_BOOST_BIMAP
boost_bimap.right.erase(boost_bimap.right.begin());
#else
CGAL_assertion(is_valid());
reverse_iterator rit = reverse_func().begin();
direct_iterator pos = direct_func().find(rit->second);
CGAL_assertion(pos != direct_func().end());
CGAL_assertion(pos->second == rit);
direct_func().erase(pos);
reverse_func().erase(rit);
CGAL_assertion(is_valid());
#endif
}
const_iterator begin() const
{
return direct_func().begin();
}
const_iterator end() const
{
return direct_func().end();
}
template <typename Func_key, typename Func_data>
void dump_direct_func(std::ostream& out,
Func_key func_key,
Func_data func_data)
{
for(typename Direct_func::iterator it = direct_func().begin();
it != direct_func().end();
++it)
{
out << func_key(it->first) << " -> "
#ifdef CGAL_USE_BOOST_BIMAP
<< func_data(it->second)
#else
<< func_data(it->second->first)
#endif
<< std::endl;
}
}
void dump_direct_func(std::ostream& out)
{
dump_direct_func(out, CGAL::Identity<Key>(), CGAL::Identity<Data>() );
}
template <typename Func_key, typename Func_data>
void dump_reverse_func(std::ostream& out,
Func_key func_key,
Func_data func_data)
{
for(typename Reverse_func::iterator it = reverse_func().begin();
it != reverse_func().end();
++it)
{
out << func_data(it->first) << " "
<< func_key(it->second) << std::endl;
}
}
void dump_reverse_func(std::ostream& out)
{
dump_reverse_func(out, CGAL::Identity<Data>(), CGAL::Identity<Key>());
}
};
template <class _Key, class _Data, class _Direct_compare,
class _Reverse_compare>
bool
Double_map<_Key, _Data, _Direct_compare, _Reverse_compare>::
erase(const Key& k)
{
CGAL_assertion(is_valid());
direct_iterator pos = direct_func().find(k);
if (pos == direct_func().end())
return false;
else
{
#ifdef CGAL_USE_BOOST_BIMAP
boost_bimap.left.erase(pos);
#else
reverse_func().erase(pos->second);
direct_func().erase(pos);
#endif
}
CGAL_assertion(is_valid());
return true;
}
} // end namespace CGAL
#include <CGAL/enable_warnings.h>
#endif // CGAL_DOUBLE_MAP_H