/*
 * 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 pl_bits[], is used to store 
 * the bit for each square.
 *
 * For example: the bit for square 45 is stored in pl_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 the
 * following of a pointer.
 *
 * In order 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 pl_lists[]. Each byte of the bitmap (see above) is 
 * an index into pl_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();


u_long   pl_bits[100];
Sqcell   *pl_lists[256];


/*
 * Do all things necessary to use the sqlist package. This includes
 * generating the lists in pl_lists[] and the bits in pl_bits[]. 
 * It is necessary to be careful when generating pl_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 pl_bits[]. */
    chnum = 0;
    for (i = 1; i <= 8; ++i) {
	bit.l = 0;
	bit.c[chnum] = 0x80;
	for (j = 1; j <= 8; ++j) {
	    pl_bits[i * 10 + j] = bit.l;
	    bit.c[chnum] >>= 1;
	}

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

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



/************************* Queue ******************************/


/*
 * 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;

    p = queue->first; 
    while (p != NULL && p->sq != sq)
	p = p->next;

    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 cell into the free list. */
    pc->next = old_squares;
    old_squares = pc;

    return sq;
}



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

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