/*
        Copyright 1999, Be Incorporated.   All Rights Reserved.
        This file may be used under the terms of the Be Sample Code License.
*/

#ifndef UTIL_H
#define UTIL_H

#include <memory.h>
#include <stdlib.h>
#include "error.h"

template <class contents>
struct LispNode {
        contents* car;
        LispNode* cdr;

        /* Create a node with no next */
        inline LispNode(contents* value)
                : car(value), cdr(0) { }

        /* Create a node with specified next */
        inline LispNode(contents* value, LispNode* next)
                : car (value), cdr(next) { }

        /* Create a node and insert it in a list right after `prev' */
        inline LispNode(LispNode* prev, contents* value)
                : car(value), cdr(prev->cdr) { prev->cdr = this; }
};


template <class contents>
struct LispList {
        LispNode<contents> *first;

        /* -------- List creation --------------- */
        /* Create an empty list */
        inline LispList()
        {
                first = 0;
        }


        /* Create a list pointing to the specified node */
        inline LispList(LispNode<contents>* _first)
        {
                first = _first;
        }


        /* ?? */
        inline LispList(LispList &init)
        {
                first = init.first;
        }


        /* ---------- List queries ------------- */
        inline int is_empty()
        {
                return first == 0;
        }


        /* Determines if a thing is on the list */
        inline int is_present(contents* element)
        {
                for (LispNode<contents>* node = first; node; node = node->cdr)
                        if (node->car == element)
                                return 1;
                return 0;
        }


        /* Returns the length of the list */
        inline int count()
        {
                int n = 0;
                for (LispNode<contents>* node = first; node; node = node->cdr)
                        n++;
            return n;
        }


        /* ----------- Adding "nodes" to the list ------------ */
        /* Add a specified node to the head of the list.  */
        inline void add_head(LispNode<contents>* new_element)
        {
                new_element->cdr = first;
                first = new_element;
        }


        /* Add a specified node anywhere on the list */
        inline void add(LispNode<contents>* new_element)
        {
                add_head (new_element);
        }


        inline void add_tail(LispNode<contents>* new_element)
        {
                LispNode<contents>** pred = &first;
                while(*pred)
                        pred = &(*pred)->cdr;
                *pred = new_element;
                new_element->cdr = 0;
        }


        /* ----------- Adding "contents" to the list ------------ */
        /* -----  (Which in my opinion is far more useful) ------ */

        /* Create new node pointing to thing, & add to head of list. */
        inline void add_head_new(contents* new_element)
        {
                first = new LispNode<contents>(new_element, first);
        }


        inline void add_head(contents* new_element)
        {
                add_head_new(new_element);
        }


        /* Create new node pointing to thing, & add to end of list. */
        inline void add_tail_new(contents* new_element)
        {
                LispNode< contents >** pred = &first;
                while (*pred)
                        pred = &(*pred)->cdr;
                        
                *pred = new LispNode< contents >(new_element);
        }
        

        inline void add_tail(contents* new_element)
        {
                add_tail_new(new_element);
        }


        /* Create new node pointing to thing, & add anywhere on list */
        inline void add_new(contents* new_element)
        {
                add_head_new(new_element);
        }


        inline void add(contents* new_element)
        {
                add_new(new_element);
        }

        
        /* Create and add a new node for a specified element, 
                but only if it's not already on the list.  */
        inline void add_new_once(contents* new_element)
        {
                if (!is_present(new_element))
                        add_head_new(new_element);
        }
        
        
        inline void add_tail_once(contents *new_element)
        {
                if (!is_present(new_element))
                        add_tail_new(new_element);
        }

  
        /* ------- Removing things from the list ------------ */

        /* Remove and return the first node on the list j.h. */
        inline LispNode<contents>* rem_head ()
        {
                LispNode<contents>* n = first;
                
                if (n) {
                        first = first->cdr;
                }
                
                return n;
        }

        
        /* Remove and return any node on the list.  */
        inline LispNode<contents>* remove ()
        {
                return( rem_head() ); 
        }

        
        /* Remove a specified node from the list.  */
        inline void remove (LispNode<contents>* node)
        {
                for (LispNode<contents> **pp = &first; *pp; pp = &(*pp)->cdr)
                        if (*pp == node) {
                                *pp = (*pp)->cdr;
                                return;
                        }
        }


        /* Remove & delete all nodes pointing to a particular element. */
        inline void rem_del (contents* element)
        {
                LispNode<contents>** pp = &first;
                while (*pp) { 
                        if ((*pp)->car == element) {
                                LispNode<contents> *o = *pp;
                                *pp = o->cdr;
                                delete o;
                        } else
                                pp = &(*pp)->cdr;
                }
        }


        /* Remove and delete all nodes on the list.  */
        inline void rem_del_all()
        {
                while (first) {
                        LispNode<contents>* old = first;
                        first = first->cdr;
                        delete old;
                }
        }


        /* -------- Simple list storage (by j.h.) ------------ */

        /* When you just want to hold a bunch of stuff on a list and then pull them 
                off later.  Note that these calls do NOT check for to see if a thing is 
                already on the list.  Use is_present() before adding.
        */
        /* Put something anywhere on the list */
        inline void put( contents* c )
        {
                add_tail( c );
        }


        /* Put something at beginning of list */
        inline void put_head( contents* c )
        {
                add_head( c );
        }


        /* Put something at end of the list */
        inline void put_tail( contents* c )
        {
                add_tail( c );
        }

#if 0 /* leaks memory */
          /* Take a specific thing off the list */
          inline contents *get(contents *element)
            {
              contents *c = 0;
              for (LispNode<contents> *node = first; node; node = node->cdr)
              {
                if (node->car == element)
                {
                  c = node->car;
                  remove(node);
                  break;
                }
              }
              return c;
            }
#endif

        /* Take the first thing off the list */
        inline contents* get_head()
        {
                contents *c = 0;
                if(first) {
                        c = first->car;
                        delete rem_head();
                }
                return c;
        }
        
        
        /* Take something off the list */
        inline contents* get()
        {
                return(get_head());
        }
        

        /* XXX inline contents *get_tail() { } */

/* -------- Stack simulation (by j.h.) ------------ */
        /* Put a thing onto the head of the list */
        inline void push(contents* c)
        {
                put_head(c);
        }


        /* Remove a thing from the head of the list */
        inline contents* pop()
        {
                return(get_head());
        }

        /* Pop everything off the stack.  Empty the stack/list. */
        inline void pop_all()
        {
                rem_del_all();
        }


        /* ----------- list/list manipulations ------------ */

        /* Add all elements present on another list to this list also. */
        inline void add_new(LispList other)
        {
                for (LispNode<contents>* n = other.first; n; n = n->cdr)
                        add_new(n->car);
        }
        
        
        inline void add_new_once(LispList other)
        {
                for (LispNode<contents>* n = other.first; n; n = n->cdr)
                        add_new_once(n->car);
        }
        

        /* Remove and delete all nodes whose contents are also present
           in a different list (set disjunction). */
        inline void rem_del(LispList other)
        {
                for (LispNode<contents>* n = other.first; n; n = n->cdr)
                        rem_del(n->car);
        }
};

template <class thetype>
struct DoubleLinkedNode
{
        thetype* next;
        thetype* prev;

        DoubleLinkedNode()
        {
                next = prev = NULL;
        }
 
 
        void insert_after(thetype* n)
        {
                if (next != NULL)
                        next->prev = n;
                        
                n->next = next;
                n->prev = (thetype*)this;
                next = n;
        }


        void insert_before(thetype* n)
        {
                prev->next = n;
                n->next = (thetype*)this;
                n->prev = prev;
                prev = n;
        }


        void remove()
        {
                assert(prev != NULL);
                prev->next = next;
                
                if (next != NULL)
                        next->prev = prev;
        }
};


template <class thetype>
struct DoubleLinkedList : public DoubleLinkedNode<thetype>
{
        DoubleLinkedList() : DoubleLinkedNode<thetype>() {};

        void insert(thetype* n)
        {
                insert_after(n);
        }
        

        void add(thetype* n)
        {
                insert_after(n);
        }
};


template <class T>
struct BufferArray {
        T * items;
        int num_items;
        int num_slots;
        int slot_inc;

        void resize(int i)
        {
                items = (T*)realloc(items,sizeof(T)*i);
                num_slots = i;
        }
        

        T & operator [](int index)
        {
                assert(index < num_items);
                return items[index];
        }
        

        T & get(int index)
        {
                assert(index < num_items);
                return items[index];
        }
        

        void add(T &item)
        {
                if (num_items == num_slots)
                        resize(num_slots+slot_inc);
        
                memcpy(items+num_items,&item,sizeof(item));
                num_items++;
        }


        BufferArray(int start_slots, int _slot_inc)
        {
                num_slots = start_slots;
                slot_inc = _slot_inc;
                assert(slot_inc > 0);
                num_items = 0;
                items = (T*)malloc(sizeof(T)*num_slots);
        }


        ~BufferArray()
        {
                free(items);
        }
};

#endif // UTIL_H