Map.hpp

Go to the documentation of this file.

/* 
 * Map.hpp 
 *
 * This file is part of the Chemical Data Processing Toolkit
 *
 * Copyright (C) 2003 Thomas Seidel <thomas.seidel@univie.ac.at>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; see the file COPYING. If not, write to
 * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */
 
#ifndef CDPL_UTIL_MAP_HPP
#define CDPL_UTIL_MAP_HPP
 
#include <map>
#include <functional>
#include <utility>
#include <string>
#include <cstddef>
#include <memory>
 
#include "CDPL/Base/Exceptions.hpp"
 
 
namespace CDPL
{
 
    namespace Util
    {
 
        template <typename ValueType, bool Allow = true>
        struct MapDefaultValue
        {
 
            static const ValueType& get()
            {
                return defValue;
            }
 
            static const ValueType defValue;
        };
 
        template <typename ValueType, bool Allow>
        const ValueType MapDefaultValue<ValueType, Allow>::defValue = ValueType();
 
        template <typename ValueType>
        struct MapDefaultValue<ValueType, false>
        {
 
            static const ValueType& get()
            {
                throw Base::OperationFailed("Map: default value not supported");
            }
        };
 
        template <typename Key, typename Value, bool AllowDefValues = false,
                  typename KeyCompFunc = std::less<Key> >
        class Map
        {
 
            typedef std::map<Key, Value, KeyCompFunc> StorageType;
 
          public:
            typedef std::shared_ptr<Map> SharedPointer;
 
            typedef Key KeyType;
 
            typedef Value ValueType;
 
            typedef typename StorageType::value_type Entry;
 
            typedef typename StorageType::const_iterator ConstEntryIterator;
 
            typedef typename StorageType::const_reverse_iterator ConstReverseEntryIterator;
 
            typedef typename StorageType::iterator EntryIterator;
 
            typedef typename StorageType::reverse_iterator ReverseEntryIterator;
 
            Map():
                data() {}
 
            Map(const KeyCompFunc& func):
                data(func) {}
 
            template <typename InputIter>
            Map(const InputIter& first, const InputIter& last):
                data(first, last)
            {}
 
            template <typename InputIter>
            Map(const InputIter& first, const InputIter& last, const KeyCompFunc& func):
                data(first, last, func)
            {}
 
            virtual ~Map() {}
 
            StorageType& getData();
 
            const StorageType& getData() const;
            
            std::size_t getSize() const;
 
            bool isEmpty() const;
 
            void clear();
 
            void swap(Map& map);
 
            KeyCompFunc getKeyCompareFunction() const;
 
            EntryIterator getEntry(const Key& key);
 
            ConstEntryIterator getEntry(const Key& key) const;
 
            bool containsEntry(const Key& key) const;
 
            Value& getValue(const Key& key);
 
            Value& getValue(const Key& key, Value& def_value);
 
            const Value& getValue(const Key& key) const;
 
            const Value& getValue(const Key& key, const Value& def_value) const;
 
            Value& operator[](const Key& key);
 
            const Value& operator[](const Key& key) const;
 
            void removeEntry(const EntryIterator& it);
 
            bool removeEntry(const Key& key);
 
            void removeEntries(const EntryIterator& first, const EntryIterator& last);
 
            std::pair<EntryIterator, bool> insertEntry(const Entry& item);
 
            std::pair<EntryIterator, bool> insertEntry(const Key& key, const Value& value);
 
            EntryIterator insertEntry(const EntryIterator& it, const Entry& item);
 
            EntryIterator insertEntry(const EntryIterator& it, const Key& key, const Value& value);
 
            EntryIterator setEntry(const Entry& item);
 
            EntryIterator setEntry(const Key& key, const Value& value);
 
            template <typename InputIter>
            void insertEntries(const InputIter& first, const InputIter& last);
 
            template <typename InputIter>
            void setEntries(const InputIter& first, const InputIter& last);
 
            EntryIterator getLowerBound(const Key& key);
 
            ConstEntryIterator getLowerBound(const Key& key) const;
 
            EntryIterator getUpperBound(const Key& key);
 
            ConstEntryIterator getUpperBound(const Key& key) const;
 
            ConstEntryIterator getEntriesBegin() const;
 
            EntryIterator getEntriesBegin();
 
            ConstEntryIterator getEntriesEnd() const;
 
            EntryIterator getEntriesEnd();
 
            ConstEntryIterator begin() const;
 
            EntryIterator begin();
 
            ConstEntryIterator end() const;
 
            EntryIterator end();
 
            ConstReverseEntryIterator getEntriesReverseBegin() const;
 
            ReverseEntryIterator getEntriesReverseBegin();
 
            ConstReverseEntryIterator getEntriesReverseEnd() const;
 
            ReverseEntryIterator getEntriesReverseEnd();
 
          
          protected:
            virtual const char* getClassName() const;
 
          private:
            const Value& getDefaultValue() const;
 
            StorageType data;
        };
 
        template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
        bool operator==(const Map<Key, Value, AllowDefValues, KeyCompFunc>& map1,
                        const Map<Key, Value, AllowDefValues, KeyCompFunc>& map2);
 
        template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
        bool operator!=(const Map<Key, Value, AllowDefValues, KeyCompFunc>& map1,
                        const Map<Key, Value, AllowDefValues, KeyCompFunc>& map2);
 
        template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
        bool operator<=(const Map<Key, Value, AllowDefValues, KeyCompFunc>& map1,
                        const Map<Key, Value, AllowDefValues, KeyCompFunc>& map2);
 
        template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
        bool operator>=(const Map<Key, Value, AllowDefValues, KeyCompFunc>& map1,
                        const Map<Key, Value, AllowDefValues, KeyCompFunc>& map2);
 
        template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
        bool operator<(const Map<Key, Value, AllowDefValues, KeyCompFunc>& map1,
                       const Map<Key, Value, AllowDefValues, KeyCompFunc>& map2);
 
        template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
        bool operator>(const Map<Key, Value, AllowDefValues, KeyCompFunc>& map1,
                       const Map<Key, Value, AllowDefValues, KeyCompFunc>& map2);
        
    } // namespace Util
} // namespace CDPL
 
 
// Implementation
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::StorageType&
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getData()
{
    return data;
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
const typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::StorageType&
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getData() const
{
    return data;
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
std::size_t CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getSize() const
{
    return data.size();
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
bool CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::isEmpty() const
{
    return data.empty();
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
void CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::clear()
{
    data.clear();
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
void CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::swap(Map& map)
{
    data.swap(map.data);
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
KeyCompFunc CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getKeyCompareFunction() const
{
    return data.key_comp();
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::EntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getEntry(const Key& key)
{
    return data.find(key);
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::ConstEntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getEntry(const Key& key) const
{
    return data.find(key);
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
bool CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::containsEntry(const Key& key) const
{
    return (data.find(key) != data.end());
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
Value& CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getValue(const Key& key)
{
    EntryIterator lb = data.lower_bound(key);
 
    if (lb == data.end() || data.key_comp()(key, (*lb).first)) {
        if (!AllowDefValues)
            throw Base::ItemNotFound(std::string(getClassName()) + ": key not found");
 
        return (*data.insert(lb, Entry(key, getDefaultValue()))).second;
    }
 
    return (*lb).second;
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
Value& CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getValue(const Key& key, Value& def_value)
{
    EntryIterator it = data.find(key);
 
    if (it == data.end())
        return def_value;
 
    return (*it).second;
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
const Value& CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getValue(const Key& key) const
{
    ConstEntryIterator it = data.find(key);
 
    if (it == data.end()) {
        if (!AllowDefValues)
            throw Base::ItemNotFound(std::string(getClassName()) + ": key not found");
 
        return getDefaultValue();
    }
 
    return (*it).second;
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
const Value& CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getValue(const Key&   key,
                                                                                const Value& def_value) const
{
    ConstEntryIterator it = data.find(key);
 
    if (it == data.end())
        return def_value;
 
    return (*it).second;
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
Value& CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::operator[](const Key& key)
{
    return getValue(key);
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
const Value& CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::operator[](const Key& key) const
{
    return getValue(key);
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
void CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::removeEntry(const EntryIterator& it)
{
    data.erase(it);
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
bool CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::removeEntry(const Key& key)
{
    return (data.erase(key) > 0);
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
void CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::removeEntries(const EntryIterator& first,
                                                                             const EntryIterator& last)
{
    data.erase(first, last);
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
std::pair<typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::EntryIterator, bool>
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::insertEntry(const Entry& item)
{
    return data.insert(item);
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
std::pair<typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::EntryIterator, bool>
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::insertEntry(const Key& key, const Value& value)
{
    return data.insert(Entry(key, value));
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::EntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::insertEntry(const EntryIterator& it, const Entry& item)
{
    return data.insert(it, item);
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::EntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::insertEntry(const EntryIterator& it, const Key& key,
                                                                      const Value& value)
{
    return data.insert(it, Entry(key, value));
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::EntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::setEntry(const Entry& item)
{
    EntryIterator lb = data.lower_bound(item.first);
 
    if (lb == data.end() || data.key_comp()(item.first, (*lb).first))
        return data.insert(lb, item);
 
    (*lb).second = item.second;
    return lb;
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::EntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::setEntry(const Key& key, const Value& value)
{
    return setEntry(Entry(key, value));
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
template <typename InputIter>
void CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::insertEntries(const InputIter& first, const InputIter& last)
{
    data.insert(first, last);
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
template <typename InputIter>
void CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::setEntries(const InputIter& first, const InputIter& last)
{
    for (InputIter it = first; it != last; ++it)
        setEntry(*it);
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::EntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getLowerBound(const Key& key)
{
    return data.lower_bound(key);
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::ConstEntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getLowerBound(const Key& key) const
{
    return data.lower_bound(key);
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::EntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getUpperBound(const Key& key)
{
    return data.upper_bound(key);
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::ConstEntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getUpperBound(const Key& key) const
{
    return data.upper_bound(key);
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::ConstEntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getEntriesBegin() const
{
    return data.begin();
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::EntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getEntriesBegin()
{
    return data.begin();
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::ConstEntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getEntriesEnd() const
{
    return data.end();
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::EntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getEntriesEnd()
{
    return data.end();
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::ConstEntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::begin() const
{
    return data.begin();
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::EntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::begin()
{
    return data.begin();
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::ConstEntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::end() const
{
    return data.end();
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::EntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::end()
{
    return data.end();
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::ConstReverseEntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getEntriesReverseBegin() const
{
    return data.rbegin();
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::ReverseEntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getEntriesReverseBegin()
{
    return data.rbegin();
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::ConstReverseEntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getEntriesReverseEnd() const
{
    return data.rend();
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
typename CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::ReverseEntryIterator
CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getEntriesReverseEnd()
{
    return data.rend();
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
const char* CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getClassName() const
{
    return "Map";
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
const Value& CDPL::Util::Map<Key, Value, AllowDefValues, KeyCompFunc>::getDefaultValue() const
{
    return MapDefaultValue<Value, AllowDefValues>::get();
}
 
// \cond DOC_IMPL_DETAILS
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
bool CDPL::Util::operator==(const Map<Key, Value, AllowDefValues, KeyCompFunc>& map1,
                            const Map<Key, Value, AllowDefValues, KeyCompFunc>& map2)
{
    return (map1.getData() == map2.getData());
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
bool CDPL::Util::operator!=(const Map<Key, Value, AllowDefValues, KeyCompFunc>& map1,
                            const Map<Key, Value, AllowDefValues, KeyCompFunc>& map2)
{
    return (map1.getData() != map2.getData());
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
bool CDPL::Util::operator<=(const Map<Key, Value, AllowDefValues, KeyCompFunc>& map1,
                            const Map<Key, Value, AllowDefValues, KeyCompFunc>& map2)
{
    return (map1.getData() <= map2.getData());
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
bool CDPL::Util::operator>=(const Map<Key, Value, AllowDefValues, KeyCompFunc>& map1,
                            const Map<Key, Value, AllowDefValues, KeyCompFunc>& map2)
{
    return (map1.getData() >= map2.getData());
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
bool CDPL::Util::operator<(const Map<Key, Value, AllowDefValues, KeyCompFunc>& map1,
                           const Map<Key, Value, AllowDefValues, KeyCompFunc>& map2)
{
    return (map1.getData() < map2.getData());
}
 
template <typename Key, typename Value, bool AllowDefValues, typename KeyCompFunc>
bool CDPL::Util::operator>(const Map<Key, Value, AllowDefValues, KeyCompFunc>& map1,
                           const Map<Key, Value, AllowDefValues, KeyCompFunc>& map2)
{
    return (map1.getData() > map2.getData());
}
 
// \endcond
 
#endif // CDPL_UTIL_MAP_HPP