// Author: Athula Gunawardena // Version 4: np_p1.c 11/02/03 Minimizes the number of shape matrices // Multileaf Collimator Problem // This version uses a global approximation with Nested Partitions // using the heuristic given in p4.c // The promising value of a shape is the possible total beam on time // in the following sequence of shapes // This version uses the unique sub matrix which does not // have zero rows or columns on the boundary and contains all the nonzero // entries of the original input matrix // #include #include #define MAX_ROWS 40 #define MAX_COLS 26 #define MAX_ROW_SHAPES 500 #define MAX_LIMIT 300 #define I_ROWS 40 #define I_COLS 25 #define NP_TABLE_LIMIT 100 #define LEVEL 10 #define MAX_NP_SHAPES 40 #define MAX_SHAPES 10 #define MAX_NO_VALUES 3 #define SHAPE_TABLE_ROWS_USED 1 typedef struct{ int price; int left; int right;} row_shapes; typedef struct{ int value; int price; int volume; int start; int end; int prev_index; int prev_row; int prom_value; int NPbeamtime; int left_index[MAX_ROWS]; int right_index[MAX_ROWS]; int index[MAX_ROWS]; } shapes; #include "heap_NP2.h" void read_file(char* f_name, int INT1[][MAX_COLS], int* n1_rows, int* n1_cols ); void submatrix(int INT1[][MAX_COLS], int n1_rows, int n1_cols, int INT[][MAX_COLS], int* s_row, int* s_col, int* n_rows, int* n_cols ); int nonzero_row(int V[], int* left, int* right, int size); void display_array(int Array[][MAX_COLS], int n_rows, int n_cols); void display_array1(int Array[][MAX_COLS], int n_rows, int n_cols, int s_row, int s_col, int n1_rows, int n1_cols); void display_array2(int Array[][MAX_COLS], int n_rows, int n_cols, int s_row, int s_col); void convert_array(int INT[][MAX_COLS],int n_rows, int n_cols, int C_INT[][MAX_COLS]); void separate_row(int value, int *row, int size, row_shapes* shape_list, int* shape_no, int flag ); int value_exists(int value, int *row, int size); void swap(shapes *a, shapes *b); int invalid( int left, int right, int *row, int value); void insert_element(shapes element, int *size, shapes heap[]); shapes remove_element(int *size, shapes heap[]); void create_shapes(int value, row_shapes shape_list[][MAX_ROW_SHAPES], int shape_no[], int C_INT[][MAX_COLS], int n_cols, int n_rows, shapes shape_array[][MAX_SHAPES], int n_shapes[] ); void heap_add(shapes element, row_shapes shape_list[][MAX_ROW_SHAPES], int shape_no[], shapes heap[], int *heap_size, int top); void display_shapes(shapes element, int row_size, int col_size); void display_shapes1(shapes element, int row_size, int col_size, int s_row, int s_col, int n1_rows, int n1_cols); void display_shapes2(shapes element, int row_size, int col_size,int s_row, int s_col); int find_value(int C_INT[][MAX_COLS], int rows, int cols); int find_values(int C_INT[][MAX_COLS], int rows, int cols, int values[],int* no_values ); void remove_shapes(shapes element, int C_INT[][MAX_COLS], int row_size, int col_size); void NPremove_shapes(shapes element, int C_INT[][MAX_COLS], int row_size, int col_size, shapes NP_table[][MAX_NP_SHAPES], int NP_row); void add_shapes(shapes element, int C_INT[][MAX_COLS], int row_size, int col_size); void heuristic( row_shapes shape_list[][MAX_ROW_SHAPES], int shape_no[], int C_INT[][MAX_COLS],int C_INT1[][MAX_COLS], int n_cols, int n_rows, int s_row, int s_col, int n1_rows, int n1_cols, shapes shape_array[][MAX_SHAPES], int n_shapes[] ); int promising_value( row_shapes shape_list[][MAX_ROW_SHAPES], int shape_no[], int C_INT[][MAX_COLS],int C_INT1[][MAX_COLS], int n_cols, int n_rows, shapes shape_array[][MAX_SHAPES], int n_shapes[] ); int find_bound(int C_INT[][MAX_COLS], int n_rows, int n_cols, int flag[]); void build_NP_table(shapes NP_table[][MAX_NP_SHAPES], row_shapes shape_list[][MAX_ROW_SHAPES], int shape_no[], int C_INT[][MAX_COLS], int C_INT1[][MAX_COLS], int n_cols, int n_rows, int s_row, int s_col, shapes shape_array[][MAX_SHAPES], int n_shapes[], int NP_n_shapes[] ); void NPheap_add(shapes NP_table[][MAX_NP_SHAPES], row_shapes shape_list[][MAX_ROW_SHAPES], int shape_no[], int C_INT[][MAX_COLS], int C_INT1[][MAX_COLS], int n_cols, int n_rows, int s_row, int s_col, shapes shape_array[][MAX_SHAPES], int n_shapes[], int NP_n_shapes[],int prev_index ); void displayNPtable(shapes NP_table[][MAX_NP_SHAPES], int NP_n_shapes[]); int straight_edge(shapes element, int s_row, int s_col); void NPdisplay_shapes(shapes element, int row_size, int col_size, shapes NP_table[][MAX_NP_SHAPES], int s_row, int s_col, int n1_rows, int n1_cols); int main(int argc, char **argv) { int INT1[MAX_ROWS][MAX_COLS]; // Original Intensity Matrix int INT[MAX_ROWS][MAX_COLS]; // Intensity Sub Matrix int C_INT[MAX_ROWS][MAX_COLS]; // Intensity Matrix with changes int C_INT1[MAX_ROWS][MAX_COLS]; // Intensity Matrix with changes int n1_rows, n1_cols, n_rows, n_cols; int s_row, s_col; int i, j; int shape_no[MAX_ROWS]; row_shapes shape_list[MAX_ROWS][MAX_ROW_SHAPES]; shapes shape_array[MAX_ROWS][MAX_SHAPES]; int n_shapes[MAX_ROWS]; shapes element; int value; int count; int values[MAX_ROWS*MAX_COLS]; int prom_value; shapes NP_table[NP_TABLE_LIMIT][MAX_NP_SHAPES]; int NP_n_shapes[NP_TABLE_LIMIT]; long t; // time long cput; // cpu time t=time(NULL); cput= clock(); if (argc != 2) { printf("usage: app file_name \n"); exit(1); } read_file(argv[1], INT1, &n1_rows, &n1_cols ); submatrix(INT1, n1_rows, n1_cols, INT, &s_row, &s_col, &n_rows, &n_cols); // printf("s_row = %d s_col = %d n1_rows = %d n1_cols = %d n_rows = %d n_cols = %d \n", // s_row, s_col, n1_rows, n1_cols, n_rows, n_cols); convert_array(INT, n_rows, n_cols, C_INT); //printf("Parameters Used: \n"); //printf("Level of the input map: %d \n", LEVEL); //printf("NP Table width: %d \n", MAX_NP_SHAPES ); //printf("Shape Table width: %d \n", MAX_SHAPES ); //printf("Max. # values used: %d \n", MAX_NO_VALUES ); //printf("Shape table rows used: %d \n", SHAPE_TABLE_ROWS_USED ); //display_array1(INT, n_rows, n_cols, s_row, s_col, n1_rows, n1_cols); // display_array(C_INT, n_rows, n_cols+1); // heuristic(shape_list, // shape_no, C_INT, C_INT1, n_cols, n_rows, s_row, s_col, n1_rows, n1_cols, // shape_array, n_shapes); build_NP_table(NP_table, shape_list, shape_no, C_INT, C_INT1, n_cols, n_rows, s_row, s_col, shape_array, n_shapes, NP_n_shapes); // display the solution with the best beam on time i=0; while(NP_n_shapes[i] > 0) i++; i =i-1; element = NP_table[i][0]; for(j =0; j < NP_n_shapes[i];j++) { if((NP_table[i][j].prom_value ==0) && (element.NPbeamtime > NP_table[i][j].NPbeamtime)) { element=NP_table[i][j]; } } NPdisplay_shapes(element,n_rows, n_cols, NP_table, s_row, s_col, n1_rows, n1_cols); t = time(NULL)-t; cput= (clock()-cput)/CLOCKS_PER_SEC; //printf("Total time = %d seconds \n", t); //printf("Total CPU time = %d seconds \n", cput); // Check the validity of the solution NPremove_shapes(element, C_INT, n_rows, n_cols+1, NP_table, element.prev_row+1); value=find_value(C_INT, n_rows, n_cols+1); if(value==0) printf("The solution is correct!!! \n"); else printf("***The solution is incorrect*** \n"); } void heuristic( row_shapes shape_list[][MAX_ROW_SHAPES], int shape_no[], int C_INT[][MAX_COLS],int C_INT1[][MAX_COLS], int n_cols, int n_rows, int s_row, int s_col, int n1_rows, int n1_cols, shapes shape_array[][MAX_SHAPES], int n_shapes[] ) { int value; int no_values; int values[MAX_ROWS*MAX_COLS]; int count; int valcnt; shapes element; int flag=1; int i, j; int beamtime=0; for(i=0; i < MAX_ROWS; i++) for(j=0; j < MAX_COLS; j++) C_INT1[i][j] = C_INT[i][j]; value= find_values(C_INT1, n_rows, n_cols+1, values,&no_values); count =0; while(value > 0) { for(valcnt=0; valcnt < no_values; valcnt++) { for(i=0; i < MAX_ROWS; i++) n_shapes[i] = 0; create_shapes(values[valcnt], shape_list, shape_no, C_INT1, n_cols, n_rows, shape_array, n_shapes); i=0; while(n_shapes[i] > 0) i++; if(valcnt ==0 && flag) {element = shape_array[i-1][0];value = values[0]; flag =0;} for(j =0; j< n_shapes[i-1];j++) if((element.price < shape_array[i-1][j].price) || ((element.price == shape_array[i-1][j].price) && (element.volume < shape_array[i-1][j].volume))) { element = shape_array[i-1][j]; value = values[valcnt]; } } // for valcnt flag=1; create_shapes(value, shape_list, shape_no, C_INT1, n_cols, n_rows, shape_array, n_shapes); printf(" Shape Matrix # %d \n", count+1); display_shapes1(element, n_rows,n_cols, s_row, s_col, n1_rows, n1_cols); remove_shapes(element, C_INT1, n_rows, n_cols+1); beamtime += value; value= find_values(C_INT1, n_rows, n_cols+1, values,&no_values); count++; if(count == 60) exit(1); } printf("Total beam on time = %d \n", beamtime); } int promising_value( row_shapes shape_list[][MAX_ROW_SHAPES], int shape_no[], int C_INT[][MAX_COLS],int C_INT1[][MAX_COLS], int n_cols, int n_rows, shapes shape_array[][MAX_SHAPES], int n_shapes[] ) { int value; int no_values; int values[MAX_ROWS*MAX_COLS]; int count; int valcnt; shapes element; int flag=1; int i, j; int beamtime=0; for(i=0; i < n_rows; i++) for(j=0; j < n_cols+1; j++) C_INT1[i][j] = C_INT[i][j]; value= find_values(C_INT1, n_rows, n_cols+1, values,&no_values); if (value==0) return 0; count =0; while(value > 0) { for(valcnt=0; valcnt < no_values; valcnt++) { for(i=0; i < MAX_ROWS; i++) n_shapes[i] = 0; create_shapes(values[valcnt], shape_list, shape_no, C_INT1, n_cols, n_rows, shape_array, n_shapes); i=0; while(n_shapes[i] > 0) i++; if(valcnt ==0 && flag) {element = shape_array[i-1][0];value = values[0]; flag =0;} for(j =0; j< n_shapes[i-1];j++) if((element.price < shape_array[i-1][j].price) || ((element.price == shape_array[i-1][j].price) && (element.volume < shape_array[i-1][j].volume))) { element = shape_array[i-1][j]; value = values[valcnt]; } } // for valcnt flag=1; create_shapes(value, shape_list, shape_no, C_INT1, n_cols, n_rows, shape_array, n_shapes); remove_shapes(element, C_INT1, n_rows, n_cols+1); beamtime += value; value= find_values(C_INT1, n_rows, n_cols+1, values,&no_values); count++; if(count == 100) { return 10000; printf(" count = %d \n", count); display_array(C_INT, n_rows, n_cols+1); exit(1); } } return (count*7+beamtime); } void read_file(char* f_name, int INT1[][MAX_COLS], int* n1_rows, int* n1_cols ) { FILE *ifp; int i, j; ifp = fopen(f_name, "r"); // fscanf(ifp, "%d %d", n1_rows, n1_cols); *n1_rows = I_ROWS; *n1_cols = I_COLS; for(i=0; i < *n1_rows; i++) for(j=0; j< *n1_cols; j++) fscanf(ifp, "%d ", &INT1[i][j]); } int nonzero_row(int V[], int* left, int* right, int size) { int i, j; int value =0; i=0; while((V[i] ==0) && (i < size)) i++; if(i < size) { value =1; *left = i; j=size-1; while(V[j] ==0) j--; *right =j; } return value; } void submatrix(int INT1[][MAX_COLS], int n1_rows, int n1_cols, int INT[][MAX_COLS], int* s_row, int* s_col, int* n_rows, int* n_cols ) { int left, right, top, bottom; int le, ri; int i, j; left = top =0; right = n1_cols -1; bottom = n1_rows -1; while(!nonzero_row(INT1[top], &left, &right, n1_cols)) top++; while(!nonzero_row(INT1[bottom], &left, &right, n1_cols)) bottom--; for(i = bottom; i >= top; i--) if(nonzero_row(INT1[i], &le, &ri, n1_cols)) { if(left > le) left = le; if(right < ri) right =ri; } *s_row = top; *s_col = left; *n_rows = bottom-top+1; *n_cols = right - left+1; for(i = top; i <= bottom; i++) for(j = left; j <= right; j++) INT[i-top][j-left]= INT1[i][j]; } // prints what is given as is void display_array(int Array[][MAX_COLS], int n_rows, int n_cols) { int i, j; printf("%4c ",' ' ); for(j=0; j< n_cols; j++) printf("%4d ", j); printf("\n"); for(i=0; i < n_rows; i++) { printf("%4d ", i); for(j=0; j< n_cols; j++) printf("%4d ", Array[i][j]); printf("\n"); } printf("\n"); } // fills in 0's for a 40x25 matrix void display_array1(int Array[][MAX_COLS], int n_rows, int n_cols, int s_row, int s_col, int n1_rows, int n1_cols) { int i, j; /* printf("%4c",' ' ); for(j=0; j< n1_cols; j++) printf("%4d", j); printf("\n"); */ for(i=0; i < s_row; i++) { // printf("%4d", i); for(j=0; j< n1_cols; j++) printf("%4d", 0); printf("\n"); } for(i=s_row; i < s_row+n_rows; i++) { // printf("%4d", i); for(j=0; j< n1_cols; j++) printf("%4d", ((j=s_col+n_cols))?0:Array[i-s_row][j-s_col]); printf("\n"); } for(i=s_row+n_rows; i < n1_rows; i++) { // printf("%4d", i); for(j=0; j< n1_cols; j++) printf("%4d", 0); printf("\n"); } printf("\n"); } // prints as is void display_array2(int Array[][MAX_COLS], int n_rows, int n_cols, int s_row, int s_col) { int i, j; printf("%4c ",' ' ); for(j=0; j< n_cols; j++) printf("%4d ", s_col+j); printf("\n"); for(i=0; i < n_rows; i++) { printf("%4d ", s_row+i); for(j=0; j< n_cols; j++) printf("%4d ", Array[i][j]); printf("\n"); } printf("\n"); } void convert_array(int INT[][MAX_COLS],int n_rows, int n_cols, int C_INT[][MAX_COLS]) { int i, j; for(i=0; i < n_rows; i++) { C_INT[i][0] = INT[i][0]; C_INT[i][n_cols]= -INT[i][n_cols-1]; } for(i=0; i < n_rows; i++) for(j=1; j< n_cols; j++) C_INT[i][j]=INT[i][j] -INT[i][j-1]; } int value_exists(int value, int *row, int size) { int i; int flag =0; for(i = 0; i< size; i++) { if(abs(row[i]) == value) { flag =1; break; } } return flag; } int invalid( int left, int right, int *row, int value) { int left_value = 0; int right_value = 0; int i; int flag =0; for(i = 0; i<= left; i++) left_value += row[i]; if(left_value < value) flag = 1; right_value = left_value; for(i = left+1; i< right; i++) { right_value += row[i]; if(right_value < value) flag = 1; } return flag; } void separate_row(int value, int *row, int size, row_shapes* shape_list, int* shape_no, int flag ) { int i, j; int price ; int count; int left, right; *shape_no =0; left=0; while(row[left] ==0) left++; right = size-1; while(row[right]==0) right--; for(i=left; i<= right -1; i++) for(j = i+1; j<= right; j++) { price =0; if(((row[i]==0)&&(row[j]==0))|| (row[i] < 0) || (row[j] >0) || ((flag ==1)&&((row[i]==0)|| (row[j]==0))) || ((flag==0)&&((row[i]!=0)&&(row[j] !=0)&& (j>i+3))) || invalid(i,j,row,value)) continue; else { if(row[i] == value) price++; if(row[j] == -value) price++; //printf( " left %d right %d price %d\n",i, j, price); shape_list[*shape_no].price = price; shape_list[*shape_no].left = i; shape_list[*shape_no].right =j; (*shape_no)++; if((*shape_no == MAX_ROW_SHAPES)) { printf(" A shape_list row is full \n"); exit(1); } } // else } // for //exit(1); } /* void separate_row(int value, int *row, int size, row_shapes* shape_list, int* shape_no ) { int i, j; int price ; int count; *shape_no =0; // for(j = 0; j< size; j++) // printf( " %d ", row[j]); // printf( " value exists= %d \n" , value_exists(value, row, size)); if(value_exists(value, row, size)) { i=0; while(i < size) { while(abs(row[i]) != value && i< size)i++; // printf( " index= %d \n", i); if(row[i] > 0) { // go to right for(j = i+1; j< size; j++) { if(row[j] == 0 || invalid(i,j,row, value)) continue; else { price =0; if(row[i] == value) price++; if(row[j] == -value) price++; shape_list[*shape_no].price = price; shape_list[*shape_no].left = i; shape_list[*shape_no].right =j; (*shape_no)++; } // else } // for }// if if(row[i] < 0) { // go to left for(j = 0; j< i ; j++) { if(row[j] == 0 || invalid(j,i, row, value)) continue; else { price =0; if(row[j] == value) price++; if(row[i] == -value) price++; if(price < 2) { shape_list[*shape_no].price = price; shape_list[*shape_no].left = j; shape_list[*shape_no].right =i; (*shape_no)++; } } // else } // for } // if // printf(" %d \n", *shape_no); i++; } // while count=0; for(i=0; i< size -1; i++) for(j = size-1; j> i; j--) { if(row[i]==0 || row[j] == 0 || count > 2 || abs(row[i]) == value || abs(row[j])==value || invalid(i,j,row, value)) continue; else { // printf( " index j= %d \n", j); shape_list[*shape_no].price = 0; shape_list[*shape_no].left = i; shape_list[*shape_no].right =j; (*shape_no)++; count++; } // else } // for } // if (value_exists) if(!value_exists(value, row, size)) { for(i=0; i< size -1; i++) for(j = i+1; j< size; j++) { if(row[i]==0 || row[j] == 0 || invalid(i,j,row, value)) continue; else { // printf( " index j= %d \n", j); shape_list[*shape_no].price = 0; shape_list[*shape_no].left = i; shape_list[*shape_no].right =j; (*shape_no)++; } // else } // for } } */ void swap(shapes *a, shapes *b) { shapes temp; temp = *a; *a = *b; *b = temp; } void insert_element(shapes element, int *size, shapes heap[]) { int child, parent; static int count1=0; if(*size == MAX_LIMIT) { child =(*size/2)+count1; if(heap[child].price >= element.price) return; // replace the last leaf with the new element heap[child] = element; count1++; if(count1 = (*size)) count1=0; } else { heap[*size] = element; (*size)++; child = (*size)-1; } if(child !=0) parent = (child-1)/2; while( child !=0 && heap[child].price > heap[parent].price) { swap(&heap[child], &heap[parent]); child = parent; if(child !=0) parent = (child-1)/2; } } /* void insert_element(shapes element, int *size, shapes heap[]) { int child, parent; if(*size == MAX_LIMIT) { printf("Heap is full \n"); return; } else heap[*size] = element; (*size)++; child = (*size)-1; if(child !=0) parent = (child-1)/2; while( child !=0 && heap[child].price > heap[parent].price) { swap(&heap[child], &heap[parent]); child = parent; if(child !=0) parent = (child-1)/2; } } */ shapes remove_element(int *size, shapes heap[]) { shapes temp; int child, parent; temp = heap[0]; heap[0] = heap[*size-1]; (*size)--; if(*size > 1) { parent=0; if(parent*2+2 <= (*size)-1) child = (heap[parent*2+1].price > heap[parent*2+2].price)? parent*2+1:parent*2+2; if(parent*2 +1 == (*size)-1) child = parent*2+1; while(parent*2+1 <= (*size)-1 && heap[parent].price < heap[child].price) { swap(&heap[parent], &heap[child]); parent =child; if(parent*2+2 <= (*size)-1) child = (heap[parent*2+1].price > heap[parent*2+2].price)? parent*2+1:parent*2+2; if(parent*2+1 == (*size)-1) child = parent*2+1; } } // if (*size > 1) return temp; } void create_shapes(int value, row_shapes shape_list[][MAX_ROW_SHAPES], int shape_no[], int C_INT[][MAX_COLS], int n_cols, int n_rows, shapes shape_array[][MAX_SHAPES], int n_shapes[] ) { shapes heap[MAX_LIMIT]; int heap_size=0; int i, j; int level; shapes element; int count; int top =1; int flag[MAX_ROWS]; count = find_bound(C_INT,n_rows, n_cols+1, flag); // insert level 1 shapes in a heap for(i=0; i< n_rows;i++) { // printf("row = %d value = %d \n", i, value); separate_row(value, C_INT[i], n_cols+1, shape_list[i], &shape_no[i], flag[i]); for(j=0; j< shape_no[i]; j++) { // printf(" %d %d %d \n", shape_list[i][j].price, shape_list[i][j].left, // shape_list[i][j].right); element.value = value; element.price= shape_list[i][j].price; element.volume = shape_list[i][j].right-shape_list[i][j].left+1; element.start = i; element.end = i; element.index[i]=j; element.left_index[i]=shape_list[i][j].left; element.right_index[i]=shape_list[i][j].right; insert_element(element, &heap_size, heap); } // printf(" \n"); } // printf(" \n"); // remove level 1 shapes from the heap and insert them in the // shape array count =0; while(heap_size >0) { if(count < MAX_SHAPES) { shape_array[0][count] = remove_element(&heap_size, heap); count ++; } else break; /* element = shape_array[0][count-1]; printf(" %d %d %d %d \n", element.price, element.start, shape_list[element.start][element.index[element.start]].left, shape_list[element.start][element.index[element.start]].right); */ } // while n_shapes[0] = count; for(level =2; level <=n_rows; level++) { heap_size =0; // insert level>=2 shapes in a heap for(i=0; i=2 shapes from the heap and insert them in the // shape array count =0; while(heap_size >0) { if(count < MAX_SHAPES) { shape_array[level-1][count] = remove_element(&heap_size, heap); count ++; } else break; // element = shape_array[0][count-1]; // printf(" %d %d %d %d \n", element.price, element.start, // shape_list[element.start][element.index[element.start]].left, // shape_list[element.start][element.index[element.start]].right); } // while n_shapes[level-1] = count; } // for level } void heap_add(shapes element, row_shapes shape_list[][MAX_ROW_SHAPES], int shape_no[], shapes heap[], int *heap_size, int top) { int i; shapes new_element; int new_end, new_start; int b1,e1,b2,e2; if(top ) { new_end = element.end + 1; for(i=0; i< shape_no[new_end]; i++) { new_element = element; b1 = shape_list[element.end][element.index[element.end]].left; e1 = shape_list[element.end][element.index[element.end]].right; b2 = shape_list[element.end+1][i].left; e2 = shape_list[element.end+1][i].right; if(!( e1 <= b2 || e2 <= b1)) { new_element.end++; new_element.index[new_element.end] =i; new_element.left_index[new_element.end] =b2; new_element.right_index[new_element.end] =e2; new_element.price += shape_list[new_element.end][i].price; new_element.volume += e2-b2+1; insert_element(new_element, heap_size, heap); } } // for } // if top if(!top ) { new_start = element.start-1; for(i=0; i< shape_no[new_start]; i++) { new_element = element; b1 = shape_list[element.start][element.index[element.start]].left; e1 = shape_list[element.start][element.index[element.start]].right; b2 = shape_list[element.start-1][i].left; e2 = shape_list[element.start-1][i].right; if(!( e1 <= b2 || e2 <= b1)) { new_element.start--; new_element.index[new_element.start] =i; new_element.left_index[new_element.start] =b2; new_element.right_index[new_element.start] =e2; new_element.price += shape_list[new_element.start][i].price; new_element.volume += e2-b2+1; insert_element(new_element, heap_size, heap); } } // for } // if !top } // heap_add void display_shapes(shapes element, int row_size, int col_size) { int i, j; int temp[MAX_ROWS][MAX_COLS]; for(i=0; i< row_size; i++) for(j=0; j< col_size; j++) temp[i][j] = 0; for(i=element.start; i<=element.end; i++) for(j=element.left_index[i]; j v[j][0]) { temp = v[i][0]; v[i][0]= v[j][0]; v[j][0]=temp; temp = v[i][1]; v[i][1]= v[j][1]; v[j][1]=temp; } if(LEVEL ==5 && count >MAX_NO_VALUES ) count=MAX_NO_VALUES; if(LEVEL ==10 && count >MAX_NO_VALUES ) count=MAX_NO_VALUES; if(LEVEL ==100 && count >MAX_NO_VALUES ) count=MAX_NO_VALUES; *no_values = count; for(i=0; i < count; i++) { values[i] = v[i][0]; // printf("value = %4d frequency = %4d \n", v[i][0], v[i][1]); if(max_freq < v[i][1]) { max_freq = v[i][1]; max_index = i; } price += v[i][1]; } // printf("Total Price = %4d \n", price); if(max_index == -1) return 0; else return (v[max_index][0]); } void remove_shapes(shapes element, int C_INT[][MAX_COLS], int row_size, int col_size) { int i, j; for(i=element.start; i<=element.end; i++) { C_INT[i][element.left_index[i]] -= element.value; C_INT[i][element.right_index[i]] += element.value; } } void build_NP_table(shapes NP_table[][MAX_NP_SHAPES], row_shapes shape_list[][MAX_ROW_SHAPES], int shape_no[], int C_INT[][MAX_COLS], int C_INT1[][MAX_COLS], int n_cols, int n_rows, int s_row, int s_col, shapes shape_array[][MAX_SHAPES], int n_shapes[], int NP_n_shapes[] ) { int row; int value; int i,j, k, l; int last_row; int values[MAX_ROWS*MAX_COLS]; int no_values=0; int count; int valcnt; shapes element, element1; int n_shapes1[MAX_ROWS]; int prev_row; int prev_index; int index_chain[NP_TABLE_LIMIT]; int shape_index; int C_INT2[MAX_ROWS][MAX_COLS]; for(i=0; i < MAX_ROWS; i++) for(j=0; j < MAX_COLS; j++) C_INT1[i][j] = C_INT[i][j]; for(i=0; i < NP_TABLE_LIMIT; i++) NP_n_shapes[i]=0; heapNP_size=0; // build the first row prev_index=-1; NPheap_add(NP_table, shape_list, shape_no, C_INT, C_INT1, n_cols, n_rows, s_row, s_col, shape_array, n_shapes, NP_n_shapes , prev_index); count =0; while(heapNP_size >0) { if(count < MAX_NP_SHAPES) { element= NPremove_element(&heapNP_size, heapNP); NP_table[0][count] = element; NP_table[0][count].prev_row = -1; NP_table[0][count].NPbeamtime = NP_table[0][count].value; count ++; } else break; //printf("heapNPsize %d \n", heapNP_size); } // while NP_n_shapes[0] = count; // for(row =1; row < 6; row++) for(row =1; row < NP_TABLE_LIMIT; row++) { heapNP_size=0; for(shape_index=0; shape_index< NP_n_shapes[row-1]; shape_index++) { element = NP_table[row-1][shape_index]; NPremove_shapes(element, C_INT1, n_rows, n_cols+1,NP_table,row-1); prev_index= shape_index; NPheap_add(NP_table, shape_list, shape_no, C_INT1, C_INT2, n_cols, n_rows, s_row, s_col, shape_array, n_shapes, NP_n_shapes , prev_index); for(i=0; i < MAX_ROWS; i++) for(j=0; j < MAX_COLS; j++) C_INT1[i][j] = C_INT[i][j]; } // for shape count =0; while(heapNP_size >0) { if(count < MAX_NP_SHAPES) { element= NPremove_element(&heapNP_size, heapNP); NP_table[row][count] = element; NP_table[row][count].prev_row = row-1; NP_table[row][count].NPbeamtime = NP_table[row][count].value+ NP_table[row-1][NP_table[row][count].prev_index].NPbeamtime; count ++; } else break; } // while NP_n_shapes[row] = count; // printf( " row = %d n shapes %d \n", row, NP_n_shapes[row]); // displayNPtable(NP_table, NP_n_shapes); if(NP_table[row][0].prom_value == 0) return; } // for row } void NPheap_add(shapes NP_table[][MAX_NP_SHAPES], row_shapes shape_list[][MAX_ROW_SHAPES], int shape_no[], int C_INT[][MAX_COLS], int C_INT1[][MAX_COLS], int n_cols, int n_rows, int s_row, int s_col, shapes shape_array[][MAX_SHAPES], int n_shapes[], int NP_n_shapes[],int prev_index ) { int value; int i,j, k, l; int last_row; int values[MAX_ROWS*MAX_COLS]; int no_values=0; int count; int valcnt; shapes element, element1; int n_shapes1[MAX_ROWS]; int row, shape_index; for(i=0; i < n_rows; i++) for(j=0; j < n_cols+1; j++) C_INT1[i][j] = C_INT[i][j]; value= find_values(C_INT1, n_rows, n_cols+1, values,&no_values); for(valcnt=0; valcnt < no_values; valcnt++) { for(i=0; i < MAX_ROWS; i++) n_shapes[i] = 0; create_shapes(values[valcnt], shape_list, shape_no, C_INT1, n_cols, n_rows, shape_array, n_shapes); i=0; while(n_shapes[i] > 0) i++; last_row = i-1; //printf("last_row %d \n", last_row); // for(row=last_row; row>= last_row/2; row--) for(row=last_row; (row>=0 && row > last_row- SHAPE_TABLE_ROWS_USED) || (row>=0 && heapNP_size < MAX_NP_SHAPES); row--) for(shape_index=0; shape_index < n_shapes[row]; shape_index++) { element = shape_array[row][shape_index]; if(!straight_edge(element,s_row, s_col)) continue; remove_shapes(element, C_INT1, n_rows, n_cols+1); element.prom_value = promising_value(shape_list, shape_no, C_INT1, C_INT1, n_cols, n_rows, shape_array, n_shapes); if(element.prom_value!= 0) element.prom_value += element.value; // if(element.start >=20 && (element.start != element.end)) // element.prom_value = 99; // if(element.end <=20 && (element.start != element.end)) // element.prom_value = 99; // element.prom_value= 1000/ element.volume; for(i=0; i < n_rows; i++) for(j=0; j < n_cols+1; j++) C_INT1[i][j] = C_INT[i][j]; create_shapes(values[valcnt], shape_list, shape_no, C_INT1, n_cols, n_rows, shape_array, n_shapes); element.prev_index =prev_index; NPinsert_element(element, &heapNP_size, heapNP); // display_NPheap(heapNP_size,heapNP); } // for } // for valcnt } void NPremove_shapes(shapes element, int C_INT[][MAX_COLS], int row_size, int col_size, shapes NP_table[][MAX_NP_SHAPES], int NP_row) { int i, j; // if there is more than one level while(element.prev_index >= 0) { for(i=element.start; i<=element.end; i++) { C_INT[i][element.left_index[i]] -= element.value; C_INT[i][element.right_index[i]] += element.value; } NP_row--; element = NP_table[NP_row][element.prev_index]; } // while // the zeroth row for(i=element.start; i<=element.end; i++) { C_INT[i][element.left_index[i]] -= element.value; C_INT[i][element.right_index[i]] += element.value; } } void add_shapes(shapes element, int C_INT[][MAX_COLS], int row_size, int col_size) { int i, j; for(i=element.start; i<=element.end; i++) { C_INT[i][element.left_index[i]] += element.value; C_INT[i][element.right_index[i]] -= element.value; } } void displayNPtable(shapes NP_table[][MAX_NP_SHAPES], int NP_n_shapes[]) { int i,j; i=0; printf("Previous Index \n"); while(NP_n_shapes[i] > 0) { for(j=0; j 0) { for(j=0; j 0) { for(j=0; j= 0) { count++; //printf(" Shape # %d \n", count); display_shapes1(element, row_size, col_size, s_row, s_col, n1_rows, n1_cols); element = NP_table[element.prev_row][element.prev_index]; } // while // the zeroth row count++; //printf(" Shape # %d \n", count); display_shapes1(element, row_size, col_size, s_row, s_col, n1_rows, n1_cols); } int find_bound(int C_INT[][MAX_COLS], int n_rows, int n_cols, int flag[]) { int i, j; int max=0, min=10000, total=0; int toprow, bottomrow; int left, right; toprow=0; while(!nonzero_row(C_INT[toprow],&left, &right,n_cols+1)) toprow++; bottomrow= n_rows-1; while(!nonzero_row(C_INT[bottomrow],&left, &right,n_cols+1)) bottomrow--; for(i=toprow; i <= bottomrow; i++) { flag[i]=0; total=0; for(j=0; j < n_cols; j++) if(C_INT[i][j] > 0) total += C_INT[i][j]; flag[i]=total; if(total > max) max = total; if(total < min && total>0 ) min = total; } //toprow=0; // while(flag[toprow]==0) toprow++; //bottomrow= n_rows-1; // while(flag[bottomrow]==0) bottomrow--; for(i=toprow; i <= bottomrow; i++) { if(max == min) flag[i]=1; else { if(flag[i]== max) flag[i]=1; else if(flag[i]==min) flag[i]=0; else flag[i]=2; } if((i==toprow) ||(i==bottomrow)) flag[i]=1; } if(min == 10000) return min; else return(max - min); } int straight_edge(shapes element, int s_row, int s_col) { int leftflag =1; int rightflag =1; int left, right; int i; if(element.start+ s_row <= 19 && element.end + s_row >= 20) return 1; if(element.start + s_row >= 20 || element.end + s_row <= 19) { // check straight edge //check left edge left = element.left_index[element.start]; for(i=element.start+1; i <= element.end; i++) if(element.left_index[i] != left) { leftflag =0; break; } if(leftflag == 1) return 1; //check right edge right = element.right_index[element.start]; for(i=element.start+1; i <= element.end; i++) if(element.left_index[i] != right) { rightflag =0; break; } if(rightflag == 1) return 1; return 0; } // if ( >= 20 }