I think we should take another look at the possibility of adding linked lists directly to the language and formalizing the concept of iterator as a basic language feature.  Can this be done?  If so, how?

A linked list is, as you know, a string of pointers

struct T
{
    T* next;
    T* prev;
    int data;
}

{
    T* head = new T;  // I really want constructors for structs!!!!!
    head->data = 0;
    head->next = 0;
    head->prev = 0;

    T* ins = new T;
    ins->data = 1;
    ins->next = 0;
    ins->prev = head;
    head->next = ins;

    T* iter = head;
    while(iter)
    {
        printf("Node %d\n", iter->data);
        iter = iter->next;
    }
}


As you can see, it's extremely boilerplate code.  Lists are so well known that a compiler could use the ultimate best algorithm for manipulating them. And they could be syntactically wrapped so they look more like container/iterator.

It would be easy with generics.  In fact, how you implement list may be a big clue as to how to go about implementing generics.  Maybe something along the lines of:

struct T
{
    int data;
    T(int d) { data = d; }
}

dlist(T) mylist;
mylist.addtail(T(0));
mylist.addtail(T(1));
dlist(T).iterator iter = mylist.head;
while (iter)
{
    printf("Node %d\n",iter->data);
    ++iter;
}

Sean

"Sean L. Palmer" <seanpalmer@earthlink.net> wrote in news:ahckjc$6mt$1@digitaldaemon.com:

> I think we should take another look at the possibility of adding linked lists directly to the language and formalizing the concept of iterator as a basic language feature.  Can this be done?  If so, how?

I would like to see the concept of iterators added to the language.

I see two types of operations on on basic arrays and the other a more generalized form.

int[] arr;

for(int i in arr) // i gets successive values from arr
{
  //...
}

class Iter // or struct
{
  bit getNext(out aType i) { }
}

obj = new Iter;

for(aType i in obj) // i gets values from successive calls to getNext
{
  //...
}

The linked list works well this way

struct ListIter
{
  ListNode cur;

  bit getNext(out aType data)
  {
    if(cur.Next)
    {
      data = cur.data;
      return true;
    }
    return false;
  }
}

ListIter iter;
iter.cur = list.head; // I too wish of struct constructors

for(aType i in iter)
{
  //...
}

Forgot the cur = cur.Next;  :)

Patrick Down <pat@codemoon.com> wrote in news:Xns9251C45EE91F3patcodemooncom@63.105.9.61:

> struct ListIter
> {
>   ListNode cur;
> 
>   bit getNext(out aType data)
>   {
>     if(cur.Next)
>     {
>       data = cur.data;
        cur = cur.Next;
>       return true;
>     }
>     return false;
>   }
> }

On Sat, 20 Jul 2002 14:35:27 -0700 "Sean L. Palmer" <seanpalmer@earthlink.net> wrote:

> It would be easy with generics.  In fact, how you implement list may be a big clue as to how to go about implementing generics.  Maybe something along the lines of:
> 
> struct T
> {
>     int data;
>     T(int d) { data = d; }
> }
> 
> dlist(T) mylist;
> mylist.addtail(T(0));
> mylist.addtail(T(1));
> dlist(T).iterator iter = mylist.head;
> while (iter)
> {
>     printf("Node %d\n",iter->data);
>     ++iter;
> }

Might I propose another syntax?

	int[*] mylist;		// linked list of ints
	mylist ~= 0;		// add to back
	mylist = 1 ~ mylist	// add to front (compiler should optimize this)
	int[*].iterator i;	// or could it be just mylist.iterator?
	for (i = mylist.head; i; i++)
		printf("Node %d\n", *i);

Also, int[*] could be one-directional linked list, while int[**] would be two-directional.

Or is it better to use int[->] and int[<->] for this purpose?

Sean L. Palmer wrote:

> I think we should take another look at the possibility of adding linked
> lists directly to the language and formalizing the concept of iterator as a
> basic language feature.  Can this be done?  If so, how?
> 
> A linked list is, as you know, a string of pointers
> 
> struct T
> {
>     T* next;
>     T* prev;
>     int data;
> }
> 
> {
>     T* head = new T;  // I really want constructors for structs!!!!!
>     head->data = 0;
>     head->next = 0;
>     head->prev = 0;
> 
>     T* ins = new T;
>     ins->data = 1;
>     ins->next = 0;
>     ins->prev = head;
>     head->next = ins;
> 
>     T* iter = head;
>     while(iter)
>     {
>         printf("Node %d\n", iter->data);
>         iter = iter->next;
>     }
> }
> 
> 
> As you can see, it's extremely boilerplate code.  Lists are so well known
> that a compiler could use the ultimate best algorithm for manipulating them.
> And they could be syntactically wrapped so they look more like
> container/iterator.


The best generic algorithm with lists tends to be the same as the worst generic algorithm.  There's not a hell of a lot you can optimise.  But they are a useful generic type.


> It would be easy with generics.  In fact, how you implement list may be a
> big clue as to how to go about implementing generics.  Maybe something along
> the lines of:
> 
> struct T
> {
>     int data;
>     T(int d) { data = d; }
> }
> 
> dlist(T) mylist;
> mylist.addtail(T(0));
> mylist.addtail(T(1));
> dlist(T).iterator iter = mylist.head;
> while (iter)
> {
>     printf("Node %d\n",iter->data);
>     ++iter;
> }

-1 linked lists as a language feature, +1 iterators, -1 making it look anything at all like STL's.  I prefer Patrick's method, but using next, and without any special syntax.  A new extension to while, perhaps, to take for-style ';' separators for local variables.  I'm not opposed to for .. in, but getting over the Bright Barrier will require something more general, methinks.

Implementation hm.  I always need first/last, so I want a header, and prefer using List and Node for each:

    struct Node (TypeInfo $type)
    {
        List ($type) *list;
        Node ($type) *next;
        Node ($type) *prev;
        $type value;

        void remove ()
        {
            synchronize (list)
            {
                if (next) next.prev = prev;
                else list.last = prev;
                if (prev) prev.next = next;
                else list.first = next;
                next = prev = null;
            }
        }
    }

    class List (TypeInfo $type)
    {
        Node ($type) *first;
        Node ($type) *last;

        Node ($type) *alloc ()
        {
            return new Node ($type); /* Should use block allocation */
        }

        Node ($type) *append ($type value)
        {
            synchronize (this)
            {
                Node ($type) *node = alloc ();

                node.next = null;
                node.prev = last;
                if (last) last.next = node;
                else first = node;
                last = node;

                return node;
            }
        }

        ListIter ($type) iter ()
        {
            return ListIter ($type) (this);
        }
    }

    struct ListIter (TypeInfo $type)
    {
        List ($type) list;
        Node ($type) *node;

        this (List ($type) list)
        {
            this.list = list;
            node = this.first;
        }

        bit next (out $type value)
        {
            synchronize (list)
            {
                if (!node) return false;
                value = node.value;
                node = node.next;
                return true;
            }
        }

        bit next (out $type *value)
        {
            synchronize (list)
            {
                if (!node) return false;
                value = &node.value;
                node = node.next;
                return true;
            }
        }

        bit next (out Node ($type) *value)
        {
            synchronize (list)
            {
                if (!node) return false;
                value = node;
                node = node.next;
                return true;
            }
        }
    }

Plus many other methods.

This sounds fine to me!  ;)  Makes it look almost just like existing dynamic array syntax.

I like int[->] and int[<->] actually.

Is there some kind of search for dynamic array yet?  What about erase entry?

Sean

"Pavel Minayev" <evilone@omen.ru> wrote in message
news:CFN374584471657523@news.digitalmars.com...
On Sat, 20 Jul 2002 14:35:27 -0700 "Sean L. Palmer"
<seanpalmer@earthlink.net>
wrote:

> It would be easy with generics.  In fact, how you implement list may be a big clue as to how to go about implementing generics.  Maybe something
along
> the lines of:
>
> struct T
> {
>     int data;
>     T(int d) { data = d; }
> }
>
> dlist(T) mylist;
> mylist.addtail(T(0));
> mylist.addtail(T(1));
> dlist(T).iterator iter = mylist.head;
> while (iter)
> {
>     printf("Node %d\n",iter->data);
>     ++iter;
> }

Might I propose another syntax?

int[*] mylist; // linked list of ints
mylist ~= 0; // add to back
mylist = 1 ~ mylist // add to front (compiler should optimize this)
int[*].iterator i; // or could it be just mylist.iterator?
for (i = mylist.head; i; i++)
printf("Node %d\n", *i);

Also, int[*] could be one-directional linked list, while int[**] would be two-directional.

Or is it better to use int[->] and int[<->] for this purpose?

"Sean L. Palmer" <seanpalmer@earthlink.net> wrote in message news:ahemp8$25c6$1@digitaldaemon.com...
> I like int[->] and int[<->] actually.

Me too.

> Is there some kind of search for dynamic array yet?  What about erase
entry?

Ha! You do it all "by hand". Reminds me of BASIC times.

Sandor

On Tue, 23 Jul 2002 09:35:51 +0200 "Sandor Hojtsy" <hojtsy@index.hu> wrote:

> 
> "Sean L. Palmer" <seanpalmer@earthlink.net> wrote in message news:ahemp8$25c6$1@digitaldaemon.com...
>> I like int[->] and int[<->] actually.
> 
> Me too.
> 
>> Is there some kind of search for dynamic array yet?  What about erase
> entry?
> 
> Ha! You do it all "by hand". Reminds me of BASIC times.

Well, erasing entry is easy:

	// delete Nth element
	array = array[0 .. N] ~ array[N+1 .. array.length];

Still, some syntactic sugar would be great.

"Pavel Minayev" <evilone@omen.ru> wrote in message news:CFN374606396220486@news.digitalmars.com...
>>Well, erasing entry is easy:
>>// delete Nth element
>>array = array[0 .. N] ~ array[N+1 .. array.length];
>>Still, some syntactic sugar would be great.

Why do I have the feeling that the underlying implementation for that expression will be slower than it could be for an explicit erase method?

Sandor

"Sandor Hojtsy" <hojtsy@index.hu> wrote in message news:ai5klg$273n$1@digitaldaemon.com...
>
> "Pavel Minayev" <evilone@omen.ru> wrote in message news:CFN374606396220486@news.digitalmars.com...
> >>Well, erasing entry is easy:
> >>// delete Nth element
> >>array = array[0 .. N] ~ array[N+1 .. array.length];
> >>Still, some syntactic sugar would be great.
>
> Why do I have the feeling that the underlying implementation for that expression will be slower than it could be for an explicit erase method?

I think you're right... especially in debug builds.

Sean