Jump to content
HHS

ARRAY.AU3 / _ArrayBinarySearch() / Bugfix

Recommended Posts

HHS

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
  • Like 1

Share this post


Link to post
Share on other sites
czardas

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
jchd

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

    • gahhon
      By gahhon
      So I had compiled my AutoIT script into executable file, I think like few weeks ago.
      But once after I compiled the script to executable file, I tested it and it work as expected.
      Somehow, I just now wanna try to execute it but failed

      Any idea what's is going on? Do I need to recompile the script again? @@
    • gahhon
      By gahhon
      I have a python script automate.py and I wanna run it via CMD.
      As I know to execute python via CMD is something like this
      $CMD = "Something python here" Run(@ComSpec & " /c " & $CMD) But how can I just open the 1 CMD and send multiple commands to the CMD based on the function called?
      For instance like:

      Launch CMD and send python then send import automate If google() function is called - send automate.google() to the CMD If yahoo() function is called - send automate.yahoo() to the CMD  I don't want to execute multiple CMD to call the automate functions. This is due to inside the python script have global variable to handle duplicate flag.
      So if I execute multiple CMD to call the functions, the global variable will be keep new as NULL. Which is not my expectation.
       
      Thanks
    • gahhon
      By gahhon
      I only found that AutoIt can actually execute the entire python script or execute the .exe (converted to .exe from .py)
      But what if I just want call the particular function? If that possible to do so?
      This is because python can't create fancy GUI like AutoIT does. So my plan is use AutoIT to have fancy GUI.
      Then each buttons will trigger specific function in the python script or .exe file.
      For instances:
      btnSum - trigger function in python script or .exe file (funcSum)
      btnMinus - trigger function in python script or .exe file (funcMinus)
       
      Thanks for advance information.
    • nacerbaaziz
      By nacerbaaziz
      Hello my friends
      Can we create a single context menu on more than one item?
      For example, a context menu includes standardized options on more than one control, such as buttons or check boxes
      to Create a context menu on one item am using this function
      GUICtrlCreateContextMenu ($ HWND)
      How to link it with more than one element please?
      or if we can't do that, please give me a solution
      so i tried to add an context menus to all the controls but the script will be long, for that if their are any solutions i hope to give it to me
      thanks in advanced
    • gahhon
      By gahhon
      _Metro_SplashTextScreen(1, "", $iMsg) AdlibRegister("_Metro_LoopInProgress") DirRemove($DIR_WA_FOLDER, 1) Local $iCopy = _WinAPI_ShellFileOperation($CUR_WA_FOLDER, $DIR_WA_FOLDER, $FO_COPY, BitOr($FOF_SIMPLEPROGRESS, $FOF_NOCONFIRMMKDIR)) AdlibUnRegister("_Metro_LoopInProgress") _Metro_SplashTextScree If @error Then _Metro_MsgBox(0, "", $iCopy) _FileWriteLog($LOG_INSTALLATION, "Error: " & $iCopy) Else _Metro_MsgBox(0, "", "Application is up to date!") _FileWriteLog($LOG_INSTALLATION, "Debug: Application is up to date.") EndIf According to the help file of _WinAPI_ShellFileOperation there are a lot of failure and error code. But how can I handle all of them and display corresponding error message based on the help file?
      The incident is like this:
      I'll lock the folder with permission, so when I execute the _WinAPI_ShellFileOperation to copy and overwrite the folder contents, it popped me an error message saying that permission issue to caused I can't access the folder and overwrite the contents.

      Then I clicked Cancel button, and my AutoIT application exit immediately and it's not execute the function _Metro_MsgBox(0, "", $iCopy) to display the message.
       
      Anyway, I did also tried the code below, the it still display "Application is up to date!"
      According to the help file, 120 - Security settings denied access to the source.
      If @error = 120 Then _Metro_MsgBox(0, "", $iCopy) _FileWriteLog($LOG_INSTALLATION, "Error: " & $iCopy) Else _Metro_MsgBox(0, "", "Application is up to date!") _FileWriteLog($LOG_INSTALLATION, "Debug: Application is up to date.") EndIf  
×