/*
Name: List.h
Purpose: Linked List template class (declarations and definitions)
Original Author: Chris Thompson
Author: Richard Szalay
Created: 27th September, 2000
History: 08/10/00 :	Added primary/secondary milestone system
*/

#ifndef __LIST_H__
#define __LIST_H__

#include <stdio.h>

template <class ListItem>
class List
{
public:
    List() 
        :m_numelements(0),
		m_lastIndex(0),
		m_msJump(64),
		m_msJump2(256)
    {
        m_head = new Link;
        m_tail = new Link;

        m_head->next = m_tail;
		m_head->prev = m_head;

        m_tail->next = m_tail;
		m_tail->prev = m_head;

    };

    ~List()
    {    
        Link* before = m_head;
        Link* after;

        while (before->next != m_tail)
        {
            after = before->next->next;
            delete before->next;
            before->next = after;
        }

        delete m_head;
        delete m_tail;
    };

    void Insert(int index, const ListItem& data)
    {
		/* Positioning removed from insert
		   - data in inserted before the tail */

        Link* newnode = new Link(data); // Create the new node

		/* inform the surrounding nodes	*/
		newnode->prev		= m_tail->prev;
		newnode->prev->next = newnode;

		m_tail->prev  = newnode;
		newnode->next = m_tail;

		/* 0 is an exception to the Milestone counter */
		if (m_numelements == 0)
		{
			m_lastMilestone = newnode;
			m_tail->prevMS = newnode;

			m_lastMilestone2 = newnode;
			m_tail->prevMS2 = newnode;

			m_lastNode = newnode;
			m_lastIndex = 0;
		}

		newnode->prevMS = m_lastMilestone; // remember the previous milestone
		newnode->prevMS2 = m_lastMilestone2;

		/* Primary Level Milestone */
		if (((m_numelements) % m_msJump) == 0)
		{
			m_lastMilestone = newnode;
			newnode->prevMS->nextMS = newnode;
			newnode->nextMS = newnode;
			m_tail->prevMS = newnode;
		}

		/* Secondary Level Milestone */
		if (((m_numelements) % m_msJump2) == 0)
		{
			m_lastMilestone2 = newnode;
			newnode->prevMS2->nextMS2 = newnode;
			newnode->nextMS2 = newnode;
			m_tail->prevMS2 = newnode;
		}

        m_numelements++;
    }

    void Remove(int index)
    {
        Link* before = m_head;
        Link* after;

		/* 
			Could/Should impliment a faster
			Remove function - but i've never 
			actually used it 
		*/

        for (int i=0;i<index;i++)
            before = before->next;

        after = before->next->next;
        delete before->next;
        before->next = after;
		after->prev = before;
        m_numelements--;
    }

    ListItem operator[](int index)
    {
        Link* element;
		int start, end, lastIndex;

		start = 0;
		end = m_numelements;
		lastIndex = m_lastIndex;

		element = m_head->next;

		/*
			Before we do anything else, check
			if we are within 16 of the beginning 
			or the end
		*/
			// Near beginning
			if (index < m_msJump)
			{
				for (int i=0; i<index; i++)
				{
					element = element->next;
				}
				m_lastIndex = index;
				m_lastNode = element;
				return element->data;
			}
			// Near end
			if (index > (m_numelements - (m_numelements % m_msJump)))
			{
				element = m_tail;
				for (int i=m_numelements; i>index; i--)
				{
					element = element->prev;
				}
				m_lastIndex = index;
				m_lastNode = element;
				return element->data;
			}

		/*
			Also, check if we are within 16 of the 
			last requested index
		*/
		// <- to the left
		if ((index < m_lastIndex)&&((m_lastIndex - index) < (m_msJump >> 1)))
		{
			element = m_lastNode;

			for (int i=m_lastIndex;i>index;i--)
			{
				element = element->prev;
			}
			m_lastIndex = index;
			m_lastNode = element;
			return element->data;
		}
		// -> to the right
		if ((index >= m_lastIndex)&&((index - m_lastIndex) < (m_msJump >> 1)))
		{
			element = m_lastNode;

			for (int i=m_lastIndex;i<index;i++)
			{
				element = element->next;
			}
			m_lastIndex = index;
			m_lastNode = element;
			return element->data;
		}

		/*
			If we are here we arent close
			to anything 'nice'. So we find
			our closest 'milestone'
		*/
		int diffModulo = (index % m_msJump);
		int closePrevMS = (index - diffModulo);
		int diffModulo2 = (closePrevMS % m_msJump2);
		int closePrevMS2 = (closePrevMS - diffModulo2);
		int i;

		/* Find secondary level milestone */
		// Which end should we start at? 
		// (which half of the list is it?)
		if (closePrevMS2 > (m_numelements >> 1)) // end?
		{
			element = m_tail->prevMS2;
			int supl = (m_numelements-(m_numelements%m_msJump2));
			for (i=supl; i>closePrevMS2; i-=m_msJump2)
			{
				element = element->prevMS2;
			}
		}
		else // beginning ?
		{
			for (i=0; i<closePrevMS2; i+=m_msJump2)
			{
				element = element->nextMS2;
			}
		}

		/* Find primary level milestone */
		// Which end should we start at? 
		// (which half of the list is it?)
		if ((diffModulo2 > (m_msJump2 >> 1)) && (element->nextMS2 != element))
		{
			element = element->nextMS2; // jumpin'
			i += m_msJump2; // we start one jump forward (for counting)

			if ((element->prevMS->nextMS != element) && 
												(element->prevMS != element))
			{
				element = element->prevMS;
				i-=m_msJump;
			}

			for (i=i; i>closePrevMS; i-=m_msJump)
			{
				element = element->prevMS;
			}
		}
		else // no - stay here and go forwards
		{
			if ((element->prevMS->nextMS != element) && 
												(element->prevMS != element))
			{
				element = element->prevMS;
				i-=m_msJump;
			}

			for (i=i; i<closePrevMS; i+=m_msJump)
			{
				element = element->nextMS;
			}
		}

		/* 
			- Final Stage -
			The closest lowest-level milestone has been located
			From here go (forwards or backwards) to find the node
		*/

		//	Should we jump to the next milestone and go backwards?
		if ((diffModulo > (m_msJump >> 1)) && (element->nextMS != element))
		{
			// yes - jump and go backwards
			element = element->nextMS; // jumpin'
			i += m_msJump; // we start one jump forward (for counting)

			for (i=i; i>index; i--)
			{
				element = element->prev;
			}
		}
		else // no - stay here and go forwards
		{
			for (i=i; i<index; i++)
			{
				element = element->next;
			}
		}

		m_lastIndex = index;
		m_lastNode = element;
        return element->data;
    }

    int Size()      // number of elements in the list
    {
        return m_numelements;
    }

private:

    // node in our list
    struct Link
    {
        Link()
            :next(NULL) {};
        Link(const ListItem& datain)
            :data(datain),
            next(NULL) {};
        Link*   next;   // next node in list    
		Link*	prev;	// previous node
        ListItem    data;   // data stored in this node
		Link*	nextMS;
		Link*	prevMS;
		Link*	nextMS2;
		Link*	prevMS2;
    };

    // head and tail
    Link*   m_head;
    Link*   m_tail;
	Link*	m_lastNode;
    int     m_numelements;
	int		m_lastIndex;
	Link*	m_lastMilestone; // link of primary level jumps (milestones)
	Link*	m_lastMilestone2; // link of secondary level jumps (milestones)
	int		m_msJump; // Size of jump for primary level
	int		m_msJump2; // Size of jump for secondary level
};

#endif