/*************************************************************************/
/*									 */
/*      Evaluation of the subsetting of a discrete attribute		 */
/*      ----------------------------------------------------		 */
/*									 */
/*************************************************************************/

#include "buildex.i"

ItemCount *Slice1, /* Slice1[c]    = saved values of Freq[x][c] in subset.c */
*Slice2; /* Slice2[c]    = saved values of Freq[y][c] */

Set **Subset; /* Subset[a][s] = subset s for att a */

short *Subsets; /* Subsets[a] = no. subsets for att a */

/*************************************************************************/
/*									 */
/*  Evaluate subsetting a discrete attribute and form the chosen	 */
/*  subsets Subset[Att][], setting Subsets[Att] to the number of	 */
/*  subsets, and the Info[] and Gain[] of a test on the attribute	 */
/*									 */
/*************************************************************************/

EvalSubset(Att, Fp, Lp, Items)
	/*  ----------  */
	Attribute Att;ItemNo Fp, Lp;ItemCount Items; {
	DiscrValue V1, V2, BestV1, BestV2, Barred;
	ItemCount KnownItems;
	ClassNo c;
	float BaseInfo, MinGain, ThisGain, ThisInfo, Val, BestVal, BestGain,
			BestInfo, PrevVal, PrevGain, PrevInfo, DiscrKnownBaseInfo(),
			Worth(), ComputeGain(), TotalInfo();
	short Blocks = 0, MissingValues = 0, ReasonableSubsets, Bytes, b;
	Boolean MergedSubsets = false;
	int SaveMINOBJS;

	SaveMINOBJS = MINOBJS;
	MINOBJS = 1;

	/*  First compute Freq[][], ValFreq[], base info, and the gain
	 and total info of a split on discrete attribute Att  */

	ComputeFrequencies(Att, Fp, Lp);

	KnownItems = Items - ValFreq[0];
	if (KnownItems < Epsilon) {
		Verbosity(2)
			printf("\tAtt %s: no known values\n", AttName[Att]);

		Gain[Att] = -Epsilon;
		Info[Att] = 0;
		return;
	}

	BaseInfo = DiscrKnownBaseInfo(KnownItems, MaxAttVal[Att]);

	PrevGain = ComputeGain(BaseInfo, UnknownRate[Att], MaxAttVal[Att],
			KnownItems);
	PrevInfo = TotalInfo(ValFreq, 0, MaxAttVal[Att]) / Items;
	PrevVal = Worth(PrevInfo, PrevGain, Epsilon);

	Verbosity(2) {
		printf("\tAtt %s", AttName[Att]);

		Verbosity(3)
			PrintDistribution(Att, MaxAttVal[Att], true);

		printf("\tinf %.3f, gain %.3f, val=%.3f\n", PrevInfo, PrevGain, PrevVal);
	}

	/*  Eliminate unrepresented attribute values from Freq[] and ValFreq[]
	 and form a separate subset for each represented attribute value  */

	Bytes = (MaxAttVal[Att] >> 3) + 1;
	ClearBits(Bytes, Subset[Att][0]);

	ForEach(V1, 1, MaxAttVal[Att]) {
		if (ValFreq[V1] > 0.5) {
			if (++Blocks < V1) {
				ValFreq[Blocks] = ValFreq[V1];
				ForEach(c, 0, MaxClass) {
					Freq[Blocks][c] = Freq[V1][c];
				}
			}
			ClearBits(Bytes, Subset[Att][Blocks]);
			SetBit(V1, Subset[Att][Blocks]);
		} else {
			SetBit(V1, Subset[Att][0]);
			MissingValues++;
		}
	}

	/*  Merge any single-class subsets with others of the same class  */
	/*  Note: have ValFreq[V] > 0 for all V  */

	ForEach(V1, 1, Blocks-1) {
		for (c = 0; Freq[V1][c] < 0.1; c++)
			;

		if (Freq[V1][c] < ValFreq[V1] - 0.1)
			continue;

		/*  Now have a single class -- look for others  */

		for (V2 = V1 + 1; V2 <= Blocks;) {
			if (Freq[V2][c] < ValFreq[V2] - 0.1) {
				V2++;
			} else {
				/*  Merge these subsets  */

				Combine(V1, V2, Blocks);

				ForEach(b, 0, Bytes-1) {
					Subset[Att][V1][b] |= Subset[Att][V2][b];
					Subset[Att][V2][b] = Subset[Att][Blocks][b];
				}

				Blocks--;
				MergedSubsets = true;
			}
		}
	}

	if (MergedSubsets) {
		PrevGain = ComputeGain(BaseInfo, UnknownRate[Att], Blocks, KnownItems);
		PrevInfo = TotalInfo(ValFreq, 0, Blocks) / Items;
		PrevVal = Worth(PrevInfo, PrevGain, Epsilon);

		Verbosity(2) {
			printf("\tAfter merging single-class subsets:");

			Verbosity(3)
				PrintDistribution(Att, Blocks, false);

			printf("\tinf %.3f, gain %.3f, val=%.3f\n", PrevInfo, PrevGain,
					PrevVal);
		}
	}

	/*  Examine possible pair mergers and hill-climb  */

	MinGain = PrevGain / 2;

	while (Blocks > 2) {
		BestVal = BestV1 = 0;
		BestGain = -Epsilon;

		/*  Check reasonable subsets; if less than 3, bar mergers
		 involving the largest block  */

		ReasonableSubsets = 0;
		Barred = 1;

		ForEach(V1, 1, Blocks) {
			if (ValFreq[V1] >= SaveMINOBJS)
				ReasonableSubsets++;

			if (ValFreq[V1] > ValFreq[Barred])
				Barred = V1;
		}

		if (ReasonableSubsets >= 3)
			Barred = 0;

		/*  For each possible pair of values, calculate the gain and
		 total info of a split in which they are treated as one.
		 Keep track of the pair with the best gain.  */

		ForEach(V1, 1, Blocks-1) {
			ForEach(V2, V1+1, Blocks) {
				if (V1 == Barred || V2 == Barred)
					continue;

				Combine(V1, V2, Blocks);

				ThisGain = ComputeGain(BaseInfo, UnknownRate[Att], Blocks - 1,
						KnownItems);
				ThisInfo = TotalInfo(ValFreq, 0, Blocks - 1) / Items;
				Val = Worth(ThisInfo, ThisGain, Epsilon);

				Verbosity(4) {
					printf("\tcombine %d %d info %.3f gain %.3f val %.3f", V1,
							V2, ThisInfo, ThisGain, Val);
					PrintDistribution(Att, Blocks - 1, false);
				}

				/*  Force a split if
				 less than two reasonable subsets, or
				 using GAIN criterion
				 Prefer this split to the previous one if
				 gain >= MinGain (and previous < MinGain), or
				 val >= previous best val  */

				if (ThisGain >= MinGain && BestGain < MinGain || Val >= BestVal
						|| !BestV1 && (!GAINRATIO || ReasonableSubsets < 2)) {
					BestVal = Val;
					BestGain = ThisGain;
					BestInfo = ThisInfo;
					BestV1 = V1;
					BestV2 = V2;
				}

				Uncombine(V1, V2);
			}
		}

		if (GAINRATIO && ReasonableSubsets >= 2 && (!BestV1 || BestVal
				< PrevVal + 1E-5 || BestVal == PrevVal && BestGain < PrevGain))
			break;

		PrevGain = BestGain;
		PrevInfo = BestInfo;
		PrevVal = BestVal;

		Combine(BestV1, BestV2, Blocks);

		ForEach(b, 0, Bytes-1) {
			Subset[Att][BestV1][b] |= Subset[Att][BestV2][b];
			Subset[Att][BestV2][b] = Subset[Att][Blocks][b];
		}

		Blocks--;

		Verbosity(2) {
			printf("\t\tform subset ");
			PrintSubset(Att, Subset[Att][BestV1]);
			printf(": %d subsets, inf %.3f, gain %.3f, val %.3f\n", Blocks,
					BestInfo, BestGain, BestVal);
			Verbosity(3) {
				printf("\t\tcombine %d, %d", BestV1, BestV2);
				PrintDistribution(Att, Blocks, false);
			}
		}
	}

	MINOBJS = SaveMINOBJS;

	if (PrevVal <= 0) {
		Gain[Att] = -Epsilon;
		Info[Att] = 0;
	} else {
		Gain[Att] = ComputeGain(BaseInfo, UnknownRate[Att], Blocks, KnownItems);
		Info[Att] = PrevInfo;

		if (MissingValues) {
			Blocks++;
			CopyBits(Bytes, Subset[Att][0], Subset[Att][Blocks]);
		}

		Subsets[Att] = Blocks;

		Verbosity(2)
			printf("\tFinal subsets:");
		Verbosity(3)
			PrintDistribution(Att, Blocks, false);
		Verbosity(2)
			printf("\tinf %.3f gain %.3f val %.3f\n", Info[Att], Gain[Att],
					Worth(Info[Att], Gain[Att], Epsilon));
	}
}

/*************************************************************************/
/*									 */
/*  Combine the distribution figures of discrete attribute values	 */
/*  x and y, putting the combined figures in Freq[x][] and		 */
/*  ValFreq[x][], and saving old values in Slice1 and Slice2		 */
/*									 */
/*************************************************************************/

Combine(x, y, Last)
	/*  -------  */
	DiscrValue x, y, Last; {
	ClassNo c;

	ForEach(c, 0, MaxClass) {
		Slice1[c] = Freq[x][c];
		Slice2[c] = Freq[y][c];

		Freq[x][c] += Freq[y][c];
		Freq[y][c] = Freq[Last][c];
	}

	Slice1[MaxClass + 1] = ValFreq[x];
	Slice2[MaxClass + 1] = ValFreq[y];

	ValFreq[x] += ValFreq[y];
	ValFreq[y] = ValFreq[Last];
}

/*************************************************************************/
/*									 */
/*  Restore old class distribution figures of discrete attribute	 */
/*  values x and y from Slice1 and Slice2				 */
/*									 */
/*************************************************************************/

Uncombine(x, y)
	/*  ---------  */
	DiscrValue x, y; {
	ClassNo c;

	ForEach(c, 0, MaxClass) {
		Freq[x][c] = Slice1[c];
		Freq[y][c] = Slice2[c];
	}

	ValFreq[x] = Slice1[MaxClass + 1];
	ValFreq[y] = Slice2[MaxClass + 1];
}

/*************************************************************************/
/*									 */
/*  Print the values of attribute Att which are in the subset Ss	 */
/*									 */
/*************************************************************************/

PrintSubset(Att, Ss)
	/*  -----------  */
	Attribute Att;Set Ss; {
	DiscrValue V1;
	Boolean First = true;

	ForEach(V1, 1, MaxAttVal[Att]) {
		if (In(V1, Ss)) {
			if (First) {
				First = false;
			} else {
				printf(", ");
			}

			printf("%s", AttValName[Att][V1]);
		}
	}
}

/*************************************************************************/
/*									 */
/*  Construct and return a node for a test on a subset of values	 */
/*									 */
/*************************************************************************/

SubsetTest(Node, Att)
	/*  -----------  */
	Tree Node;Attribute Att; {
	ItemCount CountItems();
	short S, Bytes;

	Sprout(Node, Subsets[Att]);

	Node->NodeType = BrSubset;
	Node->Tested = Att;
	Node->Errors = 0;

	Bytes = (MaxAttVal[Att] >> 3) + 1;
	Node->Subset = (Set *) calloc(Subsets[Att] + 1, sizeof(Set));
	ForEach(S, 1, Node->Forks) {
		Node->Subset[S] = (Set) malloc(Bytes);
		CopyBits(Bytes, Subset[Att][S], Node->Subset[S]);
	}
}