binary search

 

Compatibilities:

This item has not yet been rated

-- modified version of Calu's binary search to work with porp lists too, and a bugfix -- http://xtras.calu.us/articles2.php -- binary search with sorted list -- if 'charstart' is set, then it will look for the match of the first character -- put searchBinary (["1":[1,1],"2":[2,2],"3":[3,3],"4":[4,4],"5":[5,5],"6":[6,6],"ga":["ga","ga1"],"gu":["gu":"gu1"]], "g",1) -- [7, 8]

--------------------------------------------------------------- -- modified version of  Calu's binary search to work with porp lists too, and a bugfix -- http://xtras.calu.us/articles2.php -- binary search with sorted list (property lists, with accent marked chars too) -- if 'charstart' is set, then it will look for the match of the  first character -- put searchBinary (["1":[1,1],"2":[2,2],"3":[3,3],"4":[4,4],"5":[5,5],"6":[6,6],"ga":["ga","ga1"],"gu":["gu":"gu1"]], "g",1) -- [7, 8] on searchBinary ptr_list, value_toMatch,charstart -- create a matching return list _intList_matchedPos = [] -- setup _int_listCount = ptr_list.count _int_startLine = 1 _int_endLine = _int_listCount _int_currentLine = (_int_startLine+_int_endLine)/2 repeat while TRUE      if ptr_list.ilk=#proplist then      _value_current = ptr_list.getpropat(_int_currentLine)    else      _value_current = ptr_list[_int_currentLine] -- [_int_startLine] -- bug    end if      if charstart<>Void then      if stringp(_value_current)=true and stringp(value_toMatch)=true then        if _value_current.char[1]=value_toMatch.char[1] then          exit repeat        end if      else        charstart=Void      end if    end if      if ( _value_current = value_toMatch ) then      -- found a match... don't need to continue binary search      exit repeat    else      if  my_str1grstr2 (value_toMatch,_value_current) then        -- if  value_toMatch>_value_current then --        -- current value is too small, go the right more        _int_startLine = _int_currentLine + 1        _int_currentLine = ( _int_currentLine + 1 + _int_endLine ) / 2        -- ptr_list=searchBinary (ptr_list, value_toMatch)      else        -- found ID is too big, go to the left more        _int_endLine = _int_currentLine - 1        _int_currentLine_old=_int_currentLine        _int_currentLine = ( _int_startLine - 1 + _int_currentLine ) / 2      end if    end if end repeat -- allowed duplicate value so need to search the starting and ending line for the value_match if charstart=Void then    -- search starting line    _int_startLine = _int_currentLine    if ptr_list.ilk=#proplist then      value2=ptr_list.getpropat(_int_startLine)    else      value2=ptr_list[_int_startLine]    end if      repeat while ( value_toMatch = value2 )          _int_startLine = _int_startLine - 1          -- exit if we're already at the beginning      if _int_startLine = 0 then exit repeat          if ptr_list.ilk=#proplist then        value2=ptr_list.getpropat(_int_startLine)      else        value2=ptr_list[_int_startLine]      end if        end repeat    _int_startLine = _int_startLine + 1      -- search ending line    _int_endLine = _int_currentLine    if ptr_list.ilk=#proplist then      value2=ptr_list.getpropat(_int_endLine)    else      value2=ptr_list[_int_endLine]    end if      repeat while ( value_toMatch = value2 )          _int_endLine = _int_endLine + 1          -- exit if we're at the end      if ( _int_endLine > _int_listCount ) then exit repeat          if ptr_list.ilk=#proplist then        value2=ptr_list.getpropat(_int_endLine)      else        value2=ptr_list[_int_endLine]      end if        end repeat    _int_endLine = _int_endLine - 1      -- generate return list for this range    repeat with i = _int_startLine to _int_endLine      _intList_matchedPos.addAt(i)    end repeat else    -- _intList_matchedPos.add(_int_currentLine)      -- search starting line    _int_startLine = _int_currentLine      if ptr_list.ilk=#proplist then      value2=ptr_list.getpropat(_int_startLine)    else      value2=ptr_list[_int_startLine]    end if      repeat while ( value_toMatch.char[1] = value2.char[1] )      _int_startLine = _int_startLine - 1      -- exit if we're already at the beginning      if _int_startLine = 0 then exit repeat          if ptr_list.ilk=#proplist then        value2=ptr_list.getpropat(_int_startLine)      else        value2=ptr_list[_int_startLine]      end if        end repeat    _int_startLine = _int_startLine + 1      -- search ending line    _int_endLine = _int_currentLine      if ptr_list.ilk=#proplist then      value2=ptr_list.getpropat(_int_endLine)    else      value2=ptr_list[_int_endLine]    end if      repeat while ( value_toMatch.char[1] = value2.char[1] )      _int_endLine = _int_endLine + 1      -- exit if we're at the end      if ( _int_endLine > _int_listCount ) then exit repeat          if ptr_list.ilk=#proplist then        value2=ptr_list.getpropat(_int_endLine)      else        value2=ptr_list[_int_endLine]      end if        end repeat    _int_endLine = _int_endLine - 1      -- generate return list for this range    repeat with i = _int_startLine to _int_endLine      _intList_matchedPos.addAt(i)    end repeat    end if return _intList_matchedPos end ----------------------------------- -- custom string comparing on my_str1grstr2 str1,str2 if str1=Void or str2=Void then    return false end if -- threat integers if str1.ilk=#integer and str2.ilk=#integer then    if str1>str2 then      return true    else      return false    end if else    end if -- go to the shorter length h=[] h.add(str1.length) h.add(str2.length) h=min(h) -- delete the same characters repeat while str1.char[1]=str2.char[1] and str1.char[1]<>"" and str2.char[1]<>""    delete char 1 of str1    delete char 1 of str2 end repeat if str1="" and str2<>"" then    return false end if if str1<>"" and str2="" then    return true end if -- equal strings if str1="" and str2="" then    return false end if -- the first character makes sense if str1.char[1]   return false end if return true end