/*
 * This file implements efficient handling of lists (or rather
 * sets) of othello squares. Since there are only 64 squares on
 * an othello board, the set can be represented as a bitmap with
 * 64 bits, i e two longs of 32 bits each.
 *
 * The bitmap is represented as a union between 8 bytes
 * (unsigned char) and 2 unsigned longs. The bytes are used when
 * the lists are traversed (see below) and the longs are used
 * when manipulating the lists in other ways, thus providing a
 * way to handle bigger chunks of bits at the same time (32
 * instead of 8).
 *
 * Most operations, such as copying, are very fast with this
 * representation, but a few exceptions exist. Therefore a few
 * optimizations have to be made:
 *
 * The mapping between a square's number and the bit
 * representing it is complicated because the squares on the
 * board are not contiguous. The squares 0-10, 20, 29, 30, and
 * so on, i.e.  those just outside the border, will not be
 * represented in the bitmaps. Only those on the board, i.e.
 * 11-19, 21-29 etc are represented since there is no room for
 * the others in 64 bits.  A table of unsigned long, called
 * sl_bits[], is used to store the bit for each square.
 *
 * For example: the bit for square 45 is stored in sl_bits[45].
 *
 * The other operation that is rather slow with bitmaps is
 * traversal.  Sometimes we will have to go through the list and
 * since there is no faster way of traversing than following a
 * linked list, we use such a list. Thus, the only operation
 * needed in going from one square to the next is to follow a
 * pointer.
 *
 * To achieve a performance as close to the linked list
 * performance as possible we precompute 256 different lists and
 * store the pointers to the first element of each list into the
 * table sl_lists[]. Each byte of the bitmap (see above) is an
 * index into sl_lists[], and the square represented at each
 * element in the list is (row number) * 10 + (the number in the
 * list cell).  The most significant bit in each byte represents
 * square number 1 in each row, and the least significant bit is
 * square number 8.
 *
 * An example: The hexadecimal number 0x31 in one of the bytes would
 * represent the following squares: 3 4 8.
 */

#include <stdio.h>
#ifdef __GNUC__
#include "clib.h"
#endif
#include "sqlist.h"


/* Forward declaration. */
static Sqcell *cons();

/* Se documentation above */
u_long    sl_bits[100];
Sqcell  * sl_lists[256];


/*
 * Do all things necessary to use the sqlist package. This includes
 * generating the lists in sl_lists[] and the bits in sl_bits[]. 
 * It is necessary to be careful when generating sl_bits, so that
 * the code will work on both big-endian and small-endian machines.
 */

void
init_sqlists()
{
    int   i;
    int   j;
    union { u_long l; u_char c[4]; }   bit;
    int   bitnr;
    int   chnum;

    /* Generate the bits in sl_bits[]. */
    chnum = 0;
    for (i = 1; i <= 8; ++i) {
	bit.l = 0;
	bit.c[chnum] = 0x80;
	for (j = 1; j <= 8; ++j) {
	    sl_bits[i * 10 + j] = bit.l;
	    bit.c[chnum] >>= 1;
	}

	++chnum;
	if (chnum == 4)
	    chnum = 0;
    }

    /* Generate sl_lists[]. */
    for (i = 0; i < 256; ++i) {
	sl_lists[i] = NULL;
	for (bitnr = 7; bitnr >= 0; --bitnr) {
	    if ((i & (1 << bitnr)) != 0)
		sl_lists[i] = cons(sl_lists[i], 8 - bitnr);
	}
    }
}


/* ================================================================ */

/*
 * Operations on a queue of squares. This is used in calculation
 * of stable pieces.
 */


/*
 * We want to free() and malloc() as little as possible, so
 * all used square cells are saved in a single linked list
 * to be reused later. 'old_squares' is the head of this list.
 */

static Sqcell  * old_squares = NULL;



/*
 * Return a pointer to a square cell. If there are no old
 * cells to reuse, use malloc() to get one. Set the 'next' field 
 * of the cell to NULL.
 */

static Sqcell *
alloc_sq()
{
    Sqcell   *sq;

    /* Reuse an old cell if possible. */
    if (old_squares == NULL) {
	sq = (Sqcell *) malloc(sizeof(Sqcell));
	if (sq == NULL) {
	    fprintf(stderr, "Couldn't allocate space for a sqcell\n");
	    exit(1);
	}
    } else {
	sq = old_squares;
	old_squares = old_squares->next;
    }

    sq->next = NULL;
    return sq;
}



/*
 * Take a list and a square and return the list with the
 * square entered as the first element.
 */

static Sqcell *
cons(list, sq)
Sqcell  * list;
Square    sq;
{
    Sqcell  * p;

    p = alloc_sq();
    p->sq = sq;
    p->next = list;
    return p;
}



/*
 * If the square SQ is not already in QUEUE, put SQ
 * last in QUEUE. Otherwise do nothing.
 */

void
queue(queue, sq)
Sqqueue  * queue;
Square     sq;
{
    Sqcell  * p;

    /* Find the place to enter sq... */
    p = queue->first; 
    while (p != NULL && p->sq != sq)
	p = p->next;

    /* ...and enter it. */
    if (p == NULL) {
	p = alloc_sq();
	p->sq = sq;
	if (queue->first == NULL) {
	    queue->first = p;
	    queue->last = p;
	} else {
	    queue->last->next = p;
	    queue->last = p;
	}
    }
}



/*
 * If QUEUE is not empty, then return the first square in
 * the queue and delete the square from it. Otherwise return
 * a PASS.
 */

Square
dequeue_first(queue)
Sqqueue   *queue;
{
    Square   sq;
    Sqcell    *pc;

    if (emptyqueue(queue))
	return PASS;
    pc = queue->first;
    sq = pc->sq;

    queue->first = pc->next;
    if (queue->first == NULL)
	queue->last = NULL;

    /* Link the deleted cell into the free list. */
    pc->next = old_squares;
    old_squares = pc;

    return sq;
}



/*
 * Print the contents of LIST. This is used for debugging purposes.
 */

void
printlist(list)
Sqlist   list;
{
    Square   sq;
    sl_traverse(pp);

    for_all_in_sqlist(list,pp,sq) {
	printf("%3d", sq);
    }
    putchar('\n');
}