1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/gpu/GrOrderedSet.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,154 @@
1.4 +/*
1.5 + * Copyright 2014 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +
1.11 +#ifndef GrOrderedSet_DEFINED
1.12 +#define GrOrderedSet_DEFINED
1.13 +
1.14 +#include "GrRedBlackTree.h"
1.15 +
1.16 +template <typename T, typename C = GrLess<T> >
1.17 +class GrOrderedSet : public SkNoncopyable {
1.18 +public:
1.19 + /**
1.20 + * Creates an empty set
1.21 + */
1.22 + GrOrderedSet() : fComp() {}
1.23 + ~GrOrderedSet() {}
1.24 +
1.25 + class Iter;
1.26 +
1.27 + /**
1.28 + * @return true if there are no items in the set, false otherwise.
1.29 + */
1.30 + bool empty() const { return fRBTree.empty(); }
1.31 +
1.32 + /**
1.33 + * @return the number of items in the set.
1.34 + */
1.35 + int count() const { return fRBTree.count(); }
1.36 +
1.37 + /**
1.38 + * Removes all items in the set
1.39 + */
1.40 + void reset() { fRBTree.reset(); }
1.41 +
1.42 + /**
1.43 + * Adds an element to set if it does not already exists in the set.
1.44 + * @param t the item to add
1.45 + * @return an iterator to added element or matching element already in set
1.46 + */
1.47 + Iter insert(const T& t);
1.48 +
1.49 + /**
1.50 + * Removes the item indicated by an iterator. The iterator will not be valid
1.51 + * afterwards.
1.52 + * @param iter iterator of item to remove. Must be valid (not end()).
1.53 + */
1.54 + void remove(const Iter& iter);
1.55 +
1.56 + /**
1.57 + * @return an iterator to the first item in sorted order, or end() if empty
1.58 + */
1.59 + Iter begin();
1.60 +
1.61 + /**
1.62 + * Gets the last valid iterator. This is always valid, even on an empty.
1.63 + * However, it can never be dereferenced. Useful as a loop terminator.
1.64 + * @return an iterator that is just beyond the last item in sorted order.
1.65 + */
1.66 + Iter end();
1.67 +
1.68 + /**
1.69 + * @return an iterator that to the last item in sorted order, or end() if
1.70 + * empty.
1.71 + */
1.72 + Iter last();
1.73 +
1.74 + /**
1.75 + * Finds an occurrence of an item.
1.76 + * @param t the item to find.
1.77 + * @return an iterator to a set element equal to t or end() if none exists.
1.78 + */
1.79 + Iter find(const T& t);
1.80 +
1.81 +private:
1.82 + GrRedBlackTree<T, C> fRBTree;
1.83 +
1.84 + const C fComp;
1.85 +};
1.86 +
1.87 +template <typename T, typename C>
1.88 +class GrOrderedSet<T,C>::Iter {
1.89 +public:
1.90 + Iter() {}
1.91 + Iter(const Iter& i) { fTreeIter = i.fTreeIter; }
1.92 + Iter& operator =(const Iter& i) {
1.93 + fTreeIter = i.fTreeIter;
1.94 + return *this;
1.95 + }
1.96 + const T& operator *() const { return *fTreeIter; }
1.97 + bool operator ==(const Iter& i) const {
1.98 + return fTreeIter == i.fTreeIter;
1.99 + }
1.100 + bool operator !=(const Iter& i) const { return !(*this == i); }
1.101 + Iter& operator ++() {
1.102 + ++fTreeIter;
1.103 + return *this;
1.104 + }
1.105 + Iter& operator --() {
1.106 + --fTreeIter;
1.107 + return *this;
1.108 + }
1.109 + const typename GrRedBlackTree<T,C>::Iter& getTreeIter() const {
1.110 + return fTreeIter;
1.111 + }
1.112 +
1.113 +private:
1.114 + friend class GrOrderedSet;
1.115 + explicit Iter(typename GrRedBlackTree<T, C>::Iter iter) {
1.116 + fTreeIter = iter;
1.117 + }
1.118 + typename GrRedBlackTree<T,C>::Iter fTreeIter;
1.119 +};
1.120 +
1.121 +template <typename T, typename C>
1.122 +typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::begin() {
1.123 + return Iter(fRBTree.begin());
1.124 +}
1.125 +
1.126 +template <typename T, typename C>
1.127 +typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::end() {
1.128 + return Iter(fRBTree.end());
1.129 +}
1.130 +
1.131 +template <typename T, typename C>
1.132 +typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::last() {
1.133 + return Iter(fRBTree.last());
1.134 +}
1.135 +
1.136 +template <typename T, typename C>
1.137 +typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::find(const T& t) {
1.138 + return Iter(fRBTree.find(t));
1.139 +}
1.140 +
1.141 +template <typename T, typename C>
1.142 +typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::insert(const T& t) {
1.143 + if (fRBTree.find(t) == fRBTree.end()) {
1.144 + return Iter(fRBTree.insert(t));
1.145 + } else {
1.146 + return Iter(fRBTree.find(t));
1.147 + }
1.148 +}
1.149 +
1.150 +template <typename T, typename C>
1.151 +void GrOrderedSet<T,C>::remove(const typename GrOrderedSet<T,C>::Iter& iter) {
1.152 + if (this->end() != iter) {
1.153 + fRBTree.remove(iter.getTreeIter());
1.154 + }
1.155 +}
1.156 +
1.157 +#endif
