/* Copyright (c) 1997-2006
   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 7402 2006-07-27 23:44:14Z gawrilow $"

#ifndef _POLYMAKE_COMPARATORS_OPS_H
#  include <comparators_ops.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=operations::cmp<> > class 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;

   template <typename Result>
   struct rebind_generic {
      typedef GenericSet<Result, E, Comparator> type;
   };

   template <typename E1=E, typename E2=E1>
   struct rebind_comparator {
      typedef binary_op_builder<Comparator, const E1*, const E2*> builder;
      typedef typename builder::operation type;
   };

   template <typename Set2>
   struct comparator_for_pair {
      typedef typename rebind_comparator<E, typename Set2::element_type>::type cmp1;
      typedef typename Set2::template rebind_comparator<E, typename Set2::element_type>::type cmp2;
      typedef typename rebind_comparator<E, typename Set2::element_type>::builder builder;
      typedef typename identical<cmp1,cmp2>::type type;
   };

   typename rebind_comparator<>::type
   get_comparator() const
   {
      typedef typename rebind_comparator<>::builder cmpb;
      return cmpb::create(this->top().get_comparator_object());
   }

   template <typename E2>
   typename rebind_comparator<E2>::type
   get_comparator() const
   {
      typedef typename rebind_comparator<E2>::builder cmpb;
      return cmpb::create(this->top().get_comparator_object());
   }

   template <typename Set2>
   typename comparator_for_pair<Set2>::type
   get_comparator_for(const GenericSet<Set2>&) const
   {
      typedef typename comparator_for_pair<Set2>::builder cmpb;
      return cmpb::create(this->top().get_comparator_object());
   }

   const Comparator& get_comparator_object() const
   {
      // if this method is not overwritten in Top, then the comparator class is assumed to be dataless
      return reinterpret_cast<const Comparator&>(*this);
   }
};

struct is_set;

template <typename Set, typename E, typename Comparator>
struct spec_object_traits< GenericSet<Set,E,Comparator> >
   : spec_or_model_traits<Set,is_container> {
   typedef is_set generic_tag;
   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; }

   reference 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; }

   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); }

   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) { }

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

   typename super::reference 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 accompanying_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, 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, 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>,
					  list( Container1< Container >,
						Container2< sequence >,
						Operation< pair<nothing, BuildBinaryIt<operations::second_deref> > >,
						Hidden< Container > ) > {
public:
   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 accompanying_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)
   {
      static_cast<super&>(*this)=it;
      _begin=it._begin;
      return *this;
   }

   indexed_random_iterator& operator= (const Iterator& cur)
   {
      static_cast<super&>(*this)=cur;
      return *this;
   }
   indexed_random_iterator& operator= (typename alt_constructor<Iterator>::arg_type& cur)
   {
      static_cast<super&>(*this)=cur;
      return *this;
   }

   const indexed_random_iterator operator+ (int i) const
   {
      return static_cast<const super&>(*this)+i;
   }
   const indexed_random_iterator operator- (int i) const
   {
      return static_cast<const super&>(*this)-i;
   }
   friend const indexed_random_iterator operator+ (int i, const indexed_random_iterator& me)
   {
      return me+i;
   }

   typename super::difference_type operator- (const iterator& it) const
   {
      return static_cast<const super&>(*this)-it;
   }
   typename super::difference_type
   operator- (typename assign_const<const_iterator, !identical<iterator,const_iterator>::value>::type& it)
   {
      return static_cast<const super&>(*this)-it;
   }

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

private:
   void contract1(int distance_front, int, False)
   {
      static_cast<super&>(*this)+=distance_front;
   }
   void contract1(int distance_front, int distance_back, True)
   {
      super::contract(false, distance_front, distance_back);
   }
public:
   void contract(bool renumber, int distance_front, int distance_back=0)
   {
      contract1(distance_front, distance_back, bool2type<check_iterator_feature<super, contractable>::value>());
      if (renumber)
	 accompanying_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>, contractable> : True { };

template <typename Iterator, bool _reverse>
struct accompanying_iterator< indexed_random_iterator<Iterator,_reverse> >
   : accompanying_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>::value,
			    construct_random_indexed<Container>, construct_sequence_indexed<Container>
                           >::type
      container;
};

template <typename Container>
struct redirect_object_traits< construct_random_indexed<Container> > : object_traits<Container> { };

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

template <typename Container, typename Features>
struct default_enforce_features<Container, Features, object_classifier::is_constant>
   : default_enforce_features<construct_sequence_indexed<Container>, Features, object_classifier::is_manip> { };

template <typename Container>
struct default_enforce_features<Container, _reversed, object_classifier::is_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 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, 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:
