www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - sorting of array containing user defined types

reply "Andre Fornacon" <afo zlug.org> writes:
hello d programmers,

i hope someone can help me with the following problem:
how can i sort an array of userdefined types - e.g.:
mysort.d:

import std.c.stdio;

struct qtr
{
	char[] m_server;
	char[] m_volume;
	uint m_used;

	char[] toString()
	{
		char[] rv=new char[256];
		int len=sprintf(rv,"%.*s:%.*s:%d",m_server,m_volume,m_used);
		return rv[0 .. len];
	}
}

int main(char[][] args)
{
	static qtr[] ql=[{"s1","v1",10},{"s0","v0",5},{"s2","v2",15}];

	printf("ql before sort : ql.len=%d\n",ql.length);
	foreach(int n,qtr q;ql)
		printf("(%d) %.*s\n",n,q.toString());

	ql.sort;

	printf("ql after sort : ql.len=%d\n",ql.length);
	foreach(int n,qtr q;ql)
		printf("(%d) %.*s\n",n,q.toString());

	return 0;
}

compiling this:

dmd mysort.d
gcc mysort.o -o mysort -lphobos -lpthread -lm
mysort.o: In function `_Dmain':
mysort.o(.gnu.linkonce.t_Dmain+0x75): undefined reference to  
`_init_21TypeInfo_S6mysort3qtr'
collect2: ld returned 1 exit status

how can i achieve this in the d programming language ?
in C(++) i can use qsort and a custom compare function.
i found a few vague for a d qsort in the phobos sources, but wasnt able to  
to get it used.

i already played with classes derived from TypeInfo and overloading opCmp  
- and got it to link,
but not running.
i'm pretty shure it must be something realy simple i overlooked in the  
documentation ?!.

thanks for your help !
andre
May 29 2004
next sibling parent reply J Anderson <REMOVEanderson badmama.com.au> writes:
Andre Fornacon wrote:


 hello d programmers,

 i hope someone can help me with the following problem:
 how can i sort an array of userdefined types - e.g.:
 mysort.d:

 import std.c.stdio;

 struct qtr
 {
     char[] m_server;
     char[] m_volume;
     uint m_used;

     char[] toString()
     {
         char[] rv=new char[256];
         int len=sprintf(rv,"%.*s:%.*s:%d",m_server,m_volume,m_used);
         return rv[0 .. len];
     }
 }

 int main(char[][] args)
 {
     static qtr[] ql=[{"s1","v1",10},{"s0","v0",5},{"s2","v2",15}];

     printf("ql before sort : ql.len=%d\n",ql.length);
     foreach(int n,qtr q;ql)
         printf("(%d) %.*s\n",n,q.toString());

     ql.sort;

     printf("ql after sort : ql.len=%d\n",ql.length);
     foreach(int n,qtr q;ql)
         printf("(%d) %.*s\n",n,q.toString());

     return 0;
 }

 compiling this:

 dmd mysort.d
 gcc mysort.o -o mysort -lphobos -lpthread -lm
 mysort.o: In function `_Dmain':
 mysort.o(.gnu.linkonce.t_Dmain+0x75): undefined reference to  
 `_init_21TypeInfo_S6mysort3qtr'
 collect2: ld returned 1 exit status

 how can i achieve this in the d programming language ?
 in C(++) i can use qsort and a custom compare function.
 i found a few vague for a d qsort in the phobos sources, but wasnt 
 able to  to get it used.

 i already played with classes derived from TypeInfo and overloading 
 opCmp  - and got it to link,
 but not running.
 i'm pretty shure it must be something realy simple i overlooked in 
 the  documentation ?!.

 thanks for your help !
 andre


You need to overload opCmp, however you have to do it like:

class A
{

int opCmp(Object obj)
{
   A objA =  cast(A) obj;
   ...ect...
}
}

The trick is that you have to casting from object.
I've asked Walter about getting this fixed (so you don't require 
casting) but I've got no reply.  So I don't even know if this ever will 
be fixed or if Walter thinks its a bug or not.

Then you can go:

A [] a;

...

a.sort;

-- 
-Anderson: http://badmama.com.au/~anderson/
May 29 2004
parent reply andre <afo zlug.org> writes:
On 2004-05-29, J Anderson <REMOVEanderson badmama.com.au> wrote:

 Andre Fornacon wrote:


 hello d programmers,

 i hope someone can help me with the following problem:
 how can i sort an array of userdefined types - e.g.:
 mysort.d:

 import std.c.stdio;

 struct qtr
 {
     char[] m_server;
     char[] m_volume;
     uint m_used;

     char[] toString()
     {
         char[] rv=new char[256];
         int len=sprintf(rv,"%.*s:%.*s:%d",m_server,m_volume,m_used);
         return rv[0 .. len];
     }
 }

 int main(char[][] args)
 {
     static qtr[] ql=[{"s1","v1",10},{"s0","v0",5},{"s2","v2",15}];

     printf("ql before sort : ql.len=%d\n",ql.length);
     foreach(int n,qtr q;ql)
         printf("(%d) %.*s\n",n,q.toString());

     ql.sort;

     printf("ql after sort : ql.len=%d\n",ql.length);
     foreach(int n,qtr q;ql)
         printf("(%d) %.*s\n",n,q.toString());

     return 0;
 }

 compiling this:

 dmd mysort.d
 gcc mysort.o -o mysort -lphobos -lpthread -lm
 mysort.o: In function `_Dmain':
 mysort.o(.gnu.linkonce.t_Dmain+0x75): undefined reference to  
 `_init_21TypeInfo_S6mysort3qtr'
 collect2: ld returned 1 exit status

 how can i achieve this in the d programming language ?
 in C(++) i can use qsort and a custom compare function.
 i found a few vague for a d qsort in the phobos sources, but wasnt 
 able to  to get it used.

 i already played with classes derived from TypeInfo and overloading 
 opCmp  - and got it to link,
 but not running.
 i'm pretty shure it must be something realy simple i overlooked in 
 the  documentation ?!.

 thanks for your help !
 andre


 You need to overload opCmp, however you have to do it like:

 class A
 {

 int opCmp(Object obj)
 {
    A objA =  cast(A) obj;
    ...ect...
 }
 }

 The trick is that you have to casting from object.
 I've asked Walter about getting this fixed (so you don't require 
 casting) but I've got no reply.  So I don't even know if this ever will 
 be fixed or if Walter thinks its a bug or not.

 Then you can go:

 A [] a;

 ...

 a.sort;


hello,
first thanks for your very fast reply !!!
it works now - great.
i played with the following opCmp signatures:
opCmp(void*) and opCmp(qtr q)

stupid me forgot to try  'opCmp(Object)' one ...

another question:
* any chance todo this for structs instead of classes ?!
 
* how do i do sorts for different values , e.g.
  (1) sort by the m_used field,
  (2) sort by another field (m_server)
 
that mean i need to used different comparision operator,
in other language (C(++),perl) thats no problem.
looks like the current capabilities for sorting are a bit limiting ?!

thank you very much !
-- 
// Andre  -> afo <at> zlug <dot> org
//
// "Why do I get this urge to go bowling everytime I see Tux?" ;-)
May 29 2004
next sibling parent reply Arcane Jill <Arcane_member pathlink.com> writes:
another question:
* any chance todo this for structs instead of classes ?!


I haven't tried this personally, but I see no reason why it shouldn't work. For
structs, you can presumably use the good old fashioned qsort function. Its
interface should, I believe, be exactly the same as in C.

Arcane Jill
May 29 2004
parent andre <afo zlug.org> writes:
On 2004-05-29, Arcane Jill <Arcane_member pathlink.com> wrote:

another question:
* any chance todo this for structs instead of classes ?!


 I haven't tried this personally, but I see no reason why it shouldn't work. For
 structs, you can presumably use the good old fashioned qsort function. Its
 interface should, I believe, be exactly the same as in C.

 Arcane Jill


hi,

thanks for the hint - you are right (of course).
it does work.
i wasnt aware that D array are fully compatible with C "array".
and i'm not that sure if it fully intentional ?!

imho it looks *very* ugly, to much 'extern (C)',casting,... for me ;-)

and to quote from http://www.digitalmars.com/d/ctod.html#sort :
---------------------------------------------------------------
The D Way
Sorting couldn't be easier: 

type[] array;
...
array.sort;// sort array in-place
---------------------------------------------------------------
sad that it works only for builtin types and classes.
are user defined structs *that* uncommon ?

i was thinking of something like

         array.sort(compare_function);

with compare_function defaulting to 'type.opCmp()'


for those interested in the code:

import std.c.stdio;

struct qtr
{
	char[] m_server;
	char[] m_volume;
	uint m_used;

	char[] toString()
	{
		char[] rv=new char[256];
		int len=sprintf(rv,"%.*s:%.*s:%d",m_server,m_volume,m_used);
		return rv[0 .. len];
	}
}

extern (C) void qsort(void* base,size_t nmemb,size_t size,int
(*cmp)(void*,void*));

extern (C) int qtr_compare(void* p1,void* p2)
{
	qtr* q1=cast(qtr*) p1;
	qtr* q2=cast(qtr*) p2;

	return q1.m_used < q2.m_used;
}

int main(char[][] args)
{
	static qtr[] ql=[{"s1","v1",10},{"s0","v0",5},{"s2","v2",15}];

	printf("ql before sort : ql.len=%d\n",ql.length);
	foreach(int n,qtr q;ql)
		printf("(%d) %.*s\n",n,q.toString());

	qsort(cast(void*)ql,ql.length,qtr.size,&qtr_compare);

	printf("ql after sort : ql.len=%d\n",ql.length);
	foreach(int n,qtr q;ql)
		printf("(%d) %.*s\n",n,q.toString());

	return 0;
}

greetings
-- 
// Andre  -> afo <at> zlug <dot> org
//
// "Why do I get this urge to go bowling everytime I see Tux?" ;-)
May 29 2004
prev sibling parent reply J Anderson <REMOVEanderson badmama.com.au> writes:
* how do i do sorts for different values , e.g.
  (1) sort by the m_used field,
  (2) sort by another field (m_server)
  


You could wrap the class inside another class, or use a state-machine.


that mean i need to used different comparision operator,
in other language (C(++),perl) thats no problem.
looks like the current capabilities for sorting are a bit limiting ?!

thank you very much !
  


I don't see how C++ is more powerful in this regard, you can always do 
the same in D.

-- 
-Anderson: http://badmama.com.au/~anderson/
May 29 2004
parent reply andre <afo zlug.org> writes:
On 2004-05-29, J Anderson <REMOVEanderson badmama.com.au> wrote:

* how do i do sorts for different values , e.g.
  (1) sort by the m_used field,
  (2) sort by another field (m_server)
  


 You could wrap the class inside another class, or use a state-machine.


that mean i need to used different comparision operator,
in other language (C(++),perl) thats no problem.
looks like the current capabilities for sorting are a bit limiting ?!

thank you very much !
  


 I don't see how C++ is more powerful in this regard, 


the stl provides a very clean separation between container classes
(vector,list,map,...) and algorithms (sort,count,transform,replace_if,...)
combining both using the iterator interface is one of the great things 
of the stl.
and you can use your own algorithms and/or your own container classes

if you move basic container classes like dynamic arrays, maps into the language
- which is imho a good thing - you have to put similar algorithms into
the language. 
or at least provide an interface allowing to use
custom implementation of algorithmns for e.g. sorting.


 you can always do the same in D.


well i relly like the things which are much easier todo using D than C++
e.g. string handling, array's , use std library, etc.
but imho (advanced) sorting isnt one of these ...

greetings
-- 
// Andre  -> afo <at> zlug <dot> org
//
// "Why do I get this urge to go bowling everytime I see Tux?" ;-)
May 29 2004
parent reply J Anderson <REMOVEanderson badmama.com.au> writes:
andre wrote:


On 2004-05-29, J Anderson <REMOVEanderson badmama.com.au> wrote:
  


* how do i do sorts for different values , e.g.
 (1) sort by the m_used field,
 (2) sort by another field (m_server)
 

      


You could wrap the class inside another class, or use a state-machine.

    


that mean i need to used different comparision operator,
in other language (C(++),perl) thats no problem.
looks like the current capabilities for sorting are a bit limiting ?!

thank you very much !
 

      


I don't see how C++ is more powerful in this regard, 
    


the stl provides a very clean separation between container classes
(vector,list,map,...) and algorithms (sort,count,transform,replace_if,...)
combining both using the iterator interface is one of the great things 
of the stl.
and you can use your own algorithms and/or your own container classes

if you move basic container classes like dynamic arrays, maps into the language
- which is imho a good thing - you have to put similar algorithms into
the language. 
or at least provide an interface allowing to use
custom implementation of algorithmns for e.g. sorting.

  


you can always do the same in D.
    


well i relly like the things which are much easier todo using D than C++
e.g. string handling, array's , use std library, etc.
but imho (advanced) sorting isnt one of these ...

greetings
  


I'm sure this will come out in a standard lib eventually.  Note that stl 
is a lib not part of C++ itself.  However for simple things D does maps 
and arrays in a much neater-to-use way (I'm looking at this from the 
client side rather then from the implementation side as you are).  It 
shouldn't be hard to map these into your own libraries if you so wish.

-- 
-Anderson: http://badmama.com.au/~anderson/
May 29 2004
next sibling parent reply "Sarat Venugopal" <dev_ng nospam.huelix.com> writes:
"J Anderson" <REMOVEanderson badmama.com.au> wrote in message
news:c9ac0l$2kh9$1 digitaldaemon.com...

 andre wrote:


On 2004-05-29, J Anderson <REMOVEanderson badmama.com.au> wrote:



* how do i do sorts for different values , e.g.
 (1) sort by the m_used field,
 (2) sort by another field (m_server)


You could wrap the class inside another class, or use a state-machine.




that mean i need to used different comparision operator,
in other language (C(++),perl) thats no problem.
looks like the current capabilities for sorting are a bit limiting ?!

thank you very much !


I don't see how C++ is more powerful in this regard,


the stl provides a very clean separation between container classes
(vector,list,map,...) and algorithms




(sort,count,transform,replace_if,...)

combining both using the iterator interface is one of the great things
of the stl.
and you can use your own algorithms and/or your own container classes

if you move basic container classes like dynamic arrays, maps into the




language

- which is imho a good thing - you have to put similar algorithms into
the language.
or at least provide an interface allowing to use
custom implementation of algorithmns for e.g. sorting.




you can always do the same in D.


well i relly like the things which are much easier todo using D than C++
e.g. string handling, array's , use std library, etc.
but imho (advanced) sorting isnt one of these ...

greetings


 I'm sure this will come out in a standard lib eventually.  Note that stl
 is a lib not part of C++ itself.  However for simple things D does maps
 and arrays in a much neater-to-use way (I'm looking at this from the
 client side rather then from the implementation side as you are).  It
 shouldn't be hard to map these into your own libraries if you so wish.


No. There is no "STL" nowadays, really. It is all just ISO C++.
std::vector<T> is just as much a first class citizen as T[]. The same with
std::sort() and qsort().

D is evolving, so there is no need to defend absense of certain things. I
may be wrong, but the D map looks more like an associative array, which is a
different beast from the map. Anyone looked into it?

Just being objective....

Best,
Sarat Venugopal
www.huelix.com



 -- 
 -Anderson: http://badmama.com.au/~anderson/
May 29 2004
next sibling parent reply J Anderson <REMOVEanderson badmama.com.au> writes:
Sarat Venugopal wrote:


"J Anderson" <REMOVEanderson badmama.com.au> wrote in message
news:c9ac0l$2kh9$1 digitaldaemon.com...
  


andre wrote:

    


On 2004-05-29, J Anderson <REMOVEanderson badmama.com.au> wrote:


      


* how do i do sorts for different values , e.g.
(1) sort by the m_used field,
(2) sort by another field (m_server)




          


You could wrap the class inside another class, or use a state-machine.



        


that mean i need to used different comparision operator,
in other language (C(++),perl) thats no problem.
looks like the current capabilities for sorting are a bit limiting ?!

thank you very much !




          


I don't see how C++ is more powerful in this regard,


        


the stl provides a very clean separation between container classes
(vector,list,map,...) and algorithms
      




(sort,count,transform,replace_if,...)
  


combining both using the iterator interface is one of the great things
of the stl.
and you can use your own algorithms and/or your own container classes

if you move basic container classes like dynamic arrays, maps into the
      




language
  


- which is imho a good thing - you have to put similar algorithms into
the language.
or at least provide an interface allowing to use
custom implementation of algorithmns for e.g. sorting.



      


you can always do the same in D.


        


well i relly like the things which are much easier todo using D than C++
e.g. string handling, array's , use std library, etc.
but imho (advanced) sorting isnt one of these ...

greetings


      


I'm sure this will come out in a standard lib eventually.  Note that stl
is a lib not part of C++ itself.  However for simple things D does maps
and arrays in a much neater-to-use way (I'm looking at this from the
client side rather then from the implementation side as you are).  It
shouldn't be hard to map these into your own libraries if you so wish.
    


No. There is no "STL" nowadays, really. It is all just ISO C++.
std::vector<T> is just as much a first class citizen as T[]. The same with
std::sort() and qsort().

D is evolving, so there is no need to defend absense of certain things. I
may be wrong, but the D map looks more like an associative array, which is a
different beast from the map. Anyone looked into it?

Just being objective....

Best,
Sarat Venugopal
www.huelix.com

  


I didn't mean that.  What I meant was that it should be pretty easy to 
do exactly what STL does in D as STL is a library not part of the 
language.  Also you can map a vector to a D array if you wish like:

class vector(type)
{
   private type [] A;
   type opIndex(int index) { return opIndex[index]; }
...
}

So it would be much easier to create something like stl in D then C++.

-- 
-Anderson: http://badmama.com.au/~anderson/
May 29 2004
parent reply "Sarat Venugopal" <dev_ng nospam.huelix.com> writes:
"J Anderson" <REMOVEanderson badmama.com.au> wrote in message
news:c9agac$2qk7$2 digitaldaemon.com...

 Sarat Venugopal wrote:


"J Anderson" <REMOVEanderson badmama.com.au> wrote in message
news:c9ac0l$2kh9$1 digitaldaemon.com...



andre wrote:




On 2004-05-29, J Anderson <REMOVEanderson badmama.com.au> wrote:





* how do i do sorts for different values , e.g.
(1) sort by the m_used field,
(2) sort by another field (m_server)


You could wrap the class inside another class, or use a state-machine.






that mean i need to used different comparision operator,
in other language (C(++),perl) thats no problem.
looks like the current capabilities for sorting are a bit limiting ?!

thank you very much !


I don't see how C++ is more powerful in this regard,


the stl provides a very clean separation between container classes
(vector,list,map,...) and algorithms




(sort,count,transform,replace_if,...)



combining both using the iterator interface is one of the great things
of the stl.
and you can use your own algorithms and/or your own container classes

if you move basic container classes like dynamic arrays, maps into the




language



- which is imho a good thing - you have to put similar algorithms into
the language.
or at least provide an interface allowing to use
custom implementation of algorithmns for e.g. sorting.






you can always do the same in D.


well i relly like the things which are much easier todo using D than








C++

e.g. string handling, array's , use std library, etc.
but imho (advanced) sorting isnt one of these ...

greetings


I'm sure this will come out in a standard lib eventually.  Note that stl
is a lib not part of C++ itself.  However for simple things D does maps
and arrays in a much neater-to-use way (I'm looking at this from the
client side rather then from the implementation side as you are).  It
shouldn't be hard to map these into your own libraries if you so wish.


No. There is no "STL" nowadays, really. It is all just ISO C++.
std::vector<T> is just as much a first class citizen as T[]. The same




with

std::sort() and qsort().

D is evolving, so there is no need to defend absense of certain things. I
may be wrong, but the D map looks more like an associative array, which




is a

different beast from the map. Anyone looked into it?

Just being objective....

Best,
Sarat Venugopal
www.huelix.com


 I didn't mean that.  What I meant was that it should be pretty easy to
 do exactly what STL does in D as STL is a library not part of the
 language.  Also you can map a vector to a D array if you wish like:

 class vector(type)
 {
    private type [] A;
    type opIndex(int index) { return opIndex[index]; }
 ...
 }

 So it would be much easier to create something like stl in D then C++.


Of course, creating a vector like class in D shouldn't be a problem. The
OP's premise was that sorting with custom criteria was not supported by the
language or existing libraries. That is a fact. qsort clearly cannot
understand classes, so that's not an option. Of course, you could do a
myriad of things to get the effect. What C++  provides is a std::sort() (and
other algorithms) with guarantees. The user can specify their own sorting
criterion. IOW, abstractions are not quite there yet.

I do agree that it is possible to create similar (or better) libraries in
D - whether it is easier (getting the same guarantees and performance) , I
don't know.

Best,
Sarat Venugopal
www.huelix.com
May 29 2004
parent reply Sean Kelly <sean f4.ca> writes:
Sarat Venugopal wrote:

 Of course, creating a vector like class in D shouldn't be a problem. The
 OP's premise was that sorting with custom criteria was not supported by the
 language or existing libraries. That is a fact. qsort clearly cannot
 understand classes, so that's not an option. Of course, you could do a
 myriad of things to get the effect. What C++  provides is a std::sort() (and
 other algorithms) with guarantees. The user can specify their own sorting
 criterion. IOW, abstractions are not quite there yet.
 
 I do agree that it is possible to create similar (or better) libraries in
 D - whether it is easier (getting the same guarantees and performance) , I
 don't know.


The only real need in D is iterators, and this can be accomplished with 
free functions (since D has built in vectors and maps which you'd want 
to support with the same semantics as library types).  ie. it may end up 
looking something like this:

dvector!(char).inst vec; // alias for char[] vec
dvector!(char).iterator i = dvector!(char).begin( vec );

It is probably possible to improve upon this, but I've held off on 
giving it much thought until I see what Matthew does with the DTL :)

Sean
May 29 2004
next sibling parent reply Sean Kelly <sean f4.ca> writes:
I should qualify this by saying that I think there's a far smaller need 
for iterators in D than there is in C++.  Between foreach, mixins, 
delegates, and the builtin container types D already supports a good 
(and slightly different) algorithm model.  But there's currently no 
support for reverse ranges or for treating library containers with 
similar semantics to builtin containers, so I have a feeling that 
something akin to iterators may be necessary.

Sean
May 29 2004
next sibling parent Arcane Jill <Arcane_member pathlink.com> writes:
In article <c9amsm$29f$1 digitaldaemon.com>, Sean Kelly says...

I should qualify this by saying that I think there's a far smaller need 
for iterators in D than there is in C++.  Between foreach, mixins, 
delegates, and the builtin container types D already supports a good 
(and slightly different) algorithm model.  But there's currently no 
support for reverse ranges or for treating library containers with 
similar semantics to builtin containers, so I have a feeling that 
something akin to iterators may be necessary.

Sean


I've been thinking for some time that D needs some standard containers, like C++
(only better, obviously). It came to crunch point today when I realized I needed
a fifo queue of ubytes. It's a simple class to write, but one of those things
that so many people are going to recode, over and over again. It occurred to me
that I could templatize it into a queue of anythings, but even then, it would
still not quite the clean standard interface we see in C++.

So for what it's worth, here are my thoughts:

*) We don't require iterators, as such (because there is another way of doing
it). In fact, we should probably outlaw iterator for two reasons: (i) iterators
are an abstraction of pointeres, and D discourages pointers. (ii) you can't
overload unary operator * or operator -> in D.

*) We DO want the same functionality, however. But it has to be "the D way".

The obvious thing to overload is operator [] (opSlice and opIndex), thereby
making things have the semantics of arrays. This would means that we are
generalizing the CONTAINER, not the POINTER. Well that's fine. I can live with
that.

So how would that work?

Well, instead of an input iterator (something which might read from a file, for
instance), you have a container which operloads the readable variant of opIndex.
It should either ignore the parameter, or throw an exception if the parameter is
not the next in sequence. The idea is to let you do:


        // input container example
        for (int i=0; i<a.length; ++i)
        {
            T t = a[i];
            // whatever
        }


and have it actually work! I guess you'd have to overload length() too, to
return int.max until end-of-file, 0 thereafter.

An output interator could be similarly implemented using the writable variant of
opIndex.

Forward iterators would be similar, of course, except that they must also
somehow preserve state. There are ways of doing that, but I haven't come up with
a "perfect" scheme yet. But most of the schemes I've come up with allow you to
implement backward iterators in a similar way. (The only problem with backward
iterators is, do you start the index at 0 and work downwards into negative
indeces? Do you start it at -1? Or do you start at int.max and keep everything
positive? I guess we'd need begin() and end() functions - length() has suddenly
stopped being enough.

And finally of course, random access containers we already have. Just overload
[] with the usual meaning.

With this API, generic algorithms could be written to take advantage of the
knowledge that all containers implement opIndex, and probably also begin() and
end(). (We'd need language support to add begin() and end() to existing array
types, but that sounds easy).

It would also be convenient to have some interfaces:

       InputContainer
       OutputContainer
       ForwardReadContainer
       ForwardWriteContainer
       RandomAccessReadContainer
       ...


and so on, so that generic algorithms can know what to expect. This is less
important for templates, but there's no need to force EVERYTHING to be a
template.

One problem with this is that built-in arrays would have to be castable to
RandomAccessReadContainer and RandomAccessWriteContainer, and there is no way to
make that happen without Walter's help.

In summary, then: "the D way" is something we haven't invented yet. It is
possible for us D users to implement something close, but for full
container/algorithm separation we'd need Walter's assistance to allow something
like the above. And before we even THINK about asking Walter for that, we should
agree (as much as a bunch of people on a forum can agree) on what kind of
interface we actually want.

Arcane Jill
May 29 2004
prev sibling next sibling parent reply "Walter" <newshound digitalmars.com> writes:
"Sean Kelly" <sean f4.ca> wrote in message
news:c9amsm$29f$1 digitaldaemon.com...

 I should qualify this by saying that I think there's a far smaller need
 for iterators in D than there is in C++.  Between foreach, mixins,
 delegates, and the builtin container types D already supports a good
 (and slightly different) algorithm model.  But there's currently no
 support for reverse ranges or for treating library containers with
 similar semantics to builtin containers, so I have a feeling that
 something akin to iterators may be necessary.


One way to do it is to derive from the container class type, and override
opApply() to access the members in the reverse manner.
May 30 2004
parent reply Arcane Jill <Arcane_member pathlink.com> writes:
In article <c9d7va$ejj$1 digitaldaemon.com>, Walter says...

One way to do it is to derive from the container class type, and override
opApply() to access the members in the reverse manner.


I must have missed the instructions for opApply. It doesn't seem to be listed in
the Operator Overloads page. Where can I find out about it?

Arcane Jill
May 30 2004
parent J Anderson <REMOVEanderson badmama.com.au> writes:
Arcane Jill wrote:


In article <c9d7va$ejj$1 digitaldaemon.com>, Walter says...
  


One way to do it is to derive from the container class type, and override
opApply() to access the members in the reverse manner.
    


I must have missed the instructions for opApply. It doesn't seem to be listed in
the Operator Overloads page. Where can I find out about it?

Arcane Jill
  


Well it's not an operator, its a statement overloaded.  See 
http://www.digitalmars.com/d/statement.html.

-- 
-Anderson: http://badmama.com.au/~anderson/
May 30 2004
prev sibling parent Antti =?iso-8859-1?Q?Syk=E4ri?= <jsykari gamma.hut.fi> writes:
In article <c9amsm$29f$1 digitaldaemon.com>, Sean Kelly wrote:

 (and slightly different) algorithm model.  But there's currently no 
 support for reverse ranges or for treating library containers with 
 similar semantics to builtin containers, so I have a feeling that 
 something akin to iterators may be necessary.


Indeed. Iterators wouldn't be bad. I've been thinking of integrating
streams and iterators, something like:

interface InputStream(T)
{
    bool valid()
    T get();
    void next();
}

class Set(T)
{
    InputStream!(T) iterate() { .. }
    InputStream!(T) iterate_backwards() { .. }
    ..
}

void f(Set!(int) set_of_integers)
{
    InputStream!(int) stream = set_of_integers.iterate();

    // Print "1 2 3 4 ... "
    while (stream.valid)
    {
        printf("%d\n", stream.get());
        stream.next();
    }

    // Print "... 4 3 2 1"
    stream = set_of_integers.iterate_backwards();
    while (stream.valid)
    {
        printf("%d\n", stream.get());
        stream.next();
    }
}

Or, similarly, use streams for whatever you like, for example to iterate
over primes or real numbers, to filter data from other streams, read
data from standard input or a file, etc.

-Antti


-- 
I will not be using Plan 9 in the creation of weapons of mass destruction
to be used by nations other than the US.
May 30 2004
prev sibling parent "Matthew" <matthew.hat stlsoft.dot.org> writes:
"Sean Kelly" <sean f4.ca> wrote in message news:c9als7$q7$1 digitaldaemon.com...

 Sarat Venugopal wrote:

 Of course, creating a vector like class in D shouldn't be a problem. The
 OP's premise was that sorting with custom criteria was not supported by the
 language or existing libraries. That is a fact. qsort clearly cannot
 understand classes, so that's not an option. Of course, you could do a
 myriad of things to get the effect. What C++  provides is a std::sort() (and
 other algorithms) with guarantees. The user can specify their own sorting
 criterion. IOW, abstractions are not quite there yet.

 I do agree that it is possible to create similar (or better) libraries in
 D - whether it is easier (getting the same guarantees and performance) , I
 don't know.


 The only real need in D is iterators, and this can be accomplished with
 free functions (since D has built in vectors and maps which you'd want
 to support with the same semantics as library types).  ie. it may end up
 looking something like this:

 dvector!(char).inst vec; // alias for char[] vec
 dvector!(char).iterator i = dvector!(char).begin( vec );

 It is probably possible to improve upon this, but I've held off on
 giving it much thought until I see what Matthew does with the DTL :)


Not much longer old bean. June's going to be a very nasty experience for me, but
July will be much better. Expect much action in July.

btw, iterators will be one of the four cornerstones of DTL enumeration, but will
be the poorer (and less needed) brother to freaching and ranges.
Jun 04 2004
prev sibling parent "Matthew" <matthew.hat stlsoft.dot.org> writes:
 I'm sure this will come out in a standard lib eventually.  Note that stl
 is a lib not part of C++ itself.  However for simple things D does maps
 and arrays in a much neater-to-use way (I'm looking at this from the
 client side rather then from the implementation side as you are).  It
 shouldn't be hard to map these into your own libraries if you so wish.


 No. There is no "STL" nowadays, really. It is all just ISO C++.


Depends on your viewpoint. STL is still clearly identifiable, but it is a subset
of what is the C++ standard library.


 std::vector<T> is just as much a first class citizen as T[]. The same with
 std::sort() and qsort().


Again, it depends. In several important ways std::vector<T> is not the same as
T[]. For a start, std::vector<T> can be represented differently by different
compilers and/or libraries on the same operating environment. T[] is far more
consistent, packing pragmas notwithstanding.


 D is evolving, so there is no need to defend absense of certain things. I
 may be wrong, but the D map looks more like an associative array, which is a
 different beast from the map. Anyone looked into it?
Jun 04 2004
prev sibling parent reply andre <afo zlug.org> writes:
On 2004-05-29, J Anderson <REMOVEanderson badmama.com.au> wrote:

 andre wrote:


On 2004-05-29, J Anderson <REMOVEanderson badmama.com.au> wrote:
  


* how do i do sorts for different values , e.g.
 (1) sort by the m_used field,
 (2) sort by another field (m_server)
 

      


You could wrap the class inside another class, or use a state-machine.

    


that mean i need to used different comparision operator,
in other language (C(++),perl) thats no problem.
looks like the current capabilities for sorting are a bit limiting ?!

thank you very much !
 

      


I don't see how C++ is more powerful in this regard, 
    


the stl provides a very clean separation between container classes
(vector,list,map,...) and algorithms (sort,count,transform,replace_if,...)
combining both using the iterator interface is one of the great things 
of the stl.
and you can use your own algorithms and/or your own container classes

if you move basic container classes like dynamic arrays, maps into the language
- which is imho a good thing - you have to put similar algorithms into
the language. 
or at least provide an interface allowing to use
custom implementation of algorithmns for e.g. sorting.

  


you can always do the same in D.
    


well i relly like the things which are much easier todo using D than C++
e.g. string handling, array's , use std library, etc.
but imho (advanced) sorting isnt one of these ...

greetings
  


 I'm sure this will come out in a standard lib eventually.  Note that stl 
 is a lib not part of C++ itself.  However for simple things D does maps 
 and arrays in a much neater-to-use way (I'm looking at this from the 
 client side rather then from the implementation side as you are).  It 
 shouldn't be hard to map these into your own libraries if you so wish.


just to clarify - as pointed out in comment made by Arcane Jill and J Anderson
to my earlier posting there are 2 solutions to my problem:

* for arrays of builtin types - use the .sort property
  this work for classes as well if you implement 'int opCmp(Object)'

* for struct's you can use the qsort from libc.
  BUT you have to rely on the fact that D arrays are api compatible 
  with C "arrays". this might be the case now, but might change in the future?!

  to quote http://www.digitalmars.com/d/arrays.html
---------------------------------------
Static Arrays

int[3] s;

These are analogous to C arrays. Static arrays are distinguished by having a
length fixed at compile time. 

Dynamic Arrays

int[] a;

Dynamic arrays contain a length and a garbage collected pointer to the array
data.
---------------------------------------
in this context i have problems with the last statement.


whats imho a deficiency of D is that there are these two difference
solutions to the one problem 'sorting of arrays'.
it would be nice to have this inconsistency fixed.


thank yu for all the comments !

happy hacking ! ;-)
-- 
// Andre  -> afo <at> zlug <dot> org
//
// "Why do I get this urge to go bowling everytime I see Tux?" ;-)
May 29 2004
parent "Walter" <newshound digitalmars.com> writes:
"andre" <afo zlug.org> wrote in message
news:slrncbhrf5.hme.afo pvr.fornacon.org...

 * for struct's you can use the qsort from libc.
   BUT you have to rely on the fact that D arrays are api compatible
   with C "arrays". this might be the case now, but might change in the


future?!

No. Such compatibility is an important feature.
May 30 2004
prev sibling next sibling parent "Carlos Santander B." <carlos8294 msn.com> writes:
"Andre Fornacon" <afo zlug.org> escribió en el mensaje
news:opr8regpv6j1o6gb news.digitalmars.com
| hello d programmers,
|
| i hope someone can help me with the following problem:
| how can i sort an array of userdefined types - e.g.:
| mysort.d:
|
| import std.c.stdio;
|
| struct qtr
| {
| char[] m_server;
| char[] m_volume;
| uint m_used;
|
| char[] toString()
| {
| char[] rv=new char[256];
| int len=sprintf(rv,"%.*s:%.*s:%d",m_server,m_volume,m_used);
| return rv[0 .. len];
| }
| }
|
| int main(char[][] args)
| {
| static qtr[] ql=[{"s1","v1",10},{"s0","v0",5},{"s2","v2",15}];
|
| printf("ql before sort : ql.len=%d\n",ql.length);
| foreach(int n,qtr q;ql)
| printf("(%d) %.*s\n",n,q.toString());
|
| ql.sort;
|
| printf("ql after sort : ql.len=%d\n",ql.length);
| foreach(int n,qtr q;ql)
| printf("(%d) %.*s\n",n,q.toString());
|
| return 0;
| }
|
| compiling this:
|
| dmd mysort.d
| gcc mysort.o -o mysort -lphobos -lpthread -lm
| mysort.o: In function `_Dmain':
| mysort.o(.gnu.linkonce.t_Dmain+0x75): undefined reference to
| `_init_21TypeInfo_S6mysort3qtr'
| collect2: ld returned 1 exit status
|
| how can i achieve this in the d programming language ?
| in C(++) i can use qsort and a custom compare function.
| i found a few vague for a d qsort in the phobos sources, but wasnt able to
| to get it used.
|
| i already played with classes derived from TypeInfo and overloading opCmp
| - and got it to link,
| but not running.
| i'm pretty shure it must be something realy simple i overlooked in the
| documentation ?!.
|
| thanks for your help !
| andre

structs don't get a typeinfo. Try what's in
http://www.prowiki.org/wiki4d/wiki.cgi?HelmutLeitner/StructSort, but make
sure to read what's in http://www.digitalmars.com/drn-bin/wwwnews?D/28644
(from the old ng).

-----------------------
Carlos Santander Bernal
May 29 2004
prev sibling parent "Walter" <newshound digitalmars.com> writes:
"Andre Fornacon" <afo zlug.org> wrote in message
news:opr8regpv6j1o6gb news.digitalmars.com...

 how can i achieve this in the d programming language ?


At the moment, you'd have to write a custom TypeInfo for your struct. This
kinda sucks, though. I'm working on a revamp of this to fix it.
May 30 2004