#include <stdio.h>

#include <stdlib.h>
#include <time.h>
#include "conf.h"
#include "dir.h"
#include "mem.h"
#include "queue.h"


/* Return item from position pos in queue or -1 on out of range
 */

int queue_get_item (struct QUEUE *q, int pos)
{
  if (pos < q->items) {
    pos += q->pos;
    if (pos >= q->size)
      pos -= q->size;
    return q->base[pos];
  }
  return -1;
}


/* Return position of item in queue or -1 for no match
 */

int queue_search_for_item (struct QUEUE *q, int item)
{
  int i, j = q->pos;
  
  for (i=0;i<q->items;i++) {
    if (j == q->size)
      j -= q->size;
    if (q->base[j] == item)
      return i;
    j++;
  }
  return -1;
}


/* Prepend item to queue
 */

void queue_prepend (struct QUEUE *q, struct DIR_INFO *d, int item)
{
  if (d->item[item].queued)
    return;
  else
    d->item[item].queued = 1;
  
  if (q->pos > 0)
    q->pos--;
  else
    q->pos = q->size - 1;
  
  q->base[q->pos] = item;
  q->items++;
}

/* Append item to queue
 */

void queue_append (struct QUEUE *q, struct DIR_INFO *d, int item)
{
  int pos;
  
  if (d->item[item].queued)
    return;
  else
    d->item[item].queued = 1;
  
  pos = q->pos + q->items;
  if (pos >= q->size)
    pos -= q->size;
  
  q->base[pos] = item;
  q->items++;
}


/* Append every item under directory item to queue 
 */

void queue_append_dir (struct QUEUE *q, struct DIR_INFO *d, int item)
{
  int pos = 0, n = 0, ms, *list = 0, parent, child;
  
  ms = 100;
  mem_resize ((void **)&list, ms * sizeof(int));
  list[n++] = item;
  
  do {
    parent = list[pos++];
    child = -1;
    while ((child = dir_match_parent (d, parent, child + 1)) != -1) {
      if (d->item[child].type) {
	queue_append (q, d, child);
      } else {
	if (n == ms) {
	  ms += 100;
	  mem_resize ((void **)&list, ms * sizeof(int));
	}
	list[n++] = child;
      }
    }
  } while (pos < n);
  free (list);
}


/* Delete top item from queue
 */

void queue_skip (struct QUEUE *q, struct DIR_INFO *d)
{
  if (q->items) {
    d->item[q->base[q->pos]].queued = 0;
    q->items--;
    q->pos++;
    if (q->pos == q->size)
      q->pos = 0;
  }
}


/* Delete item from position pos from queue
 */

void queue_delete (struct QUEUE *q, struct DIR_INFO *d, int pos)
{
  int move, pos2;
  
  if (pos < q->items) {
    move = q->items - pos - 1;
    pos += q->pos;
    pos2 = pos + 1;    
    
    if (pos >= q->size)
      pos -= q->size;
    d->item[q->base[pos]].queued = 0;
    
    while (move) {
      if (pos >= q->size)
        pos -= q->size;
      if (pos2 >= q->size)
        pos2 -= q->size;
      q->base[pos++] = q->base[pos2++];
      move--;
    }
    q->items--;
  }
}


/* Delete every item under directory item from queue
 */

void queue_delete_dir (struct QUEUE *q, struct DIR_INFO *d, int item)
{
  int pos = 0, n = 0, ms, *list = 0, parent, child, ipos;
  
  ms = 100;
  mem_resize ((void **)&list, ms * sizeof(int));
  list[n++] = item;
  
  do {
    parent = list[pos++];
    child = -1;
    while ((child = dir_match_parent (d, parent, child + 1)) != -1) {
      if (d->item[child].type) {
	ipos = queue_search_for_item (q, child);
	if (ipos != -1)
	  queue_delete (q, d, ipos);
      } else {
	if (n == ms) {
	  ms += 100;
	  mem_resize ((void **)&list, ms * sizeof(int));
	}
	list[n++] = child;
      }
    }
  } while (pos < n);
  free (list);
}


/* Clear queue
 */

void queue_clear (struct QUEUE *q, struct DIR_INFO *d)
{
  int i, item;
  
  for (i=0; i<q->items; i++) {
    item =  queue_get_item (q, i);
    d->item[item].queued = 0;
  }
  q->pos = 0;
  q->items = 0;
}


/* Rotate integer val n steps
 */

static unsigned int ror (unsigned int val, int n)
{
  int bits = sizeof(int) * 8;
  
  n %= bits;
  return ((val >> n) | (val << (bits - n)));
}


/* Shuffle items in queue
 */

void queue_shuffle (struct QUEUE *q, struct DIR_INFO *d)
{
  int items = q->items, mod = items, count,
      *m = 0, *m2 = 0, rnd, item, i, j;
  
  mem_resize ((void **)&m, items * sizeof(int));
  mem_resize ((void **)&m2, items * sizeof(int));
  for (i=0; i<items; i++)
    m[i] = queue_get_item (q, i);
  
  for (i=0; i<items; i++) {
    rnd = ror (random (), 16) % mod;
    count = 0;
    for (j=0; j<items; j++) {
      item = m[j];
      if (item != -1)
	count++;
      if (count > rnd) {
	m[j] = -1;
	m2[i] = item;
	break;
      }
    }
    mod--;
  }
  queue_clear (q, d);
  for (i=0; i<items; i++)
    queue_append (q, d, m2[i]);
  
  free (m);
  free (m2);
}


/* Allocate memory and seed the random number generator
 */

void queue_init (struct QUEUE *q, struct DIR_INFO *d)
{
  mem_resize ((void **)&q->base, d->files * sizeof (int));
  srandom ((int)time (0));
  q->size = d->files; 
}