#ifndef _DEPOOLMULTISET_H
#define _DEPOOLMULTISET_H
/*-------------------------------------------------------------------------
 * drawElements Memory Pool Library
 * --------------------------------
 *
 * Copyright 2014 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 *//*!
 * \file
 * \brief Memory pool multiset class.
 *//*--------------------------------------------------------------------*/

#include "deDefs.h"
#include "deMemPool.h"
#include "dePoolHash.h"
#include "deInt32.h"

DE_BEGIN_EXTERN_C

void	dePoolMultiSet_selfTest		(void);

DE_END_EXTERN_C

/*--------------------------------------------------------------------*//*!
 * \brief Declare a template pool multiset class interface.
 * \param TYPENAME	Type name of the declared multiset.
 * \param KEYTYPE	Type of the key.
 *
 * This macro declares the interface for a multiset. For the implementation
 * of the multiset, see DE_IMPLEMENT_POOL_MULTISET. Usually this macro is put
 * into the header file and the implementation macro is put in some .c file.
 *
 * \todo [petri] Detailed description.
 *
 * The functions for operating the multiset are:
 * \todo [petri] Figure out how to comment these in Doxygen-style.
 *
 * \code
 * MultiSet* MultiSet_create            (deMemPool* pool);
 * int       MultiSet_getNumElements    (const MultiSet* set);
 * deBool    MultiSet_exists            (const MultiSet* set, Key key);
 * deBool    MultiSet_insert            (MultiSet* set, Key key);
 * void      MultiSet_delete            (MultiSet* set, Key key);
 * int       MultiSet_getKeyCount       (const MultiSet* set, Key key);
 * deBool    MultiSet_setKeyCount       (MultiSet* set, Key key, int count);
 * \endcode
*//*--------------------------------------------------------------------*/
#define DE_DECLARE_POOL_MULTISET(TYPENAME, KEYTYPE)		\
\
DE_DECLARE_POOL_HASH(TYPENAME##Hash, KEYTYPE, int);	\
\
typedef struct TYPENAME##_s    \
{    \
	deMemPool*			pool;    \
	int					numElements;    \
	TYPENAME##Hash*		hash;	\
} TYPENAME;    \
\
TYPENAME*	TYPENAME##_create		(deMemPool* pool);    \
void		TYPENAME##_reset		(TYPENAME* set);    \
deBool		TYPENAME##_setKeyCount	(TYPENAME* set, KEYTYPE key, int newCount);	\
\
DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* set)    \
{    \
	return set->numElements;    \
}    \
\
DE_INLINE int TYPENAME##_getKeyCount (const TYPENAME* set, KEYTYPE key)	\
{	\
	int* countPtr	= TYPENAME##Hash_find(set->hash, key);	\
	int  count		= countPtr ? *countPtr : 0;	\
	DE_ASSERT(count > 0 || !countPtr);	\
	return count;	\
}	\
\
DE_INLINE deBool TYPENAME##_exists (const TYPENAME* set, KEYTYPE key)    \
{    \
	return (TYPENAME##_getKeyCount(set, key) > 0);	\
}    \
\
DE_INLINE deBool TYPENAME##_insert (TYPENAME* set, KEYTYPE key)    \
{	\
	int oldCount = TYPENAME##_getKeyCount(set, key);	\
	return TYPENAME##_setKeyCount(set, key, oldCount + 1);	\
}	\
\
DE_INLINE void TYPENAME##_delete (TYPENAME* set, KEYTYPE key)    \
{    \
	int oldCount = TYPENAME##_getKeyCount(set, key);	\
	DE_ASSERT(oldCount > 0);	\
	TYPENAME##_setKeyCount(set, key, oldCount - 1);	\
}    \
\
struct TYPENAME##DeclareDummy_s { int dummy; }

/*--------------------------------------------------------------------*//*!
 * \brief Implement a template pool multiset class.
 * \param TYPENAME	Type name of the declared multiset.
 * \param KEYTYPE	Type of the key.
 * \param HASHFUNC	Function used for hashing the key.
 * \param CMPFUNC	Function used for exact matching of the keys.
 *
 * This macro has implements the set declared with DE_DECLARE_POOL_MULTISET.
 * Usually this macro should be used from a .c file, since the macro expands
 * into multiple functions. The TYPENAME and KEYTYPE parameters
 * must match those of the declare macro.
*//*--------------------------------------------------------------------*/
#define DE_IMPLEMENT_POOL_MULTISET(TYPENAME, KEYTYPE, HASHFUNC, CMPFUNC)		\
\
DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, int, HASHFUNC, CMPFUNC);	\
\
TYPENAME* TYPENAME##_create (deMemPool* pool)    \
{   \
	/* Alloc struct. */ \
	TYPENAME* set = DE_POOL_NEW(pool, TYPENAME); \
	if (!set) \
		return DE_NULL; \
\
	/* Init. */ \
	memset(set, 0, sizeof(TYPENAME)); \
	set->pool = pool; \
\
	set->hash = TYPENAME##Hash_create(pool);	\
\
	return set; \
} \
\
void TYPENAME##_reset (TYPENAME* set)    \
{   \
	TYPENAME##Hash_reset(set->hash);	\
	set->numElements = 0;	\
}	\
\
deBool TYPENAME##_setKeyCount (TYPENAME* set, KEYTYPE key, int newCount)	\
{	\
	int* countPtr	= TYPENAME##Hash_find(set->hash, key);	\
	int  oldCount	= countPtr ? *countPtr : 0;	\
\
	DE_ASSERT(oldCount > 0 || !countPtr);	\
	DE_ASSERT(newCount >= 0);	\
	set->numElements += (newCount - oldCount);	\
\
	if (newCount == 0 && countPtr)	\
		TYPENAME##Hash_delete(set->hash, key);	\
	else if (newCount > 0 && countPtr)	\
		*countPtr = newCount;	\
	else if (newCount > 0)	\
		return TYPENAME##Hash_insert(set->hash, key, newCount);	\
	return DE_TRUE;	\
}	\
\
struct TYPENAME##ImplementDummy_s { int dummy; }

/*--------------------------------------------------------------------*//*!
 * \brief Declare set-wise operations for a multiset template.
 * \param TYPENAME	Type name of the declared set.
 * \param KEYTYPE	Type of the key.
 *
 * This macro declares union and intersection operations for a multiset.
 * For implementation see DE_IMPLEMENT_POOL_MULTISET_UNION_INTERSECT.
 *
 * \todo [petri] Detailed description.
 *
 * The functions for operating the set are:
 * \todo [petri] Figure out how to comment these in Doxygen-style.
 *
 * \code
 * deBool	MultiSet_union				(Set* to, const Set* a, const Set* b);
 * deBool	MultiSet_unionInplace		(Set* a, const Set* b);
 * deBool	MultiSet_intersect			(Set* to, const Set* a, const Set* b);
 * void		MultiSet_intersectInplace	(Set* a, const Set* b);
 * deBool   MultiSet_sum				(Set* to, const Set* a, const Set* b);
 * deBool   MultiSet_sumInplace			(Set* a, const Set* b);
 * deBool   MultiSet_difference			(Set* to, const Set* a, const Set* b);
 * void		MultiSet_differenceInplace	(Set* a, const Set* b);
 * \endcode
*//*--------------------------------------------------------------------*/
#define DE_DECLARE_POOL_MULTISET_SETWISE_OPERATIONS(TYPENAME)	\
	deBool TYPENAME##_union (TYPENAME* to, const TYPENAME* a, const TYPENAME* b);	\
	deBool TYPENAME##_unionInplace (TYPENAME* a, const TYPENAME* b);	\
	deBool TYPENAME##_intersect (TYPENAME* to, const TYPENAME* a, const TYPENAME* b);	\
	void TYPENAME##_intersectInplace (TYPENAME* a, const TYPENAME* b);	\
	deBool TYPENAME##_sum (TYPENAME* to, const TYPENAME* a, const TYPENAME* b);	\
	deBool TYPENAME##_sumInplace (TYPENAME* a, const TYPENAME* b);	\
	deBool TYPENAME##_difference (TYPENAME* to, const TYPENAME* a, const TYPENAME* b);	\
	void TYPENAME##_differenceInplace (TYPENAME* a, const TYPENAME* b);	\
	struct TYPENAME##SetwiseDeclareDummy_s { int dummy; }

#define DE_IMPLEMENT_POOL_MULTISET_SETWISE_OPERATIONS(TYPENAME, KEYTYPE)	\
deBool TYPENAME##_union (TYPENAME* to, const TYPENAME* a, const TYPENAME* b)	\
{	\
	TYPENAME##_reset(to);	\
	return TYPENAME##_unionInplace(to, a) && TYPENAME##_unionInplace(to, b);	\
}	\
\
deBool TYPENAME##_unionInplace (TYPENAME* a, const TYPENAME* b)	\
{	\
	TYPENAME##HashIter iter;	\
	for (TYPENAME##HashIter_init(b, &iter);	\
		 TYPENAME##HashIter_hasItem(&iter);	\
		 TYPENAME##HashIter_next(&iter))	\
	{	\
		KEYTYPE	key		= TYPENAME##HashIter_getKey(&iter);	\
		int		bCount	= TYPENAME##HashIter_getValue(&iter);	\
		int		aCount	= TYPENAME##_getKeyCount(a, key);	\
		int		count	= deMax32(aCount, bCount);	\
		if (bCount && !TYPENAME##_setKeyCount(a, key, aCount + bCount))	\
			return DE_FALSE;	\
	}	\
	return DE_TRUE;	\
}	\
\
deBool TYPENAME##_intersect (TYPENAME* to, const TYPENAME* a, const TYPENAME* b)	\
{	\
	TYPENAME##HashIter iter;	\
	TYPENAME##_reset(to);	\
	for (TYPENAME##HashIter_init(a, &iter);	\
		 TYPENAME##HashIter_hasItem(&iter);	\
		 TYPENAME##HashIter_next(&iter))	\
	{	\
		KEYTYPE key		= TYPENAME##HashIter_getKey(&iter);	\
		int		aCount	= TYPENAME##HashIter_getValue(&iter);	\
		int		bCount	= TYPENAME##_getKeyValue(b, key);	\
		int		count	= deMin32(aCount, bCount);	\
		if (count && !TYPENAME##_setKeyCount(to, key, count))	\
			return DE_FALSE;	\
	}	\
	return DE_TRUE;	\
}	\
\
void TYPENAME##_intersectInplace (TYPENAME* a, const TYPENAME* b)	\
{	\
	DE_FATAL("Not implemented.");	\
}	\
\
deBool TYPENAME##_sum (TYPENAME* to, const TYPENAME* a, const TYPENAME* b)	\
{	\
	TYPENAME##_reset(to);	\
	return TYPENAME##_sumInplace(to, a) && TYPENAME##_sumInplace(to, b);	\
}	\
\
deBool TYPENAME##_sumInplace (TYPENAME* a, const TYPENAME* b)	\
{	\
	TYPENAME##HashIter iter;	\
	for (TYPENAME##HashIter_init(b, &iter);	\
		 TYPENAME##HashIter_hasItem(&iter);	\
		 TYPENAME##HashIter_next(&iter))	\
	{	\
		KEYTYPE	key		= TYPENAME##HashIter_getKey(&iter);	\
		int		aCount	= TYPENAME##_getKeyValue(a, key);	\
		int		bCount	= TYPENAME##HashIter_getValue(&iter);	\
		int		count	= aCount + bCount;	\
		if (!TYPENAME##_setKeyCount(a, key, count))	\
			return DE_FALSE;	\
	}	\
}	\
\
deBool TYPENAME##_difference (TYPENAME* to, const TYPENAME* a, const TYPENAME* b)	\
{	\
	TYPENAME##HashIter iter;	\
	TYPENAME##_reset(to);	\
	for (TYPENAME##HashIter_init(a, &iter);	\
		 TYPENAME##HashIter_hasItem(&iter);	\
		 TYPENAME##HashIter_next(&iter))	\
	{	\
		KEYTYPE key		= TYPENAME##HashIter_getKey(&iter);	\
		int		aCount	= TYPENAME##HashIter_getValue(&iter);	\
		int		bCount	= TYPENAME##_getKeyValue(b, key);	\
		int		count	= deMax32(0, aCount - bCount);	\
		if (count && !TYPENAME##_setKeyCount(to, key, count))	\
			return DE_FALSE;	\
	}	\
	return DE_TRUE;	\
}	\
\
void TYPENAME##_differenceInplace (TYPENAME* a, const TYPENAME* b)	\
{	\
	DE_FATAL("Not implemented.");	\
}	\
\
struct TYPENAME##SetwiseImplementDummy_s { int dummy; }

#endif /* _DEPOOLMULTISET_H */