---

more/gen/degenerate_set.h

Go to the documentation of this file.

//  Copyright (C) 2001  Petter Urkedal (petter.urkedal@matfys.lth.se)
//
//  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_set.h,v 1.1 2002/05/30 18:01:37 petter_urkedal Exp $


#ifndef MORE_GEN_DEGENERATE_SET_H
#define MORE_GEN_DEGENETATE_SET_H


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


namespace more {
namespace gen {

  /** \class degenerate_set degenerate_set.h more/gen/degenerate_set.h
   ** A set which supports degenerate elements.  The degeneracy of an
   ** element is defined as the number of insertions minus the number
   ** of erases of the element or values which is equal to it
   ** according to the given comparison functional. */
  template< typename Key, typename Compare = std::less<Key> >
    struct degenerate_set
    {
        typedef Key key_type;
        typedef Key value_type;
        typedef Compare key_compare;
        typedef Compare value_compare;
        typedef std::size_t size_type;

    private:
        class selector;
        class sub_key_compare;

        struct sub_value_type
        {
            explicit sub_value_type(key_type const& k)
                : value(k) {}

            sub_value_type(value_type const& val, size_type deg)
                : value(val), degeneracy(deg) {}

            sub_value_type(sub_value_type const& x)
                : value(x.value), degeneracy(x.degeneracy) {}

            sub_value_type& operator=(sub_value_type const& x)
            {
                value = x.value;
                degeneracy = x.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:
            value_type value;
            mutable size_type degeneracy;
            friend class degenerate_set;
            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, y.value);
            }

          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, const value_type>
        {
            value_type const& 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_set() {}
        degenerate_set(degenerate_set const& x)
            : S(x.S) {}
        degenerate_set(key_compare const& kc)
            : S(sub_key_compare(kc)) {}
        degenerate_set& operator=(degenerate_set const& rhs) {
            S = rhs.S;
            return *this;
        }

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

//      template<typename InputIterator>
//        degenerate_set(InputIterator it, InputIterator it_end,
//                       key_compare const& kc)
//            : S(sub_key_compare(kc)) {
//            insert(it, it_end);
//        }

        bool operator==(degenerate_set const& rhs) const { return S == rhs.S; }
        bool operator!=(degenerate_set const& rhs) const { return S != rhs.S; }
        bool operator<(degenerate_set const& rhs) const { return S < rhs.S; }
        bool operator<=(degenerate_set const& rhs) const { return S <= rhs.S; }
        bool operator>(degenerate_set const& rhs) const { return S > rhs.S; }
        bool operator>=(degenerate_set 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_set& 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));
            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, size_type>
        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

---