#include #include /* ASet, fixed maximum size, minimal use of dynamic memory. */ /* As it stands, this set implementation just stores data items of the type "example_data_item", which is defined in this file, and is only capable of holding a single integer. It is here as as example only. When you have defined your own data objects that are to be stored in the set, delete the two lines below that say "typedef ... example_data_item", and in the following "#define" line, replace the name "example_data_item" with your own data object's type. Also delete the create_item function, which will be useless. This otherwise worthless section is only here so that an example will work. */ typedef struct /* remove this */ { int value; } example_data_item; #define item example_data_item /* replace this */ item *create_item(int v) /* remove this */ { item *x; x=(item *)malloc(sizeof(item)); x->value=v; return (x); } /* Sometimes you need to search an area of storage to see if it contains a data item that matches in some way another data item that you have. (for example, searching the closed set to see if a similar state is already there) The function "search_for" searches through the set looking for a data item similar to one you provide as a pattern. If one is found, it returns a pointer to that item; if none are found it returns NULL. To use search_for, you must define a function that tests two items to see if they are similar enough; the search_for function is called with 3 parameters: the set, your is_similar function, and the item to be used as a pattern in the search. The is_similar function below illustrates how such a function could be written. For a use, see the example at the end. */ int is_similar(item *a, item *b) /* remove or replace this */ { int diff=a->value-b->value; if (diff<0) diff=-diff; if (diff<=1) return 1; else return 0; } /* This kind of set is only suitable for storing structured data (defined using a "struct" definition in C) like the "example_data_item" above. Data items in the set are referred to through pointers. This implementation uses an array to store the data. This saves quite a bit on memory use and a lot on processor time if you have a good idea of the maximum number of data items to be added. If you haven't got a good idea of the maximum, use a "dset" instead. to create an aset, call "new_aset" with the maximum capacity as a parameter; store the returned result in a variable of type "aset *", and use it to refer to the set in all further calls. the only things you can do to a set are add an item, remove a randomly selected item, and find the total number of items held. All three functions refer to the set and the item through pointers. There is a small example below. When you have completely finished with an aset, you should call "delete_aset" to return its memory to the system, unless the whole program is about to terminate. */ typedef struct { int size, max; item **data; } aset; aset *new_aset(int max_number_of_entries) { aset *a=(aset *)malloc(sizeof(aset)); a->size=0; srandomdev(); a->max=max_number_of_entries; a->data=(item **)malloc(a->max*sizeof(item *)); return (a); } void delete_aset(aset *a) { free((void *)a->data); free((void *)a); } int is_aset_full(aset *a) { return (a->size>=a->max); } int is_aset_empty(aset *a) { return (a->size<=0); } int items_in_aset(aset *a) { return (a->size); } void add_to_aset(aset *a, item *i) { if (a->size>=a->max) { fprintf(stderr,"add_to_aset() when full\n"); exit(1); } a->data[a->size]=i; a->size+=1; } item *remove_from_aset(aset *a) { item *it; long int n; if (a->size<=0) { fprintf(stderr,"remove_from_aset() when empty\n"); exit(1); } n=random(); if (n<0) n=-n; n=n%a->size; it=a->data[n]; a->size-=1; a->data[n]=a->data[a->size]; return (it); } typedef int comparer(item *, item *); item *search_aset_for(aset *a, comparer *fn, item *pattern) { int i; for (i=0; isize; i+=1) if (fn(a->data[i],pattern)) return (a->data[i]); return NULL; } /* the following "main" function is just to illustrate the use of an aquack. It should not be included in any useful programs. */ void main(void) { aset *as=new_aset(100); example_data_item *x, *y; x=create_item(17); printf("adding %d to set\n", x->value); add_to_aset(as,x); x=create_item(5); printf("adding %d to set\n", x->value); add_to_aset(as,x); x=create_item(6666666); printf("adding %d to set\n", x->value); add_to_aset(as,x); x=create_item(1); printf("adding %d to set\n", x->value); add_to_aset(as,x); x=create_item(54321); printf("adding %d to set\n", x->value); add_to_aset(as,x); x=create_item(8274); printf("adding %d to set\n", x->value); add_to_aset(as,x); y=create_item(6); printf("\nsearching for something similar to %d\n", y->value); x=search_aset_for(as,is_similar,y); if (x==NULL) printf(" Nothing similar found\n\n"); else printf(" Found %d, which is close enough\n\n", x->value); while (!is_aset_empty(as)) { printf("removing an item from the set "); x=remove_from_aset(as); printf("it was %d\n", x->value); } printf("The set is now empty.\n"); delete_aset(as); }