/********************************************************************** 
 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(void *);
  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;
  void **arr;

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

  /* Not found */
  return -1;
}

void sortlist_init(struct sortlist *slist)
{
  slist->data = fc_malloc(INIT_SORT_SIZE * sizeof(void *));
  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];
}

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

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

  arr = slist->data;

  /* Move everything down one link */
  num_bytes = (slist->num_links - old_idx - 1) * sizeof(void *);
  if(num_bytes)
    memmove(&(arr[old_idx+1]), &(arr[old_idx]), num_bytes);

  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(void *));
  slist->num_links = 0;
  slist->capacity = INIT_SORT_SIZE;
}

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

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

  arr = slist->data;
  while(low <= high) {
    mid = (high + low) / 2;
    if(data < arr[mid])
      high = mid - 1;
    else if(data > arr[mid])
      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]) {
    /* Move everything *including* 'mid' "up" */
    num_bytes = (slist->num_links - mid) * sizeof(void *);
    if(num_bytes)
      memmove(&(arr[mid+1]), &(arr[mid]), num_bytes);

    arr[mid] = data;
  }
  else {
    /* Move everything *after* the 'mid' position "up" */
    num_bytes = (slist->num_links - mid - 1) * sizeof(void *);
    if(num_bytes)
      memmove(&(arr[mid+2]), &(arr[mid+1]), num_bytes);

    arr[mid+1] = data;
  }

  slist->num_links++;
}