/********************************************************************** 
 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 <assert.h>
#include <stdlib.h>
#include <string.h>

#include "mem.h"
#include "genlist.h"

/************************************************************************
 Doubles the capacity of the current genlist data array.
 If there is no capacity, we set it to the initial list size.
************************************************************************/
static void genlist_resize(struct genlist *pgenlist) {
  pgenlist->data = fc_realloc(pgenlist->data,
                              (pgenlist->capacity * 2) * sizeof(void *));
  pgenlist->capacity *= 2;
}

/************************************************************************
 A simple linear search on the genlist data.  Return the index array
 of the data we found.  Return -1 if not found.
************************************************************************/
int genlist_find_index(struct genlist *pgenlist, void *data) {
  int i;

  for(i = 0;i < pgenlist->nelements;i++) {
    if(pgenlist->data[i] == data) {
      return i;
    }
  }

  return -1;
}

/************************************************************************
  Initialize a genlist.
  This should be called before the genlist is used in any other way.
************************************************************************/
void genlist_init(struct genlist *pgenlist)
{
  pgenlist->data = fc_malloc(INIT_LIST_SIZE * sizeof(void *));
  pgenlist->nelements = 0;
  pgenlist->capacity = INIT_LIST_SIZE;
}


/************************************************************************
  Returns the number of elements stored in the genlist.
************************************************************************/
int genlist_size(struct genlist *pgenlist)
{
  return pgenlist->nelements;
}


/************************************************************************
  Returns the user-data pointer stored in the genlist at the position
  given by 'idx'.  For idx out of range (including an empty list),
  returns 0 (the dataptr of null_link).
  Recall 'idx' can be -1 meaning the last element.
************************************************************************/
void *genlist_get(struct genlist *pgenlist, int idx)
{
  if((idx < -1) || (idx >= pgenlist->nelements))
    return NULL;

  if(idx == -1)
    idx = pgenlist->nelements - 1;

  return pgenlist->data[idx];
}


/************************************************************************
  Frees all the internal data used by the genlist (but doesn't touch
  the user-data).  At the end the state of the genlist will be the
  same as when genlist_init() is called on a new genlist.
************************************************************************/
void genlist_unlink_all(struct genlist *pgenlist)
{
  free(pgenlist->data);

  pgenlist->data = fc_malloc(INIT_LIST_SIZE * sizeof(void *));
  pgenlist->nelements = 0;
  pgenlist->capacity = INIT_LIST_SIZE;
}


/************************************************************************
  Remove an element of the genlist with the specified user-data pointer
  given by 'punlink'.  If there is no such element, does nothing.
  If there are multiple such elements, removes the first one.
************************************************************************/
void genlist_unlink(struct genlist *pgenlist, void *punlink)
{
  int i;
  int idx;

  idx = genlist_find_index(pgenlist, punlink);
  assert(idx != -1);
  if(idx == -1)  /* This shouldn't be a fatal flaw in a release version */
    return;

  /* Go through the list moving everything "down" one position.
   * It's safe to go past the new end of the array (the last i+1)
   * because that data is the old end of the array. */
  pgenlist->nelements--;
  for(i = idx;i < pgenlist->nelements;i++)
    pgenlist->data[i] = pgenlist->data[i+1];
}

/************************************************************************
  Insert a new element in the list, at position 'pos', with the specified
  user-data pointer 'data'.  Existing elements at >= pos are moved one
  space to the "right".  Recall 'pos' can be -1 meaning add at the
  end of the list.  For an empty list pos has no effect.
  A bad 'pos' value for a non-empty list is treated as -1 (is this
  a good idea?)
************************************************************************/
void genlist_insert(struct genlist *pgenlist, void *data, int pos)
{
  int i;

  if(pgenlist->nelements == pgenlist->capacity)
    genlist_resize(pgenlist);

  /* If the insert position is invalid, put the data onto the end. */
  if((pos < 0) || (pos >= pgenlist->nelements)) {
    pos = pgenlist->nelements;
  }

  /* Start at the end and move everything "up" one spot.
   * We start at the end so as not to overwrite anything as we go. */
  for(i = pgenlist->nelements;i > pos;i--)
    pgenlist->data[i] = pgenlist->data[i-1];
  pgenlist->data[pos] = data;

  pgenlist->nelements++;
}

/************************************************************************
  Initialize a genlist_iterator, for specified genlist and position
  of initial element.  If pos is out of range the link will be null_link
  (which will generally be interpreted as the iterator being finished).
  Recall 'pos' can be -1 meaning the last element.
************************************************************************/
void genlist_iterator_init(struct genlist_iterator *iter,
				struct genlist *pgenlist, int pos)
{
  iter->list = pgenlist;

  /* If the list is empty, any attempt to access the list should
   * be invalid. */
  if(!pgenlist->nelements) {
    iter->curr_pos = -1;
    iter->curr_data = NULL;
  }
  /* -1 means the end of the list */
  else if(pos == -1) {
    iter->curr_pos = pgenlist->nelements - 1;
    iter->curr_data = pgenlist->data[iter->curr_pos];
  }
  /* If the position is in bounds, then simply set the index and
   * the pointer to the correct positions. */
  else if((pos >= 0) && (pos < pgenlist->nelements)) {
    iter->curr_pos = pos;
    iter->curr_data = pgenlist->data[pos];
  }
  else {  /* We were given an invalid position index. */
    iter->curr_data = NULL;
    iter->curr_pos = -1;
  }
}

/************************************************************************
 Sort the elements of a genlist.
 
 The comparison function should be a function useable by qsort; note
 that the const void * arguments to compar should really be "pointers to
 void*", where the void* being pointed to are the genlist dataptrs.
 That is, there are two levels of indirection.
 Calling this function with compar==NULL does nothing, except to make
 it backwards-compatible with the old implementation.
************************************************************************/
void genlist_sort(struct genlist *pgenlist,
		  int (*compar)(const void *, const void *))
{
  assert(compar != NULL);
  if(compar == NULL)
    return;

  qsort(pgenlist->data, pgenlist->nelements, sizeof(void*), compar);
}

/************************************************************************
 Return the current pointer (if it exists).  We'll do some interesting
 management of the pointers to see if we can patch things up when items
 are removed from underneath us.
************************************************************************/
void *genlist_iterator_ptr(struct genlist_iterator *iter)
{
  int cp;

  cp = iter->curr_pos;
  if(!iter->curr_data) {
    return NULL;
  } else {
    if((cp >= 0) && (cp < iter->list->nelements)) {
      if(iter->curr_data != iter->list->data[cp]) {
        cp = genlist_find_index(iter->list, iter->curr_data);
      }
    } else {
      cp = genlist_find_index(iter->list, iter->curr_data);
    }
  }

  iter->curr_pos = cp;
  if(cp == -1) {
    iter->curr_data = NULL;
    return NULL;
  } else {
    iter->curr_data = iter->list->data[cp];
    return iter->curr_data;
  }
}

/************************************************************************
 Move the given iterator to the next position, with some "intelligent"
 management of where we are.
************************************************************************/
void genlist_iterator_next(struct genlist_iterator *iter)
{
  int cp;
  struct genlist *list;

  cp = iter->curr_pos;
  list = iter->list;
  if(!iter->curr_data) {
    cp = -1;
  } else {
    if((cp >= 0) && (cp < list->nelements)) {
      if(iter->curr_data != list->data[cp]) {
        cp = genlist_find_index(list, iter->curr_data);
      }
    } else {
      cp = genlist_find_index(list, iter->curr_data);
    }
  }

  if(cp == -1) {  /* For whatever reason, we couldn't find where we were
                   * before, or we were already at the end.  Either way,
                   * we still need to set this to be an invalid position.
                   */
    iter->curr_pos = -1;
    iter->curr_data = NULL;
  } else {
    if((cp + 1) == list->nelements) { /* Is the iteration going to take
                                       * us past the end of the list?  If
                                       * so, set it to be invalid. */
      iter->curr_pos = -1;
      iter->curr_data = NULL;
    } else {
      iter->curr_pos = cp + 1;
      iter->curr_data = list->data[cp + 1];
    }
  }
}

/************************************************************************
 Same as above, essentially.  Except it never gets called.
************************************************************************/
void genlist_iterator_prev(struct genlist_iterator *iter)
{
  int cp;
  struct genlist *list;

  cp = iter->curr_pos;
  list = iter->list;
  if(!iter->curr_data) {
    cp = -1;
  } else {
    if((cp >= 0) && (cp < list->nelements)) {
      if(iter->curr_data != list->data[cp]) {
        cp = genlist_find_index(list, iter->curr_data);
      }
    } else {
      cp = genlist_find_index(list, iter->curr_data);
    }
  }

  if(cp == -1) {  /* For whatever reason, we couldn't find where we were
                   * before, or we were already at the end.  Either way,
                   * we still need to set this to be an invalid position.
                   */
    iter->curr_pos = -1;
    iter->curr_data = NULL;
  } else {
    if(!cp) { /* Is the iteration going to take us past the start of
               * the list?  If so, set it to be invalid. */
      iter->curr_pos = -1;
      iter->curr_data = NULL;
    } else {
      iter->curr_pos = cp - 1;
      iter->curr_data = list->data[cp - 1];
    }
  }
}