#include <stdio.h>
#include <stdlib.h>

/* DSet, continual 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 a tree in dynamic memory to store the data. There
   is no fixed maximum size.

   to create a dset, call "new_dset" with no parameters. Store the
   returned result in a variable of type "dset *", and use it to refer
   to the set in all further calls. If you want to set a maximum size,
   use the "set_dset_maximum_size" function.

   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 a dset, you should call
   "delete_dset" to return its memory to the system, unless the whole
   program is about to terminate. */

struct link
{ item *thisitem;
  struct link *leftlink, *rightlink; };

typedef struct
{ int size, max;
  struct link *top; } dset;

dset *new_dset(void)
{ dset *a=(dset *)malloc(sizeof(dset));
  a->size=0;
  srandomdev();
  a->max=-1;
  a->top=NULL;
  return (a); }

void set_dset_maximum_size(dset *a, int max)
{ a->max=max; }

void delete_link(struct link *li)
{ if (li==NULL)
    return;
  delete_link(li->leftlink);
  delete_link(li->rightlink);
  free((void *)li); }

void delete_dset(dset *a)
{ delete_link(a->top);
  free((void *)a); }

int is_dset_full(dset *a)
{ return (a->max>0 && a->size>=a->max); }

int is_dset_empty(dset *a)
{ return (a->size<=0); }

int items_in_dset(dset *a)
{ return (a->size); }

void add_to_dset(dset *a, item *i)
{ int newind, parind;
  unsigned int scan;
  struct link *parent, *newlink;
  if (a->max>0 && a->size>=a->max)
  { fprintf(stderr,"add_to_dset() when full\n");
    exit(1); }
  newlink=(struct link *)malloc(sizeof(struct link *));
  newlink->thisitem=i;
  newlink->leftlink=NULL;
  newlink->rightlink=NULL;
  a->size+=1;
  newind=a->size;
  if (newind==1)
  { a->top=newlink;
    return; }
  parind=newind/2;
  parent=a->top;
  scan=0x80000000;
  while ((scan&parind)==0)
    scan>>=1;
  scan>>=1;
  while (scan!=0)
  { int dir=scan&parind;
    if (dir==0)
      parent=parent->leftlink;
    else
      parent=parent->rightlink;
    scan>>=1; }
  if ((newind&1)==0)
    parent->leftlink=newlink;
  else
    parent->rightlink=newlink; }

item *remove_from_dset(dset *a)
{ item *it;
  struct link *cur, *unwanted, *parent;
  int n;
  unsigned int scan;
  if (a->size<=0)
  { fprintf(stderr,"remove_from_dset() when empty\n");
    exit(1); }
  n=random();
  if (n<0) n=-n;
  n=(n%a->size)+1;
  cur=a->top;
  scan=0x80000000;
  while ((scan&n)==0)
    scan>>=1;
  scan>>=1;
  while (scan!=0)
  { int dir=scan&n;
    if (dir==0)
      cur=cur->leftlink;
    else
      cur=cur->rightlink;
    scan>>=1; }
  unwanted=cur;
  it=unwanted->thisitem;
  n=a->size;
  cur=a->top;
  parent=NULL;
  scan=0x80000000;
  while ((scan&n)==0)
    scan>>=1;
  scan>>=1;
  while (scan!=0)
  { int dir=scan&n;
    parent=cur;
    if (dir==0)
      cur=cur->leftlink;
    else
      cur=cur->rightlink;
    scan>>=1; }
  unwanted->thisitem=cur->thisitem;
  free((void *)cur);
  if (parent==NULL)
    a->top=NULL;
  else if (parent->rightlink==cur)
    parent->rightlink=NULL;
  else
    parent->leftlink=NULL;
  a->size-=1;
  return (it); }

typedef int comparer(item *, item *);

item *search_tree_for(struct link *li, comparer *fn, item *pattern)
{ item *x;
  if (li==NULL)
    return NULL;
  if (fn(li->thisitem,pattern))
    return (li->thisitem);
  x=search_tree_for(li->leftlink,fn,pattern);
  if (x!=NULL) return x;
  return search_tree_for(li->rightlink,fn,pattern); }

item *search_dset_for(dset *a, comparer *fn, item *pattern)
{ return search_tree_for(a->top,fn,pattern); }

/* 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)
{ dset *as=new_dset();
  example_data_item *x, *y;

  x=create_item(17);
  printf("adding %d to set\n", x->value);
  add_to_dset(as,x);
  x=create_item(5);
  printf("adding %d to set\n", x->value);
  add_to_dset(as,x);
  x=create_item(6666666);
  printf("adding %d to set\n", x->value);
  add_to_dset(as,x);
  x=create_item(1);
  printf("adding %d to set\n", x->value);
  add_to_dset(as,x);
  x=create_item(54321);
  printf("adding %d to set\n", x->value);
  add_to_dset(as,x);
  x=create_item(8274);
  printf("adding %d to set\n", x->value);
  add_to_dset(as,x);

  y=create_item(6);
  printf("\nsearching for something similar to %d\n", y->value);
  x=search_dset_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_dset_empty(as))
  { printf("removing an item from the set ");
    x=remove_from_dset(as);
    printf("it was %d\n", x->value); }
  printf("The set is now empty.\n");

  delete_dset(as); }