source: src/GenPoly/ScopedMap.h@ b542bfb

//
// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// ScopedMap.h --
//
// Author           : Aaron B. Moss
// Created On       : Wed Dec 2 11:37:00 2015
// Last Modified By : Aaron B. Moss
// Last Modified On : Wed Dec 2 11:37:00 2015
// Update Count     : 1
//

#ifndef _SCOPEDMAP_H
#define _SCOPEDMAP_H

#include <cassert>
#include <iterator>
#include <map>
#include <utility>
#include <vector>

namespace GenPoly {
        /// A map where the items are placed into nested scopes;
        /// inserted items are placed into the innermost scope, lookup looks from the innermost scope outward
        template<typename Key, typename Value>
        class ScopedMap {
                typedef std::map< Key, Value > Scope;
                typedef std::vector< Scope > ScopeList;

                ScopeList scopes; ///< scoped list of maps
        public:
                typedef typename Scope::key_type key_type;
                typedef typename Scope::mapped_type mapped_type;
                typedef typename Scope::value_type value_type;
                typedef typename ScopeList::size_type size_type;
                typedef typename ScopeList::difference_type difference_type;
                typedef typename Scope::reference reference;
                typedef typename Scope::const_reference const_reference;
                typedef typename Scope::pointer pointer;
                typedef typename Scope::const_pointer const_pointer;

                class iterator : public std::iterator< std::bidirectional_iterator_tag,
                                                       value_type > {
                friend class ScopedMap;
                friend class const_iterator;
                        typedef typename std::map< Key, Value >::iterator wrapped_iterator;
                        typedef typename std::vector< std::map< Key, Value > > scope_list;
                        typedef typename scope_list::size_type size_type;

                        /// Checks if this iterator points to a valid item
                        bool is_valid() const {
                                return it != (*scopes)[i].end();
                        }

                        /// Increments on invalid
                        iterator& next_valid() {
                                if ( ! is_valid() ) { ++(*this); }
                                return *this;
                        }

                        /// Decrements on invalid
                        iterator& prev_valid() {
                                if ( ! is_valid() ) { --(*this); }
                                return *this;
                        }

                        iterator(scope_list &_scopes, const wrapped_iterator &_it, size_type _i)
                                : scopes(&_scopes), it(_it), i(_i) {}
                public:
                        iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
                        iterator& operator= (const iterator &that) {
                                scopes = that.scopes; i = that.i; it = that.it;
                                return *this;
                        }

                        reference operator* () { return *it; }
                        pointer operator-> () { return it.operator->(); }

                        iterator& operator++ () {
                                if ( it == (*scopes)[i].end() ) {
                                        if ( i == 0 ) return *this;
                                        --i;
                                        it = (*scopes)[i].begin();
                                } else {
                                        ++it;
                                }
                                return next_valid();
                        }
                        iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }

                        iterator& operator-- () {
                                // may fail if this is the begin iterator; allowed by STL spec
                                if ( it == (*scopes)[i].begin() ) {
                                        ++i;
                                        it = (*scopes)[i].end();
                                }
                                --it;
                                return prev_valid();
                        }
                        iterator operator-- (int) { iterator tmp = *this; --(*this); return tmp; }

                        bool operator== (const iterator &that) {
                                return scopes == that.scopes && i == that.i && it == that.it;
                        }
                        bool operator!= (const iterator &that) { return !( *this == that ); }

                private:
                        scope_list *scopes;
                        wrapped_iterator it;
                        size_type i;
                };

                class const_iterator : public std::iterator< std::bidirectional_iterator_tag,
                                                             value_type > {
                friend class ScopedMap;
                        typedef typename std::map< Key, Value >::iterator wrapped_iterator;
                        typedef typename std::map< Key, Value >::const_iterator wrapped_const_iterator;
                        typedef typename std::vector< std::map< Key, Value > > scope_list;
                        typedef typename scope_list::size_type size_type;

                        /// Checks if this iterator points to a valid item
                        bool is_valid() const {
                                return it != (*scopes)[i].end();
                        }

                        /// Increments on invalid
                        const_iterator& next_valid() {
                                if ( ! is_valid() ) { ++(*this); }
                                return *this;
                        }

                        /// Decrements on invalid
                        const_iterator& prev_valid() {
                                if ( ! is_valid() ) { --(*this); }
                                return *this;
                        }

                        const_iterator(scope_list const &_scopes, const wrapped_const_iterator &_it, size_type _i)
                                : scopes(&_scopes), it(_it), i(_i) {}
                public:
                        const_iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
                        const_iterator(const const_iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
                        const_iterator& operator= (const iterator &that) {
                                scopes = that.scopes; i = that.i; it = that.it;
                                return *this;
                        }
                        const_iterator& operator= (const const_iterator &that) {
                                scopes = that.scopes; i = that.i; it = that.it;
                                return *this;
                        }

                        const_reference operator* () { return *it; }
                        const_pointer operator-> () { return it.operator->(); }

                        const_iterator& operator++ () {
                                if ( it == (*scopes)[i].end() ) {
                                        if ( i == 0 ) return *this;
                                        --i;
                                        it = (*scopes)[i].begin();
                                } else {
                                        ++it;
                                }
                                return next_valid();
                        }
                        const_iterator operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; }

                        const_iterator& operator-- () {
                                // may fail if this is the begin iterator; allowed by STL spec
                                if ( it == (*scopes)[i].begin() ) {
                                        ++i;
                                        it = (*scopes)[i].end();
                                }
                                --it;
                                return prev_valid();
                        }
                        const_iterator operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; }

                        bool operator== (const const_iterator &that) {
                                return scopes == that.scopes && i == that.i && it == that.it;
                        }
                        bool operator!= (const const_iterator &that) { return !( *this == that ); }

                private:
                        scope_list const *scopes;
                        wrapped_const_iterator it;
                        size_type i;
                };

                /// Starts a new scope
                void beginScope() {
                        scopes.emplace_back();
                }

                /// Ends a scope; invalidates any iterators pointing to elements of that scope
                void endScope() {
                        scopes.pop_back();
                        assert( ! scopes.empty() );
                }

                /// Default constructor initializes with one scope
                ScopedMap() { beginScope(); }

                iterator begin() { return iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
                const_iterator begin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
                const_iterator cbegin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
                iterator end() { return iterator(scopes, scopes[0].end(), 0); }
                const_iterator end() const { return const_iterator(scopes, scopes[0].end(), 0); }
                const_iterator cend() const { return const_iterator(scopes, scopes[0].end(), 0); }

                /// Gets the index of the current scope (counted from 1)
                size_type currentScope() const { return scopes.size(); }

                /// Finds the given key in the outermost scope it occurs; returns end() for none such
                iterator find( const Key &key ) {
                        for ( size_type i = scopes.size() - 1; ; --i ) {
                                typename Scope::iterator val = scopes[i].find( key );
                                if ( val != scopes[i].end() ) return iterator( scopes, val, i );
                                if ( i == 0 ) break;
                        }
                        return end();
                }
                const_iterator find( const Key &key ) const {
                                return const_iterator( const_cast< ScopedMap< Key, Value >* >(this)->find( key ) );
                }

                /// Finds the given key in the outermost scope inside the given scope where it occurs
                iterator findNext( const_iterator &it, const Key &key ) {
                        if ( it.i == 0 ) return end();
                        for ( size_type i = it.i - 1; ; --i ) {
                                typename Scope::iterator val = scopes[i].find( key );
                                if ( val != scopes[i].end() ) return iterator( scopes, val, i );
                                if ( i == 0 ) break;
                        }
                        return end();
                }
                const_iterator findNext( const_iterator &it, const Key &key ) const {
                                return const_iterator( const_cast< ScopedMap< Key, Value >* >(this)->findNext( it, key ) );
                }

                /// Inserts the given key-value pair into the outermost scope
                std::pair< iterator, bool > insert( const value_type &value ) {
                        std::pair< typename Scope::iterator, bool > res = scopes.back().insert( value );
                        return std::make_pair( iterator(scopes, res.first, scopes.size()-1), res.second );
                }

                std::pair< iterator, bool > insert( value_type &&value ) {
                        std::pair< typename Scope::iterator, bool > res = scopes.back().insert( std::move( value ) );
                        return std::make_pair( iterator(scopes, std::move( res.first ), scopes.size()-1), std::move( res.second ) );
                }

                std::pair< iterator, bool > insert( const Key &key, const Value &value ) { return insert( std::make_pair( key, value ) ); }
                std::pair< iterator, bool > insert( const Key &key, Value &&value ) { return insert( std::make_pair( key, std::move( value ) ) ); }

                Value& operator[] ( const Key &key ) {
                        iterator slot = find( key );
                        if ( slot != end() ) return slot->second;
                        return insert( key, Value() ).first->second;
                }

                iterator erase( iterator pos ) {
                        Scope& scope = (*pos.scopes) [ pos.i ];
                        const typename iterator::wrapped_iterator& new_it = scope.erase( pos.it );
                        iterator it( *pos.scopes, new_it, pos.i );
                        return it.next_valid();
                }

                size_type count( const Key &key ) const {
                        size_type c = 0;
                        auto it = find( key );
                        auto end = cend();

                        while(it != end) {
                                c++;
                                it = findNext(it, key);
                        }

                        return c;
                }

        };
} // namespace GenPoly

#endif // _SCOPEDMAP_H

// Local Variables: //
// tab-width: 4 //
// mode: c++ //
// compile-command: "make install" //
// End: //