3.0

1 files changed, 358 insertions, 0 deletions

diff --git a/shared/loki/AssocVector.h b/shared/loki/AssocVector.h
new file mode 100644
index 00000000..905e0963
--- /dev/null
+++ b/shared/loki/AssocVector.h
@@ -0,0 +1,358 @@
+////////////////////////////////////////////////////////////////////////////////
+// The Loki Library
+// Copyright (c) 2001 by Andrei Alexandrescu
+// This code accompanies the book:
+// Alexandrescu, Andrei. "Modern C++ Design: Generic Programming and Design 
+//     Patterns Applied". Copyright (c) 2001. Addison-Wesley.
+// Permission to use, copy, modify, distribute and sell this software for any 
+//     purpose is hereby granted without fee, provided that the above copyright 
+//     notice appear in all copies and that both that copyright notice and this 
+//     permission notice appear in supporting documentation.
+// The author or Addison-Wesley Longman make no representations about the 
+//     suitability of this software for any purpose. It is provided "as is" 
+//     without express or implied warranty.
+////////////////////////////////////////////////////////////////////////////////
+#ifndef LOKI_ASSOCVECTOR_INC_
+#define LOKI_ASSOCVECTOR_INC_
+
+// $Id: AssocVector.h 765 2006-10-18 13:55:32Z syntheticpp $
+
+
+#include <algorithm>
+#include <functional>
+#include <vector>
+#include <utility>
+
+namespace Loki
+{
+////////////////////////////////////////////////////////////////////////////////
+// class template AssocVectorCompare
+// Used by AssocVector
+////////////////////////////////////////////////////////////////////////////////
+
+    namespace Private
+    {
+        template <class Value, class C>
+        class AssocVectorCompare : public C
+        {
+            typedef std::pair<typename C::first_argument_type, Value>
+                Data;
+            typedef typename C::first_argument_type first_argument_type;
+
+        public:
+            AssocVectorCompare()
+            {}
+            
+            AssocVectorCompare(const C& src) : C(src)
+            {}
+            
+            bool operator()(const first_argument_type& lhs, 
+                const first_argument_type& rhs) const
+            { return C::operator()(lhs, rhs); }
+            
+            bool operator()(const Data& lhs, const Data& rhs) const
+            { return operator()(lhs.first, rhs.first); }
+            
+            bool operator()(const Data& lhs, 
+                const first_argument_type& rhs) const
+            { return operator()(lhs.first, rhs); }
+            
+            bool operator()(const first_argument_type& lhs,
+                const Data& rhs) const
+            { return operator()(lhs, rhs.first); }
+        };
+    }
+
+////////////////////////////////////////////////////////////////////////////////
+// class template AssocVector
+// An associative vector built as a syntactic drop-in replacement for std::map
+// BEWARE: AssocVector doesn't respect all map's guarantees, the most important
+//     being:
+// * iterators are invalidated by insert and erase operations
+// * the complexity of insert/erase is O(N) not O(log N)
+// * value_type is std::pair<K, V> not std::pair<const K, V>
+// * iterators are random
+////////////////////////////////////////////////////////////////////////////////
+
+
+    template
+    <
+        class K,
+        class V,
+        class C = std::less<K>,
+        class A = std::allocator< std::pair<K, V> >
+    >
+    class AssocVector 
+        : private std::vector< std::pair<K, V>, A >
+        , private Private::AssocVectorCompare<V, C>
+    {
+        typedef std::vector<std::pair<K, V>, A> Base;
+        typedef Private::AssocVectorCompare<V, C> MyCompare;
+
+    public:
+        typedef K key_type;
+        typedef V mapped_type;
+        typedef typename Base::value_type value_type;
+
+        typedef C key_compare;
+        typedef A allocator_type;
+        typedef typename A::reference reference;
+        typedef typename A::const_reference const_reference;
+        typedef typename Base::iterator iterator;
+        typedef typename Base::const_iterator const_iterator;
+        typedef typename Base::size_type size_type;
+        typedef typename Base::difference_type difference_type;
+        typedef typename A::pointer pointer;
+        typedef typename A::const_pointer const_pointer;
+        typedef typename Base::reverse_iterator reverse_iterator;
+        typedef typename Base::const_reverse_iterator const_reverse_iterator;
+
+        class value_compare
+            : public std::binary_function<value_type, value_type, bool>
+            , private key_compare
+        {
+            friend class AssocVector;
+        
+        protected:
+            value_compare(key_compare pred) : key_compare(pred)
+            {}
+
+        public:
+            bool operator()(const value_type& lhs, const value_type& rhs) const
+            { return key_compare::operator()(lhs.first, rhs.first); }
+        };
+        
+        // 23.3.1.1 construct/copy/destroy
+
+        explicit AssocVector(const key_compare& comp = key_compare(), 
+            const A& alloc = A())
+        : Base(alloc), MyCompare(comp)
+        {}
+        
+        template <class InputIterator>
+        AssocVector(InputIterator first, InputIterator last, 
+            const key_compare& comp = key_compare(), 
+            const A& alloc = A())
+        : Base(first, last, alloc), MyCompare(comp)
+        {
+            MyCompare& me = *this;
+            std::sort(begin(), end(), me);
+        }
+        
+        AssocVector& operator=(const AssocVector& rhs)
+        { 
+            AssocVector(rhs).swap(*this); 
+            return *this;
+        }
+
+        // iterators:
+        // The following are here because MWCW gets 'using' wrong
+        iterator begin() { return Base::begin(); }
+        const_iterator begin() const { return Base::begin(); }
+        iterator end() { return Base::end(); }
+        const_iterator end() const { return Base::end(); }
+        reverse_iterator rbegin() { return Base::rbegin(); }
+        const_reverse_iterator rbegin() const { return Base::rbegin(); }
+        reverse_iterator rend() { return Base::rend(); }
+        const_reverse_iterator rend() const { return Base::rend(); }
+        
+        // capacity:
+        bool empty() const { return Base::empty(); }
+        size_type size() const { return Base::size(); }
+        size_type max_size() { return Base::max_size(); }
+
+        // 23.3.1.2 element access:
+        mapped_type& operator[](const key_type& key)
+        { return insert(value_type(key, mapped_type())).first->second; }
+
+        // modifiers:
+        std::pair<iterator, bool> insert(const value_type& val)
+        {
+            bool found(true);
+            iterator i(lower_bound(val.first));
+
+            if (i == end() || this->operator()(val.first, i->first))
+            {
+                i = Base::insert(i, val);
+                found = false;
+            }
+            return std::make_pair(i, !found);
+        }
+        //Section [23.1.2], Table 69
+        //http://developer.apple.com/documentation/DeveloperTools/gcc-3.3/libstdc++/23_containers/howto.html#4
+        iterator insert(iterator pos, const value_type& val)
+        {
+            if( (pos == begin() || this->operator()(*(pos-1),val)) && 
+                (pos == end()    || this->operator()(val, *pos)) )
+            {
+                return Base::insert(pos, val);
+            }
+            return insert(val).first;
+        }
+       
+        template <class InputIterator>
+        void insert(InputIterator first, InputIterator last)
+        { for (; first != last; ++first) insert(*first); }
+        
+        void erase(iterator pos)
+        { Base::erase(pos); }
+
+        size_type erase(const key_type& k)
+        {
+            iterator i(find(k));
+            if (i == end()) return 0;
+            erase(i);
+            return 1;
+        }
+
+        void erase(iterator first, iterator last)
+        { Base::erase(first, last); }
+
+        void swap(AssocVector& other)
+        {
+            Base::swap(other);
+            MyCompare& me = *this;
+            MyCompare& rhs = other;
+            std::swap(me, rhs);
+        }
+        
+        void clear()
+        { Base::clear(); }
+
+        // observers:
+        key_compare key_comp() const
+        { return *this; }
+
+        value_compare value_comp() const
+        {
+            const key_compare& comp = *this;
+            return value_compare(comp);
+        }
+
+        // 23.3.1.3 map operations:
+        iterator find(const key_type& k)
+        {
+            iterator i(lower_bound(k));
+            if (i != end() && this->operator()(k, i->first))
+            {
+                i = end();
+            }
+            return i;
+        }
+
+        const_iterator find(const key_type& k) const
+        {       
+            const_iterator i(lower_bound(k));
+            if (i != end() && this->operator()(k, i->first))
+            {
+                i = end();
+            }
+            return i;
+        }
+
+        size_type count(const key_type& k) const
+        { return find(k) != end(); }
+
+        iterator lower_bound(const key_type& k)
+        {
+            MyCompare& me = *this;
+            return std::lower_bound(begin(), end(), k, me);
+        }
+
+        const_iterator lower_bound(const key_type& k) const
+        {
+            const MyCompare& me = *this;
+            return std::lower_bound(begin(), end(), k, me);
+        }
+
+        iterator upper_bound(const key_type& k)
+        {
+            MyCompare& me = *this;
+            return std::upper_bound(begin(), end(), k, me);
+        }
+
+        const_iterator upper_bound(const key_type& k) const
+        {
+            const MyCompare& me = *this;
+            return std::upper_bound(begin(), end(), k, me);
+        }
+
+        std::pair<iterator, iterator> equal_range(const key_type& k)
+        {
+            MyCompare& me = *this;
+            return std::equal_range(begin(), end(), k, me);
+        }
+
+        std::pair<const_iterator, const_iterator> equal_range(
+            const key_type& k) const
+        {
+            const MyCompare& me = *this;
+            return std::equal_range(begin(), end(), k, me);
+        }
+
+        template <class K1, class V1, class C1, class A1>
+        friend bool operator==(const AssocVector<K1, V1, C1, A1>& lhs,
+                        const AssocVector<K1, V1, C1, A1>& rhs);
+
+        bool operator<(const AssocVector& rhs) const
+        {
+            const Base& me = *this;
+            const Base& yo = rhs;
+            return me < yo;
+        }
+
+        template <class K1, class V1, class C1, class A1>
+        friend bool operator!=(const AssocVector<K1, V1, C1, A1>& lhs,
+                               const AssocVector<K1, V1, C1, A1>& rhs);
+
+        template <class K1, class V1, class C1, class A1>
+        friend bool operator>(const AssocVector<K1, V1, C1, A1>& lhs,
+                              const AssocVector<K1, V1, C1, A1>& rhs);
+
+        template <class K1, class V1, class C1, class A1>
+        friend bool operator>=(const AssocVector<K1, V1, C1, A1>& lhs,
+                               const AssocVector<K1, V1, C1, A1>& rhs);
+
+        template <class K1, class V1, class C1, class A1>
+        friend bool operator<=(const AssocVector<K1, V1, C1, A1>& lhs,
+                               const AssocVector<K1, V1, C1, A1>& rhs);
+    };
+
+    template <class K, class V, class C, class A>
+    inline bool operator==(const AssocVector<K, V, C, A>& lhs,
+                           const AssocVector<K, V, C, A>& rhs)
+    {
+      const std::vector<std::pair<K, V>, A>& me = lhs;
+      return me == rhs;
+    }
+
+    template <class K, class V, class C, class A>
+    inline bool operator!=(const AssocVector<K, V, C, A>& lhs,
+                           const AssocVector<K, V, C, A>& rhs)
+    { return !(lhs == rhs); }
+
+    template <class K, class V, class C, class A>
+    inline bool operator>(const AssocVector<K, V, C, A>& lhs,
+                          const AssocVector<K, V, C, A>& rhs)
+    { return rhs < lhs; }
+
+    template <class K, class V, class C, class A>
+    inline bool operator>=(const AssocVector<K, V, C, A>& lhs,
+                           const AssocVector<K, V, C, A>& rhs)
+    { return !(lhs < rhs); }
+
+    template <class K, class V, class C, class A>
+    inline bool operator<=(const AssocVector<K, V, C, A>& lhs,
+                           const AssocVector<K, V, C, A>& rhs)
+    { return !(rhs < lhs); }
+
+
+    // specialized algorithms:
+    template <class K, class V, class C, class A>
+    void swap(AssocVector<K, V, C, A>& lhs, AssocVector<K, V, C, A>& rhs)
+    { lhs.swap(rhs); }
+    
+} // namespace Loki
+
+#endif // end file guardian
+