/** -*- C++ -*-
 **
 **  KAI C++ Compiler
 **
 **  Copyright (C) 1996-2001 Intel Corp. All rights reserved.
 **/
/**
 **  Lib++  : The Modena C++ Standard Library,
 **           Version 2.4, October 1997
 **
 **  Copyright (c) 1995-1997 Modena Software Inc.
 **/

#ifndef __KAI_ITERATOR
#define __KAI_ITERATOR

#include <mcompile.h>
#include <iosfwd>
#include <cstddef>

namespace std {

// Subclause 24.3.1 -- Standard iterator tags


// 24.3.3 Standard Iterator tags
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag, public output_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag  {};

#if KAI_NONSTD_ITERATOR
// Function distance_type is not part of current ANSI draft, but widely used in 
// previous drafts and the original STL.
template <class T>
inline ptrdiff_t* distance_type(const T*) { return (ptrdiff_t*)(0); }
#endif /* KAI_NONSTD_ITERATOR */

// 24.3.1 Iterator traits
template <class Iterator>
struct iterator_traits {
    typedef typename Iterator::value_type	value_type;
    typedef typename Iterator::difference_type	difference_type;
    typedef typename Iterator::pointer		pointer;
    typedef typename Iterator::reference	reference;
    typedef typename Iterator::iterator_category iterator_category;
#if KAI_NONSTD_ITERATOR
    typedef typename Iterator::difference_type	distance_type;	// non-standard
#endif /* KAI_NONSTD_ITERATOR */
};

template <class T>
struct iterator_traits<T*> {
     typedef ptrdiff_t			difference_type;
     typedef T				value_type;
     typedef T *			pointer;
     typedef T &			reference;
     typedef random_access_iterator_tag iterator_category;
#if KAI_NONSTD_ITERATOR
    typedef ptrdiff_t			distance_type;	// non-standard
#endif /* KAI_NONSTD_ITERATOR */
};
template <class T>
struct iterator_traits<const T*> {
     typedef ptrdiff_t			difference_type;
     typedef T				value_type;
     typedef const T *			pointer;
     typedef const T &			reference;
     typedef random_access_iterator_tag iterator_category;
#if KAI_NONSTD_ITERATOR
    typedef ptrdiff_t			distance_type;	// non-standard
#endif /* KAI_NONSTD_ITERATOR */
};

// 24.3.2 -- Basic iterators
template <class Category, class T, class Distance = ptrdiff_t, class Pointer = T*, class Reference = T& >
struct iterator {
    typedef T         value_type;
    typedef Distance  difference_type;
    typedef Pointer   pointer;
    typedef Reference reference;
    typedef Category  iterator_category;
#if KAI_NONSTD_ITERATOR
    typedef Distance  distance_type;	// non-standard
#endif /* KAI_NONSTD_ITERATOR */
};

#if KAI_NONSTD_ITERATOR
// These will probably disappear in the future. Use iterator directly.
struct output_iterator : public iterator<output_iterator_tag, void, void, void, void> {};

template <class T, class Distance = ptrdiff_t>    
struct input_iterator : public iterator<input_iterator_tag, T, Distance> {};

template <class T, class Distance = ptrdiff_t>    
struct forward_iterator : public iterator<forward_iterator_tag, T, Distance> {};

template <class T, class Distance = ptrdiff_t>    
struct bidirectional_iterator : public iterator<bidirectional_iterator_tag, T, Distance> {};

template <class T, class Distance = ptrdiff_t>    
struct random_access_iterator : public iterator<random_access_iterator_tag, T, Distance> {};
#endif /* KAI_NONSTD_ITERATOR */


// 24.3.4 Iterator operations
// To make advance and distance more efficient, we use an overloaded function 
// to automatically select the most efficient version.
}  // namespace std
namespace __kai {

template <class Iterator, class Distance>
void __advance(Iterator& i, Distance n, std::input_iterator_tag *)
{
    while (n--)
	++i;
}
template <class Iterator, class Distance>
void __advance(Iterator& i, Distance n, std::bidirectional_iterator_tag *)
{
     if (n > 0)
         while (n--) ++i;
     else
         while (n++) --i;
}
template <class Iterator, class Distance>
inline void __advance(Iterator& i, Distance n, std::random_access_iterator_tag *)
{
    i += n;
}

template <class Iterator, class Distance>
Distance __distance(Iterator first, Iterator last, std::input_iterator_tag *)
{
    Distance n = 0;
    while (first != last) {
	++first;
	++n;
    }
    return n;
}
template <class Iterator, class Distance>
inline Distance __distance(Iterator first, Iterator last, std::random_access_iterator_tag *)
{
    return last - first;
}


} // namespace __kai
namespace std {

template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n)
{
    typedef typename iterator_traits <InputIterator>::iterator_category Category;
    __kai::__advance(i, n, (Category*)0);
}
template <class InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last)
{
    typedef typename iterator_traits<InputIterator>::iterator_category Category;
    typedef typename iterator_traits<InputIterator>::difference_type Distance;
    return __kai::__distance<InputIterator,Distance>(first, last, (Category*)0);
}

// Subclause 24.4 -- Predefined iterators
// Section 24.4.1 -- Reverse iterators
// Subclause 24.4.1.1 -- class reverse_iterator
template <class Iterator> 
class reverse_iterator 
     : public iterator<typename iterator_traits<Iterator>::iterator_category,
		       typename iterator_traits<Iterator>::value_type,
		       typename iterator_traits<Iterator>::difference_type,
		       typename iterator_traits<Iterator>::pointer,
		       typename iterator_traits<Iterator>::reference>
{
protected:
    Iterator current;

public:
    typedef Iterator						iterator_type;
    typedef typename iterator_traits<Iterator>::difference_type difference_type;
    typedef typename iterator_traits<Iterator>::reference	reference;
    typedef typename iterator_traits<Iterator>::pointer		pointer;

    reverse_iterator() {}
    explicit reverse_iterator(Iterator x) : current(x) {}
    template <class U> reverse_iterator(const reverse_iterator<U>& u) : current(u.base()) { }

    Iterator base() const { return current; }
    reference operator*() const { Iterator tmp = current; return *--tmp; }
    pointer operator->() const { return &(operator*()); }

    reverse_iterator& operator++()	{ --current; return *this; }
    reverse_iterator operator++(int)	{ reverse_iterator tmp = *this; --current; return tmp; }
    reverse_iterator& operator--()	{ ++current; return *this; }
    reverse_iterator operator--(int)	{ reverse_iterator tmp = *this; ++current; return tmp; }

    reverse_iterator operator+(difference_type n) const { return reverse_iterator(current - n); }
    reverse_iterator& operator+=(difference_type n) 	{ current -= n; return *this; }
    reverse_iterator operator-(difference_type n) const { return reverse_iterator(current+n); }
    reverse_iterator& operator-=(difference_type n)	{ current += n; return *this; }

    reference operator[](difference_type n) const { return current[-n-1]; }
};

template <class Iter>
inline bool operator==(const reverse_iterator<Iter>& x, const reverse_iterator<Iter>& y){ return y.base() == x.base(); }
template <class Iter>
inline bool operator<(const reverse_iterator<Iter>& x, const reverse_iterator<Iter>& y){ return y.base() < x.base(); }
template <class Iter>
inline bool operator!=(const reverse_iterator<Iter>& x, const reverse_iterator<Iter>& y){ return y.base() != x.base(); }
template <class Iter>
inline bool operator>(const reverse_iterator<Iter>& x, const reverse_iterator<Iter>& y){ return y.base() > x.base(); }
template <class Iter>
inline bool operator>=(const reverse_iterator<Iter>& x, const reverse_iterator<Iter>& y){ return y.base() >= x.base(); }
template <class Iter>
inline bool operator<=(const reverse_iterator<Iter>& x, const reverse_iterator<Iter>& y){ return y.base() <= x.base(); }

template <class Iter>
typename reverse_iterator<Iter>::difference_type operator-(const reverse_iterator<Iter>& x,
							   const reverse_iterator<Iter>& y)
{
    return y.base() - x.base();
}
template <class Iter>
reverse_iterator<Iter> operator+(typename reverse_iterator<Iter>::difference_type n, reverse_iterator<Iter>& x)
{
    return reverse_iterator<Iter>(x.base() - n);
} 

//----------------------------------------
// Subclause 24.4.2 -- Insert iterators
//----------------------------------------

// Section 24.4.2.1 -- class back_insert_iterator
template <class Container>
class back_insert_iterator : public iterator <output_iterator_tag, void, void, void, void>
{
protected:
    Container * container;
public:
    typedef Container container_type;

    explicit back_insert_iterator(Container& x) : container(&x) {}

    back_insert_iterator<Container>& operator=(typename Container::const_reference value) { 
	container->push_back(value); 
	return *this; 
    }

    back_insert_iterator<Container>& operator*() { return *this; }
    back_insert_iterator<Container>& operator++() { return *this; }
    back_insert_iterator<Container>& operator++(int) { return *this; }
};

template <class Container>
inline back_insert_iterator<Container> back_inserter(Container& x)
{
    return back_insert_iterator<Container>(x);
}

// Section 24.4.2.3 -- class front_insert_iterator
template <class Container>
class front_insert_iterator : public iterator <output_iterator_tag, void, void, void, void> {
protected:
    Container * container;
public:
    typedef Container container_type;

    explicit front_insert_iterator(Container& x) : container (&x) {}

    front_insert_iterator<Container>& operator=(typename Container::const_reference value) { 
	container->push_front(value); 
	return *this; 
    }
    front_insert_iterator<Container>& operator*() { return *this; }
    front_insert_iterator<Container>& operator++() { return *this; }
    front_insert_iterator<Container>& operator++(int) { return *this; }
};

template <class Container>
inline front_insert_iterator<Container> front_inserter(Container& x)
{
    return front_insert_iterator<Container>(x);
}

// Section 24.4.2.5 -- class insert_iterator
template <class Container>
class insert_iterator : public iterator <output_iterator_tag, void, void, void, void> {
protected:
    Container * container;
    typename Container::iterator iter;
public:
    typedef Container container_type;

    insert_iterator(Container& x, typename Container::iterator i) : container(&x), iter(i) {}

    insert_iterator<Container>&operator=(typename Container::const_reference value) { 
	iter = container->insert(iter, value);
	++iter;
	return *this;
    }

    insert_iterator<Container>& operator*() { return *this; }
    insert_iterator<Container>& operator++() { return *this; }
    insert_iterator<Container>& operator++(int) { return *this; }
};

template <class Container, class Iterator>
inline insert_iterator<Container> inserter(Container& x, Iterator i)
{
    return insert_iterator<Container>(x, Container::iterator(i));
}


//--------------------------------------------------------------------------------
// 24.5 Stream iterators
//--------------------------------------------------------------------------------

// 24.5 istream_iterator
template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t>
class istream_iterator : public iterator <input_iterator_tag, T, Distance, const T*, const T&> {

    friend bool operator==<T,char,traits,Distance>(const istream_iterator<T, charT, traits, Distance>& x,
			                           const istream_iterator<T, charT, traits, Distance>& y);
public:
    typedef charT   char_type;
    typedef traits  traits_type; 
    typedef basic_istream<charT, traits>   istream_type;

    istream_iterator() : in_stream(NULL) {}
    istream_iterator(istream_type& s) : in_stream(&s) { read(); }
    istream_iterator(const istream_iterator& x) : in_stream(x.in_stream), value(x.value) {}
 
    const T& operator*() const { return value; }
    const T* operator->() const { return &(operator*()); }
 
    istream_iterator& operator++() { read(); return *this; }
    istream_iterator operator++(int) {
	istream_iterator tmp = *this;
	read();
	return tmp;
    }

private:
    istream_type* in_stream;
    T             value;

    void read() {
	if (in_stream) {
	    __KAI_LOCK_STREAM(*in_stream);
	    if (!*in_stream || !(*in_stream >> value))
		in_stream = NULL;
	}
    }
};

template <class T, class charT, class traits, class Distance>
inline bool operator==(const istream_iterator<T, charT, traits, Distance>& x,
		       const istream_iterator<T, charT, traits, Distance>& y)
{
    return x.in_stream == y.in_stream;
}

template <class T, class charT, class traits, class Distance>
inline bool operator!=(const istream_iterator<T, charT, traits, Distance>& x,
		       const istream_iterator<T, charT, traits, Distance>& y)
{
    return !(x == y);
}
 
//24.5.2 ostream_iterator
template <class T, class charT = char, class traits =  char_traits<charT> > 
class ostream_iterator : public iterator <output_iterator_tag, void, void, void, void> {

public:
    typedef charT   char_type;
    typedef traits  traits_type; 
    typedef basic_ostream<charT, traits>   ostream_type;
    ostream_iterator(ostream_type& s) : out_stream(&s), delim(0) {}
    ostream_iterator(ostream_type& s, const charT* delimiter) : out_stream(&s), delim(delimiter) {}
    ostream_iterator(const ostream_iterator& x) : out_stream(x.out_stream), delim (x.delim) {}

    ostream_iterator<T, charT, traits>& operator=(const T& value) { 
	__KAI_LOCK_STREAM(*out_stream);
	*out_stream << value;
	if (delim) *out_stream << delim;
	return *this;
    }
    ostream_iterator<T, charT, traits>& operator*()      { return *this; }
    ostream_iterator<T, charT, traits>& operator++()     { return *this; } 
    ostream_iterator<T, charT, traits>& operator++(int)  { return *this; } 

private:
    ostream_type* out_stream;
    const charT*  delim;
};

// 24.5.3 istreambuf_iterator
template < class charT, class traits = char_traits<charT> >
class istreambuf_iterator : public iterator<input_iterator_tag, charT, typename traits::off_type, charT*, charT&>
{
public:
    typedef charT			char_type;
    typedef traits			traits_type;
    typedef typename traits::int_type	int_type;
    typedef basic_streambuf<charT, traits> streambuf_type;
    typedef basic_istream<charT, traits>   istream_type;
#if KAI_NONSTD_ITERATOR
    typedef typename traits::pos_type	pos_type;
    typedef typename traits::off_type	off_type;
#endif /* KAI_NONSTD_ITERATOR */

    class proxy {
	charT data;
	streambuf_type *sbuf;
	proxy(charT c, streambuf_type *s): data(c), sbuf(s){}
    public:
	charT operator*(){return data; }
	friend class istreambuf_iterator;
    };
 
    istreambuf_iterator() MSIPL_THROW : sbuf(0), data(traits::eof ()) { }
    istreambuf_iterator(istream_type& is) MSIPL_THROW : sbuf(is.rdbuf()) { __kai_peek_char(); }
    istreambuf_iterator(streambuf_type* sb) MSIPL_THROW : sbuf(sb) { __kai_peek_char(); }
    istreambuf_iterator(const proxy& p) MSIPL_THROW : sbuf(p.sbuf), data(p.data) {}

    inline char_type operator*() const { return data; }

    istreambuf_iterator& operator++() {
	// It is undefined if the user calls this when it is in the end-of-stream condition.
	traits::int_type c = sbuf->snextc();
	data=traits::to_char_type(c);
	if (traits::eq_int_type(c, traits::eof()))
	    sbuf=NULL;
        return *this;
    }

    proxy operator++(int) {
	// It is undefined if the user calls this when it is in the end-of-stream condition.
	proxy prev(data, sbuf);
	traits::int_type c = sbuf->snextc();
	data=traits::to_char_type(c);
	if (traits::eq_int_type(c, traits::eof()))
	    sbuf=NULL;
        return prev;
    }

    inline bool equal(const istreambuf_iterator& b) const {
	return ((sbuf == 0) == (b.sbuf == 0));
    }

private:
    streambuf_type* sbuf;
    charT data;

    void __kai_peek_char() {
	traits::int_type c;
	if (sbuf==NULL || traits::eq_int_type((c=sbuf->sgetc()), traits::eof())) {
	    sbuf=NULL;
	    data=traits::eof();
	} else {
	    data=traits::to_char_type(c);
	}
    }    
};

template <class charT, class traits>
inline bool operator==(const istreambuf_iterator<charT, traits>& a, const istreambuf_iterator<charT, traits>& b)
{ return a.equal(b); }

template <class charT, class traits>
inline bool operator!=(const istreambuf_iterator<charT, traits>& a, const istreambuf_iterator<charT, traits>& b)
{ return !a.equal(b); }

// 24.5.4 ostreambuf_iterator
template <class charT, class traits =  char_traits<charT> >
class ostreambuf_iterator : public iterator <output_iterator_tag, void, void, void, void>
{
public:
    typedef  charT                         char_type;
    typedef  traits                        traits_type;
    typedef  basic_ostream<charT, traits>   ostream_type;
    typedef  basic_streambuf<charT, traits> streambuf_type;
#if KAI_NONSTD_ITERATOR
    typedef  typename traits::pos_type     pos_type;
    typedef  typename traits::off_type     off_type;
    typedef  typename traits::int_type     int_type;
#endif /* KAI_NONSTD_ITERATOR */

    ostreambuf_iterator(ostream_type& s) MSIPL_THROW : sbuf(s.rdbuf()) {}
    ostreambuf_iterator(streambuf_type* s) MSIPL_THROW : sbuf(s) {}

    ostreambuf_iterator& operator*() { return *this; }
    ostreambuf_iterator& operator++() { return *this; }
    ostreambuf_iterator& operator++(int) { return *this; }

    ostreambuf_iterator& operator=(char_type c) {
	if (sbuf && traits::eq_int_type(sbuf->sputc(c), traits::eof()))
	        sbuf = 0;
	return *this;
    }
    bool failed() const MSIPL_THROW { return !sbuf; }

private:
    streambuf_type*  sbuf;
};

#if KAI_NONSTD_ITERATOR
// reverse_bidirectional_iterator
// This will go away in future versions of the library.
// Use reverse_iterator instead.
template <class BidirectionalIterator, 
          class T = typename iterator_traits<BidirectionalIterator>::value_type&,
          class Reference = T&, 
	  class Pointer = T*, 
          class Distance = ptrdiff_t> 
class reverse_bidirectional_iterator : public iterator<bidirectional_iterator_tag, T, Distance> {

    typedef reverse_bidirectional_iterator<BidirectionalIterator, T, Reference, Pointer, Distance> self;

    friend bool operator==<BidirectionalIterator,T,Reference,Pointer,Distance>(const self& x, const self& y);


protected:

    BidirectionalIterator current;

public:

    reverse_bidirectional_iterator() {}

    explicit reverse_bidirectional_iterator (BidirectionalIterator x) : current (x) {}

    BidirectionalIterator base() const { return current; }

    Reference operator*() const { 
        BidirectionalIterator tmp = current;
        return *--tmp;
    }

    //
    // Waiting for clarifications on this
    //
    // Pointer operator-> () const { return & (operator* ()); }

    self& operator++() {
        --current;
        return *this;
    }
    self operator++(int) {
        self tmp = *this;
        --current;
        return tmp;
    }
    self& operator--() { 
        ++current;
        return *this;
    }
    self operator--(int) {
        self tmp = *this;
        ++current;
        return tmp;
    }
};

template <class BidirectionalIterator, class T, class Reference, class Pointer, class Distance>
inline bool operator==(
  const reverse_bidirectional_iterator<BidirectionalIterator, T, Reference, Pointer, Distance>& x, 
  const reverse_bidirectional_iterator<BidirectionalIterator, T, Reference, Pointer, Distance>& y)
{ 
    return x.current == y.current;
}
#endif /* KAI_NONSTD_ITERATOR */

} // namespace std

#endif /* __KAI_ITERATOR */