sometimes you just gotta role your own, you know? :-)
while i *really* appreciate all the suggestions and brain-wracking,
jeff vance threw down the gaunlet....and i just couldn't ignore the
challenge :-)
anytime a search of data is required, you want to avoid having to do
serial search (unless you just can't help it). (i believe that's what
our c.s. professors spent four(+?) years trying to pound into our
thick little brains :-) so jeff 'decided' a binary search was 'just
the thing' that was needed to help solve my little problem. a quick
internet search on 'binary search' yield plenty of hits. i happened
to pick one that offered the standard binary search algorithm in c++.
i swear it didn't take more than a couple of minutes to 'convert'
(this) c++ into a mpe script (mostly removing semi-colons and general
beautifying)!
so what i'm including is three scripts.
1) 'search' is bascially a wrapper for....
2) 'mkarray' -- to 'array-ify' a data file
3) 'binsrch' -- does the binary search on said array
there's some hardcoded stuff in 'search' -- like it explicitly call
mkarray and binsrch. so if you choose to change the names...well, at
least you know what to look for :-) 'search' is also assuming that
mkarray and binsrch are somewhere in your search path (hppath). also,
i deliberately left mkarray and binsrch as separate scripts because (i
think) they're useful general purpose 'thing-lets'. so..... -
d
========================
'search'
parm infile='', key_value='', return_var=''
setvar _s_infile "!infile"
setvar _s_key_value "!key_value"
setvar _s_return_var "!return_var"
if _s_infile = "" or _s_infile = "?" or dwns(_s_infile)="help"
echo
echo ![basename('!HPFILE')] [data file],[key value],[var. name]
echo req. req. req.
echo ![basename('!HPFILE')] is designed to search the given
echo data file for the specified key value. If a match is
echo found, the entire record is returned in the provided CI
echo variable.
echo
echo [data file] := The name of the data file to be search. This
echo file must be a plain text file that resides in MPE namespace.
echo It must be sorted into key order prior to submission since
echo this script utilizes a binary search algorithm.
echo
echo [key value] := The value to be searched for in the data file.
echo The key must be presented in ASCII (human-readable) format.
echo
echo [var. name] := The name of the CI variable that the matching
echo data record will be placed in, if a match is made. If no
echo match is found, this variable will be set to null.
echo
echo Required CI variables:
echo KEY_BEGIN := The beginning position of the key in the data
echo file (1-relative).
echo KEY_LENGTH := The length of the key, in bytes.
echo
echo Other CI variables:
echo BIN_RETURN := If a match is found, this variable will contain
echo the record of the found data. If no match is made, this
echo will be set to -1.
echo
echo Limitations: Because this script uses a binary search
algorithm,
echo there is a practical limit to how much data should be in the
echo file. However, MPE only supports 8-9000 CI variables for any
echo one session. Given that, this script will not process data
echo files larger than 4000 records because two variables are
echo generated for every record in the file. Additionally, in
echo your enviroment, this 4000-record limit may be too high be-
echo cause of the number of CI variables already defined. So
ymmv!!
echo
return
endif
if not finfo(_s_infile,'exists')
echo
echo ERROR: The data file (!_s_infile) could not be found
deletevar _s_@
return
endif
if finfo(_s_infile,'eof') > 4000
echo
echo ERROR: The data file (!_s_infile) has more than 4000 records
deletevar _s_@
return
endif
if _s_key_value = ''
echo
echo ERROR: No key value was provided
deletevar _s_@
return
endif
if not bound (key_begin)
echo
echo ERROR: The CI variable KEY_BEGIN is not defined
deletevar _s_@
return
endif
if not bound (key_length)
echo
echo ERROR: The CI variable KEY_LENGTH is not defined
deletevar _s_@
return
endif
setvar !_s_return_var ''
MKARRAY < !_s_infile
if bound(_ma_i)
if _ma_i = finfo(_s_infile,'eof')
BINSRCH _ma_key,!_ma_i,!_s_key_value
if bin_return <> -1
setvar !_s_return_var "![_ma_rec!bin_return]"
else
echo No match was found
endif
else
echo
echo ERROR: MKARRAY failed to convert the data file into an array
endif
else
echo
echo ERROR: MKARRAY experienced an unknown failure
endif
deletevar _s_@
deletevar _ma_@
deletevar _bin_@
=========================
'mkarray'
setvar _ma_eof finfo(HPSTDIN,"eof")
setvar _ma_i 0
while setvar(_ma_eof,_ma_eof-1) >= 0
input _ma_rec
setvar _ma_i _ma_i + 1
setvar _ma_rec!_ma_i rtrim(_ma_rec)
setvar _ma_key!_ma_i str(_ma_rec,key_begin,key_length)
endwhile
======================
'binsrch'
parm array_name array_size search_value
setvar _bin_array "!array_name"
setvar _bin_array_size "!array_size"
setvar _bin_array_size !_bin_array_size
setvar _bin_value "!search_value"
setvar _bin_found false
setvar _bin_left 0
setvar _bin_right (_bin_array_size - 1)
setvar _bin_middle 0
#-- Search until value is found or there is nowhere else to look
while (_bin_left <= _bin_right)
setvar _bin_middle (!_bin_left + !_bin_right)/2
if (_bin_value < "![!_bin_array!_bin_middle]")
setvar _bin_right (!_bin_middle - 1)
elseif (_bin_value > "![!_bin_array!_bin_middle]")
setvar _bin_left (!_bin_middle + 1)
else
setvar _bin_found true
setvar _bin_left (_bin_right+1)
endif
endwhile
#-- Determine why loop terminated and return appropriate value
if _bin_found
setvar bin_return _bin_middle
else
setvar bin_return -1
endif
============================
--
Donna Garverick Sr. System Programmer
925-210-6631 [log in to unmask]
>>>MY opinions, not Longs Drug Stores'<<<
* To join/leave the list, search archives, change list settings, *
* etc., please visit http://raven.utc.edu/archives/hp3000-l.html *
|