/* PSPP - computes sample statistics.
   Copyright (C) 2004 Free Software Foundation, Inc.
   Written by Ben Pfaff <address@hidden>.

   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 of the
   License, 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.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
   02111-1307, USA. */

#ifndef list_h
#define list_h 1

struct list_elem
  {
    struct list_elem *next, *prev;
  };

struct list
  {
    struct list_elem elem;
  };

typedef int list_compare_func (const struct list_elem *a,
                               const struct list_elem *b,
                               void *aux);

void list_init (struct list *);

/* Stack- and queue-like behavior. */
void list_push_front (struct list *, struct list_elem *);
void list_push_back (struct list *, struct list_elem *);
struct list_elem *list_pop_front (struct list *);
struct list_elem *list_pop_back (struct list *);
struct list_elem *list_front (struct list *);
struct list_elem *list_back (struct list *);

/* Generalized insertion and removal. */
void list_insert (struct list_elem *before, struct list_elem *new_elem);
void list_splice (struct list_elem *before,
                  struct list_elem *first, struct list_elem *last);
void list_swap (struct list_elem *, struct list_elem *);
struct list_elem *list_remove (struct list_elem *);

/* Properties. */
size_t list_size (struct list *);
bool list_empty (struct list *);

/* Non-mutating algorithms. */
struct list_elem *
list_find (const struct list_elem *first, const struct list_elem *last,
           const struct list_elem *target);
size_t
list_count_equal (const struct list_elem *first, const struct list_elem *last,
                  const struct list_elem *target,
                  list_compare_func *compare, void *aux);
size_t
list_count_if (const struct list_elem *first, const struct list_elem *last,
               list_predicate_func *predicate, void *aux);
                   

/* Other. */
void list_reverse (struct list *);

/* Sorted list functions. */
void
list_sort (struct list *list,
           list_compare_func *compare, void *aux);
bool 
list_is_sorted (const struct list_elem *first, const struct list_elem *last,
                list_compare_func *compare, void *aux);
void 
list_unique (struct list *list, struct list *dups,
             list_compare_func *, void *aux);
void 
list_sort_unique (struct list *list, struct list *dups,
                  list_compare_func *, void *aux);
void
list_merge (struct list *dst, struct list *src,
            list_compare_func *compare, void *aux);
void
list_insert_ordered (struct list_elem *dst_first, struct list_elem *dst_last,
                     struct list_elem *new_elem,
                     list_compare_func *, void *aux);
struct list_elem *
list_partition (struct list *list,
                list_predicate_func *predicate, void *aux);
struct list_elem *
list_is_partitioned (const struct list_elem *first,
                     const struct list_elem *last,
                     list_predicate_func *predicate, void *aux);
size_t
list_remove_equal (struct list *list, struct list_elem *element,
                   list_compare_func *compare, void *aux);
int
list_lexicographical_compare_3way (const struct list_elem *a_first,
                                   const struct list_elem *a_last, 
                                   const struct list_elem *b_first,
                                   const struct list_elem *b_last, 
                                   list_compare_func *compare, void *aux);
struct list_elem *
list_adjacent_find_equal (const struct list_elem *first,
                          const struct list_elem *last,
                          list_compare_func *compare, void *aux);
                          

#endif /* dlist.h */