/*
 * manage a data structure that keeps the modes of a list of values
 * $Id: maxfreq.h,v 8.1 2012/08/31 15:29:29 ksb Exp $
 * $Publish: ${install-install} -c %f ${DESTDIR}/usr/local/lib/explode/
 * Assumptions:
 *	there aren't many different values (usually less than 16)
 *	long chains of the same number are common
 */

/*
 * test configuration
 */
#ifdef TEST
#define MAXBUF	100

typedef union MEnode {
	char ac[MAXBUF];
} ME_ELEMENT;

extern int MECopy(ME_ELEMENT *pMEDest, ME_ELEMENT *pMESource);
extern int MECompare(ME_ELEMENT *pME1, ME_ELEMENT *pME2);
extern char *progname;
extern int main();
#endif /* TEST	*/

/*
 * this is the data structure used for keeping the max frequency
 *
 * The algorithm to maintain it is O(n^2) / K; we try to keep K large
 * by predicting that the input contains long repeating sequences of
 * the same key.
 */
typedef struct MFnode {
	struct MFnode *pMFlower;/* list of nodes with lower freq's	*/
	struct MFnode *pMFequal;/* list of nodes with equal freq's	*/
	ME_ELEMENT ME;
	int icount;
} MAXFREQ;
#define nilMF	((MAXFREQ *)0)

extern ME_ELEMENT *MFIncrement(MAXFREQ **ppMFRoot, ME_ELEMENT *pME);
extern void MFFree(MAXFREQ *pMFRoot);
extern int MFCheckMax(register MAXFREQ *pMFRoot, ME_ELEMENT *pME);
extern int MFScan(MAXFREQ *pMFRoot, int (*pfi)());