Android Question [SOLVED] Search a list of customtypes?

[techknight]

I have tried searching the forum and I cant quite find what I am looking for. Maybe I am not wording it right.

Anyways, I have a custom type of PeriodInfo which contains 3 int variables. Period, Minutes, and Seconds.

I am inserting those in a list, one by one as a person adds them.

However, How do I "search" the list if any records exist matching "Period" or "minutes" which are variables/definitions of my customtype?

for example if PeriodInfo.Period = 3, then search the list for any entries that contain Period = 3.

is this possible? thanks!

 

[MarkusR]

something like that

Type PeriodInfo(Period As Int, Minutes As Int, Seconds As Int)

Sub Test

    Dim List1 As List
    List1.Initialize
    
    For i=1 To 10
        Dim Info As PeriodInfo
        Info.Period=i
        List1.Add(Info)
    Next

    Dim Search As List
    Search.Initialize
    Search.Clear
    For Each Info As PeriodInfo In List1
        If Info.Period = 5 Then
            Search.Add(Info)
        End If
    Next

    For Each Info As PeriodInfo In Search
        Log(Info.Period)
    Next
 
End Sub

 

[techknight]

Thats similar to what I was thinking.

Thanks.

 

[Erel]

The above answer is perfect.

If you have a very large list (10k+ items) and you want to make many searches then you can build an index. This will make searches very fast.

Sub Test

   Dim List1 As List
   List1.Initialize
   For i=1 To 100000
       Dim Info As PeriodInfo
       Info.Period=Rnd(1, 1000)
       List1.Add(Info)
   Next
   Dim index As Map = BuildIndex(List1) 'index should be a global variable
   Dim periods As List = index.Get(5)
   If periods.IsInitialized Then
       Log(periods)
   End If
End Sub

Sub BuildIndex (items As List) As Map
   Dim res As Map
   res.Initialize
   For Each info As PeriodInfo In items
       Dim MinutesList As List
       If res.ContainsKey(info.Period) = False Then
           Dim l As List
           l.Initialize
           res.Put(info.Period, l)
       End If
       MinutesList = res.Get(info.Period)
       MinutesList.Add(info)
   Next
   Return res
End Sub

 

[techknight]

I am staring at your BuildIndex subroutine, but I cant actually figure out whats going on in there.

I see where your declaring a list, but your storing an empty list in a map? Then there is MinutesList but it doesn't appear to go anywhere as its being re-dimed during each iteration of the loop. I'm confused.

can you elaborate on how that works a little bit? Thanks!

 

[Erel]

The index data structure is made of a Map.
Each item in a Map is made of a key / value pair.
info.Period is the key. The value is a List. Each item in the list is a PeriodInfo item where info.Period equals to the key.

Create a small index and log it or play with the debugger.

I see where your declaring a list, but your storing an empty list in a map?

There will never be an empty list. The first item will be immediately added.

 

[techknight]

Well I mean this:

           Dim l As List
           l.Initialize

You declare a list, and initialize it. but I dont see where there is any data going into that list?

 

[DonManfred]

but I dont see where there is any data going into that list?

Dim MinutesList As List
If res.ContainsKey(info.Period) = False Then
Dim l As List
l.Initialize
res.Put(info.Period, l) ' The, at this point empty, List is added to res Map using the Period as Key.
End If
MinutesList = res.Get(info.Period) ' The list is get from the Map using the Period
MinutesList.Add(info)' Add the value to the list

 

[techknight]

Some of these simple things just blow my mind. Mainly because of the level of abstraction to the background where I cant "physically" see whats going on.

I still dont see how the real data is getting into res. All I see is an empty list going into res.

I see MinutesLIst yes, but in my eyes MinutesList =/= res

 

[DonManfred]

All I see is an empty list going into res.

look a step closer

       If res.ContainsKey(info.Period) = False Then
           Dim l As List
           l.Initialize
           res.Put(info.Period, l)
       End If

The, empty list is added to res. Right?

Then, after the end if exactly this list is get from res Map.

 MinutesList = res.Get(info.Period) ' info.Period is the Key we just added in the if construct because there was no such key
' Effectively MinutesList - at this point - contains the empty List we just added. The List "l" above
       MinutesList.Add(info) ' We are adding the value to the list.

In further iterations

   For Each info As PeriodInfo In items

the code

MinutesList = res.Get(info.Period)

will return the filled List with one, two, three (and so on) items with the same Period as the Persiod is the Key.

 

[techknight]

I followed you up until you get to "in further iterations" as thats where I got lost.

I see a res.Get where it grabs the blank list and initializes MinutesList with the blank info.

But I dont see a res.Put anywhere outside of the if block. So, Thats where I am getting lost.

 

[DonManfred]

I see a res.Get where it grabs the blank list and initializes MinutesList with the blank info.

It is TRUE for the iteration where the info.Period was not available in the res Map. It is added and after the if then the list is get and added the Item.
But on every other iteration where another info comes with the same info.Period then the list is not added because the if then does not match.
Instead the existing List is get from the Map to add another Item.

 

[techknight]

I see data getting added to MinutesList. But again, I dont see a res.put(info.period, MinutesList)

 

[DonManfred]

I dont see a res.put(info.period, MinutesList)

The name does not matter. The list you get (and to which you are writing) is the List "l"!

MinutesList = res.Get(info.Period) ' This is the List l added in the IF THEN or the already available List in den Map. Again: Ths is l too if you want

 

[techknight]

Ahhh.... see thats where I get lost.

MinutesList =/= l in my head.

I am used to programming when you do a = b, a copy of b is put into a, but b still remains itself so whatever you do with b does nothing to a, and vice versa. Thats the way it is with every flavor of BASIC I had ever used, well, up until now. (never used .NET so I dunno there)

How I would know this is not the case, I would never know. Plus I might be putting my own thoughts into this because in my situation, There is never more than 1 period of each period in the list. if there is, its invalid. so If I need to pull the minutes and seconds for Period 3, I would go search for Period 3 and get that data.

 

[DonManfred]

I would go search for Period 3 and get that data.

True for small Lists of Items with the same Period.

Asume you have thousands of Items of the same Period. And you want to do a Search for another Value of the CustomType. Say Minutes for ex.
Asume you have 1000 different Periods. And for each Period you have 1000 Items.

Without the Index you would search 1000*1000 Items in your Global List to find the Items matching 15 Minutes and Period = 1

Using the Index you first get the List from the Index holding all CustomTypes with Period = 1.
Your search now only need to iterate through 1000 Items to find the Mathing Items with Minutes = 15

 

[techknight]

Oh I understand the purpose of indexing, if it wasn't valuable, then nobody would use it. right? Same thing with OS file searches. Alot of it is indexed.

I was just trying to figure out how that subroutine worked. And I still dont quite understand it completely. But I guess I will have to debug simulate it to know.

So now I have to start thinking like a C programmer where a Map or a List doesn't contain a copy of the object and its data, but instead just a "pointer" to where its already declared in memory.

Yikes and I hate C.

 

[DonManfred]

Alot of it is indexed.

It does help with a lot of UI Elements too
You can see my Answer in the Quiz #10 Thread.