Base list
using
System;
namespace
Nice4
{
/// <summary>
/// Summary description for BaseList.
/// </summary>
public abstract class
BaseList
{
public
class Element
{
public
IComparable data;
public
Element next;
public
Element(IComparable data, Element next)
{
this.data
= data;
this.next
= next;
}
}
private
Type ListType;
protected
Element head;
protected
Element tail;
protected
Element cursor;
public
BaseList(Type ListType)
{
head = tail = cursor = null;
this.ListType
= ListType;
}
protected
void InsertBeforeCursor(IComparable o)
{
Element e;
if(IsEmpty) // list is empty
{
InsertAtHead(o);
}
else
if(cursor == head) // insert before head
{
e = new Element(o, head);
head = e;
}
else // insert anywhere
else in the list
{
e = new Element(cursor.data, cursor.next); // duplicate
cursor
if(cursor
== tail)
tail = e; // e will be
the new tail
cursor.data = o; // insert the new
data to cursor
cursor.next = e; // e is now what was
pointed to by cursor
cursor = e; // set
cursor to point to its right location
}
}
protected
void InsertAfterCursor(IComparable o)
{
Element e;
if(IsEmpty) // list is empty
{
InsertAtHead(o);
}
else
if(cursor == tail) // insert after tail
{
e = new Element(o, null);
tail.next = e; // insert
after list's tail
tail = e; // set
tail to the last
}
else // insert anywhere
else in the list
{
e = new Element(o, cursor.next);
cursor.next = e;
}
}
protected
IComparable RemoveAtCursor()
{
if(IsEmpty)
// list is empty
throw
new ApplicationException("BaseList::List
is empty");
IComparable ret = cursor.data;
if(cursor
== head && cursor == tail) // one element in the list
{
head = null;
tail = null;
cursor = null;
}
else
if(cursor == head) // remove the head of the list
{
head = head.next;
cursor = head;
}
else
if(cursor == tail) // remove the tail of the list
{
Element tmp = head;
while(tmp.next
!= tail)
tmp = tmp.next;
tmp.next = null;
tail = tmp;
cursor = tmp;
}
else // remove
anywhere else in the list
{
cursor.data =
cursor.next.data; // copy the data of the element after cursor
if(cursor.next
== tail) // cursor is right after tail
{
cursor.next = null;
tail = cursor;
}
else
{
cursor.next =
cursor.next.next;
}
}
cursor = head;
return
ret;
}
protected
bool IsEmpty
{
get
{
if(head
== null)
return true;
else
return false;
}
}
protected
void TestObjectType(IComparable o)
{
if(ListType
!= o.GetType())
throw
new ArgumentException("BaseList::The
agrument is of wrong type");
}
public
abstract void
Push(IComparable o);
public
abstract IComparable Pop();
private
void InsertAtHead(IComparable o)
{
head = new Element(o, null);
tail = head;
cursor = head;
}
}
}
PopQueue
using
System;
namespace
Nice4
{
/// <summary>
/// Summary description for PopQueue.
/// </summary>
public class PopQueue:BaseList
{
public
PopQueue(Type ListDataType):base(ListDataType)
{
}
public
override IComparable Pop()
{
cursor = head;
try
{
return
RemoveAtCursor();
}
catch(ApplicationException
ex) // for example
when the list is empty
{
return
null;
}
}
public
override void
Push(IComparable o)
{
TestObjectType(o);
if(IsEmpty)
{
InsertAfterCursor(o);
return;
}
cursor = head;
try
{
while(cursor
!= tail)
{
if(o.CompareTo(cursor.data)<0)
{
InsertBeforeCursor(o);
return;
}
cursor =
cursor.next;
}
if(o.CompareTo(cursor.data)>0)
InsertAfterCursor(o);
else
InsertBeforeCursor(o);
}
catch(ArgumentException
ex)
{
throw
ex;
}
}
}
}
PushQueue
using
System;
namespace
Nice4
{
/// <summary>
/// Summary description for PushQueue.
/// </summary>
public class PushQueue:BaseList
{
public
PushQueue(Type ListDataType):base(ListDataType)
{}
public
override void
Push(IComparable o)
{
TestObjectType(o);
cursor = tail;
InsertAfterCursor(o);
}
public
override IComparable Pop()
{
if(IsEmpty)
return
null;
Element min;
min = cursor = head;
while(cursor
!= tail)
{
if(cursor.data.CompareTo(min.data)<0)
min = cursor;
cursor = cursor.next;
}
if(tail.data.CompareTo(min.data)<0)
min = tail;
cursor = min;
return
RemoveAtCursor();
}
}
}
