14fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org/* 24fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * Copyright 2014 Google Inc. 34fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * 44fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * Use of this source code is governed by a BSD-style license that can be 54fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * found in the LICENSE file. 64fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org */ 74fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 84fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org#ifndef GrOrderedSet_DEFINED 94fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org#define GrOrderedSet_DEFINED 104fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 114fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org#include "GrRedBlackTree.h" 124fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 134fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgtemplate <typename T, typename C = GrLess<T> > 14e3beb6bd7de7fa211681abbb0be58e80b19885e0commit-bot@chromium.orgclass GrOrderedSet : SkNoncopyable { 154fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgpublic: 164fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org /** 174fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * Creates an empty set 184fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org */ 194fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org GrOrderedSet() : fComp() {} 204fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org ~GrOrderedSet() {} 214fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 224fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org class Iter; 234fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 244fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org /** 254fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * @return true if there are no items in the set, false otherwise. 264fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org */ 274fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org bool empty() const { return fRBTree.empty(); } 284fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 294fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org /** 304fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * @return the number of items in the set. 314fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org */ 324fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org int count() const { return fRBTree.count(); } 334fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 344fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org /** 354fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * Removes all items in the set 364fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org */ 374fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org void reset() { fRBTree.reset(); } 384fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 394fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org /** 404fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * Adds an element to set if it does not already exists in the set. 414fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * @param t the item to add 424fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * @return an iterator to added element or matching element already in set 434fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org */ 444fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org Iter insert(const T& t); 454fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 464fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org /** 474fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * Removes the item indicated by an iterator. The iterator will not be valid 484fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * afterwards. 494fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * @param iter iterator of item to remove. Must be valid (not end()). 504fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org */ 514fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org void remove(const Iter& iter); 524fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 534fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org /** 544fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * @return an iterator to the first item in sorted order, or end() if empty 554fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org */ 564fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org Iter begin(); 574fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 584fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org /** 594fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * Gets the last valid iterator. This is always valid, even on an empty. 604fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * However, it can never be dereferenced. Useful as a loop terminator. 614fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * @return an iterator that is just beyond the last item in sorted order. 624fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org */ 634fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org Iter end(); 644fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 654fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org /** 664fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * @return an iterator that to the last item in sorted order, or end() if 674fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * empty. 684fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org */ 694fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org Iter last(); 704fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 714fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org /** 724fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * Finds an occurrence of an item. 734fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * @param t the item to find. 744fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org * @return an iterator to a set element equal to t or end() if none exists. 754fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org */ 764fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org Iter find(const T& t); 774fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 784fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgprivate: 794fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org GrRedBlackTree<T, C> fRBTree; 804fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 814fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org const C fComp; 824fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org}; 834fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 844fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgtemplate <typename T, typename C> 854fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgclass GrOrderedSet<T,C>::Iter { 864fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgpublic: 874fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org Iter() {} 884fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org Iter(const Iter& i) { fTreeIter = i.fTreeIter; } 894fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org Iter& operator =(const Iter& i) { 904fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org fTreeIter = i.fTreeIter; 914fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org return *this; 924fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } 934fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org const T& operator *() const { return *fTreeIter; } 944fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org bool operator ==(const Iter& i) const { 954fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org return fTreeIter == i.fTreeIter; 964fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } 974fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org bool operator !=(const Iter& i) const { return !(*this == i); } 984fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org Iter& operator ++() { 994fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org ++fTreeIter; 1004fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org return *this; 1014fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } 1024fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org Iter& operator --() { 1034fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org --fTreeIter; 1044fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org return *this; 1054fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } 1064fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org const typename GrRedBlackTree<T,C>::Iter& getTreeIter() const { 1074fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org return fTreeIter; 1084fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } 1094fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1104fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgprivate: 1114fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org friend class GrOrderedSet; 1124fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org explicit Iter(typename GrRedBlackTree<T, C>::Iter iter) { 1134fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org fTreeIter = iter; 1144fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } 1154fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org typename GrRedBlackTree<T,C>::Iter fTreeIter; 1164fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org}; 1174fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1184fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgtemplate <typename T, typename C> 1194fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgtypename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::begin() { 1204fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org return Iter(fRBTree.begin()); 1214fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org} 1224fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1234fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgtemplate <typename T, typename C> 1244fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgtypename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::end() { 1254fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org return Iter(fRBTree.end()); 1264fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org} 1274fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1284fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgtemplate <typename T, typename C> 1294fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgtypename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::last() { 1304fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org return Iter(fRBTree.last()); 1314fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org} 1324fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1334fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgtemplate <typename T, typename C> 1344fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgtypename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::find(const T& t) { 1354fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org return Iter(fRBTree.find(t)); 1364fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org} 1374fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1384fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgtemplate <typename T, typename C> 1394fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgtypename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::insert(const T& t) { 1404fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org if (fRBTree.find(t) == fRBTree.end()) { 1414fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org return Iter(fRBTree.insert(t)); 1424fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } else { 1434fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org return Iter(fRBTree.find(t)); 1444fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } 1454fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org} 1464fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1474fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgtemplate <typename T, typename C> 1484fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.orgvoid GrOrderedSet<T,C>::remove(const typename GrOrderedSet<T,C>::Iter& iter) { 1494fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org if (this->end() != iter) { 1504fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org fRBTree.remove(iter.getTreeIter()); 1514fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org } 1524fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org} 1534fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org 1544fcc3ca4112754f99a7d94b07e8ebbb0cb8c09eacommit-bot@chromium.org#endif 155