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)
  

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 !
  

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)
  

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 !
  


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)
 

      

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 !
 

      


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

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)

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 !


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


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


- 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

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)




          

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 !




          


(vector,list,map,...) and algorithms


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
      


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


        

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

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

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)

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 !


(vector,list,map,...) and algorithms


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


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





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

greetings

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


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


different beast from the map. Anyone looked into it?

Just being objective....

Best,
Sarat Venugopal
www.huelix.com

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

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)
 

      

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 !
 

      


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

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

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 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