Jump to content
HHS

ARRAY.AU3 / _ArrayBinarySearch() / Bugfix

Recommended Posts

Hello,

I have found a "bug" in array.au3 in the function _ArrayBinarySearch().

Summary:

Not possible to get the correct index of an element when use "ß", they found always "ss".

 

Here a little Test-Script:

#include <Array.au3>

Local $Array[6] = ["a_ausser", "a_außer", "b_ausser", "b_außer", "c_ausser", "c_außer"]
_ArraySort($Array, 0, 0)
For $i=0 to UBound($Array)-1
    ConsoleWrite("Index " & $i & ": " & $Array[$i] & @CRLF)
Next

;BinarySearch
ConsoleWrite("BinarySearchIndex: " & _ArrayBinarySearch($Array, "b_außer", 0) & " <-- must be Index 3 - b_außer" & @CRLF)
ConsoleWrite("BinarySearchIndex: " & _ArrayBinarySearch($Array, "b_ausser", 0) & " <-- must be Index 2 - b_ausser" & @CRLF)

Output:

--> Press Ctrl+Alt+Break to Restart or Ctrl+Break to Stop
Index 0: a_ausser
Index 1: a_außer
Index 2: b_ausser
Index 3: b_außer
Index 4: c_ausser
Index 5: c_außer
BinarySearchIndex: 2 <-- must be Index 3 - b_außer
BinarySearchIndex: 2 <-- must be Index 2 - b_ausser
+>09:35:08 AutoIt3.exe ended.rc:0

Here is the wrong item with Index 2 found, but I search for item 3

 

now HERE my little bugfix in __ArrayBinarySearch():

#include <Array.au3>

Local $Array[6] = ["a_ausser", "a_außer", "b_ausser", "b_außer", "c_ausser", "c_außer"]
_ArraySort($Array, 0, 0)
For $i=0 to UBound($Array)-1
    ConsoleWrite("Index " & $i & ": " & $Array[$i] & @CRLF)
Next

;BinarySearch
ConsoleWrite("BinarySearchIndex: " & __ArrayBinarySearch($Array, "b_außer", 0) & " <-- must be Index 3 - b_außer" & @CRLF)
ConsoleWrite("BinarySearchIndex: " & __ArrayBinarySearch($Array, "b_ausser", 0) & " <-- must be Index 2 - b_ausser" & @CRLF)


; #FUNCTION# ====================================================================================================================
; Author ........: Jos
; Modified.......: Ultima - added $iEnd as parameter, code cleanup; Melba23 - added support for empty & 2D arrays
; ===============================================================================================================================
Func __ArrayBinarySearch(Const ByRef $aArray, $vValue, $iStart = 0, $iEnd = 0, $iColumn = 0)
    If $iStart = Default Then $iStart = 0
    If $iEnd = Default Then $iEnd = 0
    If $iColumn = Default Then $iColumn = 0
    If Not IsArray($aArray) Then Return SetError(1, 0, -1)
    ; Bounds checking
    Local $iDim_1 = UBound($aArray, $UBOUND_ROWS)
    If $iDim_1 = 0 Then Return SetError(6, 0, -1)
    If $iEnd < 1 Or $iEnd > $iDim_1 - 1 Then $iEnd = $iDim_1 - 1
    If $iStart < 0 Then $iStart = 0
    If $iStart > $iEnd Then Return SetError(4, 0, -1)
    Local $iMid = Int(($iEnd + $iStart) / 2)
    Switch UBound($aArray, $UBOUND_DIMENSIONS)
        Case 1
            If $aArray[$iStart] > $vValue Or $aArray[$iEnd] < $vValue Then Return SetError(2, 0, -1)
            ; Search
            While $iStart <= $iMid And Not ($vValue == $Array[$iMid])
                If $vValue < $aArray[$iMid] Then
                    $iEnd = $iMid - 1
                Else
                    $iStart = $iMid + 1
                EndIf
                $iMid = Int(($iEnd + $iStart) / 2)
            WEnd
            If $iStart > $iEnd Then Return SetError(3, 0, -1) ; Entry not found
        Case 2
            Local $iDim_2 = UBound($aArray, $UBOUND_COLUMNS) - 1
            If $iColumn < 0 Or $iColumn > $iDim_2 Then Return SetError(7, 0, -1)
            If $aArray[$iStart][$iColumn] > $vValue Or $aArray[$iEnd][$iColumn] < $vValue Then Return SetError(2, 0, -1)
            ; Search
            While $iStart <= $iMid And Not ($vValue == $aArray[$iMid][$iColumn])
                If $vValue < $aArray[$iMid][$iColumn] Then
                    $iEnd = $iMid - 1
                Else
                    $iStart = $iMid + 1
                EndIf
                $iMid = Int(($iEnd + $iStart) / 2)
            WEnd
            If $iStart > $iEnd Then Return SetError(3, 0, -1) ; Entry not found
        Case Else
            Return SetError(5, 0, -1)
    EndSwitch
    Return $iMid
EndFunc   ;==>_ArrayBinarySearch

Output:

--> Press Ctrl+Alt+Break to Restart or Ctrl+Break to Stop
Index 0: a_ausser
Index 1: a_außer
Index 2: b_ausser
Index 3: b_außer
Index 4: c_ausser
Index 5: c_außer
BinarySearchIndex: 3 <-- must be Index 3 - b_außer
BinarySearchIndex: 2 <-- must be Index 2 - b_ausser
+>09:37:17 AutoIt3.exe ended.rc:0

Here is the correct item with Index 3 found.

 

Only two lines have little changes:

line 25 in function:
Original: While $iStart <= $iMid And  $vValue <> $Array[$iMid]
FIX: While $iStart <= $iMid And Not ($vValue == $Array[$iMid])
line 39 in function:
Original: While $iStart <= $iMid And $vValue <> $aArray[$iMid][$iColumn])
FIX: While $iStart <= $iMid And Not ($vValue == $aArray[$iMid][$iColumn])

 

Please check my little bugfix and check in in the repository for the next release.

Edited by HHS

Share this post


Link to post
Share on other sites

Thanks for reporting the bug. Unfortunately your fix has an issue: this function is currently not case sensitive and therefore the change would be script breaking. Your suggestion would work with the addition of an extra case sensitivity parameter. There are probably other alternatives, but this seems to be the easiest solution to this problem. It's still not perfect.

Edited by czardas

Share this post


Link to post
Share on other sites

I believe it all depends on which options are used by the internal call to StringCompareW. Unicode can be misleading, but German usually consider ß to be equivalent to ss.


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Similar Content

    • By topgundcp
      Hi, 
      This is my very first post in this forum and am also new with Autoit programming so be easy on me.
      Below is the code that I am trying to get the index of the item selected. No problem getting the text.
      Case $listEdition   ; handle of the list             local $index=0             $item=GUICTRLRead($listEdition)    ; This will return the text in the list             ; ==============   The loop below always fails  ==================             ; Meaning _GUICtrlListView_GetItemSelected($listEdition, $i) always return FALSE. WHY ???????              For $i = 0 To $editionArray[0] - 1   ; The content of the list in an array where editionArray[0] contains total count of items                 If _GUICtrlListView_GetItemSelected($listEdition, $i) Then                     $index = $i                     exitloop                 EndIf              Next              ;===================================================             ConsoleWrite( "Select Edition:     " & $item & "  index: " & $index & @CR) ....... Please look at the comments in the code & the pix attached.
      _GUICtrlListView_GetItemSelected($listEdition, $i) always returns FALSE.
      Another problem is on the list. It also populate  the total count of items from the Array. How can I skip this item from populating to the list ?.
      Please advise and thanks

    • By n0ktar
      is it possible to make a wall chams in rainbow six siege using autoit scripts? tell me please and how . 
    • By Rskm
      Hi, I am using excel as input media for my program. The excel file (i tried with .xls, .xlsx and .xlsm format) has inputs which the autoit script reads during the run and performs few calculations. Some times (not always), after the run, when i try to open the excel file manually, the file doesnt open at all in excel. see the screenshot attached. However, if the execute the autoit script, the scripts still reads the existing data from that excel and performs the calcs. I copied the excel file to another computer and there too, it doesnt open.  So, after this, i cannot edit the excel forever (if i need to change any inputs). It is only this particular file that got affected. other excel files works normal.  What could be the problem here.  please help as this is a new challenge for me during my program development. 

    • By TheAutomator
      Hi everyone!

      I'm using AutoIt for several years now and I really get the hang of it!
      I'm quite the curious OCD perfectionist kind of guy, so I can't help wondering..
      what would be the best way to program stuff for the compiler / interpreter / scripting engine?
      We're talking about the inner workings of the AutoIt's core here, and how to give it as less friction as possible but also take care of the machine running the script.
      For example,
      Imagine a script where we would constantly have to assign a Boolean value to a variable:
      ; A: local $bool = false $bool = true $bool = true $bool = false ; B: local $bool = false check(true) check(true) check(false) func check($b) if $bool = $b then return $bool = $b endfunc In this case, would it be better to just overwrite (A) the variable or first check if we really need to (B)?
      What would be best for the computers memory if it had to do this for a year non stop?
      Another example, imagine you're writing a function with an if statement.
      If you would look under the hood of AutoIt, what would be the best way to give your computer as less work / code nesting stack filling as possible:
      ; A: func decide($b_Input) if $b_Input then ;do something else ;do something else endif endfunc ; B: func decide($b_Input) if $b_Input then ;do something return endif ;do something else endfunc Last one for now:
      ; A: while 1 ; do stuff wend ; B: while true ; do stuff wend Isn't AutoIt taking an extra step in converting 1 to a Boolean in example (A)?
      Or is it the other way around and does the (B) way make AutoIt first convert a keyword (true or false) to a numerical value (0 or 1).
      I think this kinda detail stuff is quite interesting, makes me wonder how AutoIt converts and runs our code.
      What are your opinions on this topic?
      Any coders who know more about the inner workings of AutoIt?
      Any people like me who ask themselves similar questions (with examples)?

      Let me know! 😉
    • By v120
      Rapid Fire Mouse Hack Script
      *snip*
       
×
×
  • Create New...