1/* -*- c++ -*- */ 2/* 3 * Copyright (C) 2010 The Android Open Source Project 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * * Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in 13 * the documentation and/or other materials provided with the 14 * distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 19 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 20 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 22 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS 23 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 24 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 25 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 26 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 */ 29 30#ifndef ANDROID_ASTL_SET__ 31#define ANDROID_ASTL_SET__ 32 33// To include bionic's stl_pair.h, __STL_*_NAMESPACE must be defined. 34#ifndef __STL_BEGIN_NAMESPACE 35#define __STL_BEGIN_NAMESPACE namespace std { 36#define __STL_END_NAMESPACE } 37#endif 38 39#include <stl_pair.h> 40#include <iterator> 41#include <vector> 42 43namespace std { 44 45#ifdef _Key 46#error "_Key is a macro." 47#endif 48 49// Very basic and crude implementation of std::set. 50// 51// TODO: Replace the vector used to implement the set with an RB 52// tree. vector does not implement insert and is not ordered as a 53// result. 54 55template<class _Key> 56class set 57{ 58 public: 59 typedef _Key key_type; 60 typedef _Key value_type; 61 62 private: 63 typedef vector<_Key> impl_type; 64 public: 65 typedef _Key* pointer; 66 typedef const _Key* const_pointer; 67 typedef _Key& reference; 68 typedef const _Key& const_reference; 69 70 typedef typename impl_type::iterator iterator; 71 typedef typename impl_type::const_iterator const_iterator; 72 typedef typename impl_type::size_type size_type; 73 typedef typename impl_type::difference_type difference_type; 74 75 // Insert elt if and only if there is no element in the set 76 // equivalent to elt already. 77 // @param elt Element to be inserted. 78 // @return A pair made of: 79 // - an iterator which points to the equivalent element in the set 80 // (either 'elt' or the one already present), 81 // - a bool which indicates if the insertion took place. 82 pair<iterator, bool> insert(const value_type& elt) { 83 typename impl_type::iterator i = mImpl.begin(); 84 while (i != mImpl.end()) { 85 if (elt == *i) { 86 return pair<iterator, bool>(i, false); 87 } 88 ++i; 89 } 90 mImpl.push_back(elt); 91 return pair<iterator, bool>(--mImpl.end(), true); 92 } 93 94 // Set have an insert unique semantic so there is at most one 95 // instance of the elt. 96 // @param elt Element to locate. 97 // @return 0 if elt was not found, 1 otherwise. 98 size_type count(const key_type& elt) const { 99 typename impl_type::const_iterator i = mImpl.begin(); 100 while (i != mImpl.end()) { 101 if (elt == *i) { 102 return 1; 103 } 104 ++i; 105 } 106 return 0; 107 } 108 109 // @return true if the set is empty, false otherwise. 110 bool empty() const { return mImpl.size() == 0; } 111 size_type size() const { return mImpl.size(); } 112 113 iterator begin() { return mImpl.begin(); } 114 iterator end() { return mImpl.end(); } 115 116 const_iterator begin() const { return mImpl.begin(); } 117 const_iterator end() const { return mImpl.end(); } 118 119 private: 120 impl_type mImpl; 121}; 122 123} // namespace std 124 125#endif // ANDROID_ASTL_VECTOR__ 126