#ifndef INCLUDED_QUEUE_INFO
#define INCLUDED_QUEUE_INFO

#include "base.h"
#include "types.h"

#if 0
template <typename T> class Queue : T {
public:

    T();

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

    // virual void init();
};
#endif

template <typename T> class QueueInfo : public T {

public:
    /* constructor */
    QueueInfo<T>(){
	queueInfoInit();
    }
    QueueInfo<T>(QueueInfo<T> *p) {
	queueInfoInit();
	queuePool = p;
	queuePool->queuePool = queuePool;
    }

    BASE_NEW_DELETE(QueueInfo);

    /* functions */
    T *create();

    void free_(T *queue);

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

    // Iterator
    T* getNext(T* q) ;
    int length();

private:
    /* variables */

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

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



#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>void QueueInfo<T>::queueInfoInit() {
    // 最初の一つは自分
    first = last = this;
    this->next = this->prev = this;
    this->waiter = NULL;
}

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

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

    // First Queue is previous pool
    q->waiter = this->waiter; this->waiter = q;
    q = (T*)ROUND_UP_ALIGN((long)q, DEFAULT_ALIGNMENT);
    q++;

    /* Connect all free queue in the pool */
    T* p = q;
    for (; num-- > 0;) {
        p->waiter = NULL;
        queuePool->addLast(p);
	p = (T*)ROUND_UP_ALIGN((long)(p+1),DEFAULT_ALIGNMENT);
    }

    return 0;

}

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


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


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

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

template<typename T>void
QueueInfo<T>::addLast(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>T*
QueueInfo<T>::getFirst()
{
    if (empty()) return NULL;
    return first->next;
}

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

template<typename T>int
QueueInfo<T>::remove(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>T*
QueueInfo<T>::poll()
{
    T* e = first->next;
    if (e == this) {
	return NULL;
    }
    remove(e);
    return e;
}

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

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

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

template<typename T>T*
QueueInfo<T>::find(T* task)
{
    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>T*
QueueInfo<T>::getNext(T* q) 
{
    if (q->next==this) return NULL;
    return q->next;
}

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

template<typename T>void
QueueInfo<T>::freeAll()
{
    T* t;
    while((t=poll())) free_(t);
}



/* end */



#endif