www.digitalmars.com         C & C++   DMDScript  

D - Suggestion: 'sorted' Property for Arrays

reply Russell Lewis <spamhole-2001-07-16 deming-os.org> writes:
I am writing some D code where I have some arrays that must always 
remain sorted.  So I'm adding asserts periodically to make sure that my 
arrays are sorted.  Currently, I'm doing this:

assert(array[] == array.dup.sort);

But it would be nicer to just have the compiler provide a boolean property:

assert(array.sorted);

Of course, that would not be an actual variable in the array 
reference...instead, the compiler would iterate through the array and 
confirm that the array is sorted (or not), and return the answer.
Sep 25 2002
parent reply Mac Reiter <Mac_member pathlink.com> writes:
In article <3D91DE98.5060905 deming-os.org>, Russell Lewis says...
I am writing some D code where I have some arrays that must always 
remain sorted.  So I'm adding asserts periodically to make sure that my 
arrays are sorted.  Currently, I'm doing this:

assert(array[] == array.dup.sort);

But it would be nicer to just have the compiler provide a boolean property:

assert(array.sorted);

Of course, that would not be an actual variable in the array 
reference...instead, the compiler would iterate through the array and 
confirm that the array is sorted (or not), and return the answer.

The fact that the assert will remove the code during a release build changes the following argument, but I'll throw it out there anyway: If, instead of "assert()", you were doing "if()", then I would suggest that making the test is unnecessary and inefficient. If you do: if (! array.sorted) { array.sort; } you would be better off just using: array.sort; The first code makes one linear pass, followed by a sorting if needed. The second code does either one linear pass or a sorting, but never both. Of course, if you are only using this in your asserts to make sure that your other code is behaving properly, then your release build won't have any of this, and what you're doing is fine. You could make a template with a "bit sorted(in T[])" query function in it, I suppose. The property would be nicer, though. Mac
Sep 25 2002
parent reply Russell Lewis <spamhole-2001-07-16 deming-os.org> writes:
Mac Reiter wrote:
 In article <3D91DE98.5060905 deming-os.org>, Russell Lewis says...
 
I am writing some D code where I have some arrays that must always 
remain sorted.  So I'm adding asserts periodically to make sure that my 
arrays are sorted.  Currently, I'm doing this:

assert(array[] == array.dup.sort);

But it would be nicer to just have the compiler provide a boolean property:

assert(array.sorted);

Of course, that would not be an actual variable in the array 
reference...instead, the compiler would iterate through the array and 
confirm that the array is sorted (or not), and return the answer.

The fact that the assert will remove the code during a release build changes the following argument, but I'll throw it out there anyway: If, instead of "assert()", you were doing "if()", then I would suggest that making the test is unnecessary and inefficient. If you do: if (! array.sorted) { array.sort; } you would be better off just using: array.sort; The first code makes one linear pass, followed by a sorting if needed. The second code does either one linear pass or a sorting, but never both. Of course, if you are only using this in your asserts to make sure that your other code is behaving properly, then your release build won't have any of this, and what you're doing is fine. You could make a template with a "bit sorted(in T[])" query function in it, I suppose. The property would be nicer, though. Mac

You're right that array.sort would give me a sorted array without having to test first. But I'd like to be able to get an up/down validation of "is my program correct or not"
Sep 25 2002
parent "Walter" <walter digitalmars.com> writes:
"Russell Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
news:3D92257A.7010104 deming-os.org...
 You're right that array.sort would give me a sorted array without having
 to test first.  But I'd like to be able to get an up/down validation of
 "is my program correct or not"

A couple observations - I think Mac is correct in that testing to see if an array is sorted is inherent in sorting an array, so there is little efficiency to be gained by testing first. Testing for sort is a great idea for a contract, but contracts don't need to operate efficiently, so your one liner to do it (which is clever, I wouldn't have thought of it) is up to the job.
Sep 29 2002