/**
 * @file
 * $Id$
 * $Revision$
 * $Author$
 * $Date$
 *
 * This file is part of The iWear Framework.
 * In particular this file is part of the Framework Core Library
 *
 * The iWear Framework is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by the
 * Free Software Foundation as in version 2 of the License.
 * 
 * The iWear Framework is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 * more details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * The iWear Framework; if not, write to the Free Software Foundation, Inc., 59
 * Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#ifndef __IWEAR_SORTED_SEQUENCE_H
#define __IWEAR_SORTED_SEQUENCE_H

#include <vector>
#include <algorithm>

namespace iwear {

template<class T, bool is_uniq = false, class Sequence = std::vector<T> >
class sorted_sequence
{
protected:
    Sequence c;
public:
    typedef typename Sequence::size_type size_type;
    typedef typename Sequence::iterator iterator;
    typedef typename Sequence::const_iterator const_iterator;
    typedef typename Sequence::reverse_iterator reverse_iterator;
    typedef typename Sequence::const_reverse_iterator const_reverse_iterator;
    typedef sorted_sequence<T,is_uniq,Sequence> self_type;
    static const size_type npos = size_type(-1);
public:

    template<class ForwardIterator>
    sorted_sequence( ForwardIterator b, ForwardIterator e );

    sorted_sequence( ) { }

    explicit sorted_sequence( const Sequence&  );

    std::pair<iterator,bool> insert( const T& );

    iterator find( const T& );

    const T& operator[]( size_type i ) const { return c[i]; }
    T& operator[]( size_type i ) { return c[i]; }

    iterator erase( iterator i) { return c.erase(i); }
    iterator erase( iterator b, iterator s ) { return c.erase(b,s); }

    iterator begin() { return c.begin(); }
    const_iterator begin() const { return c.begin(); }

    iterator end() { return c.end(); }
    const_iterator end() const { return c.end(); }

    reverse_iterator rbegin() { return c.rbegin(); }
    const_reverse_iterator rbegin() const { return c.rbegin(); }

    reverse_iterator rend() { return c.rend(); }
    const_reverse_iterator rend() const { return c.rend(); }

    void clear() { c.clear(); }

    size_type size() const { return c.size(); }

    void resize( size_type s, T t = T() ) { c.resize(s,t); }
    void reserve( size_type s ) { c.reserve(s); }

    bool empty( ) const { return c.empty(); }

    Sequence& sequence( ) { return c; }
    const Sequence& sequence( ) const { return c; }

    void swap ( self_type& );
};

template<class T, bool is_uniq, class Sequence>
sorted_sequence<T,is_uniq,Sequence>::sorted_sequence( const Sequence& s )
    : c(s)
{
}

template<class T, bool is_uniq, class Sequence>
template<class ForwardIterator>
sorted_sequence<T,is_uniq,Sequence>::sorted_sequence( ForwardIterator b, ForwardIterator e )
{
    for(; b != e; ++b )
    {
	insert(*b);
    }
}

template<class T, bool is_uniq, class Sequence>
std::pair<typename sorted_sequence<T,is_uniq,Sequence>::iterator,bool> sorted_sequence<T,is_uniq,Sequence>::insert( const T& v )
{
    typename Sequence::iterator i = std::lower_bound(c.begin(),c.end(),v);
    std::pair< typename sorted_sequence<T,is_uniq,Sequence>::iterator, bool> r;

    if( is_uniq && i != c.end() && *i == v )
    {
	r.second = false;
    }
    else
    {
	r.second = true;
	r.first = c.insert(i,v);
    }
    return r;
}

template<class T, bool is_uniq, class Sequence>
typename sorted_sequence<T,is_uniq,Sequence>::iterator sorted_sequence<T,is_uniq,Sequence>::find( const T& v )
{
    typename Sequence::iterator i = std::lower_bound(c.begin(),c.end(),v);
    if( i == c.end() || *i != v )
    {
	return c.end();
    }
    else
    {
	return i;
    }
}

template<class T, bool is_uniq, class Sequence>
void sorted_sequence<T,is_uniq,Sequence>::swap ( self_type& s )
{
    using std::swap;
    swap(c,s.c);
}

template<class T, bool is_uniq, class Sequence>
void swap( sorted_sequence<T,is_uniq,Sequence> & a, sorted_sequence<T,is_uniq,Sequence> & b )
{
    a.swap(b);
}

}
#endif

// vim: tabstop=4 shiftwidth=4 noexpandtab