• Mason Green (79/79) Aug 19 2008 Hello, D world.
• Steven Schveighoffer (21/101) Aug 19 2008 I don't know if you realize, but there are several Link List implementat...
• Mason Green (3/9) Aug 19 2008 Thanks a lot Steve! Short and sweet. Yes, I am playing around, although...

Mason Green <mason.green gmail.com> writes:

Hello, D world.

I've finally gotten around to experimenting with Templates, and was wondering
if anyone knows of a simple way to implement a linked list iterator.... Ideally
I would like iterate through the list using foreach...

Here's what I have so far.... Any help would be appreciated....

class FastCell(T)  {
	T elt;
	FastCell!(T) next;
	
    this(T elt, FastCell!(T) next) { 
        this.elt = elt; 
        this.next = next; 
    }
}

/**
	A linked-list of elements. 
**/
class FastList(T)  {

    alias FastCell!(T) Fast;
    
	Fast head;

	/**
		Creates a new empty list.
	**/
	this() {
        head = null;
	}

	/**
		Add an element at the head of the list.
	**/
	void add(T item) {
		head = new Fast(item, head);
	}

	/**
		Returns the first element of the list, or null
		if the list is empty.
	**/
	T first() {
		return (head is null ? null : head.elt);
	}

	/**
		Removes the first element of the list and
		returns it or simply returns null if the
		list is empty.
	**/
	T pop() {
		Fast k = head;
		if( k is null )
			return null;
		else {
			head = k.next;
			return k.elt;
		}
	}

	/**
		Tells if a list is empty.
	**/
	bool isEmpty() {
		return (head is null);
	}

	/**
		Remove the first element that is [== v] from the list.
		Returns [true] if an element was removed, [false] otherwise.
	**/
	bool remove(T v) {
		Fast prev = null;
		Fast l = head;
		while( l !is null ) {
			if( l.elt == v ) {
				if( prev is null )
					head = l.next;
				else
					prev.next = l.next;
				break;
			}
			prev = l;
			l = l.next;
		}
		return (l !is null);
	}
}

"Steven Schveighoffer" <schveiguy yahoo.com> writes:

"Mason Green" wrote
 Hello, D world.

 I've finally gotten around to experimenting with Templates, and was 
 wondering if anyone knows of a simple way to implement a linked list 
 iterator.... Ideally I would like iterate through the list using 
 foreach...

 Here's what I have so far.... Any help would be appreciated....

 class FastCell(T)  {
 T elt;
 FastCell!(T) next;

    this(T elt, FastCell!(T) next) {
        this.elt = elt;
        this.next = next;
    }
 }

 /**
 A linked-list of elements.
 **/
 class FastList(T)  {

    alias FastCell!(T) Fast;

 Fast head;

 /**
 Creates a new empty list.
 **/
 this() {
        head = null;
 }

 /**
 Add an element at the head of the list.
 **/
 void add(T item) {
 head = new Fast(item, head);
 }

 /**
 Returns the first element of the list, or null
 if the list is empty.
 **/
 T first() {
 return (head is null ? null : head.elt);
 }

 /**
 Removes the first element of the list and
 returns it or simply returns null if the
 list is empty.
 **/
 T pop() {
 Fast k = head;
 if( k is null )
 return null;
 else {
 head = k.next;
 return k.elt;
 }
 }

 /**
 Tells if a list is empty.
 **/
 bool isEmpty() {
 return (head is null);
 }

 /**
 Remove the first element that is [== v] from the list.
 Returns [true] if an element was removed, [false] otherwise.
 **/
 bool remove(T v) {
 Fast prev = null;
 Fast l = head;
 while( l !is null ) {
 if( l.elt == v ) {
 if( prev is null )
 head = l.next;
 else
 prev.next = l.next;
 break;
 }
 prev = l;
 l = l.next;
 }
 return (l !is null);
 }
 }

I don't know if you realize, but there are several Link List implementations 
that you can use.

But I'm assuming you're just playing around, so here's how you do foreach 
(in your LinkList class):

int opApply(int delegate(ref T) dg)
{
   int result = 0;
   Fast l = head;
   while(l !is null)
   {
       if((result = dg(l.elt)) != 0)
           break;
       l = l.next;
   }
   return result;
}

// usage

foreach(elem; myList)
    writefln(elem); // or Stdout(elem).newline, if you are using Tango

-Steve 

Mason Green <mason.green gmail.com> writes:

Steven Schveighoffer Wrote:

 I don't know if you realize, but there are several Link List implementations 
 that you can use.
 
 But I'm assuming you're just playing around, so here's how you do foreach 
 (in your LinkList class):
 

Thanks a lot Steve! Short and sweet.  Yes, I am playing around, although I plan
on using my link list in a Tango/Phobos independent library I'm working on. 

-Mason