Add GrSet class built on top of RedBlackTree

src/gpu/GrSet.h

+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef GrSet_DEFINED
+#define GrSet_DEFINED
+
+#include "GrRedBlackTree.h"
+
+template <typename T, typename C = GrLess<T> >
+class GrSet : public SkNoncopyable {
+public:
+    /**
+     * Creates an empty set
+     */
+    GrSet() : fComp() {}
+    virtual ~GrSet() {}

[bsalomon, 2014/02/26 21:56:09]

If this guy has no other virtual functions we should probably not force a vtable
on him.

+
+    class Iter;
+
+    /**
+     * @return true if there are no items in the set, false otherwise.
+     */
+    bool empty() const {return fRBTree.empty();}

[bsalomon, 2014/02/26 21:56:09]

I think we usually do have spaces inside the braces, { return fRBTree.empty() }

+
+    /**
+     * @return the number of items in the set.
+     */
+    int count() const {return fRBTree.count();}
+
+    /**
+     * Removes all items in the set
+     */
+    void reset() {fRBTree.reset();}
+
+    /**
+     * Adds an element to set if it does not already exists in the set.
+     * @param t  the item to add
+     * @return an iterator to added element or matching element already in set
+     */
+    Iter insert(const T& t);
+
+    /**
+     * Removes the item indicated by an iterator. The iterator will not be valid
+     * afterwards.
+     * @param iter      iterator of item to remove. Must be valid (not end()).
+     */
+    void remove(const Iter& iter);
+
+    /**
+     * @return  an iterator to the first item in sorted order, or end() if empty
+     */
+    Iter begin();
+
+    /**
+     * Gets the last valid iterator. This is always valid, even on an empty.
+     * However, it can never be dereferenced. Useful as a loop terminator.
+     * @return  an iterator that is just beyond the last item in sorted order.
+     */
+    Iter end();
+
+    /**
+     * @return  an iterator that to the last item in sorted order, or end() if
+     * empty.
+     */
+    Iter last();
+
+    /**
+     * Finds an occurrence of an item.
+     * @param t     the item to find.
+     * @return an iterator to a set element equal to t or end() if none exists.
+     */
+    Iter find(const T& t);
+
+private:
+    GrRedBlackTree<T, C> fRBTree;
+
+    const C fComp;
+};
+
+template <typename T, typename C>
+class GrSet<T,C>::Iter {
+public:
+    Iter() {}
+    Iter(const Iter& i) {fTreeIter = i.fTreeIter;}
+    Iter& operator =(const Iter& i) {
+        fTreeIter = i.fTreeIter;
+        return *this;
+    }
+    T& operator *() const { return *fTreeIter; }

[bsalomon, 2014/02/26 21:56:09]

Any thoughts on the danger of allowing the user of the iterator to modify the T
object and thereby break the sorted order?

+    bool operator ==(const Iter& i) const {
+        return fTreeIter == i.fTreeIter;
+    }
+    bool operator !=(const Iter& i) const { return !(*this == i); }
+    Iter& operator ++() {
+        ++fTreeIter;
+        return *this;
+    }
+    Iter& operator --() {
+        --fTreeIter;
+        return *this;
+    }
+    const typename GrRedBlackTree<T,C>::Iter& getTreeIter() const {
+        return fTreeIter;
+    }
+
+private:
+    friend class GrSet;
+    explicit Iter(typename GrRedBlackTree<T, C>::Iter iter) {
+        fTreeIter = iter;
+    }
+    typename GrRedBlackTree<T,C>::Iter fTreeIter;
+};
+
+template <typename T, typename C>
+typename GrSet<T,C>::Iter GrSet<T,C>::begin() {
+    return Iter(fRBTree.begin());
+}
+
+template <typename T, typename C>
+typename GrSet<T,C>::Iter GrSet<T,C>::end() {
+    return Iter(fRBTree.end());
+}
+
+template <typename T, typename C>
+typename GrSet<T,C>::Iter GrSet<T,C>::last() {
+    return Iter(fRBTree.last());
+}
+
+template <typename T, typename C>
+typename GrSet<T,C>::Iter GrSet<T,C>::find(const T& t) {
+    return Iter(fRBTree.find(t));
+}
+
+template <typename T, typename C>
+typename GrSet<T,C>::Iter GrSet<T,C>::insert(const T& t) {
+    if (fRBTree.find(t) == fRBTree.end()) {
+        return Iter(fRBTree.insert(t));
+    } else {
+        return Iter(fRBTree.find(t));
+    }
+}
+
+template <typename T, typename C>
+void GrSet<T,C>::remove(const typename GrSet<T,C>::Iter& iter) {
+    if (this->end() != iter) {
+        fRBTree.remove(iter.getTreeIter());
+    }
+}
+
+#endif
+