//////////////////////////////////////////////////////////////////////////////
// $Id: Partitions.h,v 1.1.1.1 2003/09/15 16:37:52 nthiery Exp $
// Name:	Partitions.h
// Purpose:	Class Partitions for generating partitions
//		(User interface)
// Author:	Nicolas M. Thiéry <nthiery@mines.edu>
// Created:	2000/07
// Copyright:	LGPL
//////////////////////////////////////////////////////////////////////////////
//
// Synopsis:
//
//	Partitions gen(n,k,[m]);
//
//	Creates a new generator for partitions of n in k parts.
//	If m is provided, each part will be at most m.
//
// Example:
//
//	Partitions gen(4,3);
//	Partitions::pointer p;
//	while(p=gen()) {
//	  cout << *p << endl;
//	}
//
// Description:
//
// A partition is a decreasing list of non-negative integers, like
// 4,3,1,1,0. More precisely, this is a partition of 9 in 5 parts.
// Partitions are stored as SmallList's.
//
// Note that quite often two partitions which differ only by trailing
// zeroes are considered the same. Here this is not the case, since
// the number of parts is fixed.
//
// An object of the class Partitions is a generator. That is a
// function object which returns each time it's called a pointer to a
// new partition. When all partitions have been generated, the 0
// pointer is returned. The result of calling the generator afterward
// is undefined, if not dangerous.
//
//////////////////////////////////////////////////////////////////////////////

#ifndef GLIP_PARTITIONS_H
#define GLIP_PARTITIONS_H

#include <GLIP/SmallList.h>
#include <GLIP/SmallList_tmpl.h>

namespace GLIP {
class Partitions {
public:
  typedef	SmallList<>   value_type;
  typedef	value_type *pointer;
  typedef const value_type *const_pointer;
  typedef	value_type &reference;
  typedef const value_type &const_reference;
  typedef       value_type *iterator;
  typedef const value_type *const_iterator;
  
private:
  typedef       value_type::value_type cell_type;
  cell_type n;
  cell_type *begin;
  cell_type *b;
  cell_type *end;
  
public:

  // Constructors and Destructor

  Partitions();
  Partitions(int,				// Sum of the parts
	     int				// Number of parts
	     );
  Partitions(int,				// Sum of the parts
	     int,				// Number of parts
	     int				// Maximal value of a part
	     );
  ~Partitions();
  
  Partitions& operator= (const Partitions &);
  pointer operator () ();
  // Returns a pointer to the next partition, or 0 if there is none
};
}
#endif	/* GLIP_PARTITIONS_H */

// Local Variables: 
// mode: c++
// End: 
