michael@0: /*
michael@0:  * Copyright 2014 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: #ifndef GrOrderedSet_DEFINED
michael@0: #define GrOrderedSet_DEFINED
michael@0: 
michael@0: #include "GrRedBlackTree.h"
michael@0: 
michael@0: template <typename T, typename C = GrLess<T> >
michael@0: class GrOrderedSet : public SkNoncopyable {
michael@0: public:
michael@0:     /**
michael@0:      * Creates an empty set
michael@0:      */
michael@0:     GrOrderedSet() : fComp() {}
michael@0:     ~GrOrderedSet() {}
michael@0: 
michael@0:     class Iter;
michael@0: 
michael@0:     /**
michael@0:      * @return true if there are no items in the set, false otherwise.
michael@0:      */
michael@0:     bool empty() const { return fRBTree.empty(); }
michael@0: 
michael@0:     /**
michael@0:      * @return the number of items in the set.
michael@0:      */
michael@0:     int count() const { return fRBTree.count(); }
michael@0: 
michael@0:     /**
michael@0:      * Removes all items in the set
michael@0:      */
michael@0:     void reset() { fRBTree.reset(); }
michael@0: 
michael@0:     /**
michael@0:      * Adds an element to set if it does not already exists in the set.
michael@0:      * @param t  the item to add
michael@0:      * @return an iterator to added element or matching element already in set
michael@0:      */
michael@0:     Iter insert(const T& t);
michael@0: 
michael@0:     /**
michael@0:      * Removes the item indicated by an iterator. The iterator will not be valid
michael@0:      * afterwards.
michael@0:      * @param iter      iterator of item to remove. Must be valid (not end()).
michael@0:      */
michael@0:     void remove(const Iter& iter);
michael@0: 
michael@0:     /**
michael@0:      * @return  an iterator to the first item in sorted order, or end() if empty
michael@0:      */
michael@0:     Iter begin();
michael@0: 
michael@0:     /**
michael@0:      * Gets the last valid iterator. This is always valid, even on an empty.
michael@0:      * However, it can never be dereferenced. Useful as a loop terminator.
michael@0:      * @return  an iterator that is just beyond the last item in sorted order.
michael@0:      */
michael@0:     Iter end();
michael@0: 
michael@0:     /**
michael@0:      * @return  an iterator that to the last item in sorted order, or end() if
michael@0:      * empty.
michael@0:      */
michael@0:     Iter last();
michael@0: 
michael@0:     /**
michael@0:      * Finds an occurrence of an item.
michael@0:      * @param t     the item to find.
michael@0:      * @return an iterator to a set element equal to t or end() if none exists.
michael@0:      */
michael@0:     Iter find(const T& t);
michael@0: 
michael@0: private:
michael@0:     GrRedBlackTree<T, C> fRBTree;
michael@0: 
michael@0:     const C fComp;
michael@0: };
michael@0: 
michael@0: template <typename T, typename C>
michael@0: class GrOrderedSet<T,C>::Iter {
michael@0: public:
michael@0:     Iter() {}
michael@0:     Iter(const Iter& i) { fTreeIter = i.fTreeIter; }
michael@0:     Iter& operator =(const Iter& i) {
michael@0:         fTreeIter = i.fTreeIter;
michael@0:         return *this;
michael@0:     }
michael@0:     const T& operator *() const { return *fTreeIter; }
michael@0:     bool operator ==(const Iter& i) const {
michael@0:         return fTreeIter == i.fTreeIter;
michael@0:     }
michael@0:     bool operator !=(const Iter& i) const { return !(*this == i); }
michael@0:     Iter& operator ++() {
michael@0:         ++fTreeIter;
michael@0:         return *this;
michael@0:     }
michael@0:     Iter& operator --() {
michael@0:         --fTreeIter;
michael@0:         return *this;
michael@0:     }
michael@0:     const typename GrRedBlackTree<T,C>::Iter& getTreeIter() const {
michael@0:         return fTreeIter;
michael@0:     }
michael@0: 
michael@0: private:
michael@0:     friend class GrOrderedSet;
michael@0:     explicit Iter(typename GrRedBlackTree<T, C>::Iter iter) {
michael@0:         fTreeIter = iter;
michael@0:     }
michael@0:     typename GrRedBlackTree<T,C>::Iter fTreeIter;
michael@0: };
michael@0: 
michael@0: template <typename T, typename C>
michael@0: typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::begin() {
michael@0:     return Iter(fRBTree.begin());
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::end() {
michael@0:     return Iter(fRBTree.end());
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::last() {
michael@0:     return Iter(fRBTree.last());
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::find(const T& t) {
michael@0:     return Iter(fRBTree.find(t));
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::insert(const T& t) {
michael@0:     if (fRBTree.find(t) == fRBTree.end()) {
michael@0:         return Iter(fRBTree.insert(t));
michael@0:     } else {
michael@0:         return Iter(fRBTree.find(t));
michael@0:     }
michael@0: }
michael@0: 
michael@0: template <typename T, typename C>
michael@0: void GrOrderedSet<T,C>::remove(const typename GrOrderedSet<T,C>::Iter& iter) {
michael@0:     if (this->end() != iter) {
michael@0:         fRBTree.remove(iter.getTreeIter());
michael@0:     }
michael@0: }
michael@0: 
michael@0: #endif