#ifndef INCLUDED_QUEUE_INFO
#define INCLUDED_QUEUE_INFO

#include "base.h"

template <typename T> class Queue {
public:

    Queue<T>();

    T *waiter;
    T *next;
    T *prev;

    void init();
};

template <typename T> class QueueInfo : public Queue<T> {

public:
    /* constructor */
    QueueInfo<T>();

    BASE_NEW_DELETE(QueueInfo);

    /* functions */
    Queue<T> *create();

    void free_(Queue<T> *queue);

    void addFirst(Queue<T>* e);
    void addLast(Queue<T>* e);
    Queue<T>* getFirst();
    Queue<T>* getLast();
    int remove(Queue<T>* e);
    Queue<T>* poll();
    void moveToFirst(Queue<T>* e); // or use();
    Queue<T>* get(int index);
    Queue<T>* find(Queue<T> *task);
    int empty();
    void freePool() ;

    // Iterator
    Queue<T>* getNext(Queue<T>* q) ;
    int length();

private:
    /* variables */

    static QueueInfo<T> queuePool;
    Queue<T>* first;
    Queue<T>* last;

    /* functions */
    int extend_pool(int num);
    void destroy();  
};



#ifdef CHECK
#include <stdio.h>
#endif
#include <stdlib.h>


// Singleton T Pool
// you have to define it at where you want to use.
// template<typename T>static QueueInfo<T> QueueInfo<T>::queuePool;   

template<typename T>QueueInfo<T>::QueueInfo() {
    // 最初の一つは自分
    first = last = this;
    this->next = this->prev = this;
    this->waiter = NULL;
}

template<typename T>void
QueueInfo<T>::freePool() { 
    for(Queue<T> * p = queuePool.waiter; p; ) {
	Queue<T> * next = p->waiter;
	p->waiter = NULL;
	free(p);
	p = next;
    }
}

template<typename T>int
QueueInfo<T>::extend_pool(int num)
{
    Queue<T> * q = (Queue<T> *)malloc(sizeof(Queue<T>)*(num+1));

    // First Queue is previous pool
    q->waiter = this->waiter; this->waiter = q;
    q++;

    /* Connect all free queue in the pool */
    Queue<T> * p = q;
    for (; num-- > 0; p++) {
	p->waiter = NULL;
	queuePool.addLast(p);
    }

    return 0;
}

/**
 * Task をプールから取って来て返す
 *
 * @param [cmd] タスクコマンド
 */
template<typename T>Queue<T> *
QueueInfo<T>::create()
{
    Queue<T> * q =  queuePool.poll();
    if (! q)  {
	queuePool.extend_pool(64);
	q = queuePool.poll();
    }
    q->init();
    return q;
}


template<typename T>void
QueueInfo<T>::free_(Queue<T> * q)
{
    q->waiter = NULL;
    queuePool.addLast(q);
}


/*!
  QueueInfo<T> は空にならない。最低1個は要素が入っていて
  1個目は特別扱いする。getFirst すると first->next を返す
 */

/*!
  最初の1個は特別扱いなので、それの後に追加していく
 */
template<typename T>void
QueueInfo<T>::addFirst(Queue<T>* e)
{
    e->prev = first;
    e->next = first->next;
    first->next->prev = e;
    first->next = e;
}

template<typename T>void
QueueInfo<T>::addLast(Queue<T>* e)
{
#ifdef CHECK
    if (find(e)) { 
	fprintf(stderr,"Add duplicate task %0x\n",(int)e);
	return; 
       // ...  
    }
#endif
    e->next = first;
    e->prev = last;
    last->next = e;
    last = e;
}

template<typename T>Queue<T>*
QueueInfo<T>::getFirst()
{
    if (empty()) return NULL;
    return first->next;
}

template<typename T>Queue<T>*
QueueInfo<T>::getLast()
{
    if (empty()) return NULL;
    return last;
}

template<typename T>int
QueueInfo<T>::remove(Queue<T>* e)
{
#ifdef CHECK
    if (!find(e)) { 
	fprintf(stderr,"Remove non existing task %0x\n",(int)e);
	return 0; 
       // ...  
    }
#endif
    e->prev->next = e->next;
    e->next->prev = e->prev;

    if (first->next == e) {
	first->next = e->next;
    }
    if (last == e) {
	last = e->prev;
    }

    e->prev = NULL;
    e->next = NULL;

    return 1;
}

/*!
  リストの先頭を取得および削除する。リストが空の場合は NULL を返す。
 */

template<typename T>Queue<T>*
QueueInfo<T>::poll()
{
    Queue<T>* e = first->next;
    if (e == this) {
	return NULL;
    }
    remove(e);
    return e;
}

template<typename T>void
QueueInfo<T>::moveToFirst(Queue<T>* e)
{
    remove(e);
    addFirst(e);
}

/*!
  リスト内の指定された位置にある要素を返す。
  要素数を超えた位置を指定した場合 NULL を返す。
 */

template<typename T>Queue<T>*
QueueInfo<T>::get(int index)
{
    Queue<T>* e = first->next;
    for (int i = 0; i < index; i++) {
	if (e == this) return NULL;
	e = e->next;
    }
    return e;
}

template<typename T>Queue<T>*
QueueInfo<T>::find(Queue<T>* task)
{
    Queue<T>* e = first->next;
    for(;;) {
	if (e == this) return NULL;
	if (e == task) break;
	e = e->next;
    }
    return e;
}

template<typename T>int
QueueInfo<T>::empty()
{
    return this->next == this;
}

template<typename T>Queue<T>*
QueueInfo<T>::getNext(Queue<T>* q) 
{
    if (q->next==this) return NULL;
    return q->next;
}

template<typename T>int
QueueInfo<T>::length() 
{
    int i = 1;
    if (empty()) return 0;
    Queue<T>* e = first;
    while((e = e->next) != this ) i++;
    return i;
}




/* end */



#endif