/* Copyright (c) 1997-2004
   Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
   http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de

   This program 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; either version 2, or (at your option) any
   later version: http://www.gnu.org/licenses/gpl.txt.

   This program 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.
*/

#ifndef _POLYMAKE_SERIES_H
#define _POLYMAKE_SERIES_H "$Project: polymake $$Id: Series.h,v 1.13 2004/06/22 16:22:44 gawrilow Exp $"

#ifndef _POLYMAKE_COMPARATORS_H
#  include <comparators.h>
#endif
#ifndef _POLYMAKE_PLAUSIBLE_CHECKS_H
#  include <plausible_checks.h>
#endif

namespace pm {

/* ------------
 *  GenericSet
 * ------------ */

/* This should belong into GenericSet.h, but Series must be derived from GenericSet.
   On the other hand, nacked Series don't need any set-theoretical stuff defined there.
*/
template <typename E, typename Comparator=BuildBinary<operations::cmp> > class Set;
struct is_set;

template <typename _Set, typename E=typename _Set::element_type, typename Comparator=typename _Set::element_comparator>
class GenericSet : public Generic<_Set>, public operators::base {
protected:
   GenericSet() { }
   GenericSet(const GenericSet&) { }
public:
   typedef E element_type;
   typedef Comparator element_comparator;
   typedef Set<E,Comparator> persistent_type;
   typedef GenericSet generic_type;

   Comparator get_comparator() const { return Comparator(); }

   template <class Result>
   struct construct_generic {
      typedef GenericSet<Result, E, Comparator> type;
   };
   typedef is_set generic_tag;
};

template <typename Set, typename E, typename Comparator>
struct spec_object_traits< GenericSet<Set,E,Comparator> >
   : spec_or_model_traits<Set,is_container> {
   static const IO_separator_kind IO_separator=IO_sep_inherit;
};

/* --------
 *  Series
 * -------- */

template <typename E, bool step_equal_1> class Series;

template <typename E, bool _forward>
class sequence_iterator {
public:
   typedef random_access_iterator_tag iterator_category;
   typedef E value_type;
   typedef const E* pointer;
   typedef const E& reference;
   typedef ptrdiff_t difference_type;
   typedef sequence_iterator iterator;
   typedef sequence_iterator const_iterator;
protected:
   E cur;

public:
   sequence_iterator() { }
   sequence_iterator(typename function_argument<E>::type cur_arg) : cur(cur_arg) { }

   reference operator* () const { return cur; }
   pointer operator-> () const { return &cur; }

   const E operator[] (int i) const { return _forward ? cur+i : cur-i; }

   iterator& operator++ () { _forward ? ++cur : --cur; return *this; }
   iterator& operator-- () { _forward ? --cur : ++cur; return *this; }
   const iterator operator++ (int) { iterator copy=*this; operator++(); return copy; }
   const iterator operator-- (int) { iterator copy=*this; operator--(); return copy; }
   iterator& operator+= (int i) { _forward ? (cur+=i) : (cur-=i); return *this; }
   iterator& operator-= (int i) { _forward ? (cur-=i) : (cur+=i); return *this; }
   const iterator operator+ (int i) const { return _forward ? cur+i : cur-i; }
   const iterator operator- (int i) const { return _forward ? cur-i : cur+i; }
   friend const iterator operator+ (int i, const iterator& it) { return it+i; }
#if __GNUC__==3 && __GNUC_MINOR__<=1
   bool operator== (const iterator& it) const { return cur==*it; }
   bool operator== (const sequence_iterator<E, !_forward>& it) const { return cur==*it; }
   bool operator!= (const iterator& it) const { return !operator==(it); }
   bool operator!= (const sequence_iterator<E, !_forward>& it) const { return !operator==(it); }
#else
   template <bool _forward2>
   bool operator== (const sequence_iterator<E,_forward2>& it) const { return cur==*it; }
   template <bool _forward2>
   bool operator!= (const sequence_iterator<E,_forward2>& it) const { return !operator==(it); }
#endif

   difference_type operator- (const iterator& it) const { return _forward ? cur-it.cur : it.cur-cur; }
   bool operator< (const iterator& it) const { return _forward ? cur<it.cur : it.cur<cur; }
   bool operator> (const iterator& it) const { return it < *this; }
   bool operator<= (const iterator& it) const { return !(it < *this); }
   bool operator>= (const iterator& it) const { return !(*this < it); }
};

template <typename E, bool _forward>
class series_iterator : public sequence_iterator<E,_forward> {
   typedef sequence_iterator<E,_forward> super;
protected:
   E _step;

public:
   typedef series_iterator iterator;
   typedef series_iterator const_iterator;

   series_iterator() { }
   series_iterator(typename function_argument<E>::type cur_arg, typename function_argument<E>::type step_arg)
      : super(cur_arg), _step(step_arg) { }

   const E operator[] (int i) const { return _forward ? this->cur+i*_step : this->cur-i*_step; }

   typename function_argument<E>::type step() const { return _step; }

   iterator& operator++ () { _forward ? (this->cur+=_step) : (this->cur-=_step); return *this; }
   iterator& operator-- () { _forward ? (this->cur-=_step) : (this->cur+=_step); return *this; }
   const iterator operator++ (int) { iterator copy=*this; operator++(); return copy; }
   const iterator operator-- (int) { iterator copy=*this; operator--(); return copy; }
   iterator& operator+= (int i) { _forward ? (this->cur+=i*_step) : (this->cur-=i*_step); return *this; }
   iterator& operator-= (int i) { _forward ? (this->cur-=i*_step) : (this->cur+=i*_step); return *this; }
   const iterator operator+ (int i) const { return iterator(_forward ? this->cur+i*_step : this->cur-i*_step, _step); }
   const iterator operator- (int i) const { return iterator(_forward ? this->cur-i*_step : this->cur+i*_step, _step); }
   friend const iterator operator+ (int i, const iterator& it) { return it+i; }
   typename super::difference_type operator- (const super& it) const { return (_forward ? this->cur-*it : *it-this->cur)/_step; }
   bool operator< (const iterator& it) const { return (_forward ^ _step>0) ? this->cur<*it : *it<this->cur; }
   bool operator> (const iterator& it) const { return it < *this; }
   bool operator<= (const iterator& it) const { return !(it < *this); }
   bool operator>= (const iterator& it) const { return !(*this < it); }
};

template <typename E, bool _forward>
struct comparable_iterator< series_iterator<E,_forward> > {
   typedef sequence_iterator<E,_forward> type;

   static void assign(series_iterator<E,_forward>& it, const type& other)
   {
      static_cast<type&>(it)=other;
   }

   static void advance(sequence_iterator<E,_forward>& it, const series_iterator<E,_forward>& other, int n)
   {
      it+=n*other.step();
   }
};

template <typename E>
class count_down_iterator : public sequence_iterator<E,false> {
public:
   typedef count_down_iterator iterator;
   typedef count_down_iterator const_iterator;

   count_down_iterator() { }
   count_down_iterator(E cur_arg) : sequence_iterator<E,false>(cur_arg) { }
   bool at_end() const { return !this->cur; }
};

template <typename E>
struct check_iterator_feature<count_down_iterator<E>, end_sensitive> : True { };

template <typename E>
class Series<E,true> : public GenericSet<Series<E,true>, E, BuildBinary<operations::cmp> > {
protected:
   E _start;
   int _size;
public:
   typedef Series persistent_type;
   typedef E value_type;
   typedef E reference;
   typedef reference const_reference;

   Series() : _start(0), _size(0) { }

   explicit Series(typename function_argument<E>::type start_arg, int size_arg=1)
      : _start(start_arg), _size(size_arg)
   {
      INDEX_CHECK(size_arg<0, "Series - negative size");
   }

   // for the sake of interchangeability with Series<E,false>
   Series(typename function_argument<E>::type start_arg, int size_arg,
	  typename function_argument<E>::type /*dummy_step*/)
      : _start(start_arg), _size(size_arg)
   {
      INDEX_CHECK(size_arg<0, "Series - negative size");
   }

   int size() const { return _size; }
   bool empty() const { return !_size; }

   E step() const { return E(1); }

   typedef sequence_iterator<E,true> iterator;
   typedef iterator const_iterator;
   typedef sequence_iterator<E,false> reverse_iterator;
   typedef reverse_iterator const_reverse_iterator;

   const_iterator begin() const { return _start; }
   const_iterator end() const { return _start+_size; }
   const_reverse_iterator rbegin() const { return _start+_size-1; }
   const_reverse_iterator rend() const { return _start-1; }

   E front() const { return _start; }
   E back() const { return _start+_size-1; }

   E operator[] (int i) const
   {
      INDEX_CHECK(i>=_size, "operator[] - series index out of range");
      return _start+i;
   }

   bool contains(typename function_argument<E>::type k) const
   {
      return k>=_start && k<_start+_size;
   }
};

template <typename E, bool step_equal_1>
class Series : public GenericSet<Series<E,step_equal_1>, E, BuildBinary<operations::cmp> > {
protected:
   E _start;
   int _size;
   E _step;
public:
   typedef Series persistent_type;
   typedef E value_type;
   typedef E reference;
   typedef reference const_reference;

   Series() : _start(0), _size(0), _step(0) { }

   Series(typename function_argument<E>::type start_arg, int size_arg,
	  typename function_argument<E>::type step_arg)
      : _start(start_arg), _size(size_arg), _step(step_arg)
   {
      INDEX_CHECK(size_arg<0, "Series - negative size");
   }

   int size() const { return _size; }
   bool empty() const { return !_size; }

   typename function_argument<E>::type step() const { return _step; }

   typedef series_iterator<E, true> iterator;
   typedef iterator const_iterator;
   typedef series_iterator<E, false> reverse_iterator;
   typedef reverse_iterator const_reverse_iterator;

   iterator begin() const { return iterator(_start, _step); }
   iterator end() const { return iterator(_start+_size*_step, _step); }
   reverse_iterator rbegin() const { return reverse_iterator(_start+(_size-1)*_step, _step); }
   reverse_iterator rend() const { return reverse_iterator(_start-_step, _step); }

   E front() const { return _start; }
   E back() const { return _start+(_size-1)*_step; }

   E operator[] (int i) const
   {
      INDEX_CHECK(i>=_size, "operator[] - series index out of range");
      return _start+i*_step;
   }

   bool contains(typename function_argument<E>::type k) const
   {
      return k>=_start && k<_start+_size*_step && !((k-_start)%_step);
   }
};

/// alias for an integer series
typedef Series<int,false> series;

/// alias for an integer sequence
typedef Series<int,true> sequence;

/// Create a sequence of all integral numbers between and including $start$ and $end$
template <typename E> inline
Series<E,true>
range(E start, E end)
{
   return Series<E,true>(start, int(end-start)+1);
}

template <typename E>
class Count_down {
protected:
   int _size;
public:
   typedef const E const_reference;
   typedef const_reference reference;
   typedef E value_type;

   explicit Count_down(int size_arg) : _size(size_arg) { }

   int size() const { return _size; }

   typedef count_down_iterator<E> iterator;
   typedef iterator const_iterator;
   typedef typename Series<E,true>::iterator reverse_iterator;
   typedef reverse_iterator const_reverse_iterator;

   iterator begin() const { return _size; }
   iterator end() const { return 0; }
   reverse_iterator rbegin() const { return 1; }
   reverse_iterator rend() const { return _size+1; }

   E operator[] (int i) const
   {
      INDEX_CHECK(i>_size, "operator[] - series index out of range");
      return _size-i;
   }

   E front() const { return _size; }
   E back() const { return 1; }
};

typedef Count_down<int> count_down;

template <typename E>
struct spec_object_traits< Count_down<E> >
   : spec_object_traits<is_container> { };

template <typename Container>
class construct_sequence_indexed
   : public modified_container_pair_impl< construct_sequence_indexed<Container>,
	       cons< Container1< Container >,
               cons< Container2< sequence >,
               cons< Accessor< pair<nothing, BuildBinaryIt<operations::second_deref> > >,
		     Hidden< Container > > > >
            > {
public:
   Container& get_container1() { return this->hidden(); }
   const Container& get_container1() const { return this->hidden(); }
   sequence get_container2() const { return sequence(0, this->hidden().size()); }
};

template <typename Iterator, bool _reverse=false>
class indexed_random_iterator
   : public iterator_traits<Iterator>::derivable_type {
protected:
   typedef typename iterator_traits<Iterator>::derivable_type super;
   typename comparable_iterator<Iterator>::type _begin;

   template <typename,bool> friend class indexed_random_iterator;
public:
   typedef indexed_random_iterator<typename iterator_traits<Iterator>::iterator, _reverse>
      iterator;
   typedef indexed_random_iterator<typename iterator_traits<Iterator>::const_iterator, _reverse>
      const_iterator;

   indexed_random_iterator() { }

   indexed_random_iterator(const Iterator& cur_arg)
      : super(cur_arg), _begin(cur_arg) { }
   indexed_random_iterator(const Iterator& cur_arg, const Iterator& begin_arg)
      : super(cur_arg), _begin(begin_arg) { }
   indexed_random_iterator(typename alt_constructor<Iterator>::arg_type& cur_arg)
      : super(cur_arg), _begin(cur_arg) { }
   indexed_random_iterator(typename alt_constructor<Iterator>::arg_type& cur_arg,
			   typename alt_constructor<Iterator>::arg_type& begin_arg)
      : super(cur_arg), _begin(begin_arg) { }

   indexed_random_iterator(const iterator& it)
      : super(static_cast<const typename iterator::super&>(it)), _begin(it._begin) { }

   indexed_random_iterator& operator= (const iterator& it)
   {
      super::operator=(static_cast<const typename iterator::super&>(it));
      _begin=it._begin;
      return *this;
   }

   int index() const
   {
      return _reverse ? _begin-static_cast<const super&>(*this)-1 : static_cast<const super&>(*this)-_begin;
   }

   void narrow_range(int distance_front, int distance_back, bool renumber)
   {
      pm::narrow_range(static_cast<super&>(*this), distance_front, distance_back, renumber);
      if (renumber)
	 comparable_iterator<Iterator>::advance(_begin, static_cast<const super&>(*this),
						_reverse ? distance_back : distance_front);
   }
};

template <typename Iterator, bool _reverse, typename Feature>
struct check_iterator_feature<indexed_random_iterator<Iterator,_reverse>, Feature>
   : check_iterator_feature<Iterator,Feature> { };

template <typename Iterator, bool _reverse>
struct check_iterator_feature<indexed_random_iterator<Iterator,_reverse>, indexed> : True { };

template <typename Iterator, bool _reverse>
struct check_iterator_feature<indexed_random_iterator<Iterator,_reverse>, has_narrow_range> : True { };

template <typename Iterator, bool _reverse>
struct comparable_iterator< indexed_random_iterator<Iterator,_reverse> >
   : comparable_iterator<Iterator> { };

template <typename Container>
class construct_random_indexed : public Container {
protected:
   construct_random_indexed();
   ~construct_random_indexed();
public:
   typedef indexed_random_iterator<typename Container::iterator> iterator;
   typedef indexed_random_iterator<typename Container::const_iterator> const_iterator;
   typedef indexed_random_iterator<typename Container::reverse_iterator, true> reverse_iterator;
   typedef indexed_random_iterator<typename Container::const_reverse_iterator, true> const_reverse_iterator;

   iterator begin() { return iterator(Container::begin()); }
   iterator end() { return iterator(Container::end(), Container::begin()); }
   const_iterator begin() const { return const_iterator(Container::begin()); }
   const_iterator end() const { return const_iterator(Container::end(), Container::begin()); }
   reverse_iterator rbegin() { return reverse_iterator(Container::rbegin(), Container::rend()); }
   reverse_iterator rend() { return reverse_iterator(Container::rend()); }
   const_reverse_iterator rbegin() const { return const_reverse_iterator(Container::rbegin(), Container::rend()); }
   const_reverse_iterator rend() const { return const_reverse_iterator(Container::rend()); }
};

template <typename Container>
struct default_enforce_feature<Container, indexed> {
   typedef typename if_else<identical<typename iterator_traits<typename container_traits<Container>::iterator>::iterator_category,
				      random_access_iterator_tag>::answer,
			    construct_random_indexed<Container>, construct_sequence_indexed<Container>
                           >::result
      container;
};

template <typename Container>
struct spec_object_traits< construct_random_indexed<Container> >
   : spec_object_traits<Container> { };

template <> struct feature_allow_order<resettable,indexed> : False { };
template <> struct feature_allow_order<end_sensitive,indexed> : False { };
template <> struct feature_allow_order<range_capable,indexed> : False { };

template <typename Container, typename Features>
struct default_enforce_features<Container, Features, object_classifier::constant>
   : default_enforce_features<construct_sequence_indexed<Container>, Features, object_classifier::manip> { };

template <typename Container>
struct default_enforce_features<Container, _reversed, object_classifier::constant> {
   typedef Container container;
};

template <typename Subset, typename Source,
	  typename source_generic=typename object_traits<Source>::generic_type>
class generic_of_subset { };

template <typename Subset, typename Source, typename Set, typename E, typename Comparator>
class generic_of_subset<Subset, Source, GenericSet<Set,E,Comparator> >
   : public GenericSet<Subset,E,Comparator> { };

template <typename Subsets, typename Source,
	  typename source_generic=typename object_traits<Source>::generic_type>
class generic_of_subsets {
public:
   typedef BuildBinary<operations::cmp> subset_element_comparator;
};

template <typename Subsets, typename Source, typename Set>
class generic_of_subsets<Subsets, Source, GenericSet<Set> >
   : public GenericSet<Subsets, typename object_traits<Source>::persistent_type, BuildBinary<operations::cmp> > {
public:
   typedef typename Source::element_comparator subset_element_comparator;
};

} // end namespace pm

namespace polymake {
   using pm::Series;
   using pm::series;
   using pm::sequence;
   using pm::range;
}

#endif // _POLYMAKE_SERIES_H

// Local Variables:
// mode:C++
// End:
