Context Navigation

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

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

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

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

Download in other formats: