#ifndef __JCOLLECTION__
#define __JCOLLECTION__

#include <utility>
#include <vector>
#include <istream>
#include <ostream>

#include "JLang/JClass.hh"
#include "JLang/JException.hh"


namespace JTOOLS {
    
    
  /**
   * Template definition for a navigable collection of elements.
   */
  template<class _Iterator, 
	   class _ConstIterator, 
	   class _ReverseIterator, 
	   class _ConstReverseIterator, 
	   typename _Category = typename std::iterator_traits<_Iterator>::iterator_category>
  class JNavigableCollection;


  /**
   * Template specialisation for a bi-directional collection of elements.
   */
  template<class _Iterator, 
	   class _ConstIterator, 
	   class _ReverseIterator, 
	   class _ConstReverseIterator>
  class JNavigableCollection<_Iterator, 
			     _ConstIterator, 
			     _ReverseIterator, 
			     _ConstReverseIterator, 
			     typename std::bidirectional_iterator_tag>
  {
  public:

    typedef _Iterator               iterator;
    typedef _ConstIterator          const_iterator;
    typedef _ReverseIterator        reverse_iterator;
    typedef _ConstReverseIterator   const_reverse_iterator;


    /**
     * Virtual destructor.
     */
    virtual ~JNavigableCollection()
    {}


    virtual const_iterator begin() const = 0;
    virtual const_iterator end()   const = 0;

    virtual const_reverse_iterator rbegin() const = 0;
    virtual const_reverse_iterator rend()   const = 0;
    
    virtual iterator begin() = 0;
    virtual iterator end()   = 0;

    virtual reverse_iterator rbegin() = 0;
    virtual reverse_iterator rend()   = 0;
  };


  /**
   * Template specialisation for a random access collection of elements.
   */
  template<class _Iterator, 
	   class _ConstIterator,
	   class _ReverseIterator, 
	   class _ConstReverseIterator>
  class JNavigableCollection<_Iterator, 
			     _ConstIterator, 
			     _ReverseIterator, 
			     _ConstReverseIterator, 
			     typename std::random_access_iterator_tag> :
    public JNavigableCollection<_Iterator, 
				_ConstIterator, 
				_ReverseIterator, 
				_ConstReverseIterator, 
				typename std::bidirectional_iterator_tag>
  {};



  /**
   * Template interface definition for associative array (i.e. definition of operator[](<key>) = <value>).
   */
  template<class JKey_t, class JValue_t>
  class JMappableCollection 
  {
  public:

    typedef JKey_t     key_type;
    typedef JValue_t   mapped_type;


    /**
     * Virtual destructor.
     */
    virtual ~JMappableCollection()
    {}


    /**
     * Value assignment.
     *
     * \param  key          key
     * \return              value
     */
    virtual mapped_type& operator[](const key_type& key) = 0;


    /**
     * Associates the specified value with the specified key.
     *
     * \param  key          key
     * \param  value        value
     */
    virtual void put(const key_type& key, const mapped_type& value) 
    {
      (*this)[key] = value;
    }


    /**
     * Clear memory.
     */
    virtual void clear() = 0;
  };


  /**
   * Read template JMappableCollection from input stream.
   *
   * \param  in       std::istream
   * \param  buffer   JMappableCollection
   * \return          std::istream
   */
  template<class JKey_t, class JValue_t>
  inline std::istream& operator>>(std::istream& in, JMappableCollection<JKey_t, JValue_t>& buffer)
  {
    JKey_t   key;
    JValue_t value;
      
    while (in >> key >> value)
      buffer[key] = value;
    
    return in;
  }


  /**
   * Template interface definition for ordering of objects by their key.
   */
  template<class JKey_t, class JValue_t>
  class JComparator
  {
  public:

    typedef JKey_t     key_type;
    typedef JValue_t   mapped_type;


    /**
     * Template interface definition for (key,value) object that can be ordered by its key.
     */
    class JComparable 
    {
    public:

      typedef JKey_t     key_type;
      typedef JValue_t   mapped_type;

      /**
       * Virtual destructor.
       */
      virtual ~JComparable()
      {}

      virtual const key_type&    getKey()   const = 0;
      virtual const mapped_type& getValue() const = 0;

      virtual mapped_type& getValue() = 0;

      //virtual void setValue(const mapped_type) = 0;
    };


    /**
     * Get the comparator used to order the keys in this collection.
     *
     * \return           comparator
     */
    const JComparator<JKey_t, JValue_t>& getComparator() const 
    { 
      return *this;
    }


    /**
     * Less than operator for JComparable
     *
     * \param  first    JComparable
     * \param  second   JComparable
     * \return          true if first.getKey() < second.getKey(); else false
     */
    bool operator()(const JComparable& first, const JComparable& second) const
    {
      return first.getKey() < second.getKey();
    }


    /**
     * Less than operator for JComparable and key_type.
     *
     * \param  element  JComparable
     * \param  x        key
     * \return          true if element.getKey() < x; else false
     */
    bool operator()(const JComparable& element, const key_type& x) const
    {
      return element.getKey() < x;
    }


    /**
     * Less than operator for JComparable and key_type.
     *
     * \param  x        key
     * \param  element  JComparable
     * \return          true if x < element.getKey(); else false
     */
    bool operator()(const key_type& x, const JComparable& element) const
    {
      return x < element.getKey();
    }


    /**
     * Less than operator for key_type.
     *
     * \param  x        first  key
     * \param  y        second key
     * \return          true if x < y; else false
     */
    bool operator()(const key_type& x, const key_type& y) const
    {
      return x < y;
    }


    /**
     * Less than operator for std::pair<>.
     *
     * \param  first    std::pair<key_type, mapped_type>
     * \param  second   std::pair<key_type, mapped_type>
     * \return          true if first.getKey() < second.getKey(); else false
     */
    bool operator()(const std::pair<const key_type, mapped_type>& first, const std::pair<const key_type, mapped_type>& second) const
    {
      return first.first < second.first;
    }


    /**
     * Less than operator for std::pair<> and key_type.
     *
     * \param  element  std::pair<key_type, mapped_type>
     * \param  x        key
     * \return          true if element.first < x; else false
     */
    bool operator()(const std::pair<const key_type, mapped_type>& element, const key_type& x) const
    {
      return element.first < x;
    }


    /**
     * Less than operator for std::pair<> and key_type.
     *
     * \param  x        key
     * \param  element  std::pair<key_type, mapped_type>
     * \return          true if x < element.first; else false
     */
    bool operator()(const key_type& x, const std::pair<const key_type, mapped_type>& element) const
    {
      return x < element.first;
    }
  };


  /**
   * Interface for JCollection element transformation.
   */
  template<class JElement_t>
  class JCollectionElementTransformer {
  public:

    /**
     * Virtual destructor.
     */
    virtual ~JCollectionElementTransformer() 
    {}

    
    /**
     * Transform element.
     * 
     * \param  element  input  element
     * \return          output element
     */
    virtual JElement_t operator()(const JElement_t& element) const = 0;
  };


  /**
   * Template interface definition for ordered, transformable and navigable collection
   * of mappable (key,value) elements based on a standard container.
   */
  template<class JElement_t, template<class> class JContainer_t>
  class JAbstractCollection :
    public virtual JComparator<typename JElement_t::key_type, 
			       typename JElement_t::mapped_type>,
    public virtual JMappableCollection<typename JElement_t::key_type, 
				       typename JElement_t::mapped_type>,
    public JNavigableCollection<typename JContainer_t<JElement_t>::iterator,
				typename JContainer_t<JElement_t>::const_iterator,
				typename JContainer_t<JElement_t>::reverse_iterator,
				typename JContainer_t<JElement_t>::const_reverse_iterator>
  {
  public:

    typedef typename JElement_t::value_type                             value_type;
    typedef typename JElement_t::key_type                               key_type;
    typedef typename JElement_t::mapped_type                            mapped_type;

    typedef typename JContainer_t<JElement_t>::iterator                 iterator;
    typedef typename JContainer_t<JElement_t>::const_iterator           const_iterator;
    typedef typename JContainer_t<JElement_t>::reverse_iterator         reverse_iterator;
    typedef typename JContainer_t<JElement_t>::const_reverse_iterator   const_reverse_iterator;

    typedef std::pair<const_iterator, bool>                             pair;
    typedef JCollectionElementTransformer<value_type>                   transformer_type;


    /**
     * Virtual destructor.
     */
    virtual ~JAbstractCollection() 
    {}


    /**
     * Transformation of collection.
     *
     * \param  transformer  element transformer
     */
    virtual void transform(const transformer_type& transformer)
    {
      std::vector<value_type> buffer(this->begin(), this->end());

      this->clear();

      for (typename std::vector<value_type>::const_iterator i = buffer.begin(); i != buffer.end(); ++i)
	this->insert(transformer(*i));

      /*
      for (iterator i = this->begin(); i != this->end(); ++i)
	*i = transformer(*i);
      */
    }
 

    /**
     * Insert element.
     *
     * \param  element      new element
     */
    virtual pair insert(const value_type& element) = 0;


    /**
     * Get first position of element i, where x >= *i.
     *
     * \param  x            key
     * \return              position of corresponding element
     */
    virtual const_iterator lower_bound(const key_type& x) const = 0;


    /**
     * Get first position of element i, where x >= *i.
     *
     * \param  x            key
     * \return              position of corresponding element
     */
    virtual iterator lower_bound(const key_type& x) = 0;


    /**
     * Get number of elements in collection.
     *
     * \return             number of elements
     */
    virtual size_t size() const 
    {
      return (size_t) std::distance(this->begin(), this->end());
    }


    /**
     * Verify emptiness of collection.
     *
     * \return             true if empty, else false
     */
    virtual bool empty() const 
    {
      return this->begin() == this->end();
    }
  };


  /**
   * Copy collection from JAbstractCollection<> to JMappableCollection<>.
   *
   * \param  input     JAbstractCollection<>
   * \param  output    JMappableCollection<>
   */
  template<class JElement_t, template<class> class JContainer_t, class JKey_t, class JValue_t>
  inline void copy(const JAbstractCollection<JElement_t, JContainer_t>& input,
		   JMappableCollection<JKey_t, JValue_t>&               output)
  {
    output.clear();

    for (typename JAbstractCollection<JElement_t, JContainer_t>::const_iterator i = input.begin(); i != input.end(); ++i)
      output.put(i->getKey(), i->getValue());
  }
}

#endif