---

more/gen/degenerate_map.h

Go to the documentation of this file.

//  Copyright (C) 2000--2002  Petter Urkedal
//
//  This file is free software; you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation; either version 2 of the License, or
//  (at your option) any later version.
//
//  This file 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 General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
//  As a special exception, you may use this file as part of a free
//  software library without restriction.  Specifically, if other files
//  instantiate templates or use macros or inline functions from this
//  file, or you compile this file and link it with other files to
//  produce an executable, this file does not by itself cause the
//  resulting executable to be covered by the GNU General Public
//  License.  This exception does not however invalidate any other
//  reasons why the executable file might be covered by the GNU General
//  Public License.
//
//  $Id: degenerate_map.h,v 1.2 2002/08/24 13:57:08 petter_urkedal Exp $


#ifndef MORE_GEN_DEGENERATE_MAP_H
#define MORE_GEN_DEGENERATE_MAP_H


#include <more/gen/utility.h>
#include <functional>
#include <more/gen/iterator.h>
#include <set>


namespace more {
namespace gen {

  /** \class degenerate_map degenerate_map.h more/gen/degenerate_map.h
   ** A map with degenerate values.  The degeneracy of an element is
   ** defined as the number of insertions minus the number of erases
   ** of the element or keys which is equal to its key according to
   ** the given comparison functional. */
  template< typename Key, typename Data,
            typename Compare = std::less<Key> >
    struct degenerate_map
    {

        typedef Key key_type;
        typedef Data mapped_type;
        typedef std::pair<const key_type, mapped_type> value_type;
        typedef Compare key_compare;
        typedef std::size_t size_type;

    private:
        class selector;
        class sub_key_compare;

        struct value_compare
            : std::binary_function<value_type, value_type, bool>
        {
            value_compare() {}

            value_compare(key_compare const& keycomp_)
                : keycomp(keycomp_) {}

            value_compare(value_compare const& vcomp)
                : keycomp(vcomp.keycomp) {}

            bool operator()(value_type const& x, value_type const& y) const
            {
                return key_compare()(x.first, y.first);
            }

          private:
            key_compare keycomp;
        };

        struct sub_value_type
        {
            explicit sub_value_type(key_type const& k)
                : value(k, mapped_type()) {}
            sub_value_type(value_type const& val, size_type deg)
                : value(val), degeneracy(deg) {}
            sub_value_type(sub_value_type const& sub)
                : value(sub.value), degeneracy(sub.degeneracy) {}

            sub_value_type& operator=(sub_value_type const& sub)
            {
                const_cast<key_type&>(value.first) = sub.value.first;
                value.second = sub.value.second;
                degeneracy = sub.degeneracy;
                return *this;
            }

            bool operator==(sub_value_type const& rhs) const
            {
                return degeneracy == rhs.degeneracy
                    && value == rhs.value;
            }

            bool operator!=(sub_value_type const& rhs) const
            {
                return degeneracy != rhs.degeneracy
                    || value != rhs.value;
            }

            bool operator<(sub_value_type const& rhs) const
            {
                return value < rhs.value
                    || (value == rhs.value && degeneracy < rhs.degeneracy);
            }

          private:
            mutable value_type value;
//          mutable std::pair<key_type, mapped_type> value;
            mutable size_type degeneracy;
            friend class degenerate_map;
            friend class selector;
            friend class sub_key_compare;
        };

        struct sub_key_compare
        {
            sub_key_compare() {}
            sub_key_compare(sub_key_compare const& comp)
                : subcomp(comp.subcomp) {}
            sub_key_compare(key_compare const& kc)
                : subcomp(kc) {}

            bool operator()(sub_value_type const& x,
                            sub_value_type const& y) const
            {
                return subcomp(x.value.first, y.value.first);
            }

          private:
            key_compare subcomp;
        };

        typedef std::set<sub_value_type, sub_key_compare> container;
        typedef typename container::iterator sub_iterator;
        typedef typename container::reverse_iterator
                reverse_sub_iterator;

        struct selector : std::unary_function<sub_value_type, value_type>
        {
            value_type& operator()(sub_value_type const& x) const
            {
                return x.value;
            }
        };

    public:
        typedef transforming_iterator<sub_iterator, selector>
                const_iterator;
        typedef transforming_iterator<reverse_sub_iterator, selector>
                const_reverse_iterator;
        typedef const_iterator iterator;
        typedef const_reverse_iterator reverse_iterator;
        typedef value_type& reference;
        typedef const value_type& const_reference;
        typedef value_type* pointer;
        typedef typename container::difference_type difference_type;
        typedef typename container::size_type size_type;

        degenerate_map() {}
        degenerate_map(degenerate_map const& x)
            : S(x.S) {}
        degenerate_map(key_compare const& comp)
            : S(sub_key_compare(comp)) {}
        degenerate_map& operator=(degenerate_map const& rhs) {
            S = rhs.S;
            return *this;
        }

//      template<typename InputIterator>
//        degenerate_map(InputIterator it, InputIterator it_end)
//          { insert(it, it_end); }

        bool operator==(degenerate_map const& rhs) const { return S == rhs.S; }
        bool operator!=(degenerate_map const& rhs) const { return S != rhs.S; }
        bool operator<(degenerate_map const& rhs) const { return S < rhs.S; }
        bool operator<=(degenerate_map const& rhs) const { return S <= rhs.S; }
        bool operator>(degenerate_map const& rhs) const { return S > rhs.S; }
        bool operator>=(degenerate_map const& rhs) const { return S >= rhs.S; }

        iterator begin() const { return iterator(S.begin()); }
        iterator end() const { return iterator(S.end()); }
        reverse_iterator rbegin() const
            { return reverse_iterator(S.rbegin()); }
        reverse_iterator rend() const
            { return reverse_iterator(S.rend()); }

        size_type size() const { return S.size(); }
        size_type max_size() const { return S.max_size(); }
        size_type empty() const { return S.empty(); }
        key_compare key_comp() const { return S.key_comp().subcomp; }
        value_compare value_comp() const { return S.key_comp().subcomp; }
        void swap(degenerate_map& x) { S.swap(x.S); }

        /** Insert \c x into the set. \return A pair of the iterator
         ** to the value, and the degeneracy of the value before the
         ** insertion. */
        std::pair<iterator, size_type>
        insert(const value_type& x)
        {
            sub_iterator it = S.find(sub_value_type(x.first));
            if (it == S.end()) {
                std::pair<sub_iterator, bool> p
                    = S.insert(sub_value_type(x, 1));
                return std::make_pair(iterator(p.first), 0);
            } else
                return std::make_pair(iterator(it), it->degeneracy++);
        }

        /** Insert with hint. */
        std::pair<iterator, bool>
        insert(iterator hint, const value_type& x)
        {
            return insert(x);
        }

        /** Increase the degneracy of \c it. \pre \c it must be a
         ** valid iterator pointing into this container. */
        std::pair<iterator, size_type>
        insert(iterator it)
        {
            return std::make_pair(it, it.sub_iterator()->degeneracy++);
        }

//      template<typename InputIterator>
//      void insert(InputIterator it, InputIterator it_end) {
//          while (it != it_end) { insert(*it); ++it; }
//      }

        /** Decrease the degeneracy of \c it, and remove if zero. \pre
         ** it must be a valid iterator in this container. */
        void erase(iterator it)
        {
            sub_iterator it0 = it.sub_iterator();
            if (--(*it0).degeneracy <= 0) S.erase(it0);
        }

        /** Erase a range of iterators. */
        void erase(iterator it, iterator it_end)
        {
            while (it != it_end) {
                erase(it);
                ++it;
            }
        }

        /** Sink the degeneracy of \c k, and remove if zero. */
        size_type erase(key_type const& k)
        {
            iterator it = find(k);
            if (it == end())
                return 0;
            else {
                erase(it);
                return 1;
            }
        }

        iterator find(key_type const& k) const
        {
            sub_iterator it = S.find(sub_value_type(k));
            return iterator(it);
        }

        size_type count(key_type const& k) const { return S.count(k); }

        size_type degeneracy(iterator it) const
        {
            return (*it.sub_iterator()).degeneracy;
        }

        size_type degeneracy(key_type const& k) const
        {
            sub_iterator it = S.find(sub_value_type(k));
            if (it == S.end())
                return 0;
            else
                return (*it).degeneracy;
        }

        iterator lower_bound(const key_type& k) const
        {
            return iterator(S.lower_bound(k));
        }

        iterator upper_bound(const key_type& k) const
        {
            return iterator(S.upper_bound(k));
        }

        std::pair<iterator, iterator>
        equal_range(key_type const& k) const
        {
            std::pair<sub_iterator, sub_iterator> p = S.equal_range(k);
            return std::make_pair(iterator(p.first), iterator(p.second));
        }

      private:
        mutable container S;
    };
}} // more::gen

#endif

---