[M3devel] generic binary search in standard Modula-3 library?

[Jay K]

 > c) surely we con't need to handcode binary search here in the first place there is some generic reusable version?


The closest precedent I can find is:

http://modula3.elegosoft.com/cm3/doc/help/gen_html/libm3/src/sort/ArraySort.ig.html

 

so I propose *something like*:

 

m3core/src/binarysearch/BinarySearch.ig.
PROCEDURE BinarySearch(READONLY key: Elem.T; READONLY a: ARRAY OF Elem.T; cmp := Elem.Compare): INTEGER;

 

along with:

 

PROCEDURE LowerBound(READONLY key: Elem.T; READONLY a: ARRAY OF Elem.T; cmp := Elem.Compare): INTEGER;

PROCEDURE UpperBound(READONLY key: Elem.T; READONLY a: ARRAY OF Elem.T; cmp := Elem.Compare): INTEGER;

PROCEDURE EqualRange(READONLY key: Elem.T; READONLY a: ARRAY OF Elem.T; VAR lower, upper: INTEGER; cmp := Elem.Compare);

 

using -1 for not found?

 

LowerBound, UpperBound, EqualRange are closely related to BinarySearch.

When the array contains adjacent equal/equivalent elements, they let you find the first, last or first and last, whereas "regular" BinarySearch finds an arbitrary one.

See the C++ STL.

 

 

 - Jay


 


From: jay.krell at cornell.edu
To: hosking at cs.purdue.edu
Date: Wed, 31 Mar 2010 03:19:57 +0000
CC: m3devel at elegosoft.com
Subject: Re: [M3devel] m3core/src/types/Unicode.m3 var to const



"I think I can".
 Just use arrays and indices more and pointers to elements less/not at all.
 
 
Granted, moving the division is a big speed deoptimization since it is no longer by a constant (unless compiler is quite smart and does "partial inlining", and NT386 compiler is not, very few compilers are smart enough to see this).
 
It might be worth a) restoring that small part b) having two functions, one for 2-tuples, one for 3-tuples, or even c) surely we con't need to handcode binary search here in the first place there is some generic reusable version?
But that is tangential to var vs. const.
 
 
I was also considering adding: Int8, UInt8, Int16, UInt16, UInt32, UInt64.
 
In particular, in m3back, I think I'll be using UInt16 in tables -- CodeView 4.0 format uses UINT16 to represent types (CodeView 5.0 uses UINT32).
 
In reality due to padding/alignment, UINT8/16 probably have no space savings, but they will get range checks..but I'll also have to add a range check when I "allocate" a new type. "That" is "why" I was looking in this directory.
 
 - Jay

 


From: hosking at cs.purdue.edu
Date: Tue, 30 Mar 2010 22:39:25 -0400
To: jay.krell at cornell.edu
CC: m3devel at elegosoft.com
Subject: Re: [M3devel] m3core/src/types/Unicode.m3 var to const

Yes, I think that looks OK. 
The original is very weird M3 code!
Also, can you now make it a safe module instead of UNSAFE?  (No use of ADR anymore).




Antony Hosking | Associate Professor | Computer Science | Purdue University
305 N. University Street | West Lafayette | IN 47907 | USA
Office +1 765 494 6001 | Mobile +1 765 427 5484



On 30 Mar 2010, at 20:53, Jay K wrote:

This is right, right?
 
 - Jay





<1.txt>
 		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20100331/0895f5ed/attachment-0002.html>