/* Copyright (C) 2000-2003 Markus Lausser (sgop@users.sf.net)
   This is free software distributed under the terms of the
   GNU Public License.  See the file COPYING for details. */

#include <stdlib.h>

#include "lopster.h"

struct _sarray_t {
  int (*compare)(void*, void*);
  void (*delete)(void*);
  void** array;
  int allocated;
  int size;
};

sarray_t* sarray_new(int (*comp)(void*, void*),
		     void (*del)(void*)) {
  sarray_t* array;

  array = g_malloc(sizeof(*array));
  array->compare = comp;
  array->delete = del;
  array->array = NULL;
  array->allocated = 0;
  array->size = 0;
  return array;
}

int sarray_size(sarray_t* array) {
  return array->size;
}

void* sarray_find(sarray_t* array, void* item) {
  int start, stop, mid, comp;

  if (array->size == 0) return NULL;
  start = 0; 
  stop = array->size-1;
  while (start != stop) {
    mid = (start+stop)/2;
    comp = array->compare(item, array->array[mid]);
    if (comp < 0) stop = mid;
    else if (comp > 0) start = mid+1;
    else return array->array[mid];
  }
  comp = array->compare(item, array->array[start]);
  if (comp == 0) return array->array[start];
  else return NULL;
}

static int sarray_find_pos(sarray_t* array, void* item) {
  int start, stop, mid, comp;

  if (array->size == 0) return 0;
  start = 0; 
  stop = array->size-1;
  while (start != stop) {
    mid = (start+stop)/2;
    comp = array->compare(item, array->array[mid]);
    if (comp < 0) stop = mid;
    else start = mid+1;
  }
  comp = array->compare(item, array->array[start]);
  if (comp < 0) return start;
  else return start+1;
}

void sarray_insert(sarray_t* array, void* item) {
  int pos, i1;

  pos = sarray_find_pos(array, item);
  if (array->size >= array->allocated) {
    array->array = g_realloc(array->array,
			     sizeof(void*)*(array->allocated + 10));
    array->allocated += 10;
  }
  
  i1 = array->size;
  while (i1 > pos) {
    array->array[i1] = array->array[i1-1];
    i1--;
  }
  array->array[pos] = item;
  array->size++;
}

void* sarray_item(sarray_t* array, int num) {
  if (num >= array->size || num < 0) return NULL;
  return array->array[num];
}

void sarray_clear(sarray_t* array) {
  int i1;

  if (array->size == 0) return;
  for (i1 = 0; i1 < array->size; i1++) {
    array->delete(array->array[i1]);
  }
  array->size = 0;
  if (array->array) g_free(array->array);
  array->array = NULL;
  array->allocated = 0;
}

void sarray_remove(sarray_t* array, int pos) {
  int i1;

  if (pos < 0 || pos >= array->size) return;
  array->delete(array->array[pos]);
  for (i1 = pos; i1 < array->size-1; i1++) {
    array->array[i1] = array->array[i1+1];
  }
  array->size--;
}

void sarray_remove_link(sarray_t* array, void* item) {
  int i1;

  for (i1 = 0; i1 < array->size; i1++) {
    if (array->array[i1] == item) {
      sarray_remove(array, i1);
      return;
    }
  }
}

void sarray_destroy(sarray_t* array) {
  sarray_clear(array);
  g_free(array);
}