/********************************************************************** 
 Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
***********************************************************************/

#include <string.h>

#include "mem.h"
#include "sortlist.h"

/* What happens when we need more storage space */
static void resize_sortlist(struct sortlist *slist)
{
  int new_size = slist->capacity * 2 * sizeof(struct sortlist_link);
  slist->data = fc_realloc(slist->data, new_size);
  slist->capacity *= 2;
}

static int find_element_index(struct sortlist *slist, void *data)
{
  int low = 0, mid = 0;
  int high = slist->num_links - 1;
  struct sortlist_link *arr;

  arr = slist->data;
  while(low <= high) {
    mid = (high + low) / 2;
    if(data < arr[mid].dataptr)
      high = mid - 1;
    else if(data > arr[mid].dataptr)
      low = mid + 1;
    else
      return mid;
  }

  /* Not found */
  return -1;
}

void sortlist_init(struct sortlist *slist)
{
  slist->data = fc_malloc(INIT_SORT_SIZE * sizeof(struct sortlist_link));
  slist->num_links = 0;
  slist->capacity = INIT_SORT_SIZE;
}

int sortlist_size(struct sortlist *slist)
{
  return slist->num_links;
}

void* sortlist_get(struct sortlist *slist, int idx)
{
  if((idx <= 0) || (idx >= slist->num_links))
    return NULL;

  return slist->data[idx].dataptr;
}

void sortlist_unlink(struct sortlist *slist, void *olddata)
{
  int i;
  int old_idx;
  struct sortlist_link *arr;

  old_idx = find_element_index(slist, olddata);
  if(old_idx == -1)
    return;

  arr = slist->data;
  for(i = old_idx;i < (slist->num_links - 1);i++)
    memcpy(&(arr[i]), &(arr[i+1]), sizeof(struct sortlist_link));

  slist->num_links--;
}

/********************************************************************** 
 Frees the array of sortlist_links but doesn't touch the data.
 Leaves the array the same size as it is after sortlist_init.
**********************************************************************/
void sortlist_unlink_all(struct sortlist *slist)
{
  fc_free(slist->data);
  slist->data = fc_malloc(INIT_SORT_SIZE * sizeof(struct sortlist_link));
  slist->num_links = 0;
  slist->capacity = INIT_SORT_SIZE;
}

void sortlist_insert(struct sortlist *slist, void *data)
{
  int low = 0, mid = 0;
  int high = slist->num_links - 1;
  struct sortlist_link *arr;

  if(slist->capacity == slist->num_links)
    resize_sortlist(slist);

  arr = slist->data;
  while(low <= high) {
    mid = (high + low) / 2;
    if(data < arr[mid].dataptr)
      high = mid - 1;
    else if(data > arr[mid].dataptr)
      low = mid + 1;
    else
      break;
  }

  /* Regardless of how we broke out of the loop, 'mid' is the index
   * where the data "should" go.  If data is <= arr[mid], we need to
   * prepend this data into the array by shuffling everything back one.
   * If data is > arr[mid], it needs to go immediately after it.
   */
  if(data <= arr[mid].dataptr) {
    int i;

    /* Start at the back and copy everything "up" one position */
    for(i = (slist->num_links);i > mid;i--)
      memcpy(&(arr[i]), &(arr[i-1]), sizeof(struct sortlist_link));

    arr[mid].dataptr = data;
  }
  else {
    int i;

    /* Start at the back and copy everything up one, but stop before
     * we get to the 'mid' position. */
    for(i = (slist->num_links);i > (mid+1);i--)
      memcpy(&(arr[i]), &(arr[i-1]), sizeof(struct sortlist_link));

    arr[mid+1].dataptr = data;
  }

  slist->num_links++;
}

struct sortlist_link* find_sortlist_position(struct sortlist *slist, int pos)
{
  if((pos < 0) || (pos >= slist->num_links))
    return NULL;

  return &(slist->data[pos]);
}