---

key_mutable_set.h

Go to the documentation of this file.

#include <set>

template <class T> class MutableShell {
    mutable T t;
public:
    MutableShell (const T &t) : t(t) {}
    T &get ()const {return t;}
    T &operator* ()const {return t;}
    T *operator-> ()const {return &t;}
    operator T& () const {return t;}
    bool operator< (const MutableShell <T>& other) const {return t<other.t;}
};

template <class T, class _Compare = std::less <MutableShell<T> > >
class MutableSet: public std::multiset <MutableShell<T>,_Compare> {
    typedef std::multiset <MutableShell<T>,_Compare> SUPER;
};

template <class T> class KeyMutableShell {
    mutable T *t;
public:
    KeyMutableShell (T *t) :t(t) {}
    T &get ()const {return *t;}
    T &operator* ()const {return *t;}
    T *operator-> ()const {return t;}
    operator T* () const {return t;}
    bool operator< (const KeyMutableShell <T>& other) const {return (*t)<(*other.t);}
};


template <class Key, class T, class _Compare = std::less <KeyMutableShell<T> > >
class KeyMutableSet : public std::multiset <KeyMutableShell<T>,_Compare> {
    typedef std::multiset <KeyMutableShell<T>,_Compare> SUPER;
    T &valueFromKey (const Key &key) {
        static T t;
        t.changeKey(key);
        return t;
    }
public:
    typename SUPER::iterator find (T &key) {
    return SUPER::find(KeyMutableShell<T>(&key));
    }
    typename SUPER::iterator find (const Key &key) {
        return find(valueFromKey(key));
    }
    typename SUPER::iterator lower_bound (T &key) {
        return SUPER::lower_bound(KeyMutableShell<T>(&key));
    }
    typename SUPER::iterator lower_bound (const Key &key) {
        return lower_bound(valueFromKey(key));
    }
    typename SUPER::iterator upper_bound (T &key) {
        return SUPER::upper_bound(KeyMutableShell<T>(&key));
    }
    typename SUPER::iterator upper_bound (const Key &key) {
        return upper_bound(valueFromKey(key));
    }
    void checkSet () {
        _Compare comparator;
        if (begin()!=end()) {
            for (typename SUPER::iterator newiter=begin(), iter=newiter++;newiter!=end();iter=newiter++) {
                if (comparator(*newiter,*iter)) { //greater than
                    printf("ERROR: keys out of order!!!!!!\n");
                }
            }
        }
    }

    typename SUPER::iterator changeKey (typename SUPER::iterator iter, const Key & newKey) {
        typename SUPER::iterator templess=iter,tempmore=iter;
        tempmore++;
        if (templess!=begin())
            templess--;
        _Compare comparator;
        KeyMutableShell<T> newKeyShell(&valueFromKey(newKey));
        bool endOutOfOrder=false;
        if (tempmore!=end()) {
            endOutOfOrder=comparator(*tempmore,newKeyShell);
        }
        if (comparator(newKeyShell,*templess)||endOutOfOrder) {
            KeyMutableShell<T> k = *iter;
            erase(iter);
            k->changeKey(newKey);
            insert (k);
        }else {
            (*iter)->changeKey(newKey);
        }
        //checkSet();
        return tempmore;
    }
};

---