www.digitalmars.com         C & C++   DMDScript  

D - link list, iterator, and more

reply Robert <Robert_member pathlink.com> writes:
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
next sibling parent reply "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)

Already doable: 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" instead.
 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)

I feel the same away about this as I did '<'... although if we were 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...

- C. Sauls - Invironz
Dec 11 2003
parent reply Robert <Robert_member pathlink.com> writes:
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)

Already doable: 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)

 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" instead.

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)

I feel the same away about this as I did '<'... although if we were 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
parent reply "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)

Already doable: 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 creates a duplicate array using '.dup' and returns its address instead 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" instead.

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)

I feel the same away about this as I did '<'... although if we were 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
parent reply 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
parent davepermen <davepermen_member pathlink.com> writes:
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
prev sibling parent "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,

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

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

 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