Windoware

home *** CD-ROM | disk | FTP | other *** search

/ Windoware / WINDOWARE_1_6.iso / miscprog / atre20 / atree.c next >

Wrap

C/C++ Source or Header | 1991-08-08 | 83.9 KB | 2,764 lines

/***************************************************************************** **** **** **** atree.c **** **** **** **** atree release 2.0 for PC, Windows **** **** Adaptive Logic Network (ALN) simulation program. **** **** Copyright (C) A. Dwelly, R. Manderscheid, W.W. Armstrong, **** **** M. Thomas, 1991 **** **** License: **** **** A royalty-free license is granted for the use of this software for **** **** NON_COMMERCIAL PURPOSES ONLY. The software may be copied and/or **** **** modified provided this notice appears in its entirety and unchanged **** **** in all derived source programs. Persons modifying the code are **** **** requested to state the date, the changes made and who made them **** **** in the modification history. **** **** **** **** Patent License: **** **** The use of a digital circuit which transmits a signal indicating **** **** heuristic responsibility is protected by U. S. Patent 3,934,231 **** **** and others assigned to Dendronic Decisions Limited of Edmonton, **** **** W. W. Armstrong, President. A royalty-free license is granted **** **** by the company to use this patent for NON_COMMERCIAL PURPOSES to **** **** adapt logic trees using this program and its modifications. **** **** **** **** Limited Warranty: **** **** This software is provided "as is" without warranty of any kind, **** **** either expressed or implied, including, but not limited to, the **** **** implied warrantees of merchantability and fitness for a particular **** **** purpose. The entire risk as to the quality and performance of the **** **** program is with the user. Neither the authors, nor the **** **** University of Alberta, its officers, agents, servants or employees **** **** shall be liable or responsible in any way for any damage to **** **** property or direct personal or consequential injury of any nature **** **** whatsoever that may be suffered or sustained by any licensee, user **** **** or any other party as a consequence of the use or disposition of **** **** this software. **** **** **** **** Modification history: **** **** **** **** 90.09.05 Initial implementation, A.Dwelly **** **** 91.04.15 Port to PC and minor bug fixes, R. Manderscheid **** **** 91.05.31 Port to Windows & Windows Extensions, M. Thomas **** **** 91.07.17 atree v2.0 for Windows, M. Thomas **** **** **** *****************************************************************************/ #pragma inline /***************************************************************************** **** **** **** Include Files **** **** **** *****************************************************************************/ #include <windows.h> #include <stdio.h> #include <stdlib.h> #include <math.h> #include "..\atree.h" #define assert(exp)\ {\ if (!(exp))\ {\ char szBuffer[80]; \ wsprintf(szBuffer, "%s, Line %d",\ (LPSTR)__FILE__, __LINE__);\ MessageBox (NULL, szBuffer, "Assertion Failed",\ MB_OK | MB_ICONSTOP);\ }\ } /***************************************************************************** **** **** **** Constants **** **** **** *****************************************************************************/ #define AND 0 #define RIGHT 1 #define LEFT 2 #define OR 3 #define LEAF 4 #define LEFT_CHILD 0 #define RIGHT_CHILD 1 #define FALSE 0 /* As usual */ #define TRUE 1 #define UNEVALUATED 2 /* We complete the lattice of boolean functions */ #define ATREE_ERROR 3 /* Don't want conflict with Windows.h ERROR */ #define MAX_RETRY 50 /* No. of retrys before an error in atree_rand_walk */ /* Number of nodes/leaves to allocate in each call to malloc in get_node() */ #define NEWMALLOC 1024 #define BYTE 8 /*length of a byte in bits*/ /* Initialisation values */ #define MAXSET 63 #define ABOVEMID 32 #define BELOWMID 31 #define MINSET 0 #define STACKSIZE 100 /*stack used in load_tree */ #define LEAF_TOKEN 256 #define CODING_HEADER_FORMAT "vectors=%d, width=%d, range=%g,%g\n" #define CODING_HEADER_ITEMS 4 /* memory manager constants */ #define SEGLENGTH 65536L /* 64K */ #define NUMSEGS 256 /* can manage up to 16384K (16Megs) */ /* * Macros */ #define Printf(str,fmt) {\ char string[] = str; \ sprintf(szBuffer,string,fmt);\ } /* Public and private procedures */ #define public #define private static /* Infinite loops - for EVER */ #define EVER (;;) /* Printing out the boolean lattice */ #define PRINTBOOL(b) if (b == TRUE) {Printf("1",0);} else if (b == FALSE)\ {Printf("0",0);} else if (b == UNEVALUATED) {Printf("U",0);} else \ if (b == ATREE_ERROR) {Printf("E",0);} else {Printf("?",0);} /* Verbosity */ #define VERBOSE(level,s) if (verbosity >= level) {s ;} /* * Types */ typedef int bool_t; /* * Only TRUE, FALSE, UNEVALUATED or ATREE_ERROR * are used in these variables */ typedef struct token_struct { int token; int bit_no; int complemented; } token_t; /* * some static variables needed by the atree memory manager */ /* HANDLE to each segment */ static HANDLE seg[NUMSEGS]; /* memory free in each segment */ static WORD freemem[NUMSEGS]; /* * Preliminary Private Procedure Declarations */ private void NEAR PASCAL WinMem_Init(); private LPATREE NEAR PASCAL get_node(int); private void NEAR PASCAL reclaim_node(LPATREE); private LPATREE NEAR PASCAL build_tree(LPINT, bool_t far *,int,int); private void NEAR PASCAL print_tree(LPATREE, int, int, int); private bool_t NEAR PASCAL train(LPATREE, LPBIT_VEC, bool_t); private void NEAR PASCAL adapt(LPATREE, LPBIT_VEC, bool_t); private char NEAR PASCAL node_function(LPATREE); private void NEAR PASCAL compress_tree(LPATREE,LPFAST_TREE,LPFAST_TREE,LPFAST_TREE,LPINT); private int NEAR PASCAL count_leaves(LPATREE, int); private int NEAR PASCAL store_tree(LPATREE, FILE *); private int NEAR PASCAL get_token(FILE *, token_t far *); #pragma argsused HANDLE hVerbInstance; HWND hwnd; char szVerbLine1[60]; char szVerbLine2[60]; char szVerbLine3[60]; short cyChar; BOOL atree_quit_flag = FALSE; long FAR PASCAL VerbosityWndProc(HWND hwnd, WORD message, WORD wParam, LONG lParam) { static short cxChar, cxCaps; char szBuffer[10]; HDC hdc; short i; PAINTSTRUCT ps; TEXTMETRIC tm; switch (message) { case WM_CREATE: hdc = GetDC(hwnd); GetTextMetrics(hdc, &tm); cxChar = tm.tmAveCharWidth; cxCaps = (tm.tmPitchAndFamily & 1 ? 3 : 2) * cxChar / 2 ; cyChar = tm.tmHeight + tm.tmExternalLeading ; ReleaseDC(hwnd,hdc); return 0; case WM_PAINT: hdc = BeginPaint(hwnd, &ps); TextOut (hdc, 5 * cxChar, cyChar * 6, szVerbLine1, lstrlen(szVerbLine1)); TextOut (hdc, 5 * cxChar, cyChar * 7, szVerbLine2, lstrlen(szVerbLine2)); TextOut (hdc, 5 * cxChar, cyChar * 8, szVerbLine3, lstrlen(szVerbLine3)); EndPaint(hwnd, &ps); return 0; case WM_DESTROY: PostQuitMessage(0); return 0; } return DefWindowProc(hwnd,message, wParam, lParam); } /***************************************************************************** ***************************************************************************** **** **** **** Public Routines **** **** **** ***************************************************************************** *****************************************************************************/ /***************************************************************************** **** **** **** void FAR PASCAL atree_init() **** **** **** **** Synopsis: **** **** **** **** Initialises various global variables, and makes an initial call to **** **** the random number seed routine. Checks to make sure Windows is in **** **** protect mode. **** **** **** *****************************************************************************/ public void FAR PASCAL atree_init(hInstance) HANDLE hInstance; { DWORD c; static BOOL first = TRUE; WNDCLASS wndclass; static char cInstance[40]; if (first) { first = FALSE; itoa(hInstance, cInstance, 10); hVerbInstance = hInstance; wndclass.style = CS_NOCLOSE; wndclass.lpfnWndProc = VerbosityWndProc; wndclass.cbClsExtra = 0; wndclass.cbWndExtra = 0; wndclass.hInstance = hInstance; wndclass.hIcon = LoadIcon(NULL, IDI_APPLICATION); wndclass.hCursor = LoadCursor(NULL, IDC_ARROW); wndclass.hbrBackground = GetStockObject(WHITE_BRUSH); wndclass.lpszMenuName = NULL; wndclass.lpszClassName = (LPSTR) cInstance; RegisterClass(&wndclass); c = GetTickCount(); (void) srand((int) c); c = GetWinFlags(); if (!(c & WF_PMODE)) { MessageBox(NULL, "Atree software cannot run\nin Windows Real Mode!", "Not in Protected Mode!", MB_OK | MB_ICONSTOP); exit(0); } hwnd = CreateWindow((LPSTR)cInstance, "atree Status", WS_OVERLAPPEDWINDOW, CW_USEDEFAULT, CW_USEDEFAULT, 300, 180, NULL, NULL, hVerbInstance, NULL); } return; } /***************************************************************************** **** **** **** void atree_quit() **** **** **** **** sets the quit flag for use by other atree routines when an exit **** **** is desired **** *****************************************************************************/ void FAR PASCAL atree_quit(void) { atree_quit_flag = TRUE; // DestroyWindow(hwnd); } /***************************************************************************** **** **** **** LPBIT_VEC atree_rand_walk(num,width,p) **** **** **** **** int num; **** **** int width; **** **** int p; **** **** **** **** Synopsis: **** **** **** **** Creates an array of _num_ binary vectors, of _width_ bits where **** **** each is _p_ bits away from its neighbours in Hamming space. Each **** **** vector is unique. **** **** This routine returns NULL if it's unable to find enough vectors. **** *****************************************************************************/ #pragma warn -pia public LPBIT_VEC FAR PASCAL atree_rand_walk(num,width,p) int num; int width; int p; { /* * An initial vector is produced with random bits, and each subsequent * vector in the random walk just has _p_ bits flipped. In order to * guarantee that each vector is unique, it is checked against * a chained list of vectors of the same bit sum. If it is not already * in the chain it is appended to the end, or else the vector is discarded * and the process repeats itself. */ LPBIT_VEC walk; /* An array of bit vectors */ LPBIT_VEC pckd_vec; /* The packed unique ? vector */ bool_t unique; /* Uniqueness flag set during testing */ LPINT bit_sum_chain; /* Pointers to vectors of equivalent bit sums */ LPINT next_vec; /* Chain array */ LPSTR unpckd_vec; /* An unpacked vector */ LPSTR this_vec; /* An unpacked vector */ LPSTR mark_vec; /* TRUE where a bit has been flipped */ int i; int j; int old_bit_sum; /* Last number of TRUE bits in vector */ int bit_sum; /* Current number of TRUE bits in vector */ int retrys; /* Number of attempts to find a unique vec */ int victim; /* The bit just twiddled */ int current_vec; /* Part of the chain */ assert(num > 0); assert(width > 0); assert((p > 0) && (p <= width)); /* Assign space in memory */ walk = (LPBIT_VEC) Malloc((unsigned) num * sizeof(bit_vec)); MEMCHECK(walk); bit_sum_chain = (LPINT) Malloc((unsigned) (width+1) * sizeof(int)); MEMCHECK(bit_sum_chain); next_vec = (LPINT) Malloc((unsigned) num * sizeof(int)); MEMCHECK(next_vec); unpckd_vec = (LPSTR) Malloc((unsigned) width * sizeof(char)); MEMCHECK(unpckd_vec); this_vec = (LPSTR) Malloc((unsigned) width * sizeof(char)); MEMCHECK(this_vec); mark_vec = (LPSTR) Malloc((unsigned) width * sizeof(char)); MEMCHECK(mark_vec); /* Clear bit_sum_chain */ for (i = 0; i <= width; i++) { bit_sum_chain[i] = -1; } /* Clear next_vec */ for (i = 0; i < num; i++) { next_vec[i] = -1; } /* Create initial vector and bit sum */ old_bit_sum = 0; for (i = 0; i < width; i++) { if (unpckd_vec[i] = RANDOM(2)) { old_bit_sum++; } } walk[0] = *(bv_pack(unpckd_vec,width)); bit_sum_chain[old_bit_sum] = 0; /* Random walk */ for (i = 1; i < num; i++) { /* allow multitasking */ Windows_Interrupt(1000); retrys = 0; unique = FALSE; while ((!unique) && (retrys < MAX_RETRY)) { retrys++; /* Make a new vector */ bit_sum = old_bit_sum; for (j = 0; j < width; j++) { this_vec[j] = unpckd_vec[j]; mark_vec[j] = FALSE; } for (j = 0; j < p; j++) { do { victim = RANDOM(width); } while (mark_vec[victim]); mark_vec[victim] = TRUE; this_vec[victim] = !this_vec[victim]; if (this_vec[victim] == FALSE) { bit_sum--; } else { bit_sum++; } } pckd_vec = bv_pack(this_vec,width); /* Compare it with the existing ones of equal bit length */ if (bit_sum_chain[bit_sum] == -1) { /* There are no other vectors with this bit sum, so ... */ unique = TRUE; walk[i] = *pckd_vec; bit_sum_chain[bit_sum] = i; next_vec[i] = -1; } else { current_vec = bit_sum_chain[bit_sum]; for EVER /* We break out of here inside the loop */ { if (bv_equal(&(walk[current_vec]),pckd_vec)) { /* This vector already exists, unique = FALSE; */ break; } else { if (next_vec[current_vec] == -1) { unique = TRUE; walk[i] = *pckd_vec; next_vec[current_vec] = i; next_vec[i] = -1; break; } else { current_vec = next_vec[current_vec]; } } } /* for EVER */ } /* if (bit_sum_chain...) */ } /* while ((!unique... ))*/ /* * If Unique is TRUE at this point, we have a unique * vector stored, we have to set up old_bit sum and unpckd_vec * for the next vector. * If unique is FALSE, we have tried to create a unique vector * MAX_RETRY times, and failed. We therefore signal an error. */ if (unique) { for (j = 0; j < width; j++) { unpckd_vec[j] = this_vec[j]; } old_bit_sum = bit_sum; } else { (void) Free(walk); walk = NULL; break; } } /* for */ /* Free space in memory */ Free(bit_sum_chain); Free(next_vec); Free(unpckd_vec); Free(this_vec); Free(mark_vec); /* Return final vector */ return(walk); } #pragma warn .pia /***************************************************************************** **** **** **** LPATREE atree_create(numvars,leaves) **** **** **** **** int numvars; **** **** int leaves; **** **** **** **** Synopsis: **** **** **** **** Creates an adaptive tree with _leaves_ number of leaves connected **** **** to _numvars_ variables and their complements. The number of **** **** leaves should probably be at least twice _numvars_. **** **** The node functions and the connections are picked at random. **** **** **** *****************************************************************************/ public LPATREE FAR PASCAL atree_create(numvars,leaves) int numvars; int leaves; { LPATREE tree; LPINT connection; bool_t far *complemented; bool_t comp; int i; assert(leaves > 0); assert(numvars > 0); /* * Create a list of bit inputs and shuffle, complemented inputs * are marked with a TRUE in the complemented array. */ connection = (LPINT) Malloc((unsigned) sizeof(int) * leaves); MEMCHECK(connection); complemented = (bool_t far *) Malloc((unsigned) sizeof(int) * leaves); MEMCHECK(complemented); comp = FALSE; for (i = 0; i < leaves; i++) { int numvarscount = i % numvars; if (numvarscount == 0) { comp = !comp; } connection[i] = numvarscount; complemented[i] = comp; } /* Shuffle */ for (i = 0; i < leaves; i++) { int a; int b; int tmp; a = RANDOM(leaves); b = RANDOM(leaves); tmp = connection[a]; connection[a] = connection[b]; connection[b] = tmp; tmp = complemented[a]; complemented[a] = complemented[b]; complemented[b] = tmp; } tree = build_tree(connection, complemented, 0, leaves - 1); (void) Free(connection); (void) Free(complemented); return(tree); } /***************************************************************************** **** **** **** BOOL atree_eval(tree,vec) **** **** **** **** LPATREE tree; **** **** LPBIT_VEC vec; **** **** **** **** Synopsis: **** **** **** **** Applies the _tree_ to the bit vector _vec_ and returns the result, **** **** 1 for true, and 0 for false. **** *****************************************************************************/ #pragma warn -pia public BOOL FAR PASCAL atree_eval(tree,vec) LPATREE tree; LPBIT_VEC vec; { register bool_t result; switch (tree -> c_tag) { case AND: tree -> n_sig_right = UNEVALUATED; result = (tree -> n_sig_left = atree_eval(tree -> n_child[LEFT_CHILD], vec)) && (tree -> n_sig_right = atree_eval(tree -> n_child[RIGHT_CHILD], vec)); break; case RIGHT: tree -> n_sig_left = UNEVALUATED; result = (tree -> n_sig_right = atree_eval(tree -> n_child[RIGHT_CHILD], vec)); break; case LEFT: tree -> n_sig_right = UNEVALUATED; result = (tree -> n_sig_left = atree_eval(tree -> n_child[LEFT_CHILD], vec)); break; case OR: tree -> n_sig_right = UNEVALUATED; result = (tree -> n_sig_left = atree_eval(tree -> n_child[LEFT_CHILD], vec)) || (tree -> n_sig_right = atree_eval(tree -> n_child[RIGHT_CHILD], vec)); break; case LEAF: result = bv_extract((int) tree -> l_bit_no, vec) != tree -> l_comp; break; } return(result); } #pragma warn .pia /***************************************************************************** **** **** **** BOOL atree_train(tree,tset,correct_result,bit_col,tset_size, **** **** no_correct,epochs,verbosity) **** **** **** **** LPATREE tree; **** **** LPBIT_VEC tset; **** **** LPBIT_VEC correct_result; **** **** int bit_col; **** **** int tset_size; **** **** int no_correct; **** **** int epochs; **** **** int verbosity; **** **** **** **** Synopsis: **** **** **** **** This routine is the heart of the library. It takes an atree _tree_ **** **** to be trained, an array of input vectors _tset_, an array of **** **** vectors, _correct_result_ where each bit column holds a correct bit **** **** result for each vector in _tset_. [Note: Only a single vector is **** **** actually required here, but doing it this way make life convenient **** **** for training collections of trees for real numbers] An integer **** **** _bit_col_ denoting the column to be trained on. Another integer **** **** _test_size gives the size of both the _tset_ and _correct_result_ **** **** arrays. **** **** **** **** The _tree_ is trained until the number of vectors presented in **** **** _tset_ equals _epoch_ epochs, or the last presentation of the number**** **** in an epoch had at least _no_correct_ presentations. **** **** The _verbosity_ is currently 0 or 1. **** **** The routine returns TRUE if it stopped because it succeeded **** **** _no_correct_ times. **** **** **** *****************************************************************************/ public BOOL FAR PASCAL atree_train(tree,tset,correct_result,bit_col,tset_size,no_correct, epochs,verbosity) LPATREE tree; LPBIT_VEC tset; LPBIT_VEC correct_result; int bit_col; int tset_size; int no_correct; int epochs; int verbosity; { bool_t no_correct_flag = FALSE; LPINT vec_list; int i; int j; int cor_this_epoch; int vec_num; LPBIT_VEC vec; char szBuff1[60]; char szBuff2[60]; /* For the specified number of epochs */ VERBOSE(1, lstrcpy(szVerbLine1, "Beginning Training..."); lstrcpy(szVerbLine2, " "); lstrcpy(szVerbLine3, " "); ShowWindow(hwnd, SW_SHOW); UpdateWindow(hwnd) ); vec_list = (LPINT) Malloc((unsigned) sizeof(int) * tset_size); MEMCHECK(vec_list); for (i = 0; i < tset_size; i++) { vec_list[i] = i; } for (i = 0; i < epochs; i++) { cor_this_epoch = 0; VERBOSE(1,wsprintf(szBuff1,"Epoch : %d ",i)); /* Shuffle */ for (j = 0; j < tset_size; j++) { int a; int b; int tmp; a = RANDOM(tset_size); do { b = RANDOM(tset_size); } while (a == b); tmp = vec_list[a]; vec_list[a] = vec_list[b]; vec_list[b] = tmp; } /* For the elements of the test set */ for (j = 0; j < tset_size; j++) { if (atree_quit_flag) return(FALSE); /* check if exit requested */ /* Pick a random vector */ vec_num = vec_list[j]; vec = tset + vec_num; /* allow for multitasking */ Windows_Interrupt(1000); /* Train the tree */ if (train(tree,vec,(bool_t)bv_extract(bit_col,correct_result + vec_num))) { /* The tree succeeded */ cor_this_epoch++; if (cor_this_epoch == no_correct) { no_correct_flag = TRUE; break; /* out of this epoch */ } /* if (cor_this...) */ } /* if (train..) */ } /* for (j = ..) */ VERBOSE(1,wsprintf(szBuff2,"Estimated number correct was %d ",cor_this_epoch)); /* If no_correct_flag is TRUE here, its time to stop */ if (no_correct_flag || (i == epochs - 1)) { int correct = 0; for (j = 0; j < tset_size; j++) { if (atree_eval(tree, tset + j) == bv_extract(bit_col, correct_result + j)) { correct++; } } VERBOSE(1,wsprintf(szVerbLine3,"Actual number correct was %d ",correct); lstrcpy(szVerbLine1, szBuff1); lstrcpy(szVerbLine2, szBuff2); ScrollWindow(hwnd, 0, -3 * cyChar, NULL, NULL); InvalidateRect(hwnd, NULL, FALSE); UpdateWindow(hwnd)); if (correct >= no_correct) { break; /* out of the epoch loop */ } } else { VERBOSE(1,lstrcpy(szVerbLine3," "); lstrcpy(szVerbLine1, szBuff1); lstrcpy(szVerbLine2, szBuff2); ScrollWindow(hwnd, 0, -3 * cyChar, NULL, NULL); InvalidateRect(hwnd, NULL, FALSE); UpdateWindow(hwnd)); } } /* for (i = ...) */ Free(vec_list); VERBOSE(1, ShowWindow(hwnd,SW_HIDE)); return(no_correct_flag); } /***************************************************************************** **** **** **** (void) atree_print(tree,verbosity) **** **** **** **** LPATREE tree; **** **** **** **** Synopsis: **** **** **** **** Prints out a tree for diagnostic and explanation purposes, the **** **** verbosity levels are 0 or above. Currently, the Windows **** **** implementation outputs to a file called atree.out in the current **** **** directory. **** *****************************************************************************/ public void FAR PASCAL atree_print(tree,verbosity) LPATREE tree; int verbosity; { /* * This routine makes an call to the private * print tree routine that takes an extra paramater * controlling the indentation */ int hOut; /* File Handle */ if((hOut = _lcreat("atree.out", 0)) == -1) { MessageBox(NULL, "Cannot open ATREE.OUT", "atree_print", MB_OK); return; } print_tree(tree,0,verbosity, hOut); _lclose(hOut); } /***************************************************************************** **** **** **** void atree_free(tree) **** **** **** **** LPATREE tree; **** **** **** **** Synopsis: **** **** **** **** returns the memory used by _tree_ to the freelists **** *****************************************************************************/ public void FAR PASCAL atree_free(tree) LPATREE tree; { if (tree -> c_tag != LEAF) { atree_free(tree -> n_child[LEFT_CHILD]); atree_free(tree -> n_child[RIGHT_CHILD]); } reclaim_node(tree); } /***************************************************************************** * function: atree_fold * * This function removes all LEFT and RIGHT nodes from _tree_ * and returns a pointer to the resulting tree. ******************************************************************************/ public LPATREE FAR PASCAL atree_fold(tree) LPATREE tree; { LPATREE folded_tree; int keep; switch (tree -> c_tag) { case LEAF: folded_tree = tree; break; case OR: case AND: tree -> n_child[LEFT_CHILD] = atree_fold(tree -> n_child[LEFT_CHILD]); tree -> n_child[RIGHT_CHILD] = atree_fold(tree -> n_child[RIGHT_CHILD]); folded_tree = tree; break; case LEFT: case RIGHT: keep = (tree -> c_tag == LEFT) ? LEFT_CHILD : RIGHT_CHILD; folded_tree = atree_fold(tree -> n_child[keep]); atree_free(tree -> n_child[!keep]); reclaim_node(tree); break; default: assert(0); } return(folded_tree); } /****************************************************************************** * function: atree_compress * * This function converts an atree to a fast_tree. * See the commentary for the private function * compress_tree for more information. ******************************************************************************/ public LPFAST_TREE FAR PASCAL atree_compress(tree) LPATREE tree; { LPFAST_TREE ftree; int leaf_num; int leaf_count = count_leaves(tree, TRUE); ftree = (LPFAST_TREE) Malloc((unsigned) (leaf_count + 1) * sizeof(fast_tree)); MEMCHECK(ftree); ftree[leaf_count].bit_no = -1; /* mark end */ leaf_num = leaf_count - 1; compress_tree(tree, NULL, NULL, ftree, (LPINT) &leaf_num); return(ftree); } /****************************************************************************** * function: atree_fast_eval * * This function is the fast_tree equivalent of atree_eval. ******************************************************************************/ public int FAR PASCAL atree_fast_eval(tree, vec) LPFAST_TREE tree; LPBIT_VEC vec; { register int result; do { result = bv_extract(tree -> bit_no, vec) != tree -> comp; } while ((tree = tree -> next[result]) != NULL); return(result); } /****************************************************************************** * function atree_fast_print : outputs to file called fasttree.out ******************************************************************************/ public void FAR PASCAL atree_fast_print(ftree) LPFAST_TREE ftree; { int i; int hOut; /* File Handle */ char szBuffer[80]; if((hOut = _lcreat("fasttree.out", 0)) == -1) { MessageBox(NULL, "Cannot open FASTTREE.OUT", "atree_fast_print", MB_OK); return; } for (i = 0; ftree[i].bit_no >= 0; i++) { wsprintf((LPSTR)szBuffer,"[%3d] bit=%c%d, next[0]=%d, next[1]=%d\r\n", i, ftree[i].comp ? '!' : '\0', ftree[i].bit_no, ftree[i].next[0] ? ftree[i].next[0] - ftree : -1, ftree[i].next[1] ? ftree[i].next[1] - ftree : -1); _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer)); } _lclose(hOut); } /****************************************************************************** * function: atree_set_code * * This is the constructor for type code_t. * Returns non-zero on failure. ******************************************************************************/ public int FAR PASCAL atree_set_code(code, low, high, count, width, dist) LPCODE_T code; double low; double high; int count; int width; int dist; { int error = FALSE; static LPBIT_VEC zero_vec = NULL; static LPBIT_VEC one_vec = NULL; assert(low < high); assert(count > 1); assert(width > 0); assert(dist > 0); code -> width = width; code -> low = low; code -> high = high; if (width == 1) /* boolean */ { code -> vector = (LPBIT_VEC) Malloc((unsigned) sizeof(bit_vec) * 2); MEMCHECK(code -> vector); if (zero_vec == NULL) { zero_vec = bv_create(1); one_vec = bv_create(1); bv_set(0, zero_vec, 0); bv_set(0, one_vec, 1); } code -> vector[0] = *zero_vec; code -> vector[1] = *one_vec; code -> vector_count = 2; code -> step = high - low; } else { if ((code -> vector = atree_rand_walk(count, width, dist)) == NULL) { error = TRUE; } code -> vector_count = count; code -> step = (high - low) / (count -1); } return(error); } /****************************************************************************** * atree_encode: * * returns the quantization level corresponding to the floating point * value _x_. To get the bit vector, use the expression: * * code -> vector + atree_encode(x, code) ******************************************************************************/ public int FAR PASCAL atree_encode(x, code) double x; LPCODE_T code; { int index; char szBuffer[80]; if (code -> width == 1) { index = x > (code -> low + code -> high) / 2; } else if (x < code -> low) { Printf("warning: argument out of range: %g\n", x); MessageBox(NULL,szBuffer,"atree_encode",MB_OK | MB_ICONEXCLAMATION); index = 0; } else if (x > code -> high) { Printf("warning: argument out of range: %g\n", x); MessageBox(NULL,szBuffer,"atree_encode",MB_OK | MB_ICONEXCLAMATION); index = code -> vector_count - 1; } else if (x == code -> high) { index = code -> vector_count - 1; } else { double temp = (x - code->low) / code->step; index = (int)(temp); } return(index); } /****************************************************************************** * atree_decode: * * returns the quantization level corresponding to the bit vector * _vec_. To get the corresponding floating point value, use the * expression: * * code -> low + code -> step * atree_decode(vec, code) ******************************************************************************/ public int FAR PASCAL atree_decode(vec, code) LPBIT_VEC vec; LPCODE_T code; { int closest = 0; if (code->width == 1) /*boolean*/ { closest = bv_extract(0, vec); } else { int i; int diff; int closest_bit_diff = code -> width; for (i = 0; i < code -> vector_count; i++) { if ((diff = bv_diff(vec, code -> vector + i)) < closest_bit_diff) { closest_bit_diff = diff; closest = i; } } } return(closest); } /****************************************************************************** * atree I/O routines. ******************************************************************************/ public int FAR PASCAL atree_store(tree, filename) LPATREE tree; LPSTR filename; { FILE *fp; PSTR fname; char szBuffer[60]; lstrcpy((LPSTR)fname, filename); if ((fp = (FILE *) fopen(fname, "w")) == NULL) { Printf("Unable to open %s", fname); MessageBox(NULL,szBuffer,"atree_store",MB_OK | MB_ICONEXCLAMATION); return(-1); } atree_write(fp, tree); fclose(fp); return(0); } public LPATREE FAR PASCAL atree_load(filename) LPSTR filename; { FILE *fp; LPATREE tree; PSTR fname; char szBuffer[60]; lstrcpy((LPSTR)fname, filename); if ((fp = (FILE *) fopen(fname, "r")) == NULL) { Printf("Unable to open %s", fname); MessageBox(NULL,szBuffer,"atree_store",MB_OK | MB_ICONEXCLAMATION); return(NULL); } tree = atree_read(fp); fclose(fp); return(tree); } /****************************************************************************** * function: atree_write * * Stores a single _tree_ onto _stream_. * returns 0 for success, 1 on failure. ******************************************************************************/ public int FAR PASCAL atree_write(stream, tree) FILE *stream; LPATREE tree; { return store_tree(tree, stream) || fprintf(stream, ";\n") == EOF; } /****************************************************************************** * function: atree_read * * Reads tree stored in postfix notation. Valid symbols are: * '&', '|', 'L', 'R' (AND, OR, LEFT, and RIGHT respectively), * and numerals (representing bit numbers) optionally preceded * by a '!' for negation. Returns NULL if any error or EOF is * encountered. A file may store multiple trees, each tree is * separated by a ';'. ******************************************************************************/ public LPATREE FAR PASCAL atree_read(stream) FILE *stream; { token_t t; LPATREE node = NULL; int error = 0; char szBuffer[80]; LPATREE stack[STACKSIZE]; int top = 0; #define ITEMS top #define PUSH(node) stack[top++] = (node) #define POP stack[--top] while ((error = get_token(stream, (token_t far *)&t)) == 0) { if (t.token == EOF || t.token == ';') { break; } if (t.token == LEAF_TOKEN) { node = get_node(LEAF); node -> l_bit_no = t.bit_no; node -> l_comp = t.complemented; } else if (ITEMS < 2) { wsprintf(szBuffer,"too few arguments for %c, offset %ld\n", t.token, ftell(stream)); MessageBox(NULL,szBuffer,"atree_read",MB_OK | MB_ICONEXCLAMATION); error++; break; } else { node = get_node(!LEAF); node -> n_cnt_left = (t.token == '|' || t.token == 'L') ? MAXSET : MINSET; node -> n_cnt_right = (t.token == '|' || t.token == 'R') ? MAXSET : MINSET; node -> c_tag = node_function(node); node -> n_sig_left = UNEVALUATED; node -> n_sig_right = UNEVALUATED; node -> n_child[RIGHT_CHILD] = POP; node -> n_child[LEFT_CHILD] = POP; } if (ITEMS >= STACKSIZE) { wsprintf(szBuffer, "atree_read: stack overflow\n"); MessageBox(NULL,szBuffer,"atree_read",MB_OK | MB_ICONEXCLAMATION); error++; break; } else { PUSH(node); } } /* while */ if (!error && ITEMS != 1) { if (t.token == EOF) { wsprintf(szBuffer, "unexpected EOF\n"); } else { wsprintf(szBuffer, "unexpected ';', offset %ld\n", ftell(stream)); } MessageBox(NULL,szBuffer,"atree_read",MB_OK | MB_ICONEXCLAMATION); error++; } return(error ? NULL : node); #undef ITEMS #undef PUSH #undef POP } /* * code I/O routines */ /****************************************************************************** * function: atree_write_code * * writes _code_ onto _stream_. * returns 0 for success, 1 on failure. ******************************************************************************/ public int FAR PASCAL atree_write_code(stream, code) FILE *stream; LPCODE_T code; { int i; int error; error = fprintf(stream, CODING_HEADER_FORMAT, code -> vector_count, code -> width, code -> low, code -> high) == EOF; if (!error && code -> width > 1) { for (i = 0; i < code -> vector_count; i++) { if ((bv_print(stream, code -> vector + i)) || (fprintf(stream, "\n") == 0)) { error = TRUE; break; } } } return(error); } public LPCODE_T FAR PASCAL atree_read_code(stream, code) FILE *stream; LPCODE_T code; { char *buf; char *p; int i; int error = 0; char szBuffer[80]; int count, width; float high, low; if (fscanf(stream, CODING_HEADER_FORMAT, &count, &width, &low, &high) != CODING_HEADER_ITEMS) { wsprintf(szBuffer, "bad header, offset %ld\n", ftell(stream)); MessageBox(NULL, szBuffer, "atree_read_code", MB_OK | MB_ICONEXCLAMATION); return(NULL); } else if (count < 2) { wsprintf(szBuffer, "vector count too low, offset %ld\n", ftell(stream)); MessageBox(NULL, szBuffer, "atree_read_code", MB_OK | MB_ICONEXCLAMATION); return(NULL); } else if (high <= low) { wsprintf(szBuffer, "bad range, offset %ld\n", ftell(stream)); MessageBox(NULL, szBuffer, "atree_read_code", MB_OK | MB_ICONEXCLAMATION); return(NULL); } else if (width < 1) { wsprintf(szBuffer, "width must be at least 1, offset %ld\n", ftell(stream)); MessageBox(NULL, szBuffer, "atree_read_code", MB_OK | MB_ICONEXCLAMATION); return(NULL); } code -> vector_count = count; code -> width = width; code -> low = low; code -> high = high; if (code -> width == 1) /* boolean */ { atree_set_code(code, 0.0, /* low */ 1.0, /* high */ 2, /* count */ 1, /* width */ 1); /* distance */ } else { code -> step = (code->high - code->low ) / (code -> vector_count - 1); code -> vector = (LPBIT_VEC) Malloc((unsigned) sizeof(bit_vec) * code -> vector_count); MEMCHECK(code -> vector); buf = (char *) malloc((unsigned) code -> width + 2); /* room for \n and \0 */ MEMCHECK(buf); for (i = 0; i < code -> vector_count; i++) { if (fgets(buf, code -> width + 2, stream) == NULL) { wsprintf(szBuffer,"read error on offset %ld\n", ftell(stream)); MessageBox(NULL, szBuffer, "atree_read_code", MB_OK | MB_ICONEXCLAMATION); error++; break; } if (strlen(buf) != code -> width + 1 || buf[code -> width] != '\n') { wsprintf(szBuffer,"inconsistent vector length, offset %ld\n", ftell(stream)); MessageBox(NULL, szBuffer, "atree_read_code", MB_OK | MB_ICONEXCLAMATION); error++; break; } else { buf[code -> width] = '\0'; /* remove \n */ } if (strspn(buf, "01") != code -> width) { wsprintf(szBuffer,"garbage at offset %ld\n",ftell(stream)); MessageBox(NULL, szBuffer, "atree_read_code", MB_OK | MB_ICONEXCLAMATION); error++; break; } /* * prepare the vector for packing */ for (p = buf; *p; p++) { *p -= '0'; } code -> vector[i] = *(bv_pack(buf, code -> width)); } (void) free(buf); if (error) { (void) Free(code -> vector); code = NULL; } } return(code); } /***************************************************************************** **** **** **** LPBIT_VEC bv_create(length) **** **** **** **** int length; **** **** **** **** Synopsis: **** **** **** **** Produces a vector of _length_ bits, each one of which has been set **** **** to 0 **** *****************************************************************************/ public LPBIT_VEC FAR PASCAL bv_create(length) int length; { int i; LPBIT_VEC out_vec; assert(length > 0); out_vec = (LPBIT_VEC) Malloc((unsigned)sizeof(bit_vec)); MEMCHECK(out_vec); out_vec -> len = length; out_vec -> bv = Malloc((unsigned) (length + BYTE - 1) / BYTE); MEMCHECK(out_vec -> bv); for (i = 0; i < (length + BYTE - 1) / BYTE; i++) { *((out_vec -> bv) + i) = (char) 0; } return(out_vec); } /***************************************************************************** **** **** **** LPBIT_VEC bv_pack(unpacked,length) **** **** **** **** LPSTR unpacked; **** **** int length; **** **** **** **** This routine takes an array _arr_ of zero and one characters **** **** and returns a packed bit vector suitable for use with the other **** **** routines in this library. **** *****************************************************************************/ public LPBIT_VEC FAR PASCAL bv_pack(unpacked,length) LPSTR unpacked; int length; { LPBIT_VEC out_vec; LPSTR out_ptr; int i; int j; int bitptr; /* Create the structure */ out_vec = (LPBIT_VEC) Malloc((unsigned)sizeof(bit_vec)); MEMCHECK(out_vec); out_vec -> len = length; out_vec -> bv = Malloc((unsigned) (length + BYTE - 1) / BYTE); MEMCHECK(out_vec -> bv); /* Pack the vector */ out_ptr = out_vec -> bv; bitptr = 0; for (i = 0; i < (length + BYTE - 1) / BYTE; i++) { *out_ptr = 0; for (j = 0; j < BYTE; j++) { if (bitptr < length) { *out_ptr |= (unpacked[bitptr] << j); bitptr++; } else { break; } } out_ptr++; } /* Return the vector */ return(out_vec); } /***************************************************************************** **** **** **** int bv_diff(v1,v2) **** **** **** **** LPBIT_VEC v1; **** **** LPBIT_VEC v2; **** **** **** **** This function returns the number of bits that are unequal in the **** **** two vectors. They must be the same number of bits in each vector **** *****************************************************************************/ public int FAR PASCAL bv_diff(v1,v2) LPBIT_VEC v1; LPBIT_VEC v2; { int diff = 0; int i; assert (v1 -> len == v2 -> len); for (i = 0; i < v1 -> len; i++) { if (bv_extract(i,v1) != bv_extract(i,v2)) { diff++; } } return(diff); } /***************************************************************************** **** **** **** LPBIT_VEC bv_concat(n,vectors) **** **** **** **** int n; **** **** LPBIT_VEC *vectors; **** **** **** **** Synopsis: **** **** **** **** Returns the bit vector which is the string concatenation of each **** **** bit vector in _vector_; _n_ is the number of elements in _vector_. **** *****************************************************************************/ public LPBIT_VEC FAR PASCAL bv_concat(n,vector) int n; LPBIT_VEC FAR *vector; { int size; LPBIT_VEC out_vec; LPSTR str; int i; int j; int count; /* Work out how big the new vector will be */ size = 0; for (i = 0; i < n; i++) { size += vector[i] -> len; } /* Unpack the input vectors */ str = Malloc((unsigned) size); MEMCHECK(str); count = 0; for (i = 0; i < n; i++) { for (j = 0; j < vector[i] -> len; j++) { str[count] = bv_extract(j,vector[i]); count++; } } out_vec = bv_pack(str,size); Free(str); return(out_vec); } /***************************************************************************** **** **** **** LPBIT_VEC bv_copy(vector) **** **** **** **** LPBIT_VEC vector; **** **** **** **** Synopsis: **** **** **** **** Returns a copy of the bit vector _vector_. **** *****************************************************************************/ public LPBIT_VEC FAR PASCAL bv_copy(vector) LPBIT_VEC vector; { LPBIT_VEC out_vec; int i; /* Work out how big the new vector will be */ out_vec = (LPBIT_VEC) Malloc((unsigned) sizeof(bit_vec)); MEMCHECK(out_vec); out_vec -> len = vector -> len; out_vec -> bv = Malloc((unsigned) (vector -> len + BYTE - 1) / BYTE); MEMCHECK(out_vec -> bv); for (i = 0; i < (vector -> len + BYTE - 1) / BYTE; i++) { out_vec -> bv[i] = vector -> bv[i]; } return(out_vec); } /***************************************************************************** **** **** **** void bv_set(n,vec,bit) **** **** **** **** int n; **** **** LPBIT_VEC vec; **** **** BOOL bit; **** **** **** **** Synopsis: **** **** **** **** Sets bit _n_ in _vec_ to have the value in _bit_. **** *****************************************************************************/ public void FAR PASCAL bv_set(n,vec,bit) int n; LPBIT_VEC vec; BOOL bit; { char mask; LPSTR b; assert(n < vec -> len); mask = 0x1; b = (vec -> bv) + ((int) (n / BYTE)); if (bit) { *b |= (mask << (n % BYTE)); } else { *b &= ~(mask << (n % BYTE)); } } /***************************************************************************** **** **** **** BOOL bv_extract(n,vec) **** **** **** **** int n; **** **** LPBIT_VEC vec; **** **** **** **** Synopsis: **** **** **** **** Returns the _n_th bit of _vec_. **** *****************************************************************************/ public BOOL FAR PASCAL bv_extract(n,vec) int n; LPBIT_VEC vec; { register int mask = 0x1; assert(n < vec -> len); return(((*((vec -> bv) + ((int) (n / BYTE)))) & (mask << (n % BYTE))) != 0); } /***************************************************************************** **** **** **** int bv_print(stream, vector) **** **** **** **** FILE *stream; **** **** LPBIT_VEC vector; **** **** **** **** Synopsis: **** **** **** **** Prints out _vector_ in binary, MSB is the rightmost. **** *****************************************************************************/ public int FAR PASCAL bv_print(stream, vector) FILE *stream; LPBIT_VEC vector; { LPSTR ptr; /* Points to the current char */ char mask; int bits; /* Counts the number of bits output */ int i; bits = 0; for (ptr = (vector -> bv); bits < vector -> len; ptr++) { mask = 0x1; for (i = 0; i < BYTE; i++) { if (fprintf(stream, (*ptr & mask) ? "1" : "0") == EOF) { return (1); } bits++; if (bits == vector -> len) { break; } mask <<= 1; } } return(0); } /***************************************************************************** **** **** **** void bv_free(vector) **** **** **** **** LPBIT_VEC vector; **** **** **** **** Synopsis: **** **** **** **** Frees the memory used by _vector_ **** *****************************************************************************/ public void FAR PASCAL bv_free(vector) LPBIT_VEC vector; { Free(vector -> bv); Free(vector); } /***************************************************************************** **** **** **** BOOL bv_equal(v1,v2) **** **** **** **** LPBIT_VEC v1; **** **** LPBIT_VEC v2; **** **** **** **** Synopsis: **** **** **** **** Returns TRUE if each bit in v1 and v2 have the same value in the **** **** same position. It returns FALSE otherwise. **** *****************************************************************************/ public BOOL FAR PASCAL bv_equal(v1,v2) LPBIT_VEC v1; LPBIT_VEC v2; { bool_t eq; int i; eq = TRUE; if (v1 -> len != v2 -> len) { eq = FALSE; } else { for (i = 0; i < (v1 -> len + BYTE - 1) / BYTE; i++) { if (v1 -> bv[i] != v2 -> bv[i]) { eq = FALSE; break; } } } return(eq); } /***************************************************************************** **** **** **** void FAR PASCAL Windows_Interrupt(cElapsed) **** **** **** **** DWORD cElapsed **** **** **** **** Synopsis: **** **** **** **** Allows Windows to access other applications that may be running **** **** A call to PeekMessage accomplishes this, and we process all calling **** **** window messages. Will only call PeekMessage if _cElapsed_ time **** **** has passed since the last call to Windows_Interrupt. **** **** **** *****************************************************************************/ public void FAR PASCAL Windows_Interrupt(cElapsed) DWORD cElapsed; { static cTick = 0; /* number of ticks since first called */ MSG msg; /* Windows message structure */ if ((GetTickCount() - cTick) > cElapsed) { if (PeekMessage(&msg, NULL, 0, 0, PM_REMOVE)) { TranslateMessage(&msg); DispatchMessage(&msg); } cTick = GetTickCount(); } } /***************************************************************************** **** **** **** LPSTR FAR PASCAL WinMem_Malloc(wFlags, wBytes) **** **** **** **** WORD wFlags **** **** WORD wBytes **** **** **** **** Synopsis: **** **** **** **** Allocates _wBytes_ bytes of memory in a dynamically allocated **** **** segment. _wBytes_ cannot be greater than SEGLENGTH. wFlags can be **** **** any of the local memory allocation flags defined in the Windows **** **** Programmer's Reference, usually LMEM_MOVEABLE. **** **** Returns a valid pointer if successful, NULL if not. **** **** **** **** **** *****************************************************************************/ public LPSTR FAR PASCAL WinMem_Malloc(WORD wFlags, WORD wBytes) { int offset; int i,j; BOOL found; HANDLE hmem; LPSTR lp; PSTR p; LONG lSize; WORD wSeg; static BOOL bFirst = TRUE; if (bFirst) { bFirst = FALSE; WinMem_Init(); } if ((long)wBytes > (SEGLENGTH - 16)) return(NULL); for (i = 0; i < NUMSEGS; i++) { if (seg[i] == NULL) { /**** Get global segment, initialize local heap ****/ hmem = GlobalAlloc(GMEM_MOVEABLE, SEGLENGTH); if (!hmem) return(NULL); lp = GlobalWire(hmem); wSeg = HIWORD(lp); seg[i] = hmem; lSize = GlobalSize(hmem) - 16; /* * reserve 16 bytes for local * heap initialization */ if (lSize > (SEGLENGTH - 16)) lSize = SEGLENGTH - 16; if (!LocalInit(wSeg,0,lSize)) return(NULL); freemem[i] = (WORD) lSize; GlobalUnlock(hmem); /* from LocalInit */ GlobalUnWire(hmem); } if (freemem[i] > wBytes) { lp = GlobalWire(seg[i]); if (!lp) return(NULL); wSeg = HIWORD(lp); asm { push ds mov ax, wSeg mov ds, ax } hmem = LocalAlloc(wFlags, wBytes); asm { pop ds } GlobalUnWire(seg[i]); if (hmem) { j = i; break; } } } if (!hmem) return(NULL); lp = GlobalWire (seg[j]); /* * move to low memory, will be * unwired in WinMem_Free */ if (!lp) return(NULL); wSeg = HIWORD(lp); asm { push ds mov ax, wSeg mov ds, ax } i = LocalSize(hmem); p = LocalLock (hmem); asm { pop ds } freemem[j] -= i; if (!p) return(NULL); else return (LPSTR)MAKELONG (p, wSeg); } /***************************************************************************** **** **** **** LPSTR FAR PASCAL WinMem_Free(lpfree) **** **** **** **** LPSTR lpfree **** **** **** **** Synopsis: **** **** **** **** Frees the block of memory in a dynamically allocated segment **** **** pointed to by _lpFree_. **** **** Returns NULL if successful, lpfree if not **** **** **** **** **** *****************************************************************************/ public LPSTR FAR PASCAL WinMem_Free(LPSTR lpfree) { HANDLE hmem, hseg; LPSTR lp; WORD wSeg; int i,j; wSeg = HIWORD(lpfree); hseg = GlobalHandle(wSeg); j = -1; for (i = 0; i < NUMSEGS; i++) { if (seg[i] == hseg) { j = i; break; } } if (j == -1) return(lpfree); lp = GlobalWire(hseg); if (!lp) goto FAIL; asm { push ds mov ax, wSeg mov ds, ax } hmem = LocalHandle(LOWORD(lpfree)); if (!hmem) { asm { pop ds } goto FAIL; } i = LocalSize(hmem); if (!LocalUnlock (hmem)) { hmem = LocalFree(hmem); /*returns NULL if successful*/ if (hmem) { asm { pop ds } goto FAIL; } } else { asm { pop ds } goto FAIL; } asm { pop ds } freemem[j] += i; GlobalUnWire(hseg); if ((GlobalUnWire(hseg)) && (freemem[j] == (SEGLENGTH - 16))) /* TRUE if lock count at 0 */ { GlobalFree(hseg); seg[j] = NULL; freemem[j] = 0; } return(NULL); FAIL: return(lpfree); } /***************************************************************************** ***************************************************************************** **** **** **** Private Routines **** **** **** ***************************************************************************** *****************************************************************************/ /* * void FAR PASCAL WinMem_Init() * * internal routine to initialize memory manager * called automatically as needed */ private void NEAR PASCAL WinMem_Init() { int i; for (i = 0; i < NUMSEGS; i++) { seg[i] = NULL; freemem[i] = 0; } } /* * Free list management routines. */ static LPATREE_LEAF free_leaf_list = NULL; static LPATREE_NODE free_node_list = NULL; #define get_free_list(type, free_list) { \ int i; \ type far *ptr = (type far *) Malloc(sizeof(type) * NEWMALLOC); \ MEMCHECK(ptr); \ for (i = 0; i < NEWMALLOC - 1; i++) \ ptr[i].next = &ptr[i + 1]; \ ptr[NEWMALLOC - 1].next = free_list; \ free_list = ptr; \ } private LPATREE NEAR PASCAL get_node(tag) int tag; { LPATREE node; if (tag == LEAF) { /* * add to free_leaf_list if necessary. */ if (free_leaf_list == NULL) { get_free_list(atree_leaf, free_leaf_list); } node = (LPATREE) free_leaf_list; free_leaf_list = free_leaf_list -> next; } else { /* * add to free_node_list if necessary. */ if (free_node_list == NULL) { get_free_list(atree_node, free_node_list); } node = (LPATREE) free_node_list; free_node_list = free_node_list -> next; } node -> c_tag = tag; return(node); } #undef get_free_list /* * function reclaim_node() * * returns a node to its appropriate free_list */ private void NEAR PASCAL reclaim_node(tree) LPATREE tree; { if (tree -> c_tag == LEAF) { tree -> leaf.next = free_leaf_list; free_leaf_list = (LPATREE_LEAF) tree; } else { tree -> node.next = free_node_list; free_node_list = (LPATREE_NODE) tree; } } /* * This routine recursively creates a random tree in the previously allocated * space starting at _tree_. It returns a pointer giving the next available * space for other calls. */ private LPATREE NEAR PASCAL build_tree(connection,complemented,start,end) LPINT connection; bool_t far *complemented; int start; int end; { LPATREE node; int mid; /* Are we at a leaf? */ if (start == end) { node = get_node(LEAF); node -> l_comp = complemented[start]; node -> l_bit_no = connection[start]; } else { /* This is a node. */ node = get_node(AND); node -> c_tag = RANDOM(4); node -> n_cnt_left = (node -> c_tag == LEFT || node -> c_tag == OR) ? ABOVEMID : BELOWMID; node -> n_cnt_right = (node -> c_tag == RIGHT || node -> c_tag == OR) ? ABOVEMID : BELOWMID; /* clear the signals */ node -> n_sig_right = UNEVALUATED; node -> n_sig_left = UNEVALUATED; /* Create descendants */ mid = start + ((end - start)/2); node -> n_child[LEFT_CHILD] = build_tree(connection, complemented, start, mid); node -> n_child[RIGHT_CHILD] = build_tree(connection, complemented, mid+1, end); } return(node); } /* * print_tree routine prints out an atree to the * file pointed to by _fp_ */ private void NEAR PASCAL print_tree(tree,indent,verbosity,hOut) LPATREE tree; int indent; int verbosity; int hOut; { int i; char szBuffer[80]; if (tree -> c_tag != LEAF) { print_tree(tree -> n_child[RIGHT_CHILD], indent + 3, verbosity, hOut); } for (i = 0; i < indent; i++) { Printf(" ",0); _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer)); } switch (tree -> c_tag) { case AND: Printf("AND\r\n",0); _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer)); break; case LEFT: Printf("LEFT\r\n",0); _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer)); break; case RIGHT: Printf("RIGHT\r\n",0); _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer)); break; case OR: Printf("OR\r\n",0); _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer)); break; case LEAF: wsprintf(szBuffer,"%cLEAF : %d\r\n", tree -> l_comp ? '~' : '\0', tree -> l_bit_no); _lwrite(hOut, (LPSTR) szBuffer, lstrlen((LPSTR) szBuffer)); break; } if (tree -> c_tag != LEAF) { print_tree(tree -> n_child[LEFT_CHILD], indent + 3, verbosity, hOut); } } /* * bool_t train(tree,vec,result) * * LPATREE tree; * LPBITVEC vec; * bool result; * * This routine is actually responsible for the training of a tree for a * single input vector and result. If the tree gets the correct result * before the adaptation step occurs, the routine returns TRUE, otherwise, * false. */ private bool_t NEAR PASCAL train(tree,vec,desired) LPATREE tree; LPBIT_VEC vec; bool_t desired; { bool_t correct; /* Adapt the tree */ correct = (bool_t)atree_eval(tree,vec) == desired; adapt(tree,vec,desired); /* What does the tree currently think ?*/ correct = (bool_t)atree_eval(tree,vec) == desired; if (!correct) { adapt(tree,vec,desired); } return(correct); } /* * adapt(tree,vec,result) * * LPATREE tree; * LPBIT_VEC vec; * bool result; * */ private void NEAR PASCAL adapt(tree,vec,desired) LPATREE tree; LPBIT_VEC vec; bool_t desired; { register int lres; register int rres; register int funct; /* * INCR and DECR implement bounded counters, remembering that TRUE == 1, * how much should be added to t when t == MAXSET ? */ #define INCR(t) t += (t != MAXSET) #define DECR(t) t -= (t != MINSET) funct = tree -> c_tag; if (funct != LEAF) { /* If the left child is unevaluated, evaluate it */ if ((lres = tree -> n_sig_left) == UNEVALUATED) { lres = atree_eval(tree -> n_child[LEFT_CHILD], vec); tree -> n_sig_left = lres; } /* If the right child is unevaluated, evaluate it */ if ((rres = tree -> n_sig_right) == UNEVALUATED) { rres = atree_eval(tree -> n_child[RIGHT_CHILD], vec); tree -> n_sig_right = rres; } /* Update the counters if needed */ if (lres != rres) { if (lres) { (void) (desired ? (INCR(tree -> n_cnt_left)) : (DECR(tree -> n_cnt_left))); } else { (void) (desired ? (INCR(tree -> n_cnt_right)) : (DECR(tree -> n_cnt_right))); } /* has the node function changed? */ tree -> c_tag = node_function(tree); funct = tree -> c_tag; } /* Assign responsibility to the left child */ if (rres != desired || funct != (rres ? OR : AND)) { adapt(tree -> n_child[LEFT_CHILD], vec, desired); } /* Assign responsibility to the right child */ if (lres != desired || funct != (lres ? OR : AND)) { adapt(tree -> n_child[RIGHT_CHILD], vec, desired); } } #undef INCR #undef DECR } private char NEAR PASCAL node_function(tree) LPATREE tree; { int result; if ((tree -> n_cnt_left) >= ABOVEMID) { result = (tree -> n_cnt_right >= ABOVEMID) ? OR : LEFT; } else { result = (tree -> n_cnt_right >= ABOVEMID) ? RIGHT : AND; } return(result); } /* * compress_tree: * Alters the respresentation of an atree into a fast_tree. * A fast_tree is essentially a list of leaves; each leaf in the * list contains two pointers to subsequent leaves to evaluate, * one for each possible result of evaluating the current leaf. * A next pointer of NULL indicates that the evaluation is complete, * and the result of the tree is the result of the current leaf. * * parameters: * 'next_if_0' and 'next_if_1' each hold the location of the * next leaf to evaluate if the value of the current 'node' is * known. Of course, for the root these are NULL. 'leaf_num' is the * current index into 'ftree'; it starts at the last leaf. * * notes: * For non-leaf nodes, we traverse the children in reverse order * because we need to know the first leaf of a node's sibling (this * is the next leaf to evaluate if any children of 'node' produce a * tag value). If we go backwards, we know that this is the last * leaf we visited. */ private void NEAR PASCAL compress_tree(node, next_if_0, next_if_1, ftree, leaf_num) LPATREE node; LPFAST_TREE next_if_0; LPFAST_TREE next_if_1; LPFAST_TREE ftree; LPINT leaf_num; { assert(*leaf_num >= 0); switch (node -> c_tag) { case LEAF: ftree[*leaf_num].next[0] = next_if_0; ftree[*leaf_num].next[1] = next_if_1; ftree[*leaf_num].bit_no = node -> l_bit_no; ftree[*leaf_num].comp = node -> l_comp; (*leaf_num)--; break; case AND: compress_tree(node->n_child[1], next_if_0, next_if_1, ftree, leaf_num); compress_tree(node->n_child[0], next_if_0, &(ftree[*leaf_num + 1]), ftree, leaf_num); break; case OR: compress_tree(node->n_child[1], next_if_0, next_if_1, ftree, leaf_num); compress_tree(node->n_child[0], &(ftree[*leaf_num + 1]), next_if_1, ftree, leaf_num); break; case LEFT: compress_tree(node->n_child[0], next_if_0, next_if_1, ftree, leaf_num); break; case RIGHT: compress_tree(node->n_child[1], next_if_0, next_if_1, ftree, leaf_num); break; default: assert(0); } } private int NEAR PASCAL count_leaves(tree, fold) LPATREE tree; int fold; { if (tree -> c_tag == LEAF) { return 1; } else if (fold && tree -> c_tag == LEFT) { return count_leaves(tree -> n_child[LEFT_CHILD], fold); } else if (fold && tree -> c_tag == RIGHT) { return count_leaves(tree -> n_child[RIGHT_CHILD], fold); } else { return count_leaves(tree -> n_child[LEFT_CHILD], fold) + count_leaves(tree -> n_child[RIGHT_CHILD], fold); } } /* * function: store_tree * * Stores _tree_ onto _stream_ using postfix notation. * Returns non-zero on failure. */ private int NEAR PASCAL store_tree(tree, stream) LPATREE tree; FILE *stream; { int error; if (tree -> c_tag == LEAF) { error = fprintf(stream, "%s%d ", tree -> l_comp ? "!" : "", tree -> l_bit_no) == EOF; } else { error = store_tree(tree -> n_child[LEFT_CHILD], stream) || store_tree(tree -> n_child[RIGHT_CHILD], stream); if (!error) { switch (tree -> c_tag) { case AND: error = fprintf(stream, "&") == EOF; break; case OR: error = fprintf(stream, "|") == EOF; break; case LEFT: error = fprintf(stream, "L") == EOF; break; case RIGHT: error = fprintf(stream, "R") == EOF; break; } } } return(error); } /* * function: get_token * * Reads the next token from _stream_ and returns information about it * in _t_. Returns 0 for success, 1 for failure. */ private int NEAR PASCAL get_token(stream, t) FILE *stream; token_t far *t; { int c; char szBuffer[80]; /* skip white space */ while (isspace(c = getc(stream))) ; t -> complemented = 0; switch (c) { case EOF: case 'L': case 'R': case '&': case '|': case ';': t -> token = c; break; case '!': t -> complemented = 1; /* skip white space */ while (isspace(c = getc(stream))) ; if (!isdigit(c)) { wsprintf(szBuffer,"expecting digit after '!', offset %ld\n", ftell(stream)); MessageBox(NULL, szBuffer, "get_token", MB_OK | MB_ICONEXCLAMATION); return(1); } /* FALLTHRU */ case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': t -> token = LEAF_TOKEN; t -> bit_no = c - '0'; while (isdigit(c = getc(stream))) { t -> bit_no = t -> bit_no * 10 + c - '0'; } (void) ungetc(c, stream); break; default: wsprintf(szBuffer, "unexpected symbol: '%c', offset %ld\n", c, ftell(stream)); MessageBox(NULL, szBuffer, "get_token", MB_OK | MB_ICONEXCLAMATION); return(1); } return(0); }