commit-bot@chromium.org | 4fcc3ca | 2014-02-27 20:23:22 +0000 | [diff] [blame] | 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> > |
commit-bot@chromium.org | e3beb6b | 2014-04-07 19:34:38 +0000 | [diff] [blame] | 14 | class GrOrderedSet : SkNoncopyable { |
commit-bot@chromium.org | 4fcc3ca | 2014-02-27 20:23:22 +0000 | [diff] [blame] | 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 |