/*
 * DoublyLinkedList.h 
 * Copyright (c) 2011 Antillia.com TOSHIYUKI ARAI. ALL RIGHTS RESERVED. 
 */


// SOL++2000
//  
#pragma once

#include <sol\List.h>

#include <sol\ListEntry.h>


namespace SOL {

class DoublyLinkedList :public List {
private:
    ListEntry*  head;
    ListEntry*    tail;
    bool        gc;

public:
    DoublyLinkedList(bool gc1=true)
        :head(NULL), 
        tail(NULL),
        gc(gc1)
    {
    }

public:
    bool addFirst(Object* object)
    {
        ListEntry* newEntry = new ListEntry(object, NULL, head);
        if (newEntry == NULL) {
            return false;
        }
    
        if (head != NULL) {
            head ->setPrev(newEntry);
        }    

        // Set the head to be a newEntry. 
        head = newEntry;

        // If tail is NULL, set tail to be a newEntry
        if (tail == NULL) {
            tail = newEntry;
        }

        return true;
    }


public:
    // Add an object to the tail of this list.
    bool add(Object* object)
    {
        ListEntry* newEntry= new ListEntry(object, tail, NULL);
        if (newEntry == NULL) {
            return false;
        }
        if (tail != NULL) {
            tail -> setNext(newEntry); 
        }

        // Set tail to be a newEntry. 

        tail = newEntry;

        // If head is NULL, set head to be a newEntry
        if (head == NULL) {
            head = newEntry;
        }
        return true;
    }

public:
    bool remove(Object* object)
    {
        bool rc = false;
        ListEntry* ptr  = head;
        ListEntry* prev = ptr;

        while (ptr) {
            Object* obj = ptr -> getObject();

            if (obj == object) {
                if (ptr != head && ptr != tail) {
                    ListEntry* next = ptr -> getNext();
                    prev -> setNext(next);
                    if (next != NULL) {
                        next -> setPrev(prev);
                    }        
                }

                // If matched on the head of this list.

                if (ptr == head) {
                    // Update the head.
                    head = ptr -> getNext();
                    head -> setPrev(NULL);
                    ptr -> setPrev(NULL);
                }
                // If ptr were tail, update the tail. 
                if (ptr == tail) {
                    tail = ptr -> getPrev();
                    tail ->setNext(NULL);
                }

                if (gc == false) {
                    ptr -> setObject(NULL);
                }

                // delete the ptr of ListEntry
                delete ptr;
                rc = true;
                break;

            } else {
                prev = ptr;
                ptr  = ptr -> getNext();
            }
        }
        return rc;
    }


public:
    ~DoublyLinkedList()
    {
        clear();
    }

public:
    bool isContained(Object* obj)
    {
        bool rc = false;

        ListEntry* ptr  = head;

        while (ptr) {
            if (ptr -> getObject() == obj) {
                rc = true;
                break;
            }
            ptr = ptr -> getNext();
        }
        return rc;
    }

public:
    void clear()
    {
        ListEntry* ptr  = head;
        ListEntry* prev = ptr;

        while (ptr) {
            prev = ptr;
            ptr = ptr -> getNext();
            if (gc == false) {
                prev ->setObject(NULL);
            }
            delete prev;
        }
        head = NULL;
        tail = NULL;
    }

public:
    int getLength() const
    {
        ListEntry* ptr = head;
        int n = 0;
        while(ptr) {
            ptr = ptr -> getNext();
            n++;
        }
        return n;
    }

public:
    Object* getNth(int n)
    {
        int m = 0;

        Object* object = NULL;
        ListEntry* ptr = head;

        while(ptr) {
            if(m == n) {
                object = ptr ->getObject();
                break;
            }
            ptr = ptr -> getNext();
            m++;
        }
        return object;
    }

public:
    // Simple selection sort
    void sort(SortDirection dir)
    {
        int length = getLength();
        int i = 0;
        ListEntry* ith = head;
   
        while (i<length-1) {    
            ListEntry* cth = ith;
            ListEntry* jth = ith -> getNext();
            Object*    obj = ith -> getObject();

            while (jth) {
                Object* jthObj = jth->getObject();
                if (dir == ASCENDING) {
                    if (jthObj -> compare(obj) > 0) {
                        cth = jth;
                        obj = jth -> getObject();
                    }    
                }
                if (dir == DESCENDING) {
                    if (jthObj -> compare(obj) < 0) {
                        cth = jth;
                        obj = jth -> getObject();
                    }    
                }
                jth = jth -> getNext();
            }

            cth -> setObject(ith->getObject());
            ith -> setObject(obj);

            ith = ith -> getNext();
            i++;
        }    // wile
    }

public:
    void reverse()
    {
        ListEntry* tmp = head;
        ListEntry* ptr = tail;
        ListEntry* rev = NULL;
        
        while (ptr) {
            ListEntry* prev = ptr -> getPrev();
            ListEntry* next = ptr -> getNext();
            ptr -> setNext(prev);
            ptr -> setPrev(next);
            ptr = prev;
        }

        head = tail;
        tail = tmp;
    }


    bool    addLast(Object* object) { 
        return add(object); 
    }

    ListEntry*  getHead() const { 
        return head; 
    }

    ListEntry*  getTail() const { 
        return tail; 
    }

    void    enableGC() {
            gc = true;
    }
    void    disableGC() {
            gc = false;
    }
};

}