#ifndef _JPA_LIST_H_
#define _JPA_LIST_H_

#include "iostream.h"
#include "assert.h"

template<class T> 
class JPAList {
private:
  struct JPAListNode {
    JPAListNode *next;
    JPAListNode *prev;
    T *data;
  };

  JPAListNode *GetNewNode (void)
    {
      _size++;
      if (!_mem)
	return new JPAListNode;
      else
	{
	  if (_num_blocks_used == _num_blocks_allocd)
	    {
	    cerr << "trying to add to JPAlist beyond pre-alloced size!" << endl;
	    return NULL;
	    }
	  else
	    {
	      //construct it in place
	      char *thismem = _cur_mem;
	      _cur_mem += sizeof (JPAListNode);
	      _num_blocks_used++;
#ifndef _WINDOWS
		  return (new (thismem) JPAListNode);
#else
		assert (0);
		  return NULL;
#endif
	    }
	}

    }

  void RemoveNode (JPAListNode *node)
  {
    if (!_mem)//if we pre-alloced mem, can't free individual blocks! it's lost.
      delete node;
  }

  JPAListNode* _head, *_tail;
  int _size;
  
  //you can either pre-size the list to reduce memory alloc time or
  //do it 1-by-1, which lets you grow to any size but has to do 
  //a new for every new list element.

  char *_mem; //pre-alloced memory
  char *_cur_mem; //which block is up next to be used
  int _num_blocks_allocd; //how many blocks alloc'd
  int _num_blocks_used; //how many blocks in use

public:
    JPAList (void) : _size(0), _head (NULL), _tail (NULL), _mem (NULL), _num_blocks_allocd (0), _cur_mem (NULL), _num_blocks_used (0) {}

    ~JPAList (void) {
      Clear();
    }

    void Clear (void) {
      if (_mem)
	{
	delete[] _mem;
	_cur_mem = _mem = NULL;
	}
      else
	{
	  JPAListNode *cur = _head;
	  while (_head)
	    {
	      //find the next one
	      _head = _head->next;
	      delete cur; //delete the prev one
	      cur = _head; //move forward
	    }
	}
      _tail = NULL;
      _size = 0;
      _num_blocks_allocd = 0;
      _num_blocks_used = 0;
      _head = NULL;
    }

    void PlaceInSortedList (T *addme, int (*compfxn)(const T *t1, const T *t2))
      {
	JPAListNode *newnode = GetNewNode();
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->data = addme;	

	//is there a head?
	if (!_head)
	  {
	    _head = _tail = newnode;
	    return;
	  }
	
    //are we before the head?
	if (compfxn (newnode->data, _head->data) < 0)
	  {
	    newnode->next = _head;
	    _head->prev = newnode;
	    _head = newnode;
	    return;
	  }
    
    //ok, we are sometime after the head then
	//we need to find a current s.t. that we're >= current but not
        //> current->next
	JPAListNode *current = _head;

    while (current->next && compfxn (newnode->data, current->next->data) > 0)
      {
	current = current->next;
      }

   newnode->next = current->next;
   current->next = newnode;
   newnode->prev = current;
   if (current == _tail)
      _tail = newnode;
}

    void PlaceInList (T *addme) {
      JPAListNode *newnode = GetNewNode();
      newnode->next = NULL;
      newnode->prev = NULL;
      newnode->data = addme;

      if (_tail)
        {
	_tail->next = newnode;
	newnode->prev = _tail;
        }
      else
	{
	  assert (!_head);
	  _head = newnode;
	}
      _tail = newnode;
    }

    void Remove (const void *&removeme)
  {
    JPAListNode *dead = (JPAListNode*)removeme;
    removeme = dead->next;
    if (dead->prev) dead->prev->next = dead->next;
    if (dead->next) dead->next->prev = dead->prev;
    if (dead == _head) _head = dead->next;
    if (dead == _tail) _tail = dead->prev;
    RemoveNode (dead);
    _size--;
  }

  void PreAlloc (int size)
  {
#ifndef _WINDOWS
	  assert (!_mem);
    assert (_size == 0); //can't mix & match! prealloc or don't.
    _num_blocks_allocd = size;
    _cur_mem = _mem = new char [sizeof (JPAListNode) * _num_blocks_allocd];
    _num_blocks_used = 0;
#else
    cerr << "can't prealloc in Windows yet!" << endl;
#endif
  }

    int Size (void) {return _size;}

    void Reset (const void *&start) {start = _head;}
    T *Peek (const void *where) {return ((JPAListNode *)where)->data;}
    void Next (const void *&advanceme) {advanceme = ((JPAListNode *)advanceme)->next;}
    void Prev (const void *&advanceme) {advanceme = ((JPAListNode *)advanceme)->prev;}
};

#endif