/*
 *   Pure Data Packet header file. List class
 *   Copyright (c) by Tom Schouten <tom@zwizwa.be>
 *
 *   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., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 */

/* who can live without a list, hmm? 

   this is sorth of a compromise between lists, queues,
   stacks, lisp and forth. list contain pf atoms
   (floats, ints, symbols, pointers, packets or lists) */


#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <pf/list.h>
#include <pf/symbol.h>
#include <pf/packet.h>
#include <pf/type.h>
#include <pf/typedefs.h>
#include <pf/mem.h>
#include <pf/stream.h>
#include <pf/debug.h>

#include <pf/macros.h>


#define D if (0)

/* ALLOC / DEALLOC */

static pf_atom_t *atoms;
static pf_list_t *lists;

// this file should really be the only file that has access to the
// internals of the atom and list structures.

//#define PF_SETTER(strct, name, type, member)				
//    static inline void pf_##strct##_set_##name(pf_atom_t *a, type member) 
//    { a-> member = member ; }



#if PF_LIST_OLD
//PF_SETTER(atom, next, pf_atom_t*, next)
//PF_SETTER(atom, word, pf_word_t, w)

static inline void pf_atom_set_next(pf_atom_t *a, pf_atom_t *n) { a->next = n; }
static inline void pf_atom_set_word(pf_atom_t *a, pf_word_t w) { a->w = w; }
static inline void pf_atom_set_type(pf_atom_t *a, pf_word_type_t t) { a->t = t; }

static inline void pf_list_set_first(pf_list_t *l, pf_atom_t *a) { l->first = a; }
static inline void pf_list_set_last(pf_list_t *l, pf_atom_t *a) { l->last = a; }
static inline void pf_list_set_elements(pf_list_t *l, int e) { l->elements = e; }

#else

static inline void pf_atom_set_next(pf_atom_t *a, pf_atom_t *n) { a->_next = n; }
static inline void pf_atom_set_word(pf_atom_t *a, pf_word_t w) { a->_w = w; }
static inline void pf_atom_set_type(pf_atom_t *a, pf_word_type_t t) { a->_t = t; }

static inline void pf_list_set_first(pf_list_t *l, pf_atom_t *a) { l->_first = a; }
static inline void pf_list_set_last(pf_list_t *l, pf_atom_t *a) { l->_last = a; }
static inline void pf_list_set_elements(pf_list_t *l, int e) { l->_elements = e; }

#endif

#define SET_NEXT pf_atom_set_next
#define SET_TYPE pf_atom_set_type
#define SET_WORD(a,w) pf_atom_set_word(a, ((pf_word_t)w))

#define SET_FIRST    pf_list_set_first
#define SET_LAST     pf_list_set_last
#define SET_ELEMENTS pf_list_set_elements


static inline void SET_WPACKET(pf_atom_t *a, pf_packet_t p) { 
    SET_WORD(a, p); 
}
static inline void SET_WSYMBOL(pf_atom_t *a, pf_symbol_t *s) { 
    SET_WORD(a, s); 
}
static inline void SET_WLIST(pf_atom_t *a, pf_list_t *l) { 
    SET_WORD(a, l); 
}
static inline void COPY_W(pf_atom_t *dst, pf_atom_t *src){
    SET_WORD(dst, WORD(src));
}

#define NEW_ATOM(t, w) ({pf_atom_t *a = pf_atom_new(); SET_TYPE(a, t); SET_WORD(a, w); a;})

pf_atom_t *pf_atom_new(void){
    pf_atom_t *a;
    if (atoms){
	a = atoms;
	atoms = NEXT(atoms);
      gotit:
	SET_TYPE(a, a_undef);
	SET_WORD(a, -1);
	SET_NEXT(a, 0);
	return a;
    }
    a = pf_alloc(sizeof(*a));
    goto gotit;
}

void pf_atom_free(pf_atom_t *a){
    SET_TYPE(a, a_stale);
    SET_NEXT(a, atoms);
    atoms = a;
}

pf_list_t *pf_list_new(void){
    pf_list_t *l;
    if (lists){
	l = lists;
	lists = (pf_list_t*)FIRST(lists);
      gotit:
	SET_ELEMENTS(l, 0);
	SET_FIRST(l, 0);
	SET_LAST(l, 0);
	return l;
    }
    l = pf_alloc(sizeof(*l));
    goto gotit;
}

static void empty_list_free(pf_list_t *l){
    ASSERT(ELEMENTS(l) == 0);
    ASSERT(FIRST(l) == 0);
    ASSERT(LAST(l) == 0);
    SET_FIRST(l, (pf_atom_t *)lists);
    lists = l;
}


#define DEALLOC empty_list_free


#define DOCASE(x) case x: return #x ;
char *pf_type(pf_word_type_t t){
    switch(t){
	DOCASE(a_undef);
	DOCASE(a_int);
	DOCASE(a_float);
	DOCASE(a_list);
	DOCASE(a_atom_pointer);
	DOCASE(a_packet);
    default:
	return "unknown";
    }
}



/* list pool setup */
void pf_list_setup(void)
{
    atoms = 0;
    lists = 0;
}




/* atom manips 
   these are only well-defined in relation to stacks (refcount managed)
   meaning: all lists encountered in atoms are treated as stacks
 */

/*
  IMPORANT NOTE:
  code cannot be duplicated. trying to do so will result in the
  copy being a symbol '#<ghost>'
 */

static int iscode(pf_atom_t *a){
    return (a && 
	    (TYPE(a) == a_list) &&
	    (LAST(WLIST(a))) &&
	    (TYPE(LAST(WLIST(a))) == a_forth_sentinel)) ;
}

// CENTRAL REFCOUNT MANAGEMENT
pf_atom_t *pf_stackatom_dup(pf_atom_t *a){
    ASSERT(a);
    pf_atom_t *b = pf_atom_new();
    SET_TYPE(b, TYPE(a));
    if (TYPE(a) == a_packet) {
	SET_WPACKET(b, pf_packet_register(WPACKET(a)));
    }
    else if (iscode(a)){
	SET_WSYMBOL(b, pf_symbol("#<ghost>"));
    }
    else if (pf_atom_islist(a)){
	SET_WLIST(b, pf_stack_copy(WLIST(a)));
    }
    else COPY_W(b, a);
    return b;
}

void pf_stackatom_clear(pf_atom_t *a){
    ASSERT(a);
    if (TYPE(a) == a_packet) pf_packet_unregister(WPACKET(a));
    else if (pf_atom_islist(a)) pf_stack_free(WLIST(a));
    SET_TYPE(a, a_stale);  // this is used by safe-drop
    SET_WORD(a, -1);
}

void pf_stackatom_drop(pf_atom_t *a){
    ASSERT(a);
    pf_stackatom_clear(a);
    pf_atom_free(a);
}


/* LIST / TREE / STACK manips

list: operates on flat list structure
tree: operates recursively on lists
stack: same as tree, but does refcount management

 */

/* NEW */
pf_list_t* pf_tree_new(void) { return pf_list_new(); }
pf_list_t* pf_stack_new(void) { return pf_list_new(); }


#define ASSERT_EMPTY(l) { \
	ASSERT(FIRST(l) == 0); \
	ASSERT(LAST(l) == 0); \
	ASSERT(ELEMENTS(l) == 0); \
}

/* CLEAR */
void pf_list_clear(pf_list_t *l)
{
    ASSERT(l);
    pf_atom_t *a;
    while (a = pf_list_pop_atom(l)){
	pf_atom_free(a);
    }
}

void pf_tree_clear(pf_list_t *l)
{
    ASSERT(l);
    pf_atom_t *a;

    while (a = pf_list_pop_atom(l)){
	if (pf_atom_islist(a)) pf_tree_free(WLIST(a));
	pf_atom_free(a);
    }
    ASSERT_EMPTY(l);
}

void pf_stack_clear(pf_list_t *l){
    ASSERT(l);
    pf_atom_t *a;

    while (a = pf_list_pop_atom(l)) pf_stackatom_drop(a);
    ASSERT_EMPTY(l);
}

/* FREE */
void pf_list_free(pf_list_t *l) { pf_list_clear(l); DEALLOC(l); }
void pf_tree_free(pf_list_t *l) { pf_tree_clear(l); DEALLOC(l); }
void pf_stack_free(pf_list_t *l) { pf_stack_clear(l); DEALLOC(l); }



/* PUSH */


/* add a atom/word to the start of the list
   for tree -> add atom
   for stack -> dup+add atom
 */
void pf_list_push_atom(pf_list_t *l, pf_atom_t *a)
{
    SET_NEXT(a, FIRST(l));
    if (!LAST(l)) SET_LAST(l, a);
    SET_FIRST(l, a);
    SET_ELEMENTS(l, 1 + ELEMENTS(l));
}


void pf_list_push(pf_list_t *l, pf_word_type_t t, pf_word_t w)
{
    pf_list_push_atom(l, NEW_ATOM(t,w));
}

void pf_tree_push_atom(pf_list_t *l, pf_atom_t *a) { pf_list_push_atom(l, a); }
void pf_stack_push_atom(pf_list_t *l, pf_atom_t *a) { pf_list_push_atom(l, pf_stackatom_dup(a)); }


/* QUEUE */

/*
  for stacks, the queued element is dupped
*/

/* add a word to the end of the list */
void pf_list_queue_atom(pf_list_t *l, pf_atom_t *a)
{
    SET_NEXT(a, 0);
    if (LAST(l)) SET_NEXT(LAST(l), a);
    else SET_FIRST(l, a);
    SET_LAST(l, a);
    SET_ELEMENTS(l, 1 + ELEMENTS(l));
}
void pf_tree_queue_atom(pf_list_t *l, pf_atom_t *a) { pf_list_queue_atom(l, a); }


void pf_stack_queue_atom(pf_list_t *l, pf_atom_t *a) { pf_list_queue_atom(l, pf_stackatom_dup(a)); }

void pf_list_queue(pf_list_t *l, pf_word_type_t t, pf_word_t w){
    pf_list_queue_atom(l, NEW_ATOM(t, w));
}
void pf_tree_queue(pf_list_t *l, pf_word_type_t t, pf_word_t w){ pf_list_queue(l, t, w); }

void pf_list_insert_atom(pf_list_t *l, int n, pf_atom_t *a){
    ASSERT(n >= 0);
    ASSERT(n <= ELEMENTS(l));
    if (n == 0) { pf_list_push_atom(l, a); }
    else {
	pf_atom_t *b = FIRST(l);
	while (--n) { b = NEXT(b); }
	SET_NEXT(a, NEXT(b));
	SET_NEXT(b, a);
	SET_ELEMENTS(l, 1 + ELEMENTS(l));
	if (!NEXT(a)) SET_LAST(l, a);
    }
}

/* POP:
   not defined for stack or tree */


/* pop: return first item and remove */
pf_atom_t  *pf_list_pop_atom(pf_list_t *l)
{
    pf_atom_t *a = FIRST(l);
    if (!a) return a;

    SET_FIRST(l, NEXT(a));
    SET_ELEMENTS(l, ELEMENTS(l) - 1);

    if (!FIRST(l)) SET_LAST(l, 0);
    SET_NEXT(a, 0); // detach
    return a;
}


/* pop: return first item and remove */
pf_word_t pf_list_pop(pf_list_t *l)
{
    pf_atom_t *a = pf_list_pop_atom(l);
    pf_word_t w = WORD(a);
    pf_atom_free(a);
    return w;
}





/*  COPY  */

// only defined for stack
// if you want to do other kinds of copy, do it manually

pf_list_t *pf_stack_copy(pf_list_t *list){
    ASSERT(list);
    pf_list_t *newlist = pf_list_new();
    pf_atom_t *a;
    PF_ATOM_IN (list, a) {
	pf_stack_queue_atom(newlist, a);
    }
    return newlist;
}





/* MISC OPS */


/* return element at index */
pf_word_t pf_list_index(pf_list_t *l, int index)
{
    ASSERT(index >= 0);
    ASSERT(index < ELEMENTS(l));
    pf_atom_t *a;
    for (a = FIRST(l); index--; a = NEXT(a));
    return WORD(a);
}


/* inplace join 2 lists: inplace */
void pf_list_join (pf_list_t *l, pf_list_t *tail)
{
    if (ELEMENTS(tail)){
	SET_ELEMENTS(l, ELEMENTS(tail) + ELEMENTS(l));

	if (LAST(l)){
	    SET_NEXT(LAST(l), FIRST(tail));
	    SET_LAST(l, LAST(tail));
	}
	else {
	    SET_FIRST(l, FIRST(tail));
	    SET_LAST(l, LAST(tail));
	}
    }
    SET_FIRST(tail, 0); // detach
    SET_LAST(tail, 0);
    SET_ELEMENTS(tail, 0);
    DEALLOC(tail); //delete the tail header
}


/* in place reverse: atoms stay the same
   they are just relinked. so pointers will stay accurate */
void pf_list_reverse(pf_list_t *l)
{
    pf_list_t tmp;
    pf_atom_t *a;
    SET_FIRST(&tmp, FIRST(l));
    SET_LAST(&tmp, LAST(l));
    SET_ELEMENTS(&tmp, ELEMENTS(l));

    SET_FIRST(l, 0);
    SET_LAST(l, 0);
    SET_ELEMENTS(l, 0);

    while (a = pf_list_pop_atom(&tmp)){
	pf_list_push_atom(l, a);
    }
}