/*** Copyright 1989 Norbert Schlenker.  All rights reserved.

  *** This software is distributed subject to the following provisions:

  ***    - this notice may not be removed;

  ***    - you may modify the source code, as long as redistributed

  ***      versions have their modifications clearly marked;

  ***    - no charge, other than a nominal copying fee, may be made

  ***      when providing copies of this source code to others;

  ***    - if this source code is used as part of a product which is

  ***      distributed only as a binary, a copy of this source code

  ***      must be included in the distribution.

  ***

  *** Unlike the GNU GPL, use of this code does not obligate you to

  *** disclose your own proprietary source code.

  *** The author of this software provides no warranty, express or

  *** implied, as to its utility or correctness.  That said, reports

  *** of bugs or compatibility problems will be gladly received by

  *** nfs@princeton.edu, and fixes will be attempted.

  ***/

 /*** index.c - routines to manipulate index lists */

 /*** Definition:  An "index list" is an ascending sequence of positive

  ***              integers that can be operated upon as follows:

  ***

  ***                 make_index_list - makes an index list of consecutive

  ***                    integers from some lower bound through an upper bound.

  ***                 choose_index - given a number "k", removes the integer

  ***                    in the k'th position in the index list and returns it.

  ***                    Requests for positions less than 1 or greater than

  ***                    the current list length return zero.

  ***                 remove_index - removes a specified integer from the

  ***                    index list.  Requests to remove integers not in the

  ***                    list are ignored, except that they reduce the list's

  ***                    "pseudo_size" (see below).

  ***                 index_size - returns the number of integers in the

  ***                    index list.

  ***                 pseudo_size - returns the number of integers in the

  ***                    index list, less the number for which remove_index

  ***                    failed due to a request to remove a non-existent one.

  ***			(Note that this is here solely to support an apparent

  ***			bug in the original definition of the NETGEN program.)

  *** Two simple methods of accomplishing these functions are:

  ***   - allocating an array of flags that indicate whether a particular

  ***     integer is valid, and searching the array during the choose_index

  ***     operation for the k'th valid integer.

  ***   - allocating a linked list for the indices and updating the list

  ***     during both the choose_index and remove_index operations.

  ***

  *** For small index lists, the first of these methods is quite efficient

  *** and is, in fact, implemented in the following code.  Unfortunately,

  *** for the uses we have in mind (i.e. NETGEN), the typical access pattern

  *** to index lists involves a large list, with both choose_index and

  *** remove_index operations occurring at random positions in the list.

  ***

  *** As a result, the code has been extended for the case of large lists.

  *** The enclosed implementation makes use of a binary interval tree, which

  *** records information regarding the valid intervals from which indices

  *** may be chosen.  At a cost of a substantial increase in space requirements,

  *** and under rather generous assumptions regarding the randomness of the

  *** positions supplied to choose_index, running time becomes logarithmic

  *** per choose_index and remove_index operation.

  ***/

 #include "netgen.h"

 /*** Useful constants */

 #define FLAG_LIMIT 100		/* upper limit for simple implementation */

 /*** Internally useful types */

 typedef unsigned char FLAG;

 typedef struct index_header {

   INDEX original_size;		/* original size of index */

   INDEX index_size;		/* number of indices in the index */

   INDEX pseudo_size;		/* almost the number of indices in the index */

   union {

     INDEX index_base;		/* base of index list - small case */

     INDEX index_nodes;		/* number of nodes in the interval tree - large case */

   } i;

   union {

     FLAG* flag;			/* pointer to flag array - small */

     struct interval_node* first_node; /* pointer to root of interval tree - large */

   } p;

 } HEADER;

 typedef struct interval_node {

   INDEX base;			/* smallest integer in this subtree */

   INDEX count;			/* count of indices in this subtree */

   struct interval_node* left_child; /* pointers down the tree */

 } INODE;

 /*** Static storage */

 static INDEX_LIST active_handles = 0;

 static HEADER* index_headers = NULL;

 /*** Make a new index list with a specified range.  Returns an integer handle

  *** to identify the list, or -1 if an error occurs.

  ***/

 INDEX_LIST make_index_list(from, to)

 INDEX from;			/* lower limit of index list */

 INDEX to;			/* upper limit of index list */

 {

   INDEX_LIST handle = 0;

   HEADER* hp;

   INODE* np;

   if (from <= 0 || from > to)	/* sanity check */

     return -1;

 /*** Find an inactive list header or allocate a new one. */

   for (hp = index_headers; handle < active_handles; hp++, handle++) {

     if (hp->original_size == 0)

       break;

   }

   if (handle == active_handles) {

     ++active_handles;

     if (handle == 0)

       index_headers = (HEADER*) malloc(active_handles * sizeof(HEADER));

     else

       index_headers = (HEADER*) realloc(index_headers, active_handles * sizeof(HEADER));

   }

   if (index_headers == NULL)

     return -1;

 /*** Fill in the list header and allocate space for the list. */

   hp = &index_headers[handle];

   hp->pseudo_size = hp->index_size = hp->original_size = to - from + 1;

   if (hp->original_size <= FLAG_LIMIT) { /* SMALL */

     hp->i.index_base = from;

     hp->p.flag = (FLAG*) malloc(hp->original_size * sizeof(FLAG));

     if (hp->p.flag == NULL)

       return -1;

     (void)memset((void *)hp->p.flag, 0, hp->original_size * sizeof(FLAG));

   } else {			/* LARGE */

     hp->i.index_nodes = 1;

     np = (INODE*) malloc(hp->original_size * sizeof(INODE));

     if (np == NULL)

       return -1;

     hp->p.first_node = np;

     np->base = from;

     np->count = hp->original_size;

     np->left_child = NULL;

   }

   return handle;

 }

 /*** Free an existing index list.  The header is zeroed afterwards

  *** to indicate that it can be reused.

  ***/

 void free_index_list(handle)

 INDEX_LIST handle;

 {

   HEADER* hp;

   if (handle < 0 || handle >= active_handles)	/* sanity check */

     return;

   hp = &index_headers[handle];

   if (hp->p.flag)

     free((void *)hp->p.flag);

   (void)memset((void *)hp, 0, sizeof(HEADER));

 }

 /*** Choose the integer at a certain position in an index list.  The

  *** integer is then removed from the list so that it won't be chosen

  *** again.  Choose_index returns 0 if the position is invalid.

  ***/

 INDEX choose_index(handle, position)

 INDEX_LIST handle;

 INDEX position;

 {

   HEADER* hp;

   FLAG* cp;

   INODE* np;

   INODE* npl;

   INODE* npr;

   INDEX index;

   if (handle < 0 || handle >= active_handles)	/* sanity checks */

     return 0;

   hp = &index_headers[handle];

   if (hp->p.flag == NULL)

     return 0;

   if (position < 1 || position > hp->index_size)

     return 0;

 /*** Adjust counts of remaining indices. */

   hp->index_size--;

   hp->pseudo_size--;

 /*** Find the index we want and remove it from the list. */

   if (hp->original_size <= FLAG_LIMIT) { /* SMALL */

     for (cp = hp->p.flag; position > 0; cp++)

       if (!*cp)

 	position--;

     *(--cp) = 1;

     return hp->i.index_base + (INDEX)(cp - hp->p.flag);

   } else {			/* LARGE */

     np = hp->p.first_node;

     while (np->left_child) {

       np->count--;

       np = np->left_child;

       if (position > np->count) {

 	position -= np->count;

 	np++;

       }

     }

     np->count--;

     if (position == 1) {	/* beginning of interval */

       index = np->base++;

     }

     else

     if (position > np->count) {	/* end of interval */

       index = np->base + np->count;

     }

     else			/* middle of interval - split it */

     {

       index = np->base + position - 1;

       npl = np->left_child = hp->p.first_node + hp->i.index_nodes;

       npr = npl + 1;

       hp->i.index_nodes += 2;

       npl->base = np->base;

       npl->count = position - 1;

       npl->left_child = NULL;

       npr->base = index + 1;

       npr->count = np->count - npl->count;

       npr->left_child = NULL;

     }

     return index;

   }

 }

 /*** Remove a particular integer from an index list.  If the integer

  *** does not exist in the list, we reduce the list's pseudo-size,

  *** but return no error indication.

  ***/

 void remove_index(handle, index)

 INDEX_LIST handle;

 INDEX index;

 {

   HEADER* hp;

   FLAG* cp;

   INODE* np;

   INODE* npl;

   INODE* npr;

   if (handle < 0 || handle >= active_handles)	/* sanity checks */

     return;

   hp = &index_headers[handle];

   if (hp->p.flag == NULL)

     return;

 /*** Adjust the pseudo-size before looking for the index. */

   hp->pseudo_size--;

 /*** Remove the index from the index list. */

   if (hp->original_size <= FLAG_LIMIT) { /* SMALL */

     if (index < hp->i.index_base || index >= hp->i.index_base + hp->original_size)

       return;

     cp = hp->p.flag + (index - hp->i.index_base);

     if (!*cp) {

       *cp = 1;

       hp->index_size--;

     }

     return;

   } else {			/* LARGE */

     np = hp->p.first_node;

     while (np->left_child) {

       np->count--;

       np = np->left_child + 1;

       if (index < np->base)

 	np--;

     }

     if (index < np->base || index >= np->base + np->count) { /* mistake - back out */

       np = hp->p.first_node;

       while (np->left_child) {

         np->count++;

 	np = np->left_child + 1;

 	if (index < np->base)

 	  np--;

       }

       return;

     }

     np->count--;

     if (index == np->base) {			/* beginning of interval */

       np->base++;

     }

     else

     if (index == np->base + np->count) {	/* end of interval */

     }

     else    	    	    			/* middle of interval - split it */

     {

       npl = np->left_child = hp->p.first_node + hp->i.index_nodes;

       npr = npl + 1;

       hp->i.index_nodes += 2;

       npl->base = np->base;

       npl->count = index - np->base;

       npl->left_child = NULL;

       npr->base = index + 1;

       npr->count = np->count - npl->count;

       npr->left_child = NULL;

     }

     hp->index_size--;

     return;

   }

 }

 /*** Return actual number of remaining entries in the index list.

  ***/

 INDEX index_size(handle)

 INDEX_LIST handle;

 {

   if (handle < 0 || handle >= active_handles)	/* sanity check */

     return 0;

   return index_headers[handle].index_size;

 }

 /*** Return a peculiar number, vaguely related to the number of

  *** remaining entries in the index list.  Required by NETGEN.

  ***/

 INDEX pseudo_size(handle)

 INDEX_LIST handle;

 {

   if (handle < 0 || handle >= active_handles)	/* sanity check */

     return 0;

   return index_headers[handle].pseudo_size;

 }