Inserting Item into a Sorted ListView

[Beege]

What I am trying to do is make a function that will got through my sorted ListView and find the correct index to insert my next item. Since the Listview is always going to be sorted, I should be able to make something similar to how _ArrayBinarySearch() works, but am running into problems getting it to work. Any help is greatly appreciated.

Here is the example I set up to work with.

expandcollapse popup

include <array.au3>
#include <GuiListView.au3>
#include <GUIConstantsEx.au3>
#include <WindowsConstants.au3>

$Form1 = GUICreate("Form1", 620, 432, 268, 160)
$hListView = GUICtrlCreateListView("col   ", 24, 24, 559, 357)
GUISetState(@SW_SHOW)

Global $randoms = _Generate_Random_Array(), $index

For $i = 1 To $randoms[0]
    $index = _GCLV_GetSortedIndex2($hListView, $randoms[$i])
;~  $index = _GCLV_GetSortedIndex_old($hListView, $randoms[$i])
    _GUICtrlListView_InsertItem($hListView, $randoms[$i], $index)
    ConsoleWrite('Index = ' & $index & @CRLF)
Next
ConsoleWrite('Count = ' & _GUICtrlListView_GetItemCount($hListView) & @CRLF)

;I have this here to see what the list should look like when correctly sorted.
$sorted = $randoms
_ArraySort($sorted)
_ArrayDisplay($sorted, 'True Sorted')


Func _GCLV_GetSortedIndex2($hListView, $item)

    Local $iCount = _GUICtrlListView_GetItemCount($hListView)
    Local $iStart = 0, $iEnd = ($iCount - 1)

    If $iCount = 0 Then Return 0; List is empty

    Local $iMid = Int(($iEnd + $iStart) / 2)

    Do
        If StringCompare($item, _GUICtrlListView_GetItemText($hListView, $iMid)) < 0 Then; item is less than text
            $iEnd = $iMid - 1
        Else; item is greater than text
            $iStart = $iMid + 1
        EndIf
        $iMid = Int(($iEnd + $iStart) / 2)

    Until Abs($iStart - $iEnd) < 10; Here the distance is less then ten items to check. a better way??

    ConsoleWrite(StringFormat('iStart = %d, iEnd = %d', $iStart, $iEnd) & @CRLF)

;    For $i = $iStart-1 To $iEnd+1
;       If StringCompare($item, _GUICtrlListView_GetItemText($hListView, $iMid)) < 0 Then Return $i
;    Next
    For $i = $iStart To $iEnd
        If StringCompare($item, _GUICtrlListView_GetItemText($hListView, $i)) < 0 Then Return $i
    Next
    
;If I got this far then the item must be the largest value in the list..

    Return ($iCount + 1)

EndFunc   ;==>_GCLV_InsertAphabatized2

;xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
;~ Function Works but is very slow
;xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Func _GCLV_GetSortedIndex_old($hListView, $item)

    Local $iCount = _GUICtrlListView_GetItemCount($hListView)

    If $iCount = 0 Then Return 0

    For $i = 0 To ($iCount - 1)
        If StringCompare($item, _GUICtrlListView_GetItemText($hListView, $i)) < 0 Then Return $i
    Next
    
    Return ($iCount + 1)

EndFunc   ;==>_GCLV_InsertAphabatized3


Func _Generate_Random_Array()
    Local $arr[4] = ['a', 'b', 'c', 'd'], $array[201] = [200], $string = ''
    For $i = 1 To 200
        $string = ''
        For $j = 0 To 3
            $string &= $arr[Random(0, 3)]
        Next
        $array[$i] = $string
    Next
    Return $arrayEndFunc   ;==>_Generate_Random_Array

Edit: Changed For Statement

Edited June 26, 2010 by Beege

[Beege]

Ok I made some changes to the main function and now it gets close but still screws up somewhere.

expandcollapse popup

Func _GCLV_GetSortedIndex2($hListView, $item)

    Local $iCount = _GUICtrlListView_GetItemCount($hListView)
    Local $iStart = 0, $iEnd = ($iCount - 1)

    Switch $iCount
        Case 0 ;List is empty
            Return 0
        Case 1
            If StringCompare($item, _GUICtrlListView_GetItemText($hListView, 0)) < 0 Then
                Return 0
            Else
                Return 1
            EndIf
    EndSwitch

    If $iCount > 5 Then
        Local $iMid = Int(($iEnd + $iStart) / 2)
        Do
            If StringCompare($item, _GUICtrlListView_GetItemText($hListView, $iMid)) < 0 Then; item is less than text
                $iEnd = $iMid - 1
            Else; item is greater than text
                $iStart = $iMid + 1
            EndIf
            $iMid = Int(($iEnd + $iStart) / 2)
;~      ConsoleWrite(StringFormat('$iStart = %d, iMid = %d, $iEnd = %d', $iStart, $iMid, $iEnd) & @CRLF)
        Until Abs($iStart - $iEnd) < 10; Here the distance is less then ten items to check. a better way??
    EndIf

    ConsoleWrite(StringFormat('iStart = %d, iEnd = %d', $iStart, $iEnd) & @CRLF)

    For $i = $iStart To $iEnd
        If StringCompare($item, _GUICtrlListView_GetItemText($hListView, $i)) < 0 Then Return $i
    Next

    Return ($iCount + 1)

EndFunc   ;==>_GCLV_GetSortedIndex2

[Authenticity]

Why don't you use $LVS_SORTASCENDING style?

[Beege]

Why don't you use $LVS_SORTASCENDING style?

Thanks for the reply. For what Im trying to do that wouldn't quite work. I also plan on making the function have other options. Cant happen until I get the heart of it working.

[Authenticity]

expandcollapse popup

#include <array.au3>
#include <GuiListView.au3>
#include <GUIConstantsEx.au3>
#include <WindowsConstants.au3>

$Form1 = GUICreate("Form1", 620, 432, 268, 160)
$hListView = GUICtrlCreateListView("col   ", 24, 24, 559, 357)
GUISetState(@SW_SHOW)

Global $randoms = _Generate_Random_Array(), $index

_GUICtrlListView_BeginUpdate($hListView)
For $i = 1 To $randoms[0]
    $index = _GCLV_GetSortedIndex2($hListView, $randoms[$i])
;~  $index = _GCLV_GetSortedIndex_old($hListView, $randoms[$i])
    _GUICtrlListView_InsertItem($hListView, $randoms[$i], $index)
    ConsoleWrite('Index = ' & $index & @CRLF)
Next
ConsoleWrite('Count = ' & _GUICtrlListView_GetItemCount($hListView) & @CRLF)
_GUICtrlListView_SetColumnWidth($hListView, 0, $LVSCW_AUTOSIZE)
_GUICtrlListView_EndUpdate($hListView)

;I have this here to see what the list should look like when correctly sorted.
$sorted = $randoms
_ArraySort($sorted)
_ArrayDisplay($sorted, 'True Sorted')


Func _GCLV_GetSortedIndex2($hListView, $item)

    Local $iCount = _GUICtrlListView_GetItemCount($hListView)
    If $iCount = 0 Then Return -1

    Local $iStart = 0, $iEnd = $iCount, $iMid = Int($iEnd/2)

    While ($iEnd-$iStart) > 10
        If StringCompare($item, _GUICtrlListView_GetItemText($hListView, $iMid)) <= 0 Then
            $iEnd = $iMid
            $iMid -= Int(($iEnd-$iStart)/2)
        Else
            $iStart = $iMid
            $iMid += Int(($iEnd-$iStart)/2)
        EndIf
    WEnd

    For $i = $iStart To $iEnd
        If StringCompare($item, _GUICtrlListView_GetItemText($hListView, $i)) <= 0 Then Return $i
    Next

    Return -1
EndFunc   ;==>_GCLV_InsertAphabatized2

Func _Generate_Random_Array()
    Local $arr[5] = ['a', 'b', 'c', 'd', 'e'], $array[201] = [200], $string = ''
    For $i = 1 To 200
        $string = ''
        For $j = 0 To 4
            $string &= $arr[Random(0, 4)]
        Next
        $array[$i] = $string
    Next
    Return $array
EndFunc   ;==>_Generate_Random_Array

[Beege]

Aggg! Just as I get it you come up something better!

Yours is quicker. Going to go with your style. Thank you very much for all the help. I really appreciated it.

expandcollapse popup

#include <array.au3>
#include <GuiListView.au3>
#include <GUIConstantsEx.au3>
#include <WindowsConstants.au3>

$Form1 = GUICreate("Form1", 620, 432, 268, 160)
$hListView = GUICtrlCreateListView("col   ", 24, 24, 559, 357)
GUISetState(@SW_SHOW)

Global $randoms = _Generate_Random_Array(), $index

For $i = 1 To $randoms[0]
    $index = _GCLV_GetSortedIndex($hListView, $randoms[$i])
;~  $index = _GCLV_GetSortedIndex_old($hListView, $randoms[$i])
    _GUICtrlListView_InsertItem($hListView, $randoms[$i], $index)
    ConsoleWrite('Index = ' & $index & @CRLF)
Next
ConsoleWrite('Count = ' & _GUICtrlListView_GetItemCount($hListView) & @CRLF)

;I have this here to see what the list should look like when correctly sorted.
$sorted = $randoms
_ArraySort($sorted)
_ArrayDisplay($sorted, 'True Sorted')

Func _GCLV_GetSortedIndex($hListView, $item)

    Local $iCount = _GUICtrlListView_GetItemCount($hListView)
    Local $iStart = 0, $iEnd = ($iCount - 1)

    Switch $iCount
        Case 0 ;List is empty
            Return 0
        Case 1
            If StringCompare($item, _GUICtrlListView_GetItemText($hListView, 0)) < 0 Then Return 0
            Return 1
    EndSwitch

    If $iCount < 5 Then ;Return _GCLV_GetSortedIndex_old($hListView, $item)
        Local $iMid = Int(($iEnd + $iStart) / 2)
        Local $sMid = _GUICtrlListView_GetItemText($hListView, $iMid)
        Do
            $iCompare = StringCompare($item, _GUICtrlListView_GetItemText($hListView, $iMid))
            Switch $iCompare
                Case -1; item is less than text
                    If StringCompare($item, _GUICtrlListView_GetItemText($hListView, $iMid - 1)) > 0 Then Return $iMid
                    $iEnd = $iMid
                Case 1;item is greater than text
                    If StringCompare($item, _GUICtrlListView_GetItemText($hListView, $iMid + 1)) < 0 Then Return $iMid + 1
                    $iStart = $iMid
                Case 0; strings are equal
                    Return $iMid
            EndSwitch
            $iMid = Int(($iEnd + $iStart) / 2)
        Until Abs($iStart - $iEnd) < 5;
    EndIf

    For $i = $iStart To $iEnd
        If StringCompare($item, _GUICtrlListView_GetItemText($hListView, $i)) < 0 Then Return $i
    Next

    Return $iCount + 1

EndFunc   ;==>_GCLV_GetSortedIndex

Func _Generate_Random_Array()
    Local $arr[4] = ['a', 'b', 'c', 'd'], $array[201] = [200], $string = ''
    For $i = 1 To 200
        $string = ''
        For $j = 0 To 3
            $string &= $arr[Random(0, 3)]
        Next
        $array[$i] = $string
    Next
    Return $array
EndFunc   ;==>_Generate_Random_Array

Edited June 27, 2010 by Beege