/*
	Copyright (C) 2004 Stephan Wienczny

	This software is provided 'as-is', without any express or implied
	warranty.  In no event will the authors be held liable for any damages
	arising from the use of this software.

	Permission is granted to anyone to use this software for any purpose,
	including commercial applications, and to alter it and redistribute it
	freely, subject to the following restrictions:

	1. The origin of this software must not be misrepresented; you must not
	   claim that you wrote the original software. If you use this software
	   in a product, an acknowledgment in the product documentation would be
	   appreciated but is not required.
	2. Altered source versions must be plainly marked as such, and must not be
	   misrepresented as being the original software.
	3. This notice may not be removed or altered from any source distribution.
*/

module List;

class IteratorException: Exception
{
	this(char[] error){super(error);}
}

class IlleagalIterator : IteratorException
{
	this(char[] error){super(error);}
}

class IteratorNotConnected : IteratorException
{
	this(){super("ListIterator not connected!");}
}


template TContainer(T)
{
class Node
{
 protected:
 Node next = null, prev = null;
 T m_value;
 public:
 this(){}
 this(T value) {m_value = value;}
 this(T value, Node p , Node n )
 {
  m_value = value;
  prev = p;
  next = n;
 }
 T Value() {return m_value;}
 void Value(T value) {m_value = value;}
}

class List
{
 protected:
 Node root = null, end = null;
 uint m_size = 0;
 public:
 this()
 {
 }

 ~this()
 {
  Clear();
 }

 void Clear()
 {
  Node cursor = root;
  Node tmp;
  while (cursor != null)
  {
   tmp = cursor.next;
   delete cursor;
   cursor = tmp;
  }
  root = null;
  end = null;
  m_size = 0;
 }

 uint Size() { return m_size; }
 uint length() {return Size();}

 void Recount()
 {
     m_size = 0;
     Node elem = root;

     while(elem)
    {
        elem = elem.next;
        m_size++;
    }
 }

 void Append(T value)
 {
    Node cursor = new Node(value, end, null);
    m_size++;
    if (!root)root = cursor;
    if (end) end.next = cursor;
    end = cursor;
 }

 void Prepend(T value)
 {
    Node cursor = new Node(value, null, root);
    m_size++;
    if (root)root.prev = cursor;
    if (!end) end = cursor;
    root = cursor;
 }

 void InsertAfter(Node iter, T value)
 {
    if (!iter) throw new IlleagalIterator("Given iterator does not exists");

    Node elem = new Node(value, iter, iter.next);
    m_size++;
    iter.next = elem;
    iter.next.prev = elem;
    if (elem.next) elem.next.prev = elem;
 }

 void InsertBefore(Node iter, T value)
 {
     if (!iter) throw new IlleagalIterator("Given iterator does not exists");

     Node elem = new Node(value, iter.prev, iter);
    m_size++;
    iter.prev = elem;
    iter.prev.next = elem;
    if (elem.prev) elem.prev.next = elem;
 }

 void Delete(ListIterator iter)
 {
     if (!iter) throw new IlleagalIterator("Given iterator does not exists");

    Node elem = iter.iterelem;
     printf("Delete: %i\n", elem.Value());

     if (elem.prev)
         elem.prev.next = elem.next;
     if (elem.next)
         elem.next.prev = elem.prev;

     if (elem == root) root = elem.next;
     if (elem == end) end = elem.prev;

     delete iter;
     m_size--;
 }

 ListIterator Find(T value, ListIterator begin, ListIterator end)
 {
    Node elem = begin.iterelem;

    if (!begin) elem = root;

    do
    {
        if (elem.m_value == value) return new ListIterator(elem);
        elem = elem.next;
    }
    while(elem && elem != end.iterelem);

    return new ListIterator(null);
 }

 uint Replace(T value, T newvalue, uint maxcount, ListIterator begin, ListIterator end)
 {
    if (!begin) throw new IlleagalIterator("iterator \"begin\" does not exists!");
    if (!end) throw new IlleagalIterator("iterator \"end\" does not exists!");

    Node elem = begin.iterelem;
    uint replaced = 0;

    if (!begin) elem = root;

    do
    {
        if (elem.m_value == value)
        {
         elem.m_value = newvalue;
         replaced++;
        }
        elem = elem.next;
    }
    while(elem && elem != end.iterelem && maxcount - replaced);

    return replaced;
 }

 ListIterator Find(T value)
 {
     return Find(value, GetFirst(), GetLast());
 }

 uint ReplaceAll(T value, T newvalue)
 {
     return Replace(value, newvalue, uint.max, GetFirst(), GetLast());
 }

 T[] GenArray()
 {
     T[] result = new T[m_size+1];
     uint pos = 0;


     Node elem = root;

     while (elem)
     {
      result[pos] = elem.Value();
      pos++;
     }


     return result;
 }

 ListIterator GetFirst() {return new ListIterator(root);}
 ListIterator GetLast()  {return new ListIterator(end);}
}

class ListIterator
{
 protected:
 Node iterelem = null;

 public:
 this(Node myelem)
 {
  iterelem = myelem;
 }

 ListIterator Copy()
 {
  return new ListIterator(iterelem);
 }

 bit Exists()
 {
  return iterelem ? true : false;
 }

 T Value()
 {
  return iterelem.Value();
 }

 void Value(T value)
 {
  iterelem.Value(value);
 }

 void next()
 {
    if (!iterelem) throw new IteratorNotConnected();
    iterelem = iterelem.next;
 }

 void prev()
 {
    if (!iterelem) throw new IteratorNotConnected();
    iterelem = iterelem.prev;
 }

 void postinc()
 {
	next();
 };

 void postdec()
 {
	prev();
 }

 int eq(ListIterator o)
 {
  return (iterelem === o.iterelem)? true: false;
 }
}

}


unittest
{
     try
    {

    printf("Init ");
    TContainer!(uint).List list = new TContainer!(uint).List();
    printf("done\n");
    printf("Append ");
    list.Append(5);
    list.Append(6);
    list.Append(7);
    list.Append(8);
    printf("done\n");
    printf("Prepend ");
    list.Prepend(4);
    list.Prepend(3);
    list.Prepend(2);
    list.Prepend(1);
    printf("done\n");

    for (TContainer!(uint).ListIterator iter = list.GetFirst(); iter.Exists(); iter++)
    {
		stdout.write(iter.Value);
    }
    }finally
    {

    }
    return 0;
}