D - link list, iterator, and more

• Robert (45/45) Dec 11 2003 D has normal array and associative array, but not link list.
• C. Sauls (35/56) Dec 11 2003 Already doable:
• Robert (25/57) Dec 11 2003 Yeah. Indeed, I can do it.
• C. Sauls (11/107) Dec 12 2003 I think someone is already working on a D equivelant to STL to be added
• Ilya Minkov (12/17) Dec 12 2003 Daniel Yokomiso from Brazil was. Here's the link.
• davepermen (2/3) Dec 12 2003 you want good luck, or bad luck?
• Y.Tomino (16/62) Dec 11 2003 I think we should write "link list" for every case.
```D has normal array and associative array, but not link list.
I would like it.
It is because all of them are `container' and
I think that they should be dealt with by unified approach.
To that end, link list is also directly supported by D.
And, I would like reversal foreach (rforeach), insert, erase, find, iterator,
and sort using user-defined comparison function (or opCmp and opEqual) too.
I think that it's barren to make class template for myself in order to realize
these features,
and iterator helps us to use insert, erase and find and make many other
features.

e.g.

int[*] a;  // link list as std::list<int> in C++

a.push(9);         // [9] : equivalent to a ~= 9;
a.push(4);         // [9; 4] : equivalent to a ~= 4;
a.rpush(3);        // [3; 9; 4]
a.rpush(1);        // [1; 3; 9; 4]
b = a.peek();      // b is 4 and a is invariant
b = a.rpeek();     // b is 1 and a is invariant
b = a.pop();       // b is 4 and a is [1; 3; 9]
b = a.rpop();      // b is 1 and a is [3; 9]
foreach(int elem; a)  { printf("%d;", elem); }  // 3;9;
rforeach(int elem; a) { printf("%d;", elem); }  // 9;3;
static int[*] b = [3; 4; 5];
a ~= b;            // [3; 9; 3; 4; 5]

int[<] a;  // LIFO stack (implemented by one way list)

a.push(5);        // [5] : equivalent to a ~= 5;
a.push(7);        // [7; 5] : equivalent to a ~= 7;
a.push(0);        // [0; 7; 5]
b = a.peek();     // b is 0 and a is invariant
b = a.pop();      // b is 0 and a is [7; 5]
foreach(int elem; a) { printf("%d;", elem); }   // 7,5,

// Error! ('cause one way list)
rforeach(int elem; a) { printf("%d;", elem); }

int[<<] a;  // FIFO queue (implemented by one way list)

a.push(5);        // [5]
a.push(7);        // [5; 7]
a.push(0);        // [5; 7; 0]
b = a.peek();     // b is 5 and a is invariant
b = a.pop();      // b is 5 and a is [7; 0]
foreach(int elem; a) { printf("%d;", elem); }   // 7;0;

// Error! ('cause one way list)
rforeach(int elem; a) { printf("%d;", elem); }

Above syntax is tentative...

Robert (Japanese)
```
Dec 11 2003
"C. Sauls" <ibisbasenji yahoo.com> writes:
```Robert wrote:
D has normal array and associative array, but not link list.

Linked lists easily implemented as templated structs.

And, I would like reversal foreach (rforeach)

int[15] iarray;
foreach (int i; iarray.reverse)
{ ... }

int[*] a;  // link list as std::list<int> in C++

a.push(9);         // [9] : equivalent to a ~= 9;
a.push(4);         // [9; 4] : equivalent to a ~= 4;

I, for one, rather like just typing ~= to do this...

a.rpush(3);        // [3; 9; 4]
a.rpush(1);        // [1; 3; 9; 4]

Now this has a point, since as far as I know 'a' ~ "abc" doesn't work.
Maybe it should?  Although it would be a bit backward.  Maybe we should
allow an array literal format?  So then this could become {'a'} ~ "abc"

b = a.peek();      // b is 4 and a is invariant
b = a.rpeek();     // b is 1 and a is invariant

b = a[0];
b = a[a.length - 1];

Although like some others I think we need a last-index symbol for
arrays.  I'm somewhat fond of [\$] but only because I work with MOO and
that's how MOO scripts do it.

b = a.pop();       // b is 4 and a is [1; 3; 9]
b = a.rpop();      // b is 1 and a is [3; 9]

Now this could be useful.  As it is:
b = a[0];
a = a[1..a.length];

b = a[a.length - 1];
a = a[0..a.length - 1];

foreach(int elem; a)  { printf("%d;", elem); }  // 3;9;
rforeach(int elem; a) { printf("%d;", elem); }  // 9;3;

foreach(int elem; a)         { printf("%d;", elem); } // 3;9;
foreach(int elem; a.reverse) { printf("%d;", elem); } // 9;3;

static int[*] b = [3; 4; 5];
a ~= b;            // [3; 9; 3; 4; 5]

As stated before, I do feel we need an array literal syntax that can be
plugged into expressions.

int[<] a;  // LIFO stack (implemented by one way list)

Stacks, like linked lists, are easily implented with (templated)
structs.  And although your type[*] may have some potential.. I think
type[<] is just... well, odd.

// Error! ('cause one way list)
rforeach(int elem; a) { printf("%d;", elem); }

Hmm.

int[<<] a;  // FIFO queue (implemented by one way list)

going to use those symbols, I would recommend '>' for this one.. and
maybe even '<>' for the bidirectional list, for consistancy sake.

Above syntax is tentative...

Duly noted.

- C. Sauls
- Invironz
```
Dec 11 2003
```In article <brajde\$2lte\$1 digitaldaemon.com>, C. Sauls says...
Robert wrote:
D has normal array and associative array, but not link list.

Linked lists easily implemented as templated structs.

Yeah.  Indeed, I can do it.
But, linked list is one of the most standard data structures.
IMHO, this should be given by D or Phobos.

And, I would like reversal foreach (rforeach)

int[15] iarray;
foreach (int i; iarray.reverse)
{ ... }

This has two problems.
One is that iarray is changed and we should pay some unnecessary cost.
Another is that 'i's of
foreach(int i, int n; iarray.reverse)

are indices of iarray.reverse, not of iarray before reversal.

int[*] a;  // link list as std::list<int> in C++

a.push(9);         // [9] : equivalent to a ~= 9;
a.push(4);         // [9; 4] : equivalent to a ~= 4;

I, for one, rather like just typing ~= to do this...

a.rpush(3);        // [3; 9; 4]
a.rpush(1);        // [1; 3; 9; 4]

Now this has a point, since as far as I know 'a' ~ "abc" doesn't work.
Maybe it should?  Although it would be a bit backward.  Maybe we should
allow an array literal format?  So then this could become {'a'} ~ "abc"

Linked lists can easily do push, rpush, pop, rpop, insert and erase,
and any repositionings don't occur.
This is a most different point between linked lists and arrays.
Though arrays can do anything which linked lists can do, it is not always
efficient.
Unless indexing is needed, linked lists are more useful than arrays in many
cases.

static int[*] b = [3; 4; 5];
a ~= b;            // [3; 9; 3; 4; 5]

As stated before, I do feel we need an array literal syntax that can be
plugged into expressions.

Me, too.

int[<] a;  // LIFO stack (implemented by one way list)

Stacks, like linked lists, are easily implented with (templated)
structs.  And although your type[*] may have some potential..

Stacks and queues can be implemented with one-way linked list enough.
It can be more efficiently implemented than two-way linked list.

I think type[<] is just... well, odd.

int[<<] a;  // FIFO queue (implemented by one way list)

going to use those symbols, I would recommend '>' for this one.. and
maybe even '<>' for the bidirectional list, for consistancy sake.

To tell the truth,
I was thinking the syntax was odd, too.
(So, I wrote "Above syntax is tentative...")
I thought the typo is the most troublesome problem.
It's very difficult to solve it...
I have no ideas.

Robert (Japanese)
```
Dec 11 2003
"C. Sauls" <ibisbasenji yahoo.com> writes:
```Robert wrote:
In article <brajde\$2lte\$1 digitaldaemon.com>, C. Sauls says...

Robert wrote:

D has normal array and associative array, but not link list.

Linked lists easily implemented as templated structs.

Yeah.  Indeed, I can do it.
But, linked list is one of the most standard data structures.
IMHO, this should be given by D or Phobos.

I think someone is already working on a D equivelant to STL to be added
to Phobos.  Try searching for it.

And, I would like reversal foreach (rforeach)

int[15] iarray;
foreach (int i; iarray.reverse)
{ ... }

This has two problems.
One is that iarray is changed and we should pay some unnecessary cost.
Another is that 'i's of

foreach(int i, int n; iarray.reverse)

are indices of iarray.reverse, not of iarray before reversal.

I hear you, but I think I might be misunderstanding something.. :)  If I
recall correctly, the reversed array returned by '.reverse' first
of the address of the original.

int[*] a;  // link list as std::list<int> in C++

a.push(9);         // [9] : equivalent to a ~= 9;
a.push(4);         // [9; 4] : equivalent to a ~= 4;

I, for one, rather like just typing ~= to do this...

a.rpush(3);        // [3; 9; 4]
a.rpush(1);        // [1; 3; 9; 4]

Now this has a point, since as far as I know 'a' ~ "abc" doesn't work.
Maybe it should?  Although it would be a bit backward.  Maybe we should
allow an array literal format?  So then this could become {'a'} ~ "abc"

Linked lists can easily do push, rpush, pop, rpop, insert and erase,
and any repositionings don't occur.
This is a most different point between linked lists and arrays.
Though arrays can do anything which linked lists can do, it is not always
efficient.
Unless indexing is needed, linked lists are more useful than arrays in many
cases.

static int[*] b = [3; 4; 5];
a ~= b;            // [3; 9; 3; 4; 5]

As stated before, I do feel we need an array literal syntax that can be
plugged into expressions.

Me, too.

Preach it brother!

int[<] a;  // LIFO stack (implemented by one way list)

Stacks, like linked lists, are easily implented with (templated)
structs.  And although your type[*] may have some potential..

Stacks and queues can be implemented with one-way linked list enough.
It can be more efficiently implemented than two-way linked list.

I think type[<] is just... well, odd.

int[<<] a;  // FIFO queue (implemented by one way list)

going to use those symbols, I would recommend '>' for this one.. and
maybe even '<>' for the bidirectional list, for consistancy sake.

To tell the truth,
I was thinking the syntax was odd, too.
(So, I wrote "Above syntax is tentative...")
I thought the typo is the most troublesome problem.
It's very difficult to solve it...
I have no ideas.

Fair enough.  :)  You do have some ideas in there.  Walter????  :D

- C. Sauls
- Invironz
```
Dec 12 2003
Ilya Minkov <minkov cs.tum.edu> writes:
```C. Sauls wrote:
I think someone is already working on a D equivelant to STL to be added
to Phobos.  Try searching for it.

Daniel Yokomiso from Brazil was. Here's the link.

http://www.minddrome.com/produtos/d/

Scroll down to librararies, Deimos.

The version out there is quite old and has to be fixed to work with new
compiler.

We are all thankful to Daniel because he is the one who made pressure on
Walter to include templates. Without him we were now still in the stone
age of "Java with Structs" or "C with GC & Classes". :)

As stated before, I do feel we need an array literal syntax that can
be plugged into expressions.

Preach it brother!

Walter promised to do it, IIRC

-eye

PS. got a math test tomorrow. wish me luck everyone.
```
Dec 12 2003
```PS. got a math test tomorrow. wish me luck everyone.

you want good luck, or bad luck?

well, i wish you good luck. hope that helps
```
Dec 12 2003
"Y.Tomino" <demoonlit inter7.jp> writes:
```D is an another language.
When we want to use C++, we should use C++.

int[*] a;  // link list as std::list<int> in C++

I think we should write "link list" for every case.
"Array" is simple, but there are many variation of "list".
Optimal method rely the case.
We can use template for other containers.

However, I'd like to use ['a']~"abc", too.
['a'] convert from T to T[] like constant arrays of D. (const char[] a =
['x', 'y', 'z'];)
But, &c[0..1] works now... (c is a variable)

YT

"Robert" <Robert_member pathlink.com> wrote in message
news:br9dvd\$sg9\$1 digitaldaemon.com...
D has normal array and associative array, but not link list.
I would like it.
It is because all of them are `container' and
I think that they should be dealt with by unified approach.
To that end, link list is also directly supported by D.
And, I would like reversal foreach (rforeach), insert, erase, find,

iterator,
and sort using user-defined comparison function (or opCmp and opEqual)

too.
I think that it's barren to make class template for myself in order to

realize
these features,
and iterator helps us to use insert, erase and find and make many other
features.

e.g.

int[*] a;  // link list as std::list<int> in C++

a.push(9);         // [9] : equivalent to a ~= 9;
a.push(4);         // [9; 4] : equivalent to a ~= 4;
a.rpush(3);        // [3; 9; 4]
a.rpush(1);        // [1; 3; 9; 4]
b = a.peek();      // b is 4 and a is invariant
b = a.rpeek();     // b is 1 and a is invariant
b = a.pop();       // b is 4 and a is [1; 3; 9]
b = a.rpop();      // b is 1 and a is [3; 9]
foreach(int elem; a)  { printf("%d;", elem); }  // 3;9;
rforeach(int elem; a) { printf("%d;", elem); }  // 9;3;
static int[*] b = [3; 4; 5];
a ~= b;            // [3; 9; 3; 4; 5]

int[<] a;  // LIFO stack (implemented by one way list)

a.push(5);        // [5] : equivalent to a ~= 5;
a.push(7);        // [7; 5] : equivalent to a ~= 7;
a.push(0);        // [0; 7; 5]
b = a.peek();     // b is 0 and a is invariant
b = a.pop();      // b is 0 and a is [7; 5]
foreach(int elem; a) { printf("%d;", elem); }   // 7,5,

// Error! ('cause one way list)
rforeach(int elem; a) { printf("%d;", elem); }

int[<<] a;  // FIFO queue (implemented by one way list)

a.push(5);        // [5]
a.push(7);        // [5; 7]
a.push(0);        // [5; 7; 0]
b = a.peek();     // b is 5 and a is invariant
b = a.pop();      // b is 5 and a is [7; 0]
foreach(int elem; a) { printf("%d;", elem); }   // 7;0;

// Error! ('cause one way list)
rforeach(int elem; a) { printf("%d;", elem); }

Above syntax is tentative...

Robert (Japanese)

```
Dec 11 2003