[REBOL] Re: Algorithm challenge: selecting a range from multiple blocks
From: Tom::Conlin::gmail::com at: 22-Sep-2007 16:54
is it ok for the results to have a mix of new and existing objects
is 'data only appended to
can 'data objects with empty items: [] be safely deleted from 'data?
what is the ratio between updating and querying 'data
what are typical ranges?
how often do ranges fall within one items block?
how big is length? data
...
get-subset: func [ data[block!] range[block!]
/local result here there hi lo hi-tally lo-tally
lo-len hi-len these-items
][
these-items: func[ser][get in first ser 'items]
lo-len: lo-tally: 0
lo: first range hi: second range
here: data
;;; linear scan of 'data for items block containing beginning range
while[lo > lo-tally: lo-tally + lo-len: length? these-items here][
here: next here
]
there: here hi-tally: lo-tally hi-len: lo-len
;;; scan for items block containing end range
while[hi > hi-tally][
there: next there
hi-tally: hi-tally + hi-len: length? these-items there
]
;;; isolate the blocks of interest
result: copy/part here next there
;;; trim trailing items (new object)
result: back tail result
if 0 < (hi-len -(hi-tally - hi))[
change result make first result [
items: copy/part these-items result hi-len -(hi-tally - hi)
]
]
;;; trim leading items (new object)
result: head result
if 0 < (-1 + lo-len -(lo-tally - lo))[
change result make first result [
items: copy skip these-items result -1 + lo-len -(lo-tally - lo)
]
]
;;; could be worked in with the second loop
;;; if cleaning 'data is allowed
remove-each obj result [empty? get in obj 'items]
result
]
Sunanda wrote:
