dcsimg
Results 1 to 22 of 22

Thread: Binary Search Troubles

  1. #1

    Thread Starter
    Addicted Member
    Join Date
    Nov 2018
    Posts
    164

    Binary Search Troubles

    Hello,

    I'm using the BinarySearch algorithm to get the index of particular items in a sorted UDT array.

    I want the index values of the first occurrence of three items in the UDT - column, row, objectType.

    Only the first item I am after is correct.
    (not coincidently I guess because this item is sorted first in the array)

    Any guidance as to how to correct this?

    Form1 Code:
    Code:
    Option Explicit
    
    
    Private Sub Form_Load()
    
        Command1.Caption = "Run"
    
    End Sub
    
    
    Private Sub Command1_Click()
    
        Call LoadTestData01
    
        Dim o As Long   'object counter
        
        '-----------------------------------------------------------------------------------------
        ' Print obj for inspection (UNSORTED)
    
        Debug.Print "----------------------------------------------------------------------------"
        Debug.Print "obj() array UNSORTED"
        Debug.Print "----------------------------------------------------------------------------"
        Debug.Print "ndx          Column         Row                       ObjectType"
        For o = 1 To UBound(obj)
            Debug.Print "[" & o & "]", _
                        obj(o).Position.col, obj(o).Position.row, _
                        "|" & obj(o).objectType & "|"
        Next o
        '-----------------------------------------------------------------------------------------
        
        ' Sort obj array
        Call HeapSortGridObject(obj)
        
        '----------------------------------------------------------------------------------------
        ' Print obj for inspection (SORTED)
        
        Debug.Print "----------------------------------------------------------------------------"
        Debug.Print "obj() array SORTED"
        Debug.Print "----------------------------------------------------------------------------"
        Debug.Print "ndx          Column         Row                       ObjectType"
        For o = 1 To UBound(obj)
            Debug.Print "[" & o & "]", _
                        obj(o).Position.col, obj(o).Position.row, _
                        "|" & obj(o).objectType & "|"
        Next o
        '-----------------------------------------------------------------------------------------
        
        
        '-----------------------------------------------------------------------------------------
        ' Get Indexes
        
        Dim col As Long
        Dim row As Long
        Dim objectType As String
        
        col = 31
        row = 3
        objectType = "Bar"
        
        MsgBox "First occurrence of Column " & col & " at index " & _
               BinarySearchForColumn(obj, col)
        MsgBox "First occurrence of Row " & row & " at index " & _
               BinarySearchForRow(obj, row)
        MsgBox "First occurrence of objectType " & objectType & " at index " & _
               BinarySearchForObjectType(obj, objectType)
        '-------------------------------------------------------------------------------------------
        
    End Sub
    
    
    Private Sub LoadTestData01()
    
        ReDim obj(1 To 7)
    
        obj(1).Position.col = 322
        obj(1).Position.row = 7
        obj(1).objectType = "Note"
        
        obj(2).Position.col = 17
        obj(2).Position.row = 3
        obj(2).objectType = "Bar"
        
        obj(3).Position.col = 12
        obj(3).Position.row = 15
        obj(3).objectType = "Note"
        
        obj(4).Position.col = 48
        obj(4).Position.row = 12
        obj(4).objectType = "Bar"
        
        obj(5).Position.col = 19
        obj(5).Position.row = 8
        obj(5).objectType = "Note"
        
        obj(6).Position.col = 19
        obj(6).Position.row = 5
        obj(6).objectType = "Note"
    
        obj(7).Position.col = 31
        obj(7).Position.row = 6
        obj(7).objectType = "Note"
    
    End Sub
    Module1 Code:
    Code:
    Option Explicit
    
    
    '-----------------------------------
    Public Type GridPosition
        col As Long
        row As Long
    End Type
    '-----------------------------------
    
    '-----------------------------------
    Public Type GridObject
        objectType As String * 32
        Position As GridPosition
        glyphNum As Long
    End Type
    
    Public obj() As GridObject
    '-----------------------------------
    Module2 Code:
    Code:
    Option Explicit
    
    
    '-----------------------------------------------------------------------------------------------
    ' Heap Sort Routines
    
    ' HeapSort (SiftDown) set for: 1-base/ascending/3-item sort
    
    Public Sub HeapSortGridObject(ByRef Items() As GridObject)
        Dim last As Long
        Dim Temp As GridObject
        
        HeapifyGridObject Items, UBound(Items)
        For last = UBound(Items) To 2 Step -1
            Temp = Items(last)
            Items(last) = Items(1)
            Items(1) = Temp
            SiftDownGridObject Items, 1, last - 1
        Next
    End Sub
    
    
    Private Sub HeapifyGridObject(ByRef Items() As GridObject, _
                                  ByVal count As Long)
        Dim Start As Long
        
        For Start = count \ 2 To 1 Step -1
            SiftDownGridObject Items, Start, count
        Next
    End Sub
    
    
    Private Sub SiftDownGridObject(ByRef Items() As GridObject, _
                                   ByVal Start As Long, ByVal last As Long)
        Dim Root As Long
        Dim Child As Long
        Dim Swap As Long
        Dim Comp As Integer
        Dim Temp As GridObject
        
        '-------------------------------------------------------------------------------------------
        
    
        '-------------------------------------------------------------------------------------------
        ' Sort on 3 fields (.Position.Col then .Position.Row then .objectType)
    
        Root = Start
        Do While Root * 2 <= last
            Child = Root * 2
            Swap = Root
            Comp = Sgn(Items(Swap).Position.col - Items(Child).Position.col)
            If Comp = 0 Then
                Comp = Sgn(Items(Swap).Position.row - Items(Child).Position.row)
                If Comp = 0 Then
                    Comp = Sgn(Items(Swap).objectType - Items(Child).objectType)
                End If
            End If
            If Comp < 0 Then Swap = Child
            If Child + 1 <= last Then
                Comp = Sgn(Items(Swap).Position.col - Items(Child + 1).Position.col)
                If Comp = 0 Then
                    Comp = Sgn(Items(Swap).Position.row - Items(Child + 1).Position.row)
                    If Comp = 0 Then
                        Comp = Sgn(Items(Swap).objectType - Items(Child + 1).objectType)
                    End If
                End If
                If Comp < 0 Then Swap = Child + 1
            End If
            If Swap <> Root Then
                Temp = Items(Root)
                Items(Root) = Items(Swap)
                Items(Swap) = Temp
                Root = Swap
            Else
                Exit Do
            End If
        Loop
        '-------------------------------------------------------------------------------------------
    
        
    End Sub
    Module3 Code:
    Code:
    Option Explicit
    
    
    Public Function BinarySearchForColumn(aSorted() As GridObject, key As Long) As Long
    
        ' (iterative) binary search algorithm (or half-interval search algorithm)
        ' finds position of a specified input value (search key) within an array sorted by key value
        
        ' algorithm modified to insert at leftmost position
        ' if the key value appears one or more times in the array
        
        Dim minIndex     As Long 'Integer
        Dim maxIndex     As Long 'Integer
        Dim midIndex     As Long 'Integer
        
        minIndex = 1 '0
        maxIndex = UBound(aSorted) - 1
    
        
        Do While minIndex <= maxIndex
            midIndex = Int((minIndex + maxIndex) / 2)
            If key <= aSorted(midIndex).Position.col Then
                maxIndex = midIndex - 1
            Else
                minIndex = midIndex + 1
            End If
        Loop
            
        ' key not found; insert at minIndex
        BinarySearchForColumn = minIndex
    
    End Function
    
    
    Public Function BinarySearchForRow(aSorted() As GridObject, key As Long) As Long
    
        ' (iterative) binary search algorithm (or half-interval search algorithm)
        ' finds position of a specified input value (search key) within an array sorted by key value
        
        ' algorithm modified to insert at leftmost position
        ' if the key value appears one or more times in the array
        
        Dim minIndex     As Long 'Integer
        Dim maxIndex     As Long 'Integer
        Dim midIndex     As Long 'Integer
        
        minIndex = 1 '0
        maxIndex = UBound(aSorted) - 1
    
        
        Do While minIndex <= maxIndex
            midIndex = Int((minIndex + maxIndex) / 2)
            If key <= aSorted(midIndex).Position.row Then
                maxIndex = midIndex - 1
            Else
                minIndex = midIndex + 1
            End If
        Loop
            
        ' key not found; insert at minIndex
        BinarySearchForRow = minIndex
    
    End Function
    
    
    Public Function BinarySearchForObjectType(aSorted() As GridObject, key As String) As Long
    
        ' (iterative) binary search algorithm (or half-interval search algorithm)
        ' finds position of a specified input value (search key) within an array sorted by key value
        
        ' algorithm modified to insert at leftmost position
        ' if the key value appears one or more times in the array
        
        Dim minIndex     As Long 'Integer
        Dim maxIndex     As Long 'Integer
        Dim midIndex     As Long 'Integer
        
        minIndex = 1 '0
        maxIndex = UBound(aSorted) - 1
    
        
        Do While minIndex <= maxIndex
            midIndex = Int((minIndex + maxIndex) / 2)
            If key <= aSorted(midIndex).objectType Then
                maxIndex = midIndex - 1
            Else
                minIndex = midIndex + 1
            End If
        Loop
            
        ' key not found; insert at minIndex
        BinarySearchForObjectType = minIndex
    
    End Function

  2. #2
    PowerPoster Arnoutdv's Avatar
    Join Date
    Oct 2013
    Posts
    3,553

    Re: Binary Search Troubles

    If all three items are important then you should sort on all fields.
    First on column, then if the column is the same on rows, if the row is the same then on object type.

    But it seems you want to Search on either Column, Row or Object?
    In that case you would need 3 separate lists

  3. #3

  4. #4
    PowerPoster Zvoni's Avatar
    Join Date
    Sep 2012
    Location
    To the moon and then left
    Posts
    1,868

    Re: Binary Search Troubles

    What i don't understand:
    If you're searching in a grid by column and row, why are you, additionally (!), searching for Object-Type?
    A position in a grid can never have two (or more) Objects.
    If coordinate col=300, row=17 is occupied by Object "Bar", then it doesn't make sense to look for "Foo" at those coordinates.

    Maybe your problem becomes more "managable" if you only have 2 dimensions to search....

    or i'm really way off in understanding your problem...
    One System to rule them all, One IDE to find them,
    One Code to bring them all, and to the Framework bind them,
    in the Land of Redmond, where the Windows lie
    ---------------------------------------------------------------------------------
    People call me crazy because i'm jumping out of perfectly fine airplanes.
    ---------------------------------------------------------------------------------
    For health reasons i try to avoid reading unformatted Code

  5. #5

    Thread Starter
    Addicted Member
    Join Date
    Nov 2018
    Posts
    164

    Re: Binary Search Troubles

    My main goal here, was to find the first occurrence of Bar in the grid.

    Zvoni
    Yes, a Position (column, row) in a grid can have only one object,
    but each column can have a many rows (in my case 75).
    So then yes, any grid position (Position.Col, Position.Row) can hold only one object.

    Arnoutdv
    I am searching on all 3 fields: (column, row, type)
    first on Position.Col, then on Position.Row, then on objectType

    wqweto
    I will try separate heaps for each of these items, as you suggest.
    I thought by sorting on all three fields simultaneously (as I have done), I would
    eliminate the need to do separate heapsorts, thus saving time.
    Last edited by mms_; Sep 9th, 2019 at 08:03 AM.

  6. #6
    PowerPoster techgnome's Avatar
    Join Date
    May 2002
    Posts
    32,406

    Re: Binary Search Troubles

    But a binary search can only work on a single aspect at a time... That's how it works. It looks at a single aspect, compares it to the middle element and see how it falls... if the value is grater then, it discards the first half of the array. If you give it (3,2,"Notes") .. how can you compare that to something and determine which way to go? Or for that matter, is (3,2, "Notes") grater or less than (2,3, "Notes") ?

    Further complicating things, in one statement you declare that a grid position can only have one object, but then the next thing you state is that you are searching on all three... why? If there can be only one object, why does the type come into play?

    -tg
    * I don't respond to private (PM) requests for help. It's not conducive to the general learning of others.*
    * I also don't respond to friend requests. Save a few bits and don't bother. I'll just end up rejecting anyways.*
    * How to get EFFECTIVE help: The Hitchhiker's Guide to Getting Help at VBF - Removing eels from your hovercraft *
    * How to Use Parameters * Create Disconnected ADO Recordset Clones * Set your VB6 ActiveX Compatibility * Get rid of those pesky VB Line Numbers * I swear I saved my data, where'd it run off to??? *

  7. #7
    PowerPoster Arnoutdv's Avatar
    Join Date
    Oct 2013
    Posts
    3,553

    Re: Binary Search Troubles

    If all three items are important then you should sort on all fields.
    First on column, then if the column is the same on rows, if the row is the same then on object type.
    But then you need to pass all 3 wanted items in the search, are use a compound sort key.

    Code:
    Option Explicit
    
    Private Enum enObjectType
      otBar = 1
      otNote = 2
    End Enum
    
    Private Type tpUDT
      lCol As Long
      lRow As Long
      iObjectType As enObjectType
      sSortKey As String
    End Type
    
    Private Sub Form_Load()
      Dim tData() As tpUDT
      pLoadData
      pAddSortKey
      pSortData
    End Sub
    
    Private Sub pLoadData(tData() As tpUDT)
      ReDim tData(6)
    
      tData(0).lCol = 322
      tData(0).lRow = 7
      tData(0).iObjectType = 2
      
      tData(1).lCol = 17
      tData(1).lRow = 3
      tData(1).iObjectType = 1
      
      tData(2).lCol = 12
      tData(2).lRow = 15
      tData(2).iObjectType = 2
      
      tData(3).lCol = 48
      tData(3).lRow = 12
      tData(3).iObjectType = 1
      
      tData(4).lCol = 19
      tData(4).lRow = 8
      tData(4).iObjectType = 2
      
      tData(5).lCol = 19
      tData(5).lRow = 5
      tData(5).iObjectType = 2
    
      tData(6).lCol = 31
      tData(6).lRow = 6
      tData(6).iObjectType = 2
    End Sub
    
    Private Sub pAddSortKey(tData() As tpUDT)
      Dim i As Long
      
      For i = LBound(tData) To UBound(tData)
        With tData(i)
          .sSortKey = Format(.lCol, "000000") & "*" & Format(.lRow, "000000") & "*" & Format(.iObjectType, "00")
        End With
      Next i
    End Sub
    
    Private Sub pSortData(tData() As tpUDT)
      Dim lLBound As Long, lUBound As Long
      Dim lLoop As Long, lHold As Long, lHValue As Long
      Dim tTemp As tpUDT
      
      lLBound = LBound(tData)
      lUBound = UBound(tData)
      
      lHValue = lLBound
    
      Do
        lHValue = 3 * lHValue + 1
      Loop Until lHValue > lUBound
        
      Do
        lHValue = lHValue / 3
        
        For lLoop = lHValue + lLBound To lUBound
          tTemp = tData(lLoop)
          lHold = lLoop
          Do While tData(lHold - lHValue).sSortKey > tTemp.sSortKey
            tData(lHold) = tData(lHold - lHValue)
            lHold = lHold - lHValue
            If lHold < lHValue Then Exit Do
          Loop
          tData(lHold) = tTemp
        Next lLoop
      Loop Until lHValue = lLBound
    
    End Sub
    
    Private Function pGetIndex(ByVal sKey As Long, tData() As tpUDT) As Long
      Dim lFirst As Long, lLast As Long, lMiddle As Long
      
      ' assume search failed
      pGetIndex = -1
      
      lFirst = 0
      lLast = UBound(tData)
      
      Do
        lMiddle = (lFirst + lLast) \ 2
        If tData(lMiddle).sSortKey = sKey Then
          pGetIndex = lMiddle
          Exit Do
        ElseIf tData(lMiddle).sSortKey < sKey Then
          lFirst = lMiddle + 1
        Else
          lLast = lMiddle - 1
        End If
      Loop Until lFirst > lLast
      
    End Function
    What I don't understand is how you use the data array.
    If you want to populate a grid then you can simply walk through all items in the array and fill each cell you encounter based, because each items has a row and col property.

    Or are you starting from the grid, walking through all rows and columns and then try to find the correct item?
    Last edited by Arnoutdv; Sep 9th, 2019 at 09:00 AM.

  8. #8
    PowerPoster Zvoni's Avatar
    Join Date
    Sep 2012
    Location
    To the moon and then left
    Posts
    1,868

    Re: Binary Search Troubles

    tg, the hint is in his first sentence: he searches for the first occurence of "Bar" in his Grid.

    Now the question is: What defines "first"?
    Are you searching columnwise or rowwise?

    Is row=1, col=7 "earlier" than row=4,col=5 or not?
    going by rows, it's earlier, going by column it's later

    And in case the Search key can appear multiple times (as in your code-sample above, Object "Note") in your Array, i don't think a Binary Search is the best way, especially since you search for the first occurence

    EDIT: Arnout just gave me this idea with his compound-key:
    Invisible/Hidden ListBox (sorted),
    filled up with his compound key in Format "ObjectXXXYYY" (you'll have to define if row (X) or column (Y) comes first), e.g. "Bar003017"
    Use Sendmessage with LB_FINDSTRING, which should return the first (partial) Match for "Bar"
    Last edited by Zvoni; Sep 9th, 2019 at 09:06 AM.
    One System to rule them all, One IDE to find them,
    One Code to bring them all, and to the Framework bind them,
    in the Land of Redmond, where the Windows lie
    ---------------------------------------------------------------------------------
    People call me crazy because i'm jumping out of perfectly fine airplanes.
    ---------------------------------------------------------------------------------
    For health reasons i try to avoid reading unformatted Code

  9. #9

    Thread Starter
    Addicted Member
    Join Date
    Nov 2018
    Posts
    164

    Re: Binary Search Troubles

    After I heapsort, I get the following output:
    Code:
    ----------------------------------------------------------------------------
    obj() array SORTED
    ----------------------------------------------------------------------------
    ndx          Column         Row                       ObjectType
    [1]            12            15           |Note                            |
    [2]            17            3            |Bar                             |
    [3]            19            5            |Note                            |
    [4]            19            8            |Note                            |
    [5]            31            6            |Note                            |
    [6]            48            12           |Bar                             |
    [7]            322           7            |Note                            |
    I thought BinarySearchForObjectType(obj, "Bar") would return ndx = 2
    and from that I would then know that
    the first Bar object is at grid position (17,5)

    ...or at least that's what I want

    My next question was going to be...
    How to seek to the next bar object and then be able to determine it's position is (48,12)

  10. #10
    PowerPoster Arnoutdv's Avatar
    Join Date
    Oct 2013
    Posts
    3,553

    Re: Binary Search Troubles

    This screams for a simple data table, either ADO or SQLite.
    Build a in memory data table with 3 columns
    Fill the table.
    Then query the table:
    select col, row from mytable where objecttype="Bar" order by col, row

    This would give you a recordset with only the "Bar" records ordered by col and row.

  11. #11

    Thread Starter
    Addicted Member
    Join Date
    Nov 2018
    Posts
    164

    Re: Binary Search Troubles

    Arnoutdv
    Or are you starting from the grid, walking through all rows and columns and then try to find the correct item?
    Yes, I am starting from the grid...

    As user places new objects into the grid, I always make sure it stays in a sorted state.

    thus from this sorted state
    Code:
    ----------------------------------------------------------------------------
    obj() array SORTED
    ----------------------------------------------------------------------------
    ndx          Column         Row                       ObjectType
    [1]            12            15           |Note                            |
    [2]            17            3            |Bar                             |
    [3]            19            5            |Note                            |
    [4]            19            8            |Note                            |
    [5]            31            6            |Note                            |
    [6]            48            12           |Bar                             |
    [7]            322           7            |Note                            |
    I just want to seek to each Bar object and determine their co-ordinates.

    Yes, your suggestion to use data table is a good one, but I am so deep into this methodology that I have already set up,
    I'd like to stick with it, and work with that.

    ps
    I tried your code, but as of yet, I cannot get it to execute.


    Zvoni
    Is row=1, col=7 "earlier" than row=4,col=5 or not?
    my array is first sorted by column (ascending) then row (ascending)
    so
    col=4,row=5 is "earlier" than col=7,row=1
    I think the 7 record listing above, demonstrates this.
    Last edited by mms_; Sep 9th, 2019 at 10:00 AM.

  12. #12
    PowerPoster Elroy's Avatar
    Join Date
    Jun 2014
    Location
    Near Nashville TN
    Posts
    5,663

    Re: Binary Search Troubles

    I haven't done binary searches in a while, as databases have taken over most of that work, and I seldom (if ever) concern myself with how these database back-ends do their searching.

    However, there was once a time when I wrote and maintained binary search algorithms fairly regularly. For me, the first decision was always whether it was going to be disk-based or memory-based. The second decision is always whether I'm actually going to sort the data, or create a sorted pointer array that points into the data without needing to actually sort it.

    If you use the pointer array approach, you can actually have several of these sorted pointer arrays (sorting your data in several different ways). These would be conceptually similar to indices in a database.

    But, as you seem to recognize, a binary search will only work if the data are sorted (or has a sorted pointer array). So, that's an underlying assumption.

    So, once those decisions are made, it's just a matter of doing the binary search. As I remember, what's most important is to always test the "edge" conditions, such as:
    • What happens when your dataset is empty?
    • What happens when there's only one record in your dataset?
    • What happens when there's only two records in your dataset?
    • What happens with three records in the dataset.
    • Does it work correctly with an odd number of records?
    • Does it work correctly with an even number of records?
    • Will you need to deal with duplicates (in the fields/columns), and how should they be handled?

    Just some thoughts. I've actually always thought binary searches were fun. It's more the add/delete methods (and updating all the pointers) that took some care.

    Good Luck,
    Elroy
    Any software I post in these forums written by me is provided “AS IS” without warranty of any kind, expressed or implied, and permission is hereby granted, free of charge and without restriction, to any person obtaining a copy. Please understand that I’ve been programming since the mid-1970s and still have some of that code. My contemporary VB6 project is approaching 1,000 modules. In addition, I have a “VB6 random code folder” that is overflowing. I’ve been at this long enough to truly not know with absolute certainty from whence every single line of my code has come, with much of it coming from programmers under my employ who signed intellectual property transfers. I have not deliberately attempted to remove any licenses and/or attributions from any software. If someone finds that I have inadvertently done so, I sincerely apologize, and, upon notice and reasonable proof, will re-attach those licenses and/or attributions. To all, peace and happiness.

  13. #13
    Frenzied Member wqweto's Avatar
    Join Date
    May 2011
    Posts
    1,491

    Re: Binary Search Troubles

    Quote Originally Posted by Elroy View Post
    If you use the pointer array approach, you can actually have several of these sorted pointer arrays (sorting your data in several different ways). These would be conceptually similar to indices in a database.
    This is a sound advice -- using separate index arrays FTW.

    OP can create 3 indexes, i.e. arrays of Long w/ indexes into data (sorted by whatever field) and implement binary search on these indexes, not on original array of UDTs.

    cheers,
    </wqw>

  14. #14
    Sinecure devotee
    Join Date
    Aug 2013
    Location
    Southern Tier NY
    Posts
    5,333

    Re: Binary Search Troubles

    Quote Originally Posted by mms_ View Post
    After I heapsort, I get the following output:
    Code:
    ----------------------------------------------------------------------------
    obj() array SORTED
    ----------------------------------------------------------------------------
    ndx          Column         Row                       ObjectType
    [1]            12            15           |Note                            |
    [2]            17            3            |Bar                             |
    [3]            19            5            |Note                            |
    [4]            19            8            |Note                            |
    [5]            31            6            |Note                            |
    [6]            48            12           |Bar                             |
    [7]            322           7            |Note                            |
    I thought BinarySearchForObjectType(obj, "Bar") would return ndx = 2
    and from that I would then know that
    the first Bar object is at grid position (17,5)

    ...or at least that's what I want

    My next question was going to be...
    How to seek to the next bar object and then be able to determine it's position is (48,12)
    The ObjectType column is not sorted, so you can't do a binary search on that column. You might want to read about the construction of a binary sort to understand why that is (brief synopsis by techgnome already in post #6). You would just do a linear search on the object column, or create a sorted list based on that column, as has already been mentioned several times. But, since the "key" appears multiple times in your list (as has also been mentioned), then a binary search would still not be the best approach, since once you find one, you have to do a linear search down to find the first, and work from there to find the next.

    I don't work with databases, so don't know the proper way to approach it from that angle, but I do implement these kind of things myself in place of using a database. In that case, I would create lists of lists, essentially. So, for each object type create an entry in an array (so that can be your sorted list based on object type name), and then you would have a list of indexes that contain that type.

    So, with your simple example, you would have two entries in your key list, with multiple entries in the list associated with that key.
    Code:
    Bar, 2, 6
    Note, 1, 3, 4, 5, 7

  15. #15
    PowerPoster Zvoni's Avatar
    Join Date
    Sep 2012
    Location
    To the moon and then left
    Posts
    1,868

    Re: Binary Search Troubles

    Quote Originally Posted by Arnoutdv View Post
    This screams for a simple data table, either ADO or SQLite.
    Build a in memory data table with 3 columns
    Fill the table.
    Then query the table:
    select col, row from mytable where objecttype="Bar" order by col, row

    This would give you a recordset with only the "Bar" records ordered by col and row.
    After reading everything else, i‘m with you on this one, except i would SELECT all 3 „Fields“ with no WHERE-Filter, but yor ORDER BY
    then he could just use the Find/Filter of the RS.

    EDIT: or if everything fails, there is still my approach with the hidden listbox *shrug*
    Last edited by Zvoni; Sep 9th, 2019 at 02:58 PM.
    One System to rule them all, One IDE to find them,
    One Code to bring them all, and to the Framework bind them,
    in the Land of Redmond, where the Windows lie
    ---------------------------------------------------------------------------------
    People call me crazy because i'm jumping out of perfectly fine airplanes.
    ---------------------------------------------------------------------------------
    For health reasons i try to avoid reading unformatted Code

  16. #16
    Frenzied Member wqweto's Avatar
    Join Date
    May 2011
    Posts
    1,491

    Re: Binary Search Troubles

    Quote Originally Posted by Zvoni View Post
    After reading everything else, i‘m with you on this one, except i would SELECT all 3 „Fields“ with no WHERE-Filter, but yor ORDER BY
    then he could just use the Find/Filter of the RS.

    EDIT: or if everything fails, there is still my approach with the hidden listbox *shrug*
    This is called Abstraction Inversion anti-pattern. In this case when you need to implement a binary search you bring in a whole RDBMS only for the search and then the funny part is that the RDBMS (or ADO) do use binary search implemented underneath it all :-))

    cheers,
    </wqw>

  17. #17
    PowerPoster Arnoutdv's Avatar
    Join Date
    Oct 2013
    Posts
    3,553

    Re: Binary Search Troubles

    How @mms_ describes what he needs that would be easily solved with simple queries on a table.
    There is in my opinion no need for a DB or RecordSet either.
    I don't see why @mms_ starts from the grid and the searches the data for each cell.
    I would start from the data and populate the grid, because the data already has row,col properties.

  18. #18
    Frenzied Member wqweto's Avatar
    Join Date
    May 2011
    Posts
    1,491

    Re: Binary Search Troubles

    Quote Originally Posted by Arnoutdv View Post
    I don't see why @mms_ starts from the grid and the searches the data for each cell.
    He *is* implementing a grid control IMO. We are staring at the guts of it and using DB queries to manage internal state is not an option IMO.

    cheers,
    </wqw>

  19. #19
    PowerPoster Zvoni's Avatar
    Join Date
    Sep 2012
    Location
    To the moon and then left
    Posts
    1,868

    Re: Binary Search Troubles

    Quote Originally Posted by Arnoutdv View Post
    I don't see why @mms_ starts from the grid and the searches the data for each cell.
    I would start from the data and populate the grid, because the data already has row,col properties.
    Because "his" User places an Object into the Grid, the Grid is not "prepopulated".
    See Post #11
    One System to rule them all, One IDE to find them,
    One Code to bring them all, and to the Framework bind them,
    in the Land of Redmond, where the Windows lie
    ---------------------------------------------------------------------------------
    People call me crazy because i'm jumping out of perfectly fine airplanes.
    ---------------------------------------------------------------------------------
    For health reasons i try to avoid reading unformatted Code

  20. #20
    PowerPoster Arnoutdv's Avatar
    Join Date
    Oct 2013
    Posts
    3,553

    Re: Binary Search Troubles

    Okay, I'm out, I seem to miss the complete picture and only make things more confusing.

  21. #21

    Thread Starter
    Addicted Member
    Join Date
    Nov 2018
    Posts
    164

    Re: Binary Search Troubles

    Thanks for all the help...
    It is truly appreciated!

    The user enters all objects onto grid (not necessarily paying attention to proper positioning of these objects),
    then computer algorithm re-positions these objects properly between the "Bars"

    For now, I will use a simple For i = ... block to walk through all items in the grid searching for "Bar"

    This works properly, I just thought I could make use of a Binary Search to do the same thing,
    and that this would be lighting fast if user placed thousands of objects in grid.

    I will re-visit this in the future.
    Last edited by mms_; Sep 10th, 2019 at 11:30 PM.

  22. #22
    PowerPoster Zvoni's Avatar
    Join Date
    Sep 2012
    Location
    To the moon and then left
    Posts
    1,868

    Re: Binary Search Troubles

    Have you thought about my approach with the hidden Listbox?
    Presort your Array of UDT's acc. to your requirements (First Col, then Row)
    Place invisible ListBox on Form (Sorted=False)
    Enter the sorted Array into the Listbox in Format "TypeColRow" (e.g. "Bar017003") using the Array-Index as ItemData.
    Use API SendMessage with LB_FINDSTRING to find the first (partial) Match for "Bar".
    Save the returned ListIndex of your first search to use as wParam in the next search
    https://docs.microsoft.com/en-us/win.../lb-findstring
    One System to rule them all, One IDE to find them,
    One Code to bring them all, and to the Framework bind them,
    in the Land of Redmond, where the Windows lie
    ---------------------------------------------------------------------------------
    People call me crazy because i'm jumping out of perfectly fine airplanes.
    ---------------------------------------------------------------------------------
    For health reasons i try to avoid reading unformatted Code

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Featured


Click Here to Expand Forum to Full Width