Home | History | Annotate | Download | only in gpu 
      1 /*
      2  * Copyright 2014 Google Inc.
      3  *
      4  * Use of this source code is governed by a BSD-style license that can be
      5  * found in the LICENSE file.
      6  */
      7 
      8 #ifndef GrOrderedSet_DEFINED
      9 #define GrOrderedSet_DEFINED
     10 
     11 #include "GrRedBlackTree.h"
     12 
     13 template <typename T, typename C = GrLess<T> >
     14 class GrOrderedSet : SkNoncopyable {
     15 public:
     16     /**
     17      * Creates an empty set
     18      */
     19     GrOrderedSet() : fComp() {}
     20     ~GrOrderedSet() {}
     21 
     22     class Iter;
     23 
     24     /**
     25      * @return true if there are no items in the set, false otherwise.
     26      */
     27     bool empty() const { return fRBTree.empty(); }
     28 
     29     /**
     30      * @return the number of items in the set.
     31      */
     32     int count() const { return fRBTree.count(); }
     33 
     34     /**
     35      * Removes all items in the set
     36      */
     37     void reset() { fRBTree.reset(); }
     38 
     39     /**
     40      * Adds an element to set if it does not already exists in the set.
     41      * @param t  the item to add
     42      * @return an iterator to added element or matching element already in set
     43      */
     44     Iter insert(const T& t);
     45 
     46     /**
     47      * Removes the item indicated by an iterator. The iterator will not be valid
     48      * afterwards.
     49      * @param iter      iterator of item to remove. Must be valid (not end()).
     50      */
     51     void remove(const Iter& iter);
     52 
     53     /**
     54      * @return  an iterator to the first item in sorted order, or end() if empty
     55      */
     56     Iter begin();
     57 
     58     /**
     59      * Gets the last valid iterator. This is always valid, even on an empty.
     60      * However, it can never be dereferenced. Useful as a loop terminator.
     61      * @return  an iterator that is just beyond the last item in sorted order.
     62      */
     63     Iter end();
     64 
     65     /**
     66      * @return  an iterator that to the last item in sorted order, or end() if
     67      * empty.
     68      */
     69     Iter last();
     70 
     71     /**
     72      * Finds an occurrence of an item.
     73      * @param t     the item to find.
     74      * @return an iterator to a set element equal to t or end() if none exists.
     75      */
     76     Iter find(const T& t);
     77 
     78 private:
     79     GrRedBlackTree<T, C> fRBTree;
     80 
     81     const C fComp;
     82 };
     83 
     84 template <typename T, typename C>
     85 class GrOrderedSet<T,C>::Iter {
     86 public:
     87     Iter() {}
     88     Iter(const Iter& i) { fTreeIter = i.fTreeIter; }
     89     Iter& operator =(const Iter& i) {
     90         fTreeIter = i.fTreeIter;
     91         return *this;
     92     }
     93     const T& operator *() const { return *fTreeIter; }
     94     bool operator ==(const Iter& i) const {
     95         return fTreeIter == i.fTreeIter;
     96     }
     97     bool operator !=(const Iter& i) const { return !(*this == i); }
     98     Iter& operator ++() {
     99         ++fTreeIter;
    100         return *this;
    101     }
    102     Iter& operator --() {
    103         --fTreeIter;
    104         return *this;
    105     }
    106     const typename GrRedBlackTree<T,C>::Iter& getTreeIter() const {
    107         return fTreeIter;
    108     }
    109 
    110 private:
    111     friend class GrOrderedSet;
    112     explicit Iter(typename GrRedBlackTree<T, C>::Iter iter) {
    113         fTreeIter = iter;
    114     }
    115     typename GrRedBlackTree<T,C>::Iter fTreeIter;
    116 };
    117 
    118 template <typename T, typename C>
    119 typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::begin() {
    120     return Iter(fRBTree.begin());
    121 }
    122 
    123 template <typename T, typename C>
    124 typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::end() {
    125     return Iter(fRBTree.end());
    126 }
    127 
    128 template <typename T, typename C>
    129 typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::last() {
    130     return Iter(fRBTree.last());
    131 }
    132 
    133 template <typename T, typename C>
    134 typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::find(const T& t) {
    135     return Iter(fRBTree.find(t));
    136 }
    137 
    138 template <typename T, typename C>
    139 typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::insert(const T& t) {
    140     if (fRBTree.find(t) == fRBTree.end()) {
    141         return Iter(fRBTree.insert(t));
    142     } else {
    143         return Iter(fRBTree.find(t));
    144     }
    145 }
    146 
    147 template <typename T, typename C>
    148 void GrOrderedSet<T,C>::remove(const typename GrOrderedSet<T,C>::Iter& iter) {
    149     if (this->end() != iter) {
    150         fRBTree.remove(iter.getTreeIter());
    151     }
    152 }
    153 
    154 #endif
    155