#ifndef __UNBOUNDED_HPP
#define __UNBOUNDED_HPP

#include <stddef.h>

class Unmanaged {
        Unmanaged();
        void operator=(Unmanaged &);
public:
        static void *alloc(size_t s) {
                return ::operator new(s);
        }
        static void free(void *p, size_t) {
                ::operator delete(p);
        }
};


template<class Item, class StorageManager>
class Node {
public:
        Node<Item,StorageManager> *prev, *next;
        Item item;
        Node(const Item& i,Node<Item,StorageManager> *p, Node<Item,StorageManager> *n)
          : prev(p), next(n), item(i)
        {
                if(prev) prev->next=this;
                if(next) next->prev=this;
        }
        ~Node() {
                if(prev) prev->next=next;
                if(next) next->prev=prev;
        }

        static void *operator new(size_t s) {
                return StorageManager::alloc(s);
        }
        static void operator delete(void *p, size_t s) {
                StorageManager::free(p,s);
        }
};



template<class Item, class StorageManager>
class Unbounded {
public:
        Unbounded();
        Unbounded(const Unbounded<Item,StorageManager>&);
        virtual ~Unbounded();
        Unbounded<Item,StorageManager> operator=(const Unbounded<Item,StorageManager>&);

        void clear();
        void insert(const Item &);
        void insert(const Item &, unsigned before);
        void append(const Item &);
        void append(const Item &, unsigned after);
        void remove(unsigned at);
        void replace(unsigned at, const Item &);

        int isEmpty() const;
        unsigned length() const;
        const Item& first() const;
        const Item& last() const;
        const Item& itemAt(unsigned at) const;
        Item& itemAt(unsigned at);
        const Item& operator[](unsigned at) const { return itemAt(at); }
        Item& operator[](unsigned at) { return itemAt(at); }

private:
        Node<Item,StorageManager> *left, *right;
        unsigned size;

        Node<Item,StorageManager> *cache;
        unsigned cacheIndex;

        Node<Item,StorageManager>* seek(unsigned index) const;
        Node<Item,StorageManager>* seek(unsigned index);
};

#include "unbounded.cpp"

#endif