/* ecs - equivalence class routines */

/*  Copyright (c) 1990 The Regents of the University of California. */

/*  All rights reserved. */

/*  This code is derived from software contributed to Berkeley by */

/*  Vern Paxson. */

/*  The United States Government has rights in this work pursuant */

/*  to contract no. DE-AC03-76SF00098 between the United States */

/*  Department of Energy and the University of California. */

/* This file is part of flex */

/*  Redistribution and use in source and binary forms, with or without */

/*  modification, are permitted provided that the following conditions */

/*  are met: */

/*  1. Redistributions of source code must retain the above copyright */

/*     notice, this list of conditions and the following disclaimer. */

/*  2. Redistributions in binary form must reproduce the above copyright */

/*     notice, this list of conditions and the following disclaimer in the */

/*     documentation and/or other materials provided with the distribution. */

/*  Neither the name of the University nor the names of its contributors */

/*  may be used to endorse or promote products derived from this software */

/*  without specific prior written permission. */

/*  THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR */

/*  IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */

/*  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */

/*  PURPOSE. */

#include "flexdef.h"

/* ccl2ecl - convert character classes to set of equivalence classes */

void    ccl2ecl (void)

{

	int     i, ich, newlen, cclp, ccls, cclmec;

	for (i = 1; i <= lastccl; ++i) {

		/* We loop through each character class, and for each character

		 * in the class, add the character's equivalence class to the

		 * new "character" class we are creating.  Thus when we are all

		 * done, character classes will really consist of collections

		 * of equivalence classes

		 */

		newlen = 0;

		cclp = cclmap[i];

		for (ccls = 0; ccls < ccllen[i]; ++ccls) {

			ich = ccltbl[cclp + ccls];

			cclmec = ecgroup[ich];

			if (cclmec > 0) {

				ccltbl[cclp + newlen] = cclmec;

				++newlen;

			}

		}

		ccllen[i] = newlen;

	}

}

/* cre8ecs - associate equivalence class numbers with class members

 *

 * fwd is the forward linked-list of equivalence class members.  bck

 * is the backward linked-list, and num is the number of class members.

 *

 * Returned is the number of classes.

 */

int     cre8ecs (int fwd[], int bck[], int num)

{

	int     i, j, numcl;

	numcl = 0;

	/* Create equivalence class numbers.  From now on, ABS( bck(x) )

	 * is the equivalence class number for object x.  If bck(x)

	 * is positive, then x is the representative of its equivalence

	 * class.

	 */

	for (i = 1; i <= num; ++i)

		if (bck[i] == NIL) {

			bck[i] = ++numcl;

			for (j = fwd[i]; j != NIL; j = fwd[j])

				bck[j] = -numcl;

		}

	return numcl;

}

/* mkeccl - update equivalence classes based on character class xtions

 *

 * synopsis

 *    unsigned char ccls[];

 *    int lenccl, fwd[llsiz], bck[llsiz], llsiz, NUL_mapping;

 *    void mkeccl( unsigned char ccls[], int lenccl, int fwd[llsiz], int bck[llsiz],

 *			int llsiz, int NUL_mapping );

 *

 * ccls contains the elements of the character class, lenccl is the

 * number of elements in the ccl, fwd is the forward link-list of equivalent

 * characters, bck is the backward link-list, and llsiz size of the link-list.

 *

 * NUL_mapping is the value which NUL (0) should be mapped to.

 */

void    mkeccl (unsigned char ccls[], int lenccl, int fwd[], int bck[], int llsiz, int NUL_mapping)

{

	int     cclp, oldec, newec;

	int     cclm, i, j;

	static unsigned char cclflags[CSIZE];	/* initialized to all '\0' */

	/* Note that it doesn't matter whether or not the character class is

	 * negated.  The same results will be obtained in either case.

	 */

	cclp = 0;

	while (cclp < lenccl) {

		cclm = ccls[cclp];

		if (NUL_mapping && cclm == 0)

			cclm = NUL_mapping;

		oldec = bck[cclm];

		newec = cclm;

		j = cclp + 1;

		for (i = fwd[cclm]; i != NIL && i <= llsiz; i = fwd[i]) {	/* look for the symbol in the character class */

			for (; j < lenccl; ++j) {

				int ccl_char;

				if (NUL_mapping && ccls[j] == 0)

					ccl_char = NUL_mapping;

				else

					ccl_char = ccls[j];

				if (ccl_char > i)

					break;

				if (ccl_char == i && !cclflags[j]) {

					/* We found an old companion of cclm

					 * in the ccl.  Link it into the new

					 * equivalence class and flag it as

					 * having been processed.

					 */

					bck[i] = newec;

					fwd[newec] = i;

					newec = i;

					/* Set flag so we don't reprocess. */

					cclflags[j] = 1;

					/* Get next equivalence class member. */

					/* continue 2 */

					goto next_pt;

				}

			}

			/* Symbol isn't in character class.  Put it in the old

			 * equivalence class.

			 */

			bck[i] = oldec;

			if (oldec != NIL)

				fwd[oldec] = i;

			oldec = i;

		      next_pt:;

		}

		if (bck[cclm] != NIL || oldec != bck[cclm]) {

			bck[cclm] = NIL;

			fwd[oldec] = NIL;

		}

		fwd[newec] = NIL;

		/* Find next ccl member to process. */

		for (++cclp; cclp < lenccl && cclflags[cclp]; ++cclp) {

			/* Reset "doesn't need processing" flag. */

			cclflags[cclp] = 0;

		}

	}

}

/* mkechar - create equivalence class for single character */

void    mkechar (int tch, int fwd[], int bck[])

{

	/* If until now the character has been a proper subset of

	 * an equivalence class, break it away to create a new ec

	 */

	if (fwd[tch] != NIL)

		bck[fwd[tch]] = bck[tch];

	if (bck[tch] != NIL)

		fwd[bck[tch]] = fwd[tch];

	fwd[tch] = NIL;

	bck[tch] = NIL;

}