Basic implementation of set.

This impl uses vector (non-sorted) to provide a basic
level of functionality to build gtest (blocker).
The poor performance is not a concern for now, an RB tree
replacement is being worked on.

3 files changed, 265 insertions, 0 deletions

diff --git a/include/set b/include/set
new file mode 100644
index 0000000..5f00c66
--- /dev/null
+++ b/include/set
@@ -0,0 +1,125 @@
+/* -*- c++ -*- */
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *  * Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *  * Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
+ * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef ANDROID_ASTL_SET__
+#define ANDROID_ASTL_SET__
+
+// To include bionic's stl_pair.h, __STL_*_NAMESPACE must be defined.
+#ifndef __STL_BEGIN_NAMESPACE
+#define __STL_BEGIN_NAMESPACE namespace std {
+#define __STL_END_NAMESPACE   }
+#endif
+
+#include <stl_pair.h>
+#include <iterator>
+#include <vector>
+
+namespace std {
+
+#ifdef _Key
+#error "_Key is a macro."
+#endif
+
+// Very basic and crude implementation of std::set.
+//
+// TODO: Replace the vector used to implement the set with an RB
+// tree. vector does not implement insert and is not ordered as a
+// result.
+
+template<class _Key>
+class set
+{
+  public:
+    typedef _Key key_type;
+    typedef _Key value_type;
+
+  private:
+    typedef vector<_Key> impl_type;
+  public:
+    typedef _Key*        pointer;
+    typedef const _Key*  const_pointer;
+    typedef _Key&        reference;
+    typedef const _Key&  const_reference;
+
+    typedef typename impl_type::iterator        iterator;
+    typedef typename impl_type::const_iterator  const_iterator;
+    typedef typename impl_type::size_type       size_type;
+    typedef typename impl_type::difference_type difference_type;
+
+    // Insert elt if and only if there is no element in the set
+    // equivalent to elt already.
+    // @param elt Element to be inserted.
+    // @return A pair made of:
+    //         - an iterator which points to the equivalent element in the set
+    //           (either 'elt' or the one already present),
+    //         - a bool which indicates if the insertion took place.
+    pair<iterator, bool> insert(const value_type& elt) {
+        typename impl_type::iterator i = mImpl.begin();
+        while (i != mImpl.end()) {
+            if (elt == *i) {
+                return pair<iterator, bool>(i, false);
+            }
+            ++i;
+        }
+        mImpl.push_back(elt);
+        return pair<iterator, bool>(--mImpl.end(), true);
+    }
+
+    // Set have an insert unique semantic so there is at most one
+    // instance of the elt.
+    // @param elt Element to locate.
+    // @return 0 if elt was not found, 1 otherwise.
+    size_type count(const key_type& elt) const {
+        typename impl_type::const_iterator i = mImpl.begin();
+        while (i != mImpl.end()) {
+            if (elt == *i) {
+                return 1;
+            }
+            ++i;
+        }
+        return 0;
+    }
+
+    // @return true if the set is empty, false otherwise.
+    bool empty() const { return mImpl.size() == 0; }
+    size_type size() const { return mImpl.size(); }
+
+    iterator begin() { return mImpl.begin(); }
+    iterator end() { return mImpl.end(); }
+
+    const_iterator begin() const { return mImpl.begin(); }
+    const_iterator end() const { return mImpl.end(); }
+
+  private:
+    impl_type mImpl;
+};
+
+}  // namespace std
+
+#endif  // ANDROID_ASTL_VECTOR__
diff --git a/tests/Android.mk b/tests/Android.mk
index b83aa0a..586f778 100644
--- a/tests/Android.mk
+++ b/tests/Android.mk
@@ -64,6 +64,7 @@ sources := \
     test_algorithm.cpp \
     test_functional.cpp \
     test_limits.cpp \
+    test_set.cpp \
     test_string.cpp \
     test_type_traits.cpp \
     test_uninitialized.cpp \
diff --git a/tests/test_set.cpp b/tests/test_set.cpp
new file mode 100644
index 0000000..e58b921
--- /dev/null
+++ b/tests/test_set.cpp
@@ -0,0 +1,139 @@
+/* -*- c++ -*- */
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *  * Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *  * Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
+ * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include "../include/set"
+#ifndef ANDROID_ASTL_SET__
+#error "Wrong header included!!"
+#endif
+#include <climits>
+#include <cstring>
+#include <string>
+#include "common.h"
+
+namespace android {
+using std::pair;
+using std::set;
+using std::string;
+
+bool testConstructor()
+{
+    set<int> s;
+    EXPECT_TRUE(s.empty());
+    EXPECT_TRUE(s.size() == 0);
+    EXPECT_TRUE(s.begin() == s.end());
+    EXPECT_TRUE(s.count(10) == 0);
+    return true;
+}
+
+bool testInsertPOD()
+{
+    set<int> s;
+    pair<set<int>::iterator, bool> res;
+
+    EXPECT_TRUE(s.count(10) == 0);
+
+    res = s.insert(10);
+
+    // begin should point to the element inserted.
+    EXPECT_TRUE(res.first == s.begin());
+    EXPECT_TRUE(s.end() != s.begin());
+    EXPECT_TRUE(*(res.first) == 10);
+    set<int>::iterator elt_in_set = res.first;
+    EXPECT_TRUE(*(s.begin()) == 10);
+
+    // insert was a success.
+    EXPECT_TRUE(res.second);
+
+    // element can be found
+    EXPECT_TRUE(s.count(10) == 1);
+
+    // Try to insert the same element again, this time it should fail.
+    res = s.insert(10);
+    // insert was a failure.
+    EXPECT_TRUE(!res.second);
+
+    // Insert should return an iterator pointing to the element
+    // already in the set.
+    EXPECT_TRUE(res.first == elt_in_set);
+
+    // element can still be found
+    EXPECT_TRUE(s.count(10) == 1);
+    return true;
+}
+
+bool testInsertString()
+{
+    set<string> s;
+    pair<set<string>::iterator, bool> res;
+    string str("a string");
+    string str_equiv("a string");
+    string str_missing("a string not in the set");
+
+    EXPECT_TRUE(s.count(str) == 0);
+
+    res = s.insert(str);
+
+    // begin should point to the element inserted.
+    EXPECT_TRUE(res.first == s.begin());
+    set<string>::iterator marker = res.first;
+    EXPECT_TRUE(s.end() != s.begin());
+    EXPECT_TRUE(*(res.first) == str);
+    EXPECT_TRUE(*(s.begin()) == str);
+
+    // insert was a success.
+    EXPECT_TRUE(res.second);
+
+    // element can be found
+    EXPECT_TRUE(s.count(str) == 1);
+
+    // Try to insert an element equivalent.
+    res = s.insert(str_equiv);
+
+    // insert did not happen since there is one string equivalent
+    // already.
+    EXPECT_TRUE(!res.second);
+
+    // The iterator points to the copy already in the set.
+    EXPECT_TRUE(res.first == marker);
+
+    // element can still be found
+    EXPECT_TRUE(s.count(str) == 1);
+    EXPECT_TRUE(s.count(str_equiv) == 1);
+    return true;
+}
+
+}  // namespace android
+
+int main(int argc, char **argv)
+{
+    FAIL_UNLESS(testConstructor);
+    FAIL_UNLESS(testInsertPOD);
+    FAIL_UNLESS(testInsertString);
+    return kPassed;
+}