be_memory_orderedmap.h

Go to the documentation of this file.

/*
 * This software was developed at the National Institute of Standards and
 * Technology (NIST) by employees of the Federal Government in the course
 * of their official duties. Pursuant to title 17 Section 105 of the
 * United States Code, this software is not subject to copyright protection
 * and is in the public domain. NIST assumes no responsibility whatsoever for
 * its use by other parties, and makes no guarantees, expressed or implied,
 * about its quality, reliability, or any other characteristic.
 */
 
#ifndef __ORDERED_MAP_H__
#define __ORDERED_MAP_H__
 
#include <iterator>
#include <list>
#include <memory>
#include <unordered_map>
 
 
namespace BiometricEvaluation
{
        namespace Memory
        {
                /* Forward declarations */
                template<class Key, class T> class OrderedMap;
                template<class Key, class T> class OrderedMapIterator;
                template<class Key, class T> class OrderedMapConstIterator;
                
                template<class Key, class T>
                class OrderedMapIterator
                {
                public:
                        /*
                         * Satisfy std::iterator_traits<> expectations.
                         */
 
                        using iterator_category =
                            std::bidirectional_iterator_tag;
                        using value_type = std::pair<Key, T>;
                        using difference_type = std::ptrdiff_t;
                        using pointer = value_type*;
                        using reference = value_type&;
 
                        friend class OrderedMap<Key, T>;
                        friend class OrderedMapConstIterator<Key, T>;
                        
                        OrderedMapIterator();
                        ~OrderedMapIterator();
                        
                        reference
                        operator*()
                            const;
                        
                        pointer
                        operator->()
                            const;
                        
                        OrderedMapIterator&
                        operator++();
                
                        OrderedMapIterator
                        operator++(
                            int);
                        
                        OrderedMapIterator&
                        operator--();
                        
                        OrderedMapIterator
                        operator--(
                            int);
                
                        bool
                        operator==(
                            const OrderedMapIterator &rhs)
                            const;
                            
                         bool
                         operator!=(
                             const OrderedMapIterator &rhs)
                             const;
                             
                private:
                        OrderedMapIterator(
                            const OrderedMap<Key, T> *orderedMap,
                            const typename std::list<Key>::iterator listIter);
                        
                        const OrderedMap<Key, T>  *_orderedMap;
                        typename std::list<Key>::iterator _listIter;
                        mutable std::pair<Key, T> _currentPair;
                };
                
                template<class Key, class T>
                class OrderedMapConstIterator
                {
                public:
                        /*
                         * Satisfy std::iterator_traits<> expectations.
                         */
 
                        using iterator_category =
                            std::bidirectional_iterator_tag;
                        using value_type = std::pair<Key, T>;
                        using difference_type = std::ptrdiff_t;
                        using pointer = const value_type*;
                        using reference = const value_type&;
                
                        friend class OrderedMap<Key, T>;
                        
                        OrderedMapConstIterator();
                        OrderedMapConstIterator(
                            const OrderedMapIterator<Key, T> &iterator);
                        ~OrderedMapConstIterator();
                        
                        reference
                        operator*()
                            const;
                        
                        pointer
                        operator->()
                            const;
                        
                        OrderedMapConstIterator&
                        operator++();
                
                        OrderedMapConstIterator
                        operator++(
                            int);
                        
                        OrderedMapConstIterator&
                        operator--();
                        
                        OrderedMapConstIterator
                        operator--(
                            int);
                
                        bool
                        operator==(
                            const OrderedMapConstIterator &rhs)
                            const;
                            
                         bool
                         operator!=(
                             const OrderedMapConstIterator &rhs)
                             const;
                             
                private:
                        OrderedMapConstIterator(
                            const OrderedMap<Key, T> *orderedMap,
                            const typename std::list<Key>::iterator listIter);
                        
                        const OrderedMap<Key, T>  *_orderedMap;
                        mutable typename std::list<Key>::iterator _listIter;
                        mutable std::pair<Key, T> _currentPair;
                };
                
                
                template<class Key, class T>
                class OrderedMap
                {
                public:
                        using container = typename std::unordered_map<Key, T>;
                        using iterator = OrderedMapIterator<Key, T>;
                        using const_iterator = OrderedMapConstIterator<Key, T>;
                        
                        using size_type = typename container::size_type;
                        using value_type = typename container::value_type;
                        using key_type = Key;
                        using mapped_type = T;
                        
                        using key_equal = typename container::key_equal;
                        
                        friend class OrderedMapIterator<Key, T>;
                        friend class OrderedMapConstIterator<Key, T>;
                
                        OrderedMap();
                        
                        bool
                        push_back(
                            const value_type &value);
                            
                        void
                        erase(
                            iterator pos);
                            
                        void
                        erase(
                            const Key &key);
                        
                        iterator
                        begin();
                        
                        const_iterator
                        begin()
                            const;
 
                        const_iterator
                        cbegin()
                            const;
                        
                        iterator
                        end();
                        
                        const_iterator
                        end()
                            const;
 
                        const_iterator
                        cend()
                            const;
                        
                        size_type
                        size()
                            const;
                        
                        bool
                        keyExists(
                            const Key &key)
                            const;
                            
                        const OrderedMapIterator<Key, T>
                        find(
                            const Key &key)
                            const;
                            
                        std::shared_ptr<value_type>
                        find_quick(
                            const Key &key)
                            const;
                        
                        T&
                        operator[](
                            const Key &key);
 
                        key_equal
                        key_eq()
                            const;
                        
                        ~OrderedMap();
                
                private:
                        container *_elements;
                        std::list<Key> *_ordering;
                };
        }
}
 
template<class Key, class T>
BiometricEvaluation::Memory::OrderedMap<Key, T>::OrderedMap() :
    _elements(new container()),
    _ordering(new std::list<Key>())
{
 
}
 
template<class Key, class T>
BiometricEvaluation::Memory::OrderedMap<Key, T>::~OrderedMap()
{
        if (_elements != nullptr)
                delete _elements;
        if (_ordering != nullptr)
                delete _ordering;
}
 
template<class Key, class T>
bool
BiometricEvaluation::Memory::OrderedMap<Key, T>::push_back(
    const value_type &value)
{
        if (_elements->insert(value).second) {
                _ordering->push_back(value.first);
                return (true);
        } else
                return (false);
}
 
template<class Key, class T>
void
BiometricEvaluation::Memory::OrderedMap<Key, T>::erase(
    iterator pos)
{
        _ordering->remove(pos->first);
        _elements->erase(pos);
}
 
template<class Key, class T>
void
BiometricEvaluation::Memory::OrderedMap<Key, T>::erase(
    const Key &key)
{
        _ordering->remove(key);
        _elements->erase(_elements->find(key));
}
 
template<class Key, class T>
typename BiometricEvaluation::Memory::OrderedMap<Key, T>::iterator
BiometricEvaluation::Memory::OrderedMap<Key, T>::begin()
{
        return (OrderedMapIterator<Key, T>(this, _ordering->begin()));
}
 
template<class Key, class T>
typename BiometricEvaluation::Memory::OrderedMap<Key, T>::const_iterator
BiometricEvaluation::Memory::OrderedMap<Key, T>::begin()
    const
{
        return (OrderedMapIterator<Key, T>(this, _ordering->begin()));
}
 
template<class Key, class T>
typename BiometricEvaluation::Memory::OrderedMap<Key, T>::const_iterator
BiometricEvaluation::Memory::OrderedMap<Key, T>::cbegin()
    const
{
        return (OrderedMapIterator<Key, T>(this, _ordering->begin()));
}
        
template<class Key, class T>
typename BiometricEvaluation::Memory::OrderedMap<Key, T>::iterator
BiometricEvaluation::Memory::OrderedMap<Key, T>::end()
{
        return (OrderedMapIterator<Key, T>(this, _ordering->end()));
}
 
template<class Key, class T>
typename BiometricEvaluation::Memory::OrderedMap<Key, T>::const_iterator
BiometricEvaluation::Memory::OrderedMap<Key, T>::end()
    const
{
        return (OrderedMapIterator<Key, T>(this, _ordering->end()));
}
 
template<class Key, class T>
typename BiometricEvaluation::Memory::OrderedMap<Key, T>::const_iterator
BiometricEvaluation::Memory::OrderedMap<Key, T>::cend()
    const
{
        return (OrderedMapIterator<Key, T>(this, _ordering->end()));
}
 
template<class Key, class T>
typename BiometricEvaluation::Memory::OrderedMap<Key, T>::size_type
BiometricEvaluation::Memory::OrderedMap<Key, T>::size()
    const
{
        return (_elements->size());
}
 
template<class Key, class T>
bool
BiometricEvaluation::Memory::OrderedMap<Key, T>::keyExists(
    const Key &key)
    const
{
        return (_elements->find(key) != _elements->end());
}
 
template<class Key, class T>
T&
BiometricEvaluation::Memory::OrderedMap<Key, T>::operator[](
    const Key &key)
{
        std::pair<typename container::iterator, bool> result = 
            _elements->insert(std::make_pair(key, T()));
            
        if (result.second) {
                /* New insertion */
                _ordering->push_back(key);
                return (result.first->second);
        } else
                /* Already in list */
                return (result.first->second);
}
 
template<class Key, class T>
const BiometricEvaluation::Memory::OrderedMapIterator<Key, T>
BiometricEvaluation::Memory::OrderedMap<Key, T>::find(
    const Key &key)
    const
{
        return (OrderedMapIterator<Key, T>(this,
            std::find(_ordering->begin(), _ordering->end(), key)));
}
 
template<class Key, class T>
std::shared_ptr<
typename BiometricEvaluation::Memory::OrderedMap<Key, T>::value_type>
BiometricEvaluation::Memory::OrderedMap<Key, T>::find_quick(
    const Key &key)
    const
{
        typename container::const_iterator it = _elements->find(key);
        if (it != _elements->end())
                return (std::shared_ptr<
                    typename OrderedMap<Key, T>::value_type>(
                    new typename OrderedMap<Key, T>::value_type(it->first,
                    it->second)));
        return (std::shared_ptr<
            typename OrderedMap<Key, T>::value_type>());
}
 
template<class Key, class T>
typename BiometricEvaluation::Memory::OrderedMap<Key, T>::key_equal
BiometricEvaluation::Memory::OrderedMap<Key, T>::key_eq()
    const
{
        return (_elements->key_eq());
}
 
/*
 * OrderedMapIterator Implementation
 */
 
template<class Key, class T>
BiometricEvaluation::Memory::OrderedMapIterator<Key, T>::OrderedMapIterator() :
    _orderedMap(nullptr),
    _listIter()
{
 
}
 
template<class Key, class T>
BiometricEvaluation::Memory::OrderedMapIterator<Key, T>::OrderedMapIterator(
    const OrderedMap<Key, T> *orderedMap,
    const typename std::list<Key>::iterator listIter) :
    _orderedMap(orderedMap),
    _listIter(listIter)
{
 
}
 
template<class Key, class T>
typename BiometricEvaluation::Memory::OrderedMapIterator<Key, T>::reference
BiometricEvaluation::Memory::OrderedMapIterator<Key, T>::operator*()
    const
{
        _currentPair = *(_orderedMap->_elements->find(*_listIter));
        return (_currentPair);
}
 
template<class Key, class T>
typename BiometricEvaluation::Memory::OrderedMapIterator<Key, T>::pointer
BiometricEvaluation::Memory::OrderedMapIterator<Key, T>::operator->()
    const
{
        _currentPair = *(_orderedMap->_elements->find(*_listIter));
        return (&_currentPair);
}
 
template<class Key, class T>
BiometricEvaluation::Memory::OrderedMapIterator<Key, T>&
BiometricEvaluation::Memory::OrderedMapIterator<Key, T>::operator++()
{
        ++_listIter;
        return (*this);
}
 
template<class Key, class T>
BiometricEvaluation::Memory::OrderedMapIterator<Key, T>
BiometricEvaluation::Memory::OrderedMapIterator<Key, T>::operator++(
    int)
{
        OrderedMapIterator previousIterator(*this);
        ++(*this);
        return (previousIterator);
}
 
template<class Key, class T>
BiometricEvaluation::Memory::OrderedMapIterator<Key, T>&
BiometricEvaluation::Memory::OrderedMapIterator<Key, T>::operator--()
{
        --_listIter;
        return (*this);
}
 
template<class Key, class T>
BiometricEvaluation::Memory::OrderedMapIterator<Key, T>
BiometricEvaluation::Memory::OrderedMapIterator<Key, T>::operator--(
    int)
{
        OrderedMapIterator previousIterator(*this);
        --(*this);
        return (previousIterator);
}
 
template<class Key, class T>
bool
BiometricEvaluation::Memory::OrderedMapIterator<Key, T>::operator==(
    const OrderedMapIterator &rhs)
    const
{
        return ((_orderedMap == rhs._orderedMap) &&
            (_listIter == rhs._listIter));
}
 
template<class Key, class T>
bool
BiometricEvaluation::Memory::OrderedMapIterator<Key, T>::operator!=(
    const OrderedMapIterator &rhs)
    const
{
        return (!(this->operator==(rhs)));
}
 
template<class Key, class T>
BiometricEvaluation::Memory::OrderedMapIterator<Key, T>::~OrderedMapIterator()
{
        /* Don't delete _orderedMap, we don't own it. */
}
 
/* 
 * OrderedMapConstIterator Implementation
 */
 
template<class Key, class T>
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>::
OrderedMapConstIterator() :
    _orderedMap(nullptr),
    _listIter()
{
 
}
 
template<class Key, class T>
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>::
OrderedMapConstIterator(
    const OrderedMap<Key, T> *orderedMap,
    const typename std::list<Key>::iterator listIter) :
    _orderedMap(orderedMap),
    _listIter(listIter)
{
 
}
 
template<class Key, class T>
typename
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>::reference
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>::operator*()
    const
{
        _currentPair = *(_orderedMap->_elements->find(*_listIter));
        return (_currentPair);
}
 
template<class Key, class T>
typename
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>::pointer
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>::operator->()
    const
{
        _currentPair = *(_orderedMap->_elements->find(*_listIter));
        return (&_currentPair);
}
 
template<class Key, class T>
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>&
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>::operator++()
{
        ++_listIter;
        return (*this);
}
 
template<class Key, class T>
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>::operator++(
    int)
{
        OrderedMapConstIterator previousIterator(*this);
        ++(*this);
        return (previousIterator);
}
 
template<class Key, class T>
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>&
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>::operator--()
{
        --_listIter;
        return (*this);
}
 
template<class Key, class T>
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>::operator--(
    int)
{
        OrderedMapConstIterator previousIterator(*this);
        --(*this);
        return (previousIterator);
}
 
template<class Key, class T>
bool
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>::operator==(
    const OrderedMapConstIterator &rhs)
    const
{
        return ((_orderedMap == rhs._orderedMap) &&
            (_listIter == rhs._listIter));
}
 
template<class Key, class T>
bool
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>::operator!=(
    const OrderedMapConstIterator &rhs)
    const
{
        return (!(this->operator==(rhs)));
}
 
template<class Key, class T>
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>::
OrderedMapConstIterator(
    const OrderedMapIterator<Key, T> &iterator) :
    _orderedMap(iterator._orderedMap),
    _listIter(iterator._listIter),
    _currentPair(iterator._currentPair)
{
 
}
 
template<class Key, class T>
BiometricEvaluation::Memory::OrderedMapConstIterator<Key, T>::
~OrderedMapConstIterator()
{
        /* Don't delete _orderedMap, we don't own it. */ 
}
 
#endif /* __ORDERED_MAP_H__ */