<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
--></style>
</head>
<body class='hmmessage'>
> c) surely we con't need to handcode binary search here in the first place there is some generic reusable version?<BR><BR>
The closest precedent I can find is:<BR><BR><A href="http://modula3.elegosoft.com/cm3/doc/help/gen_html/libm3/src/sort/ArraySort.ig.html">http://modula3.elegosoft.com/cm3/doc/help/gen_html/libm3/src/sort/ArraySort.ig.html</A><BR>
<BR>
so I propose *something like*:<BR>
<BR>
m3core/src/binarysearch/BinarySearch.ig.<BR>PROCEDURE BinarySearch(READONLY key: Elem.T; READONLY a: ARRAY OF Elem.T; cmp := Elem.Compare): INTEGER;<BR>
<BR>
along with:<BR>
<BR>
PROCEDURE LowerBound(READONLY key: Elem.T; READONLY a: ARRAY OF Elem.T; cmp := Elem.Compare): INTEGER;<BR>
PROCEDURE UpperBound(READONLY key: Elem.T; READONLY a: ARRAY OF Elem.T; cmp := Elem.Compare): INTEGER;<BR>
PROCEDURE EqualRange(READONLY key: Elem.T; READONLY a: ARRAY OF Elem.T; VAR lower, upper: INTEGER; cmp := Elem.Compare);<BR>
<BR>
using -1 for not found?<BR>
<BR>
LowerBound, UpperBound, EqualRange are closely related to BinarySearch.<BR>
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.<BR>
See the C++ STL.<BR>
<BR>
<BR>
- Jay<BR>
<BR> <BR>
<HR id=stopSpelling>
From: jay.krell@cornell.edu<BR>To: hosking@cs.purdue.edu<BR>Date: Wed, 31 Mar 2010 03:19:57 +0000<BR>CC: m3devel@elegosoft.com<BR>Subject: Re: [M3devel] m3core/src/types/Unicode.m3 var to const<BR><BR>
<STYLE>
.ExternalClass .ecxhmmessage P
{padding:0px;}
.ExternalClass body.ecxhmmessage
{font-size:10pt;font-family:Verdana;}
</STYLE>
"I think I can".<BR> Just use arrays and indices more and pointers to elements less/not at all.<BR> <BR> <BR>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).<BR> <BR>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?<BR>But that is tangential to var vs. const.<BR> <BR> <BR>I was also considering adding: Int8, UInt8, Int16, UInt16, UInt32, UInt64.<BR> <BR>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).<BR> <BR>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.<BR> <BR> - Jay<BR><BR> <BR>
<HR id=ecxstopSpelling>
From: hosking@cs.purdue.edu<BR>Date: Tue, 30 Mar 2010 22:39:25 -0400<BR>To: jay.krell@cornell.edu<BR>CC: m3devel@elegosoft.com<BR>Subject: Re: [M3devel] m3core/src/types/Unicode.m3 var to const<BR><BR><BASE>Yes, I think that looks OK.
<DIV>The original is very weird M3 code!</DIV>
<DIV>Also, can you now make it a safe module instead of UNSAFE? (No use of ADR anymore).</DIV>
<DIV><BR>
<DIV><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxecxApple-style-span>
<DIV style="WORD-WRAP: break-word"><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxecxApple-style-span>
<DIV><FONT class=ecxecxApple-style-span color=#0000ff><FONT class=ecxecxApple-style-span face="Gill Sans"><SPAN style="FONT-FAMILY: 'Gill Sans'; COLOR: rgb(0,0,255)" class=ecxecxApple-style-span><SPAN style="FONT-FAMILY: 'Gill Sans'; COLOR: rgb(0,0,255)" class=ecxecxApple-style-span>Antony Hosking</SPAN></SPAN></FONT></FONT><FONT class=ecxecxApple-style-span face="Gill Sans"><SPAN style="FONT-FAMILY: 'Gill Sans'" class=ecxecxApple-style-span><SPAN style="FONT-FAMILY: 'Gill Sans'" class=ecxecxApple-style-span><SPAN class=ecxecxApple-converted-space> </SPAN>|<SPAN class=ecxecxApple-converted-space> </SPAN></SPAN></SPAN><SPAN style="FONT-FAMILY: 'Gill Sans'" class=ecxecxApple-style-span><SPAN style="FONT-FAMILY: 'Gill Sans'" class=ecxecxApple-style-span>Associate Professor</SPAN></SPAN><SPAN style="FONT-FAMILY: 'Gill Sans'" class=ecxecxApple-style-span><SPAN style="FONT-FAMILY: 'Gill Sans'" class=ecxecxApple-style-span> | Computer Science | Purdue University</SPAN></SPAN></FONT></DIV>
<DIV><FONT class=ecxecxApple-style-span face=GillSans-Light><SPAN style="FONT-FAMILY: GillSans-Light" class=ecxecxApple-style-span>305 N. University Street | West Lafayette | IN 47907 | USA</SPAN></FONT></DIV>
<DIV><FONT class=ecxecxApple-style-span color=#0000ff face="Gill Sans"><SPAN style="FONT-FAMILY: 'Gill Sans'; COLOR: rgb(0,0,255)" class=ecxecxApple-style-span><SPAN style="FONT-FAMILY: 'Gill Sans'; COLOR: rgb(0,0,255)" class=ecxecxApple-style-span>Office</SPAN></SPAN></FONT><FONT class=ecxecxApple-style-span face=GillSans-Light><SPAN style="FONT-FAMILY: GillSans-Light" class=ecxecxApple-style-span><SPAN style="FONT-FAMILY: GillSans-Light" class=ecxecxApple-style-span> +1 765 494 6001 |<SPAN class=ecxecxApple-converted-space> </SPAN></SPAN></SPAN></FONT><FONT class=ecxecxApple-style-span color=#0000ff face="Gill Sans"><SPAN style="FONT-FAMILY: 'Gill Sans'; COLOR: rgb(0,0,255)" class=ecxecxApple-style-span><SPAN style="FONT-FAMILY: 'Gill Sans'; COLOR: rgb(0,0,255)" class=ecxecxApple-style-span>Mobile</SPAN></SPAN></FONT><FONT class=ecxecxApple-style-span face=GillSans-Light><SPAN style="FONT-FAMILY: GillSans-Light" class=ecxecxApple-style-span><SPAN style="FONT-FAMILY: GillSans-Light" class=ecxecxApple-style-span><SPAN class=ecxecxApple-converted-space> </SPAN>+1 765 427 5484</SPAN></SPAN></FONT></DIV>
<DIV><FONT class=ecxecxApple-style-span face=GillSans-Light><BR class=ecxecxkhtml-block-placeholder></FONT></DIV></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN><BR class=ecxecxApple-interchange-newline></SPAN></DIV></SPAN></SPAN><BR class=ecxecxApple-interchange-newline></DIV><BR>
<DIV>
<DIV>On 30 Mar 2010, at 20:53, Jay K wrote:</DIV><BR class=ecxecxApple-interchange-newline>
<BLOCKQUOTE><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: medium Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; WORD-SPACING: 0px" class=ecxecxApple-style-span>
<DIV style="FONT-FAMILY: Verdana; FONT-SIZE: 10pt" class=ecxecxhmmessage>This is right, right?<BR> <BR> - Jay<BR><BR><BR><BR><BR><BR><SPAN><1.txt></SPAN></DIV></SPAN></BLOCKQUOTE></DIV><BR></DIV> </body>
</html>