/* 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_MONOMIAL_H
#define _POLYMAKE_MONOMIAL_H "$Project: polymake $$Id: Monomial.h 4714 2004-06-22 16:23:15Z gawrilow $"

#include <SparseVector.h>
#include <GenericVector.h>
#include <Array.h>

#include <string>
#include <sstream>

namespace pm {

template <typename Exponent=int>
class Monomial {

  // no tailing zeros allowed

protected:
  typedef SparseVector<Exponent> monom;

  monom the_monom;
  Array<int> weights;  // FIXME: to be replaced by a traits class
                       // DEBUG: weight[i] > 0

  // FIXME: to be replaced by a traits class
  // term order: graded revlex order
  // m1 > m2  => return 1
  // m1 < m2  => return -1
  // m1 == m2 => return 0
  int cmp(const monom& m1, const monom& m2) const
  {
    Exponent weighted_sum1 = Exponent(0);
    Exponent weighted_sum2 = Exponent(0);

    for (typename Entire<monom>::const_iterator it1=entire(m1);
	 !it1.at_end(); ++it1) {
      const int index=it1.index();
      const int w= index<weights.size() ? weights[index] : 1;  // iff weights is to small
      weighted_sum1 += *it1*Exponent(w);
    }
    for (typename Entire<monom>::const_iterator it2=entire(m2);
	 !it2.at_end(); ++it2) {
      const int index=it2.index();
      const int w= index<weights.size() ? weights[index] : 1;
      weighted_sum2 += *it2*Exponent(w);
    }

    //    cerr << "cmp: weighted_sum of " << m1
    //	 << " : " << weighted_sum1 << endl;
    //    cerr << "cmp: weighted_sum of " << m2
    //	 << " : " << weighted_sum2 << endl;

    if (weighted_sum1 > weighted_sum2)
      return 1;
    if (weighted_sum1 < weighted_sum2)
      return -1;

    // revlex as tie-braker
    if (m1.dim() < m2.dim())
      return 1;
    if (m1.dim() > m2.dim())
      return -1;

    monom m = m1-m2;
    if (m.empty())
      return 0;

    const_iterator back=m.end();
    back--;
    if (*back < Exponent(0))
      //    if (m.back() > Exponent(0))  FIXME
      return 1;
    return -1;
  }

  void make_consistent()
  {
    if (the_monom.empty())
      the_monom.resize(0);

    else {
      const_iterator back=the_monom.end();
      back--;
      the_monom.resize(back.index()+1);
      //    prod.resize(the_monom.back().first+1);  FIXME
    }
  }

  bool is_consistent()
  {
    if (the_monom.empty())
      return the_monom.dim()==0;

    const_iterator back=the_monom.end();
    back--;

    //    Vector<Exponent> v=the_monom;
    //     cerr << v << "    back index: " << back.index()
    //	   << "    dim: " << the_monom.dim() << endl;

    //    return the_monom.back().first==the_monom.dim()-1;  FIXME
    return back.index()==the_monom.dim()-1;
  }

public:
  typedef typename monom::const_iterator const_iterator;
  typedef typename monom::iterator iterator;
  typedef typename iterator::reference reference;
  typedef reference const_reference;
  
  Monomial() {
    the_monom = monom(0);
    weights = Array<int>(0);
  }
  
  template <typename _Vector>
  Monomial(const GenericVector<_Vector,Exponent>& m, const Array<int>& w=Array<int>(0),
	   const bool proper_sized=false)
  {
    the_monom = m;
    make_consistent();
    weights = w;
    
#ifdef POLY_DEBUG
    if (!is_consistent())
      throw std::runtime_error("Monomial: Input vector has tailing zeros.");
#endif
  }
  
  int dim() const {
    return the_monom.dim();
  }

  void clear() {
    the_monom.clear();
  }
  
  bool empty() const {
    return the_monom.empty();
  }

  const_iterator begin() const {
    return the_monom.begin();
  }
    
  const_iterator end() const {
    return the_monom.end();
  }
    
  int size() const {
    return the_monom.size();
  }

  std::string pretty_print() const
  {
    std::ostringstream str;
    if (the_monom.empty()) {  // constant monom
      str << 1;
      return str.str();
    }

    typename monom::const_iterator it=the_monom.begin();
    str << "x" << it.index();
    if (*it != Exponent(1))
      str << "^" << *it;
    ++it;

    for ( ; it!=the_monom.end(); ++it) {
      str << " * x" << it.index();
    if (*it != Exponent(1))
      str << "^" << *it;
    }

    return str.str();
  }
  
  bool operator> (const Monomial& m) const {
    return cmp(the_monom,m.monomial())>0;
  }

  bool operator< (const Monomial& m) const {
    return cmp(the_monom,m.monomial())<0;
  }

  bool operator== (const Monomial& m) const {
    return cmp(the_monom,m.monomial())==0;
  }

  Exponent operator[] (const int i) const {
    return the_monom[i];
  }

  Monomial operator* (const Monomial& m_in) const
  {
    const int n_varibles = std::max(m_in.dim(), the_monom.dim());

    monom m1 = m_in.monomial();
    m1.resize(n_varibles);
    monom m2 = the_monom;
    m2.resize(n_varibles);

    return Monomial(m1+m2);
  }

  const monom& monomial() const {
    return the_monom;
  }
};

  // FIXME:
  // operator<<

} // end namespace pm

namespace polymake {
   using pm::Monomial;
}

// FIXME: check
namespace std_ext {
  template <typename T> struct hash;

  template<typename Exponent>
  struct hash< pm::Monomial<Exponent> > {
    size_t operator() (const pm::Monomial<Exponent>& m) const {

      //      cerr << "hash::operator():" << endl;
      //      cerr << "monomial: " << m.pretty_print() << endl;

      hash< pm::SparseVector<Exponent> > vector_hash;

      //      cerr << "value: " << vector_hash(m.monomial()) << endl;
      return vector_hash(m.monomial());
    }
  };
}

#endif // _POLYMAKE_MONOMIAL_H


// Local Variables:
// mode:C++
// c-basic-offset:3
// End:
