Context Navigation

source: proiecte/Parallel-DT/R8/Src/build.c @ 98

Last change on this file since 98 was 82, checked in by (none), 14 years ago

File size: 17.0 KB

Rev	Line
[26]	1	/*************************************************************************/
	2	/* */
	3	/* Central tree-forming algorithm incorporating all criteria */
	4	/* --------------------------------------------------------- */
	5	/* */
	6	/*************************************************************************/
	7
	8	#include "defns.i"
	9	#include "types.i"
	10	#include "extern.i"
[65]	11	//#include "buildex.i"
[26]	12
[65]	13	#include <omp.h>
[26]	14
[82]	15	#define MAX_DISCR_VAL 50
	16	#define MAX_CLASS 50
	17	#define MAX_ATT 50
[26]	18
[65]	19	ItemCount Weight, / Weight[i] = current fraction of item i */
	20	*Freq, / Freq[x][c] = no. items of class c with outcome x */
	21	ValFreq, / ValFreq[x] = no. items with outcome x */
	22	ClassFreq; / ClassFreq[c] = no. items of class c */
[26]	23
[65]	24	float Gain, / Gain[a] = info gain by split on att a */
	25	Info, / Info[a] = potential info of split on att a */
	26	Bar, / Bar[a] = best threshold for contin att a */
	27	UnknownRate; / UnknownRate[a] = current unknown rate for att a */
[26]	28
[65]	29	Boolean Tested, / Tested[a] set if att a has already been tested */
	30	MultiVal; /* true when all atts have many values */
[26]	31
[65]	32	/* External variables initialised here */
[26]	33
[65]	34	extern float SplitGain, / SplitGain[i] = gain with att value of item i as threshold */
	35	SplitInfo; / SplitInfo[i] = potential info ditto */
[26]	36
[65]	37	extern ItemCount Slice1, / Slice1[c] = saved values of Freq[x][c] in subset.c */
	38	Slice2; / Slice2[c] = saved values of Freq[y][c] */
[26]	39
[65]	40	extern Set *Subset; / Subset[a][s] = subset s for att a */
[26]	41
[65]	42	extern short Subsets; / Subsets[a] = no. subsets for att a */
[26]	43
	44	/*************************************************************************/
	45	/* */
	46	/* Allocate space for tree tables */
	47	/* */
	48	/*************************************************************************/
	49
[65]	50	InitialiseTreeData()
[26]	51	/* ------------------ */
[65]	52	{
	53	DiscrValue v;
	54	Attribute a;
[26]	55
[65]	56	Tested = (char *) calloc(MaxAtt + 1, sizeof(char));
[26]	57
[65]	58	Gain = (float *) calloc(MaxAtt + 1, sizeof(float));
	59	Info = (float *) calloc(MaxAtt + 1, sizeof(float));
	60	Bar = (float *) calloc(MaxAtt + 1, sizeof(float));
[26]	61
[65]	62	Subset = (Set *) calloc(MaxAtt + 1, sizeof(Set ));
	63	ForEach(a, 0, MaxAtt) {
	64	if (MaxAttVal[a]) {
	65	Subset[a] = (Set *) calloc(MaxDiscrVal + 1, sizeof(Set));
	66	ForEach(v, 0, MaxAttVal[a]) {
	67	Subset[a][v] = (Set) malloc((MaxAttVal[a] >> 3) + 1);
	68	}
	69	}
[26]	70	}
[65]	71	Subsets = (short *) calloc(MaxAtt + 1, sizeof(short));
[26]	72
[65]	73	SplitGain = (float *) calloc(MaxItem + 1, sizeof(float));
	74	SplitInfo = (float *) calloc(MaxItem + 1, sizeof(float));
[26]	75
[65]	76	Weight = (ItemCount *) calloc(MaxItem + 1, sizeof(ItemCount));
[26]	77
[65]	78	Freq = (ItemCount *) calloc(MaxDiscrVal + 1, sizeof(ItemCount ));
	79	ForEach(v, 0, MaxDiscrVal) {
	80	Freq[v] = (ItemCount *) calloc(MaxClass + 1, sizeof(ItemCount));
	81	}
[26]	82
[65]	83	ValFreq = (ItemCount *) calloc(MaxDiscrVal + 1, sizeof(ItemCount));
	84	ClassFreq = (ItemCount *) calloc(MaxClass + 1, sizeof(ItemCount));
[26]	85
[65]	86	Slice1 = (ItemCount *) calloc(MaxClass + 2, sizeof(ItemCount));
	87	Slice2 = (ItemCount *) calloc(MaxClass + 2, sizeof(ItemCount));
[26]	88
[65]	89	UnknownRate = (float *) calloc(MaxAtt + 1, sizeof(float));
[26]	90
[65]	91	/* Check whether all attributes have many discrete values */
[26]	92
[65]	93	MultiVal = true;
	94	if (!SUBSET) {
	95	for (a = 0; MultiVal && a <= MaxAtt; a++) {
	96	if (SpecialStatus[a] != IGNORE) {
	97	MultiVal = MaxAttVal[a] >= 0.3 * (MaxItem + 1);
	98	}
	99	}
[26]	100	}
	101
	102
[65]	103	}
[26]	104
	105	/*************************************************************************/
	106	/* */
	107	/* Initialise the weight of each item */
	108	/* */
	109	/*************************************************************************/
	110
[65]	111	InitialiseWeights()
[26]	112	/* ----------------- */
	113	{
[65]	114	ItemNo i;
[26]	115
[65]	116	ForEach(i, 0, MaxItem) {
	117	Weight[i] = 1.0;
	118	}
[26]	119	}
	120
	121	/*************************************************************************/
	122	/* */
	123	/* Build a decision tree for the cases Fp through Lp: */
	124	/* */
	125	/* - if all cases are of the same class, the tree is a leaf and so */
	126	/* the leaf is returned labelled with this class */
	127	/* */
	128	/* - for each attribute, calculate the potential information provided */
	129	/* by a test on the attribute (based on the probabilities of each */
	130	/* case having a particular value for the attribute), and the gain */
	131	/* in information that would result from a test on the attribute */
	132	/* (based on the probabilities of each case with a particular */
	133	/* value for the attribute being of a particular class) */
	134	/* */
	135	/* - on the basis of these figures, and depending on the current */
	136	/* selection criterion, find the best attribute to branch on. */
	137	/* Note: this version will not allow a split on an attribute */
	138	/* unless two or more subsets have at least MINOBJS items. */
	139	/* */
	140	/* - try branching and test whether better than forming a leaf */
	141	/* */
	142	/*************************************************************************/
	143
	144	Tree FormTree(Fp, Lp)
[65]	145	/* --------- */
	146	ItemNo Fp, Lp; {
	147	ItemNo i, Kp, Ep, Group();
	148	ItemCount Cases, NoBestClass, KnownCases, CountItems();
	149	float Factor, BestVal, Val, AvGain = 0, Worth();
	150	Attribute Att, BestAtt, Possible = 0;
	151	ClassNo c, BestClass;
	152	Tree Node, Leaf();
	153	DiscrValue v;
	154	Boolean PrevAllKnown;
[26]	155
[65]	156	Cases = CountItems(Fp, Lp);
[26]	157
[65]	158	/* Generate the class frequency distribution */
[26]	159
[65]	160	// ########### begin parallel region ############## //
[82]	161	//#pragma omp parallel default(shared)
	162	//{
[26]	163
[65]	164	//printf("The parallel region is executed by thread %d\n", omp_get_thread_num());
	165	/* THIS CAN BE PARALELIZED */
[82]	166	//#pragma omp for private(c)
[65]	167	ForEach(c, 0, MaxClass) {
	168	ClassFreq[c] = 0;
	169	}
[26]	170
[65]	171	/* THIS CAN BE PARALELIZED */
[82]	172	//#pragma omp for private(i)
[65]	173	ForEach(i, Fp, Lp) {
[82]	174	//#pragma omp atomic
[65]	175	ClassFreq[Class(Item[i])] += Weight[i];
	176	}
[82]	177	//}
[26]	178
[65]	179	/* Find the most frequent class */
	180	/* THIS CAN BE PARALELIZED */
	181	BestClass = 0;
[26]	182
[65]	183	ForEach(c, 0, MaxClass) {
	184	if (ClassFreq[c] > ClassFreq[BestClass]) {
	185	BestClass = c;
	186	}
	187	}
[26]	188
[65]	189	NoBestClass = ClassFreq[BestClass];
[26]	190
[65]	191	Node = Leaf(ClassFreq, BestClass, Cases, Cases - NoBestClass);
[26]	192
[65]	193	/* If all cases are of the same class or there are not enough
	194	cases to divide, the tree is a leaf */
[26]	195
[65]	196	if (NoBestClass == Cases \|\| Cases < 2 * MINOBJS) {
	197	return Node;
	198	}
[26]	199
[65]	200	Verbosity(1)
	201	printf("\n%d items, total weight %.1f\n", Lp - Fp + 1, Cases);
[26]	202
[65]	203	/* For each available attribute, find the information and gain */
[26]	204
[65]	205	ForEach(Att, 0, MaxAtt) {
	206	Gain[Att] = -Epsilon;
	207
	208	if (SpecialStatus[Att] == IGNORE)
	209	continue;
	210
	211	if (MaxAttVal[Att]) {
	212	/* discrete valued attribute */
	213
	214	if (SUBSET && MaxAttVal[Att] > 2) {
	215	EvalSubset(Att, Fp, Lp, Cases);
	216	} else if (!Tested[Att]) {
	217	EvalDiscreteAtt(Att, Fp, Lp, Cases);
	218	}
	219	} else {
	220	/* continuous attribute */
	221
	222	EvalContinuousAtt(Att, Fp, Lp);
	223	}
	224
	225	/* Update average gain, excluding attributes with very many values */
	226
	227	if (Gain[Att] > -Epsilon && (MultiVal \|\| MaxAttVal[Att] < 0.3 * (MaxItem + 1))) {
	228	Possible++;
	229	AvGain += Gain[Att];
	230	}
	231
[26]	232	}
	233
[65]	234	/* Find the best attribute according to the given criterion */
	235	BestVal = -Epsilon;
	236	BestAtt = None;
	237	AvGain = (Possible ? AvGain / Possible : 1E6);
[26]	238
[65]	239	Verbosity(2) {
	240	if (AvGain < 1E6)
	241	printf("\taverage gain %.3f\n", AvGain);
	242	}
[26]	243
[65]	244	ForEach(Att, 0, MaxAtt) {
	245	if (Gain[Att] > -Epsilon) {
	246	Val = Worth(Info[Att], Gain[Att], AvGain);
	247	if (Val > BestVal) {
	248	BestAtt = Att;
	249	BestVal = Val;
	250	}
	251	}
[26]	252	}
	253
	254
[65]	255	/* Decide whether to branch or not */
[26]	256
[65]	257	if (BestAtt != None) {
	258	Verbosity(1) {
	259	printf("\tbest attribute %s", AttName[BestAtt]);
	260	if (!MaxAttVal[BestAtt]) {
	261	printf(" cut %.3f", Bar[BestAtt]);
	262	}
	263	printf(" inf %.3f gain %.3f val %.3f\n", Info[BestAtt],
	264	Gain[BestAtt], BestVal);
	265	}
[26]	266
[65]	267	/* Build a node of the selected test */
[26]	268
[65]	269	if (MaxAttVal[BestAtt]) {
	270	/* Discrete valued attribute */
[26]	271
[65]	272	if (SUBSET && MaxAttVal[BestAtt] > 2) {
	273	SubsetTest(Node, BestAtt);
	274	} else {
	275	DiscreteTest(Node, BestAtt);
	276	}
	277	} else {
	278	/* Continuous attribute */
[26]	279
[65]	280	ContinTest(Node, BestAtt);
	281	}
[26]	282
[65]	283	/* Remove unknown attribute values */
	284
	285	PrevAllKnown = AllKnown;
	286
	287	Kp = Group(0, Fp, Lp, Node) + 1;
	288	if (Kp != Fp)
	289	AllKnown = false;
	290	KnownCases = Cases - CountItems(Fp, Kp - 1);
	291	UnknownRate[BestAtt] = (Cases - KnownCases) / (Cases + 0.001);
	292
	293	Verbosity(1) {
	294	if (UnknownRate[BestAtt] > 0) {
	295	printf("\tunknown rate for %s = %.3f\n", AttName[BestAtt],
	296	UnknownRate[BestAtt]);
	297	}
	298	}
	299
	300	/* Recursive divide and conquer */
	301
	302	++Tested[BestAtt];
	303
	304	Ep = Kp - 1;
	305	Node->Errors = 0;
	306
	307	ForEach(v, 1, Node->Forks) {
	308	Ep = Group(v, Kp, Lp, Node);
	309
	310	if (Kp <= Ep) {
	311	Factor = CountItems(Kp, Ep) / KnownCases;
	312
	313	ForEach(i, Fp, Kp-1) {
	314	Weight[i] *= Factor;
	315	}
	316
	317	Node->Branch[v] = FormTree(Fp, Ep);
	318	Node->Errors += Node->Branch[v]->Errors;
	319
	320	Group(0, Fp, Ep, Node);
	321	ForEach(i, Fp, Kp-1) {
	322	Weight[i] /= Factor;
	323	}
	324	} else {
	325	Node->Branch[v] = Leaf(Node->ClassDist, BestClass, 0.0, 0.0);
	326	}
	327	}
	328
	329	--Tested[BestAtt];
	330	AllKnown = PrevAllKnown;
	331
	332	/* See whether we would have been no worse off with a leaf */
	333
	334	if (Node->Errors >= Cases - NoBestClass - Epsilon) {
	335	Verbosity(1)
	336	printf("Collapse tree for %d items to leaf %s\n", Lp - Fp + 1,
	337	ClassName[BestClass]);
	338
	339	Node->NodeType = 0;
	340	}
	341	}
	342	else {
	343	Verbosity(1)
	344	printf("\tno sensible splits %.1f/%.1f\n", Cases, Cases
	345	- NoBestClass);
	346	}
	347
	348	return Node;
	349	}
	350
	351	Tree FormTree_Discr(Fp, Lp)
	352	/* --------- */
	353	ItemNo Fp, Lp; {
	354	ItemNo i, Kp, Ep, Group();
	355	ItemCount Cases, NoBestClass, KnownCases, CountItems();
	356	float Factor, BestVal, Val, AvGain = 0, Worth();
	357	Attribute Att, BestAtt, Possible = 0;
	358	ClassNo c, BestClass;
	359	Tree Node, Leaf();
	360	DiscrValue v;
	361	Boolean PrevAllKnown;
[82]	362	ItemCount** Freq_discr, *ValFreq_discr;
	363	float* UnknownRate_discr;
[65]	364
	365	Cases = CountItems(Fp, Lp);
	366
	367	/* Generate the class frequency distribution */
	368
	369	// ########### begin parallel region ############## //
[82]	370	//#pragma omp parallel
	371	//{
[65]	372	//printf("The parallel region is executed by thread %d\n", omp_get_thread_num());
	373	/* THIS CAN BE PARALELIZED */
[82]	374	//#pragma omp for private(c)
[65]	375	ForEach(c, 0, MaxClass) {
	376	ClassFreq[c] = 0;
	377	}
	378
	379	/* THIS CAN BE PARALELIZED */
[82]	380	//#pragma omp for private(i)
[65]	381	ForEach(i, Fp, Lp) {
[82]	382	//#pragma omp atomic
[65]	383	ClassFreq[Class(Item[i])] += Weight[i];
	384	}
[82]	385	//}
[26]	386
[65]	387	/* Find the most frequent class */
	388	/* THIS CAN BE PARALELIZED */
	389	BestClass = 0;
[26]	390
[65]	391	ForEach(c, 0, MaxClass) {
	392	if (ClassFreq[c] > ClassFreq[BestClass]) {
	393	BestClass = c;
	394	}
	395	}
[26]	396
[65]	397	NoBestClass = ClassFreq[BestClass];
[26]	398
[65]	399	Node = Leaf(ClassFreq, BestClass, Cases, Cases - NoBestClass);
[26]	400
[65]	401	/* If all cases are of the same class or there are not enough
	402	cases to divide, the tree is a leaf */
	403
	404	if (NoBestClass == Cases \|\| Cases < 2 * MINOBJS) {
	405	return Node;
	406	}
	407
[26]	408	Verbosity(1)
[65]	409	printf("\n%d items, total weight %.1f\n", Lp - Fp + 1, Cases);
	410
	411
	412	/* For each available attribute, find the information and gain */
	413	/* THIS MUST BE PARALELIZED */
[82]	414	#pragma omp parallel default(shared) shared(Possible, AvGain) private(v, Freq_discr, ValFreq_discr, UnknownRate_discr)
[26]	415	{
[82]	416	Freq_discr = (ItemCount *) calloc(MaxDiscrVal + 1, sizeof(ItemCount ));
	417	ForEach(v, 0, MaxDiscrVal) {
	418	Freq_discr[v] = (ItemCount *) calloc(MaxClass + 1, sizeof(ItemCount));
	419	}
[65]	420
[82]	421	ValFreq_discr = (ItemCount *) calloc(MaxDiscrVal + 1, sizeof(ItemCount));
	422	UnknownRate_discr = (float *) calloc(MaxAtt + 1, sizeof(float));
	423
	424
	425	#pragma omp for private(Att) schedule(static)
[65]	426	ForEach(Att, 0, MaxAtt) {
	427	Gain[Att] = -Epsilon;
	428
	429	if (SpecialStatus[Att] == IGNORE)
	430	continue;
	431
	432	if (MaxAttVal[Att]) {
	433	/* discrete valued attribute */
	434
	435	if (SUBSET && MaxAttVal[Att] > 2) {
	436	EvalSubset(Att, Fp, Lp, Cases);
	437	} else if (!Tested[Att]) {
[82]	438
	439	EvalDiscreteAtt_Discr(Att, Fp, Lp, Cases, Freq_discr, ValFreq_discr, UnknownRate_discr);
[65]	440	}
	441	} else {
	442	/* continuous attribute */
	443
	444	EvalContinuousAtt(Att, Fp, Lp);
	445	}
	446
	447	/* Update average gain, excluding attributes with very many values */
	448	#pragma omp critical
	449	{
[82]	450	if (Gain[Att] > -Epsilon && (MultiVal \|\| MaxAttVal[Att] < 0.3 * (MaxItem + 1))){
	451	//#pragma omp atomic
[65]	452	Possible++;
[82]	453
	454	//#pragma omp atomic
[65]	455	AvGain += Gain[Att];
	456	}
	457	}
	458	}
	459
[82]	460	free(UnknownRate_discr);
	461	free(ValFreq_discr);
	462	ForEach(v, 0, MaxDiscrVal) {
	463	free(Freq_discr[v]);
	464	}
	465	free(Freq_discr);
	466
[26]	467	}
	468
[65]	469	/* Find the best attribute according to the given criterion */
	470	//#pragma omp single
	471	//{
	472	BestVal = -Epsilon;
	473	BestAtt = None;
	474	AvGain = (Possible ? AvGain / Possible : 1E6);
[26]	475
[65]	476	Verbosity(2) {
	477	if (AvGain < 1E6)
	478	printf("\taverage gain %.3f\n", AvGain);
	479	}
[26]	480
[65]	481	ForEach(Att, 0, MaxAtt) {
	482	if (Gain[Att] > -Epsilon) {
	483	Val = Worth(Info[Att], Gain[Att], AvGain);
	484	if (Val > BestVal) {
	485	BestAtt = Att;
	486	BestVal = Val;
	487	}
	488	}
	489	}
	490	//}
	491	//}
	492	/* Decide whether to branch or not */
[26]	493
[65]	494	if (BestAtt != None) {
	495	Verbosity(1) {
	496	printf("\tbest attribute %s", AttName[BestAtt]);
	497	if (!MaxAttVal[BestAtt]) {
	498	printf(" cut %.3f", Bar[BestAtt]);
	499	}
	500	printf(" inf %.3f gain %.3f val %.3f\n", Info[BestAtt],
	501	Gain[BestAtt], BestVal);
	502	}
[26]	503
[65]	504	/* Build a node of the selected test */
[26]	505
[65]	506	if (MaxAttVal[BestAtt]) {
	507	/* Discrete valued attribute */
	508
	509	if (SUBSET && MaxAttVal[BestAtt] > 2) {
	510	SubsetTest(Node, BestAtt);
	511	} else {
	512	DiscreteTest(Node, BestAtt);
	513	}
	514	} else {
	515	/* Continuous attribute */
	516
	517	ContinTest(Node, BestAtt);
[26]	518	}
	519
[65]	520	/* Remove unknown attribute values */
[26]	521
[65]	522	PrevAllKnown = AllKnown;
	523
	524	Kp = Group(0, Fp, Lp, Node) + 1;
	525	if (Kp != Fp)
	526	AllKnown = false;
	527	KnownCases = Cases - CountItems(Fp, Kp - 1);
	528	UnknownRate[BestAtt] = (Cases - KnownCases) / (Cases + 0.001);
	529
	530	Verbosity(1) {
	531	if (UnknownRate[BestAtt] > 0) {
	532	printf("\tunknown rate for %s = %.3f\n", AttName[BestAtt],
	533	UnknownRate[BestAtt]);
	534	}
[26]	535	}
	536
[65]	537	/* Recursive divide and conquer */
[26]	538
[65]	539	++Tested[BestAtt];
[26]	540
[65]	541	Ep = Kp - 1;
	542	Node->Errors = 0;
[26]	543
[65]	544	ForEach(v, 1, Node->Forks) {
	545	Ep = Group(v, Kp, Lp, Node);
[26]	546
[65]	547	if (Kp <= Ep) {
	548	Factor = CountItems(Kp, Ep) / KnownCases;
[26]	549
[65]	550	ForEach(i, Fp, Kp-1) {
	551	Weight[i] *= Factor;
	552	}
[26]	553
[65]	554	Node->Branch[v] = FormTree(Fp, Ep);
	555	Node->Errors += Node->Branch[v]->Errors;
[26]	556
[65]	557	Group(0, Fp, Ep, Node);
	558	ForEach(i, Fp, Kp-1) {
	559	Weight[i] /= Factor;
	560	}
	561	} else {
	562	Node->Branch[v] = Leaf(Node->ClassDist, BestClass, 0.0, 0.0);
	563	}
	564	}
	565
	566	--Tested[BestAtt];
	567	AllKnown = PrevAllKnown;
	568
	569	/* See whether we would have been no worse off with a leaf */
	570
	571	if (Node->Errors >= Cases - NoBestClass - Epsilon) {
	572	Verbosity(1)
	573	printf("Collapse tree for %d items to leaf %s\n", Lp - Fp + 1,
	574	ClassName[BestClass]);
	575
	576	Node->NodeType = 0;
	577	}
	578	}
	579	else {
	580	Verbosity(1)
	581	printf("\tno sensible splits %.1f/%.1f\n", Cases, Cases
	582	- NoBestClass);
	583	}
	584
	585	return Node;
	586	}
[26]	587	/*************************************************************************/
	588	/* */
	589	/* Group together the items corresponding to branch V of a test */
	590	/* and return the index of the last such */
	591	/* */
	592	/* Note: if V equals zero, group the unknown values */
	593	/* */
	594	/*************************************************************************/
	595
	596	ItemNo Group(V, Fp, Lp, TestNode)
[65]	597	/* ----- */
	598	DiscrValue V;ItemNo Fp, Lp;Tree TestNode; {
	599	ItemNo i;
	600	Attribute Att;
	601	float Thresh;
	602	Set SS;
	603	void Swap();
[26]	604
[65]	605	Att = TestNode->Tested;
[26]	606
[65]	607	if (V) {
	608	/* Group items on the value of attribute Att, and depending
	609	on the type of branch */
[26]	610
[65]	611	switch (TestNode->NodeType) {
	612	case BrDiscr:
[26]	613
[65]	614	ForEach(i, Fp, Lp) {
	615	if (DVal(Item[i], Att) == V)
	616	Swap(Fp++, i);
	617	}
	618	break;
[26]	619
[65]	620	case ThreshContin:
[26]	621
[65]	622	Thresh = TestNode->Cut;
	623	ForEach(i, Fp, Lp) {
	624	if ((CVal(Item[i], Att) <= Thresh) == (V == 1))
	625	Swap(Fp++, i);
	626	}
	627	break;
[26]	628
[65]	629	case BrSubset:
[26]	630
[65]	631	SS = TestNode->Subset[V];
	632	ForEach(i, Fp, Lp) {
	633	if (In(DVal(Item[i], Att), SS))
	634	Swap(Fp++, i);
	635	}
	636	break;
[26]	637	}
[65]	638	} else {
	639	/* Group together unknown values */
[26]	640
[65]	641	switch (TestNode->NodeType) {
	642	case BrDiscr:
	643	case BrSubset:
[26]	644
[65]	645	ForEach(i, Fp, Lp) {
	646	if (!DVal(Item[i], Att))
	647	Swap(Fp++, i);
	648	}
	649	break;
[26]	650
[65]	651	case ThreshContin:
[26]	652
[65]	653	ForEach(i, Fp, Lp) {
	654	if (CVal(Item[i], Att) == Unknown)
	655	Swap(Fp++, i);
	656	}
	657	break;
[26]	658	}
	659	}
	660
[65]	661	return Fp - 1;
[26]	662	}
	663
	664	/*************************************************************************/
	665	/* */
	666	/* Return the total weight of items from Fp to Lp */
	667	/* */
	668	/*************************************************************************/
	669
	670	ItemCount CountItems(Fp, Lp)
[65]	671	/* ---------- */
	672	ItemNo Fp, Lp; {
	673	register ItemCount Sum = 0.0, Wt, LWt;
	674	ItemNo i;
[26]	675
[65]	676	if (AllKnown)
	677	return Lp - Fp + 1;
[26]	678
[65]	679	//Lwt = Weight + Lp;
[26]	680
[82]	681	//#pragma omp parallel for reduction(+:Sum)
[65]	682	for (i = Fp; i <= Lp; i++) {
	683	Sum += Weight[i];
	684	}
	685
	686	return Sum;
[26]	687	}
	688
	689	/*************************************************************************/
	690	/* */
	691	/* Exchange items at a and b */
	692	/* */
	693	/*************************************************************************/
	694
[65]	695	void Swap(a, b)
	696	/* ---- */
	697	ItemNo a, b; {
	698	register Description Hold;
	699	register ItemCount HoldW;
[26]	700
[65]	701	Hold = Item[a];
	702	Item[a] = Item[b];
	703	Item[b] = Hold;
[26]	704
[65]	705	HoldW = Weight[a];
	706	Weight[a] = Weight[b];
	707	Weight[b] = HoldW;
[26]	708	}

Note: See TracBrowser for help on using the repository browser.

Download in other formats: