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);
	}
}

"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

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