Search Arraylist in Arraylist.

S

Simon Says

Hi all,

I've an arraylist A1 that contains {0,1,2,3,4,5,9,8,7}
I've another arraylist A2 that contains {4,5,9}

I would like to search whether if A2 is present in A1 and maybe return the
first occurance index. Can anyone advise on this?

Thanks,
Simon
 
S

Simon Says

Cor,

I've tried this but doesn't seem to be working. I think what this function
does is that it searches through each items in my A1 for the exact matches
of the whole of A2. That is to say:

Items in A1: Items in A2:
0 {4,5,9}
1
2
3
4
5
9
8
7

It searches each items in A1 for an arraylist of {4,5,9}. Instead, I need
something like

Items in A1: Items in A2:
0 4
1 5
2 9
3
4
5
9
8
7

Sorry I can't explain too well, but any other ways?

--Simon
 
A

Andrew Morton

Simon said:
Hi all,

I've an arraylist A1 that contains {0,1,2,3,4,5,9,8,7}
I've another arraylist A2 that contains {4,5,9}

I would like to search whether if A2 is present in A1 and maybe
return the first occurance index. Can anyone advise on this?

Are you saying that the elements in A1 and A2 are unique and in order? Are
A1 and A2 of trivial length?

if count(A2)>count(A1) then no match
take first element of A2 and find it in A1
check there are enough elements remaining in A1 for a match to be possible
take subsequent elements of A2 and compare them to subsequent elements of A1

Andrew
 
C

Cor Ligthert [MVP]

Simon,

First of all, I do probably not understand what you want.

A try
\\\
Dim a1 As New ArrayList
a1.AddRange(New Object() {0, 1, 2, 3, 4, 5, 9, 6, 8, 7})
Dim a2 As New ArrayList
a2.AddRange(New Object() {4, 5, 9})
For i As Integer = 0 To a2.Count - 1
Dim ind As Integer = a1.IndexOf(a2(i))
If ind > -1 Then
MessageBox.Show(ind.ToString)
End If
Next
///

I hope this helps,

cor
 
S

Simon Says

Can't understand myself too :) Anyway, I've tried something like,

//
dim a1 as new ArrayList
dim a2 as new ArrayList

a1.AddRange(New Integer() {0,1,2,3,4,5,9,8,7})
a2.AddRange(New Integer() {4,5,9})

if a1.IndexOf(a2) > -1 then
call msgbox("Found")
else
call msgbox("Not Found")
End if
//

The result I got is "Not Found". I think with IndexOf function it searches
throught a1 in following sequence:

0 ----> {4,5,9}
1 ----> {4,5,9}
2 ----> {4,5,9}
....
7 ----> {4,5,9}

Therefore, I will not be able to get a match. If Cor's method is the only
way, I will try to change my implementation as O(n*m) performance isn't
quite impressive - O(n) for IndexOf function call and O(m) for looping
through a2.

Any more insights?

--Simon
 
A

Andrew Morton

If so, convert them to strings (somehow) and use string functions on them.

Using ArrayList.IndexOf(someArrayList) won't work because it looks for an
ArrayList entity within your ArrayList, but the entities in your array list
are numbers.

Andrew
 
S

Simon Says

Hi Andrew,

I can't convert them to string as the data I'm working on is network
streaming bytes that contains compressed data. Converting them to string
will sort of mess up my compressed data. All my streaming bytes will be
stored in A1 which will varies in size, and I will check for delimiter -
A2 - which will be of fixed length.

I've already worked out a helper function as suggested by Cor, but the
O(n*m) performance just worries me a little.

--Simon
 
A

Andrew Morton

Simon said:
I can't convert them to string as the data I'm working on is network
streaming bytes that contains compressed data. Converting them to
string will sort of mess up my compressed data. All my streaming
bytes will be stored in A1 which will varies in size, and I will
check for delimiter - A2 - which will be of fixed length.

Imagine streem is your incoming data and eos is the sequence indicating the
end of the packet in the stream. In your case they would be bytes, but for
my convenience I've used strings, so remember that VB strings have their
first character at position 1, not 0.

Dim streem As String = "4632468249214747473773"
Dim eos As String = "324"
Dim c As String

Dim eosPos As Integer = 1 ' position in eos
Dim streemPos As Integer = 1 ' position in streem
Dim dataEnd As Integer ' the length of the data, less the eos marker

While streemPos <= Len(streem)
streemPos += 1
c = Mid(streem, streemPos, 1)
If c = Mid(eos, eosPos, 1) Then
eosPos += 1
If eosPos > Len(eos) Then
' we have found the end of the data
dataEnd = streemPos - Len(eos)
Exit While
End If
Else
eosPos = 1
End If
End While

Andrew
 
S

Simon Says

Since my data is in byte, my values are in the range of 0-255. By converting
my stream of data to string (also tried based64String) will totally messed
up my data.

What I've tried was convert my byte() to string (using
Convert.ToBased64String) then find the delimiter position and extract out
the data portion, then convert the data portion back to byte(). It just
messed up my compressed data.
 
A

Andrew Morton

Simon said:
Since my data is in byte, my values are in the range of 0-255. By
converting my stream of data to string (also tried based64String)
will totally messed up my data.

What I've tried was convert my byte() to string (using
Convert.ToBased64String) then find the delimiter position and extract
out the data portion, then convert the data portion back to byte().
It just messed up my compressed data.

No! No! Change it to use bytes. I used strings for my convenience, but as
I've been waiting for my computer to process a load of stuff I've had a few
minutes to have a go myself.

* If this is homework then do not read on until you have failed to change it
yourself. *













If you have a form with a textbox named TextBox1, then...

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As
System.EventArgs) Handles MyBase.Load

Dim streemB As New ArrayList ' the pretend data
Dim bytes As String() =
Split("12,13,14,15,0,255,19,127,13,10,255,18,17,34,65,76,13,10,255,7,6,5,13,10,255,1,2,3",
",")
For i As Integer = LBound(bytes) To UBound(bytes)
streemB.Add(CByte(CInt(bytes(i))))
Next

Dim eop As New ArrayList ' the end-of-packet (eop) marker
eop.Add(13)
eop.Add(10)
eop.Add(255)

Dim packet As New ArrayList

Dim packetNo As Integer = 0

Dim eopPos As Integer = 0 ' position in eop
Dim streemPos As Integer = 0 ' position in streemB

Dim dataStart As Integer = 0
Dim dataEnd As Integer ' the end of a packet

While streemPos < streemB.Count
If CByte(streemB(streemPos)) = CByte(eop(eopPos)) Then
eopPos += 1
If eopPos = eop.Count Then
' we have found the end of a packet
' so copy it to its own ArrayList
packet.Add(New ArrayList)
dataEnd = streemPos - eop.Count
For i As Integer = dataStart To dataEnd
DirectCast(packet.Item(packetNo), ArrayList).Add(streemB(i))
Next
packetNo += 1
dataStart = streemPos + 1
eopPos = 0
End If
Else
' this byte was not part of the eop marker, therefore not at end of
packet
eopPos = 0
End If
streemPos += 1
End While

printit:
Dim s As New System.Text.StringBuilder
Dim a As ArrayList

For i As Integer = 0 To packet.Count - 1
a = DirectCast(packet.Item(i), ArrayList)
For j As Integer = 0 To a.Count - 1
s.Append(a.Item(j).ToString)
s.Append(", ")
Next
' remove extra ", "
s.Length = Math.Max(s.Length - 2, 0)
s.Append(Environment.NewLine)
Next
' remove extra Environment.NewLine
s.Length = Math.Max(s.Length - Environment.NewLine.Length, 0)
TextBox1.Text = s.ToString

End Sub

(watch for line-
wrap)

The displayed output will be:
12, 13, 14, 15, 0, 255, 19, 127
18, 17, 34, 65, 76
7, 6, 5

- notice it hasn't included the last bytes (1,2,3) because it hasn't seen an
end-of-packet marker.

Additionally, I don't see much point in storing the bytes in an ArrayList if
it's a stream from a network. It will not be much effort for you to change
the code to work with a stream of unknown length.

The 2.0 .NET framework may make it tidier than having to use DirectCast to
tell it the ArrayList you put in is an ArrayList (grrrr...).

Um, how do you propose to ensure your compressed data does not just happen
to have the same sequence of bytes as the eop marker? Why not send the
length of the compressed data, followed by the compressed data?

Now, who's going to show us how to do it in three lines? :)

Andrew
 
S

Simon Says

Hi Andrew,

Well, I'm too old for doing homework :) Anyway, just to share it, I've the
following to find the 1st index of occurance:

////
//searchList contains my streaming data.
Private Function FindDelimiter(ByVal searchList As ArrayList, ByVal
delimiter() As Byte) As Integer

Dim searchIndex As Integer = 0



While True

searchIndex = searchList.IndexOf(delimiter(0), searchIndex)

If searchIndex > -1 Then

Dim searchArray As ArrayList =
searchList.GetRange(searchIndex, delimiter.Length)

For i As Integer = 0 To delimiter.Length - 1

If searchArray.Item(i) <> delimiter(i) Then

searchIndex += i

Continue While

End If

Next

Return searchIndex

Else

Return -1

End If

End While



End Function

////

Regarding your question on how to ensure the right eos sequence, I was
thinking of sending the message length following with the compressed
message, but later opt for using delimiter. I've a header and footer -
<Packet> and </Packet>. And since I'm using GZip for my compressed data,
with the 'magic number' 31,139,08' as the header, I'm using these 3
delimiters to find the compressed data.

Now, the question is why I opt for using delimiter? Umm ... not too sure
myself. Althought my streaming data is via TCP where it guarantee ordered
data delivery, I think I'm just paranoid with the sequence of streaming
(length - msg - length - msg - length - msg ...) with both the TCP and my
multi-threaded application.

Thanks,
Simon
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top