// -*-C++-*- 

/*  src/algorithms/enumerations/EnumerationAlgorithms.cpp  */


/*
 * Author: Philogelos A. <Philogelos@yahoo.com>
 * Maintainer: Philogelos A.
 * Keywords: C++, library, containers
 *
 * Copyright (C) 1998 Philogelos A.
 *
 * This file is part of Quercus Robusta.
 *
 * Quercus Robusta is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as published by
 * the Free Software Foundation; either version 2, or (at your option)
 * any later version.
 *
 * This software 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 Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public License
 * along with this software; see the file COPYING.LIB.  If not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 *
 */


/* $Id: EnumerationAlgorithms.cpp,v 1.4 1999/03/03 19:09:32 philogelos Exp $ */
#if !defined(_INLINE)
static char cvsid[] = "@(#)$Id: EnumerationAlgorithms.cpp,v 1.4 1999/03/03 19:09:32 philogelos Exp $";
static char debugFileId[] = __FILE__;
#endif


#include "algorithms/enumerations/EnumerationAlgorithms.hpp"
#include "Debug.hpp"
#include "OGuard.hpp"
#include "LinkManager.hpp"
#include "AeternalLifeController.hpp"

#include "iter/enumerations/Enumeration.hpp"
#include "iter/enumerations/ResettableEnumeration.hpp"
#include "iter/enumerations/Cursor.hpp"
#include "containers/MutablePosition.hpp"
#include "containers/PositionFactory.hpp"
#include "containers/ModifiableContainer.hpp"
#include "containers/Container.hpp"
#include "containers/EnumeratedValues.hpp"
#include "containers/Pair.hpp"

#include "exceptions/InternalError.hpp"
#include "exceptions/NoEntity.hpp"


EnumerationAlgorithms::EnumerationAlgorithms()
{
  Object::setLifeTimeController( new AeternalLifeController() );
}

EnumerationAlgorithms::~EnumerationAlgorithms()
{}

Index EnumerationAlgorithms::findIndex( Enumeration *anEnum, 
										const Top *anObject, 
										const Index aMaxSearch ) const
{
  OGuard _enum( anEnum, ( Top * ) this );
  OGuard _object( anObject, ( Top * ) this );

  for( Index ind = 0; ind < aMaxSearch ; ++ind )
	{
	  Top *element;

	  if( !( anEnum -> hasMoreElements() ) )
		{
		  /* XXX should create new exception class in stead. */
		  throw new NoEntity
			( "EnumerationAlgorithms::findIndex(): not enough elements",
			  null );
		}
	  element = anEnum -> getNextElement();
	  if( anObject == nil )
		{
		  if( element == nil )
			{
			  return ind;
			}
		}
	  else
		{
		  if( element -> equals( anObject ) )
			{
			  return ind;
			}
		}
	}
  /* XXX should create new exception class in stead. */
  throw new NoEntity
	( "EnumerationAlgorithms::findIndex(): index not found",
	  null );
}

Index EnumerationAlgorithms::getCardinality( Enumeration *anEnum )
{
  preC_( anEnum != ( Enumeration * ) NIL );
  Index card;

  OGuard _enum( anEnum, ( Top * ) this );
  for( card = 0 ; 
	   anEnum -> hasMoreElements() ; 
	   anEnum -> getNextElement(), ++card );
  return card;
}

boolean EnumerationAlgorithms::contains( Enumeration *anEnum, const Top *anElement )
{
  preC_( anEnum != ( Enumeration * ) NIL );
  //  preC_( anElement != nil );

  OGuard _element( anElement, ( Top * ) this );
  OGuard _enum( anEnum, ( Top * ) this );

  for( ; anEnum -> hasMoreElements() ; )
	{
	  const Top *item;

	  item = anEnum -> getNextElement();
	  if( anElement == nil )
		{
		  if( item == nil )
			{
			  return true;
			}
		}
	  else
		{
		  if( anElement -> equals( item ) )
			{
			  return true;
			}
		}
	}
  return false;
}

Container *EnumerationAlgorithms::getAsContainer( ResettableEnumeration *anEnum )
{
  preC_( anEnum != ( ResettableEnumeration * ) NIL );
  return new EnumeratedValues( anEnum );
}

boolean EnumerationAlgorithms::add( ModifiableContainer *aContainer, Enumeration *anEnum )
{
  preC_( aContainer != ( ModifiableContainer * ) NIL );
  preC_( anEnum != ( Enumeration * ) NIL );
  return addAt( aContainer -> getDefaultPositionFactory(), anEnum );
}

boolean EnumerationAlgorithms::addAt( PositionFactory *aFactory, Enumeration *anEnum )
{
  preC_( aFactory != ( PositionFactory * ) NIL );
  preC_( anEnum != ( Enumeration * ) NIL );

  OGuard _factory( aFactory, ( Top * ) this );
  OGuard _enum( anEnum, ( Top * ) this );

  while( ( aFactory -> hasMoreElements() ) &&
		 ( anEnum -> hasMoreElements() ) )
	{
	  Top *objectToAdd;
	  MutablePosition *freshPosition;

	  objectToAdd = anEnum -> getNextElement();
	  freshPosition = aFactory -> createPosition();

	  OGuard _object( objectToAdd, ( Top * ) this );
	  OGuard _position( freshPosition, ( Top * ) this );

	  test_( freshPosition != ( MutablePosition * ) NIL );
	  freshPosition -> setValue( objectToAdd );
	}
  return( ! ( anEnum -> hasMoreElements() ) );
}

ResettableEnumeration *EnumerationAlgorithms::getFromContainer( Container *aContainer )
{
  return new ContainerEnumeration( aContainer );
}

ResettableEnumeration *EnumerationAlgorithms::getSum( ResettableEnumeration *aFirst, ResettableEnumeration *aSecond )
{
  preC_( aFirst  != ( ResettableEnumeration * ) NIL );
  preC_( aSecond != ( ResettableEnumeration * ) NIL );
  return new SumEnumeration( aFirst, aSecond );
}

ResettableEnumeration *EnumerationAlgorithms::getUnion( ResettableEnumeration *aFirst, ResettableEnumeration *aSecond )
{
  preC_( aFirst  != ( ResettableEnumeration * ) NIL );
  preC_( aSecond != ( ResettableEnumeration * ) NIL );
  return new UnionEnumeration( aFirst, aSecond );
}

ResettableEnumeration *EnumerationAlgorithms::getIntersection( ResettableEnumeration *aFirst, ResettableEnumeration *aSecond )
{
  preC_( aFirst  != ( ResettableEnumeration * ) NIL );
  preC_( aSecond != ( ResettableEnumeration * ) NIL );
  return new IntersectionEnumeration( aFirst, aSecond );
}


ResettableEnumeration *EnumerationAlgorithms::getProd( ResettableEnumeration *aFirst, ResettableEnumeration *aSecond )
{
  preC_( aFirst  != ( ResettableEnumeration * ) NIL );
  preC_( aSecond != ( ResettableEnumeration * ) NIL );
  return new ProdEnumeration( aFirst, aSecond );
}

/*
ResettableEnumeration *EnumerationAlgorithms::getBeta( ResettableEnumeration *anEnum )
{
  preC_( anEnum  != ( ResettableEnumeration * ) NIL );
  return new BetaEnumeration( anEnum );
}

ResettableEnumeration *EnumerationAlgorithms::getBetaOfN( ResettableEnumeration *anEnum, Index aCardinality )
{
  preC_( anEnum  != ( ResettableEnumeration * ) NIL );
  return new BetaOfNEnumeration( anEnum, aCardinality );
}


ResettableEnumeration *EnumerationAlgorithms::getOrdBeta( ResettableEnumeration *anEnum )
{
  preC_( anEnum  != ( ResettableEnumeration * ) NIL );
  return new OrdBetaEnumeration( anEnum );
}

ResettableEnumeration *EnumerationAlgorithms::getOrdBetaOfN( ResettableEnumeration *anEnum, 
															 Index aCardinality )
{
  preC_( anEnum  != ( ResettableEnumeration * ) NIL );
  return new OrdBetaOfNEnumeration( anEnum, aCardinality );
}

*/

ResettableEnumeration *EnumerationAlgorithms::getInterleaved( ResettableEnumeration *aFirst, 
															  ResettableEnumeration *aSecond )
{
  preC_( aFirst  != ( ResettableEnumeration * ) NIL );
  preC_( aSecond != ( ResettableEnumeration * ) NIL );
  return new InterleavedEnumeration( aFirst, aSecond );
}

EnumerationAlgorithms *EnumerationAlgorithms::get()
{
  if( instance == ( EnumerationAlgorithms * ) NIL )
	{
	  instance = new EnumerationAlgorithms();
	}
  return instance;
}

Top *EnumerationAlgorithms::clone() const
{
  return ( Top * ) this;
}

String  EnumerationAlgorithms::getClassName() const
{
  return "EnumerationAlgorithms";
}

EnumerationAlgorithms *EnumerationAlgorithms::instance = ( EnumerationAlgorithms * ) NIL;

EnumUnaryOp::EnumUnaryOp( ResettableEnumeration *aFirst )
{
  preC_( aFirst != ( ResettableEnumeration * ) NIL );
  LinkManager::reg( this, aFirst );
  firstArg = aFirst;
}

EnumUnaryOp::~EnumUnaryOp()
{
  LinkManager::free( this, firstArg );
  firstArg = ( ResettableEnumeration * ) NIL;
}

void EnumUnaryOp::reset()
{
  firstArg -> reset();
}

EnumBinaryOp::EnumBinaryOp( ResettableEnumeration *aFirst, ResettableEnumeration *aSecond ) :
  EnumUnaryOp( aFirst )
{
  preC_( aSecond != ( ResettableEnumeration * ) NIL );
  LinkManager::reg( this, aSecond );
  secondArg = aSecond;
}

EnumBinaryOp::~EnumBinaryOp()
{
  LinkManager::free( this, secondArg );
  secondArg = ( ResettableEnumeration * ) NIL;
}

void EnumBinaryOp::reset()
{
  secondArg -> reset();
  EnumUnaryOp::reset();
}


SumEnumeration::SumEnumeration( ResettableEnumeration *aFirst, ResettableEnumeration *aSecond ) :
  EnumBinaryOp( aFirst, aSecond )
{
  firstDone = false;
}

SumEnumeration::~SumEnumeration()
{}

Top *SumEnumeration::getNextElement()
{
  if( ! firstDone )
	{
	  return( firstArg -> getNextElement() );
	}
  else
	{
	  return( secondArg -> getNextElement() );
	}
}

boolean SumEnumeration::hasMoreElements()
{
  if( ! firstDone )
	{
	  if( firstArg -> hasMoreElements() )
		{
		  return true;
		}
	  else
		{
		  firstDone = true;
		  return hasMoreElements();
		}
	}
  else
	{
	  return( secondArg -> hasMoreElements() );
	}
}

void SumEnumeration::reset()
{
  firstDone = false;
  EnumBinaryOp::reset();
}

Top *SumEnumeration::clone() const
{
  return new SumEnumeration( firstArg, secondArg );
}

UnionEnumeration::UnionEnumeration( ResettableEnumeration *aFirst, 
									ResettableEnumeration *aSecond ) :
  EnumBinaryOp( aFirst, aSecond )
{
  firstDone = false;
  cacheValid = false;
  hasMore = true;
  cachedObject = nil;
}

UnionEnumeration::~UnionEnumeration()
{
  if( cachedObject != nil )
	{
	  LinkManager::free( this, cachedObject );
	}
}

Top *UnionEnumeration::getNextElement()
{
  if( ! firstDone )
	{
	  return( firstArg -> getNextElement() );
	}
  else
	{
	  if( cacheValid )
		{
		  test_( hasMore );
		  cacheValid = false;
		  LinkManager::unreg( this, cachedObject );
		  return cachedObject;
		}
	  else
		{
		  hasMore = getNextElementInternal();
		  return getNextElement();
		}
	}
}

boolean UnionEnumeration::hasMoreElements()
{
  if( ! firstDone )
	{
	  if( firstArg -> hasMoreElements() )
		{
		  return true;
		}
	  else
		{
		  firstDone = true;
		  return hasMoreElements();
		}
	}
  else
	{
	  if( cacheValid )
		{
		  return hasMore;
		}
	  else
		{
		  hasMore = getNextElementInternal();
		  return hasMoreElements();
		}
	}
}

void UnionEnumeration::reset()
{
  firstDone = false;
  cacheValid = false;
  hasMore = true;

  EnumBinaryOp::reset();
}

Top *UnionEnumeration::clone() const
{
  return new UnionEnumeration( firstArg, secondArg );
}

boolean UnionEnumeration::getNextElementInternal()
{
  preC_( firstDone );

  cacheValid = true;
  while( true )
	{
	  if( ! ( secondArg -> hasMoreElements() ) )
		{
		  LinkManager::move( this, cachedObject, nil );
		  cachedObject = nil;
		  return false;
		}
	  else
		{
		  Top *nextObject;

		  nextObject = secondArg -> getNextElement();
		  OGuard _next( nextObject, ( Top * ) this );

		  firstArg -> reset();
		  if( ! ( EAlg::get() 
				  -> contains( firstArg, nextObject ) ) )
			{
			  LinkManager::move( this, cachedObject, nextObject );
			  cachedObject = nextObject;
			  return true;
			}
		}
	}
}



IntersectionEnumeration::IntersectionEnumeration( ResettableEnumeration *aFirst, 
												  ResettableEnumeration *aSecond ) :
  EnumBinaryOp( aFirst, aSecond )
{
  cacheValid = false;
  hasMore = true;
  cachedObject = nil;
}

IntersectionEnumeration::~IntersectionEnumeration()
{
  if( cachedObject != nil )
	{
	  LinkManager::free( this, cachedObject );
	}
}

Top *IntersectionEnumeration::getNextElement()
{
  if( cacheValid )
	{
	  test_( hasMore );
	  cacheValid = false;
	  LinkManager::unreg( this, cachedObject );
	  return cachedObject;
	}
  else
	{
	  hasMore = getNextElementInternal();
	  return getNextElement();
	}
}

boolean IntersectionEnumeration::hasMoreElements()
{
  if( cacheValid )
	{
	  return hasMore;
	}
  else
	{
	  hasMore = getNextElementInternal();
	  return hasMoreElements();
	}
}

void IntersectionEnumeration::reset()
{
  cacheValid = false;
  hasMore = true;

  EnumBinaryOp::reset();
}

Top *IntersectionEnumeration::clone() const
{
  return new IntersectionEnumeration( firstArg, secondArg );
}

boolean IntersectionEnumeration::getNextElementInternal()
{
  cacheValid = true;
  while( true )
	{
	  if( ! ( firstArg -> hasMoreElements() ) )
		{
		  //		  LinkManager::move( this, cachedObject, nil );
		  cachedObject = nil;
		  return false;
		}
	  else
		{
		  Top *nextObject;

		  nextObject = firstArg -> getNextElement();
		  OGuard _next( nextObject, ( Top * ) this );

		  secondArg -> reset();
		  if( EAlg::get()
			  -> contains( secondArg, nextObject ) )
			{
			  LinkManager::reg( this, nextObject );
			  cachedObject = nextObject;
			  return true;
			}
		}
	}
}


ContainerEnumeration::ContainerEnumeration( Container *aContainer )
{
  preC_( aContainer != ( Container * ) NIL );
  LinkManager::reg( this, aContainer );
  container = aContainer;
  en = container -> getValueEnumeration();
  LinkManager::reg( this, en );
}

ContainerEnumeration::~ContainerEnumeration()
{
  LinkManager::free( this, container );
  LinkManager::free( this, en );
}

Top *ContainerEnumeration::getNextElement()
{
  preC_( en -> hasMoreElements() );
  return( en -> getNextElement() );
}

boolean ContainerEnumeration::hasMoreElements()
{
  return( en -> hasMoreElements() );
}

void ContainerEnumeration::reset()
{
  Enumeration *newEn;

  newEn = container -> getValueEnumeration();
  LinkManager::move( this, en, newEn );
  en = newEn;
}

Top *ContainerEnumeration::clone() const
{
  return new ContainerEnumeration( container );
}

ProdEnumeration::ProdEnumeration( ResettableEnumeration *aFirst, ResettableEnumeration *aSecond ) :
  EnumBinaryOp( aFirst, aSecond ),
  isEmpty( ( !( aFirst  -> hasMoreElements() ) ) ||
		   ( !( aSecond -> hasMoreElements() ) ) )
{
  /* product is empty iff one set is empty (axiom of choice :-)) */
  if( !isEmpty )
	{
	  rowObject = firstArg -> getNextElement();
	  if( rowObject != nil )
		{
		  LinkManager::reg( this, rowObject );
		}
	}
  else
	{
	  rowObject = nil;
	}
}

ProdEnumeration::~ProdEnumeration()
{
  if( !isEmpty )
	{
	  if( rowObject != nil )
		{
		  LinkManager::free( this, rowObject );
		}
	}
}

Top *ProdEnumeration::getNextElement()
{
  preC_( hasMoreElements() );
  if( ! secondArg -> hasMoreElements() )
	{
	  Top *newRowObject;

	  secondArg -> reset();
	  test_( secondArg -> hasMoreElements() );

	  newRowObject = firstArg -> getNextElement();
	  LinkManager::move( this, rowObject, 
						 newRowObject );
	  rowObject = newRowObject;
	}
  test_( secondArg -> hasMoreElements() );
  return new Pair( rowObject, secondArg -> getNextElement() );
}

boolean ProdEnumeration::hasMoreElements()
{
  return ( ( !isEmpty ) &&
		   ( ( firstArg  -> hasMoreElements() ) || 
			 ( secondArg -> hasMoreElements() ) ) );
}

void ProdEnumeration::reset()
{
  EnumBinaryOp::reset();
  if( !isEmpty )
	{
	  Top *newRowObject;

	  newRowObject = firstArg -> getNextElement();
	  LinkManager::move( this, rowObject, newRowObject );
	  rowObject = newRowObject;
	}
  else
	{
	  rowObject = nil;
	}
}

Top *ProdEnumeration::clone() const
{
  return new ProdEnumeration( firstArg, secondArg );
}



InterleavedEnumeration::InterleavedEnumeration( ResettableEnumeration *aFirst, 
												ResettableEnumeration *aSecond ) :
  EnumBinaryOp( aFirst, aSecond )
{
  current = firstArg;
}

InterleavedEnumeration::~InterleavedEnumeration()
{}

Top *InterleavedEnumeration::getNextElement()
{
  Top *result;

  result = current -> getNextElement();
  if( current == firstArg )
	{
	  current = secondArg;
	}
  else
	{
	  current = firstArg;
	}
  return result;
}

boolean InterleavedEnumeration::hasMoreElements()
{
  return( current -> hasMoreElements() );
}

void InterleavedEnumeration::reset()
{
  EnumBinaryOp::reset();
  current = firstArg;
}

Top *InterleavedEnumeration::clone() const
{
  return new InterleavedEnumeration( firstArg, secondArg );
}

#if defined( TESTING )

#include "containers/lists/List.hpp"
#include "containers/arrays/CArray.hpp"
#include "String.hpp"
#include "Debug.hpp"
#include "OGuard.hpp"
#include "LinkManager.hpp"

#include "containers/Empty.hpp"
#include "containers/Singleton.hpp"
#include "containers/MutablePositionEnumeration.hpp"
#include "containers/MutablePosition.hpp"


boolean EnumerationAlgorithms::tester( int ) const
{
  CArray *array;
  List *list;

  array = new CArray( 0, 4 );
  OGuard _array( array, this );

  list = new List();
  OGuard _list( list, this );
		
  array -> setAt( 0, new String( "0" ) );
  array -> setAt( 1, new String( "1" ) );
  array -> setAt( 2, new Empty() );
  array -> setAt( 3, new Singleton( new String( "3" ) ) );

  EAlg::get() -> add( list, array -> getValueEnumeration() );
  Debug::getLogger() -> logObject( list );

  list -> behead();
  Debug::getLogger() -> logObject( list );

  Container *sum;

   sum = EAlg::get() 
 	-> getAsContainer( EAlg::get() 
 					   -> getSum( EAlg::get() -> getFromContainer( array ),
 								  EAlg::get() -> getFromContainer( list ) ) );
   OGuard _sum( sum, this );
   Debug::getLogger() -> logObject( sum );

   Container *un;

   un = EAlg::get() 
 	-> getAsContainer( EAlg::get() 
 					   -> getUnion( EAlg::get() -> getFromContainer( array ),
 									EAlg::get() ->	getFromContainer( list ) ) );
   OGuard _un( un, this );
   Debug::getLogger() -> logObject( un );

   Container *in;

   in = EAlg::get() 
 	-> getAsContainer( EAlg::get() 
 					   -> getIntersection( EAlg::get() -> getFromContainer( array ),
 										   EAlg::get() -> getFromContainer( list ) ) );
   OGuard _in( in, this );
   Debug::getLogger() -> logObject( in );
   Debug::getLogger() -> logObject( array );

   Container *prod;

   prod = EAlg::get() 
	 -> getAsContainer( EAlg::get() 
						-> getProd( EAlg::get() -> getFromContainer( array ),
									EAlg::get() -> getFromContainer( list ) ) );

   OGuard _prod( prod, this );
   Debug::getLogger() -> log( "prod" );
   Debug::getLogger() -> logObject( prod );

   Container *intr;

   intr = EAlg::get() 
	 -> getAsContainer( EAlg::get() 
						-> getInterleaved( EAlg::get() -> getFromContainer( array ),
										   EAlg::get() -> getFromContainer( list ) ) );

   OGuard _intr( intr, this );
  Debug::getLogger() -> log( "intr" );
  Debug::getLogger() -> logObject( intr );

  return true;
}
#endif

#if defined(_INLINE)
#include "../src/Debug.ipp"
#endif


#if defined(_INLINE)
#include "../src/String.ipp"
#endif

/* $Log: EnumerationAlgorithms.cpp,v $
 * Revision 1.4  1999/03/03 19:09:32  philogelos
 * Put sources under GNU Library License
 *
 * Revision 1.3  1999/02/28 16:29:04  philogelos
 * Tuned for inlines. ::findIndex() added
 *
 * Revision 1.2  1998/12/01 16:20:02  philogelos
 * conditionally compile ::tester()
 *
 * Revision 1.1.1.1  1998/11/25 20:11:02  philogelos
 * Quercus Robusta
 * */