////////////////////////////////////////////////////////////////////////////////
// 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-Welsey Longman make no representations about the
//     suitability of this software for any purpose. It is provided “as is”
//     without express or implied warranty.
////////////////////////////////////////////////////////////////////////////////

// Last update: February 19, 2001

#ifndef SORTEDVECTOR_INC_
#define SORTEDVECTOR_INC_

#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <utility>

// namespace Loki
// {
////////////////////////////////////////////////////////////////////////////////
// class template SortedVector
// A sorted vector built as a syntactic drop-in replacement for std::set
// BEWARE: SortedVector doesn't respect all set'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)
// * iterators are random
////////////////////////////////////////////////////////////////////////////////

    template
    <
        class K,
        class C = std::less<K>
    >
    class SortedVector
        : private std::vector<K>
    {
        typedef std::vector<K> Base;

    public:
        typedef K key_type;
        typedef K value_type;

        typedef C key_compare;
        typedef typename Base::allocator_type allocator_type;
        typedef typename Base::reference reference;
        typedef typename Base::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 Base::pointer pointer;
        typedef typename Base::const_pointer const_pointer;
        typedef typename Base::reverse_iterator reverse_iterator;
        typedef typename Base::const_reverse_iterator const_reverse_iterator;

        // 23.3.1.1 construct/copy/destroy

        explicit SortedVector(const key_compare & = key_compare())
        : Base()
        {}

        template <class InputIterator>
        SortedVector(InputIterator first, InputIterator last)
        : Base(first, last)
        {
	    // There's an error in aCC, where it will attempt to copy the
	    // padding byte in an otherwise empty class, if passed by value.
	    // This annoys Purify, because the padding byte is uninitialized.
	    // The workaround?  Declare an instantiation of the empty class
	    // (a comparison functor) statically, which initializes the bytes.
	    static C compare;
            std::sort(begin(), end(), compare);
        }

        SortedVector& operator=(const SortedVector& rhs)
        { SortedVector(*this).swap(*this); }

        // iterators:
// This was changed from compliance with gcc3.0.  This should not be needed, as the
// casting should be done for us, but for whatever reason, it is needed for gcc3.0
//	using Base::begin;
	iterator begin()       { return Base::begin();}
	iterator begin() const { return Base::begin();}
//	using Base::end;
	iterator end()       { return Base::end();}
	iterator end() const { return Base::end();}
	using Base::rbegin;
	using Base::rend;

        // capacity:
	using Base::empty;
	using Base::size;
	using Base::max_size;

        // modifiers:
	void push_back(const key_type &key) {
		Base::push_back(key);
	}

        std::pair<iterator, bool> insert(const key_type& key)
        {
            bool found(true);
            iterator i = lower_bound(key);

            if (i == end() || C()(key, *i))
            {
                i = Base::insert(i, key);
                found = false;
            }
            return std::make_pair(i, !found);
        }

        iterator insert(iterator pos, const key_type& key)
        {
            if (pos != end() || C()(key, *pos))
                return Base::insert(pos, key);
            return insert(key).first;
        }

        template <class InputIterator>
        iterator 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)
        {
            const 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(SortedVector& other)
        {
            using namespace std;
            Base::swap(other);
            C me = *this;
            C rhs = other;
            swap(me, rhs);
        }

        using Base::clear;

        // observers:
        key_compare key_comp() const {
		static C compare;
		return compare;
	}


        // 23.3.1.3 map operations:
        iterator find(const key_type& k)
        {
            iterator i = lower_bound(k);
            if (i != end() && key_compare()(k, *i))
                i = end();
            return i;
        }

        const_iterator find(const key_type& k) const
        {
            const_iterator i = lower_bound(k);
            if (i != end() && key_compare()(k, *i))
                i = end();
            return i;
        }

        size_type count(const key_type& k) const
        { return find(k) != end(); }

        iterator lower_bound(const key_type& k)
        {
	    static C compare;
            return std::lower_bound(begin(), end(), k, compare);
        }

        const_iterator lower_bound(const key_type& k) const
        {
	    static C compare;
            return std::lower_bound(begin(), end(), k, compare);
        }

        iterator upper_bound(const key_type& k)
        {
	    static C compare;
            return std::upper_bound(begin(), end(), k, compare);
        }

        const_iterator upper_bound(const key_type& k) const
        {
	    static C compare;
            return std::upper_bound(begin(), end(), k, compare);
        }

        std::pair<iterator, iterator> equal_range(const key_type& k)
        {
	    static C compare;
            return std::equal_range(begin(), end(), k, compare);
        }

        std::pair<const_iterator, const_iterator> equal_range(
            const key_type& k) const
        {
	    static C compare;
            return std::equal_range(begin(), end(), k, compare);
        }

        friend bool operator==(const SortedVector& lhs, const SortedVector& rhs)
        {
            const Base& me = lhs;
            return me == rhs;
        }

        friend bool operator<(const SortedVector& lhs, const SortedVector& rhs)
        {
            const Base& me = lhs;
            return me < rhs;
        }

        friend bool operator!=(const SortedVector& lhs, const SortedVector& rhs)
        { return !(lhs == rhs); }

        friend bool operator>(const SortedVector& lhs, const SortedVector& rhs)
        { return rhs < lhs; }

        friend bool operator>=(const SortedVector& lhs, const SortedVector& rhs)
        { return !(lhs < rhs); }

        friend bool operator<=(const SortedVector& lhs, const SortedVector& rhs)
        { return !(rhs < lhs); }
    };

    // specialized algorithms:
    template <class K, class C>
    void swap(SortedVector<K, C>& lhs, SortedVector<K, C>& rhs)
    { lhs.swap(rhs); }

// } // namespace Loki

#endif // SORTEDVECTOR_INC_