Home | History | Annotate | Download | only in include 
      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 
     43 namespace 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 
     55 template<class _Key>
     56 class 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