/********************************************************************** 
 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.
***********************************************************************/
#ifndef FC__GENLIST_H
#define FC__GENLIST_H

/********************************************************************** 
  MODULE: genlist

  A "genlist" is a generic list stored as an array.  That is:
    generic:  stores (void*) pointers to arbitrary user data;
    array:    can be efficiently traversed both "forwards" and
                and "backwards", with quick indexing.
		    
  The list data structures are allocated dynamically, and list
  elements can be added or removed at arbitrary positions.
  
  Positions in the list are specified starting from 0, up to n-1
  for a list with n elements.  The position -1 can be used to
  refer to the last element (that is, the same as n-1, or n when
  adding a new element), but other negative numbers are not
  meaningful.

  There is a memory management issue:
  
  - The user-data pointed to by the genlist elements; these are
    entirely the user's responsibility, and the genlist code just
    treats these as opaque data, not doing any allocation or freeing.
    
  See also the speclist module.
***********************************************************************/

/* A genlist, storing the number of elements (for quick retrieval and
   testing for empty lists), the capacity of the current array, and an
   array of pointers to generic data.  We allow the array to grow in a
   transparent fashion so users don't have to worry about running out
   of space in their list.  This current implementation is somewhat bound
   to the old, inefficient implementation (hopefully we can phase out the
   iterators eventually and make programmers use the newer API -jdm).
*/
struct genlist {
  int nelements;
  int capacity;
  void **data;
};

/* A genlist iterator.  These will be horrendously inefficient for now.
   In time the ITERATOR_* macros will go away (hopefully). */
struct genlist_iterator {
  struct genlist *list;
  void *curr_data;
  int curr_pos;
};

int genlist_size(struct genlist *pgenlist);
void *genlist_get(struct genlist *pgenlist, int inx);
void genlist_init(struct genlist *pgenlist);
void genlist_unlink_all(struct genlist *pgenlist);
void genlist_insert(struct genlist *pgenlist, void *data, int pos);
void genlist_unlink(struct genlist *pgenlist, void *punlink);

void genlist_sort(struct genlist *pgenlist,
		  int (*compar)(const void *, const void *));

void genlist_iterator_init(struct genlist_iterator *iter,
				struct genlist *pgenlist, int pos);

/* These functions replace the old macros due to scoping problems
 * introduced when trying to 'emulate' linked-list behavior with an
 * array.  Yes, they're slower, but they're correct.  And provide
 * an incentive for programmers to use the stable iterators.
 */
void *genlist_iterator_ptr(struct genlist_iterator *iter);
void genlist_iterator_next(struct genlist_iterator *iter);
void genlist_iterator_prev(struct genlist_iterator *iter);

/* This will be pretty slow, but will hopefully decline as the use of
 * iterators are phased out over time. */
#define ITERATOR_PTR(X)  genlist_iterator_ptr(&(X))
#define ITERATOR_NEXT(X) genlist_iterator_next(&(X))
#define ITERATOR_PREV(X) genlist_iterator_prev(&(X))

/* This is to iterate for a type defined like:
     struct unit_list { struct genlist list; };
   where the pointers in the list are really pointers to "atype".
   Eg, see speclist.h, which is what this is really for.
*/
#define SAFE_TYPED_LIST_ITERATE(atype, typed_list, var, myiter) { \
  struct genlist_iterator myiter;                                 \
  atype *var;                                                     \
  genlist_iterator_init(&myiter, &(typed_list).list, 0);          \
  for(; ITERATOR_PTR(myiter);) {                                  \
    var=(atype *)ITERATOR_PTR(myiter);                            \
    ITERATOR_NEXT(myiter);
#define LIST_ITERATE_END }}

#define TYPED_LIST_ITERATE(atype, typed_list, var) \
  SAFE_TYPED_LIST_ITERATE(atype, (typed_list), var, myiter)

/* Same, but iterate backwards: */
#define SAFE_TYPED_LIST_ITERATE_REV(atype, typed_list, var, myiter) {  \
  struct genlist_iterator myiter;                                      \
  atype *var;                                                          \
  genlist_iterator_init(&myiter, &(typed_list).list, -1);              \
  for(; ITERATOR_PTR(myiter);) {                                       \
    var=(atype *)ITERATOR_PTR(myiter);                                 \
    ITERATOR_NEXT(myiter);
#define LIST_ITERATE_REV_END }}

#define TYPED_LIST_ITERATE_REV(atype, typed_list, var) \
  SAFE_TYPED_LIST_ITERATE_REV(atype, (typed_list), var, myiter)

/* The newer iteration functions (that don't use iterators).
 * These are faster and should become the standard soon.
 */
#define STABLE_TYPED_LIST_ITERATE(atype, typed_list, var) { \
  int _gitr;                                                \
  atype *var;                                               \
  void **arr = (typed_list).list.data;                      \
  for(_gitr=0;_gitr<(typed_list).list.nelements;_gitr++) {  \
    var=(atype *)arr[_gitr];
#define STABLE_TYPED_LIST_ITERATE_END }}

#define STABLE_TYPED_LIST_ITERATE_REV(atype, typed_list, var) { \
  atype *var;                                                   \
  int _gitr;                                                    \
  void **arr = (typed_list).list.data;                          \
  for(_gitr=(typed_list).list.nelements-1;_gitr>=0;_gitr--) {   \
    var=(atype *)arr[_gitr];
#define STABLE_TYPED_LIST_ITERATE_REV_END  }}

#define INIT_LIST_SIZE 8

#endif  /* FC__GENLIST_H */