Search Arraylist in Arraylist.

3 Feb 2006 7:18 AM

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

3 Feb 2006 7:42 AM

Cor Ligthert [MVP]

Simon,

I would use this method.

http://msdn2.microsoft.com/en-us/library/system.collections.arraylist.indexof.aspx

I hope this helps,

Cor

3 Feb 2006 10:00 AM

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

Show quoteHide quote

"Cor Ligthert [MVP]" <notmyfirstn***@planet.nl> wrote in message
news:%23A8ZAVJKGHA.1424@TK2MSFTNGP12.phx.gbl...
> Simon,
>
> I would use this method.
>
> http://msdn2.microsoft.com/en-us/library/system.collections.arraylist.indexof.aspx
>
> I hope this helps,
>
> Cor
>

3 Feb 2006 1:58 PM

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

3 Feb 2006 12:08 PM

Andrew Morton

Simon Says wrote:

> 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

3 Feb 2006 4:51 PM

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

Show quoteHide quote

"Andrew Morton" <a**@in-press.co.uk.invalid> wrote in message
news:OwcyRqLKGHA.528@TK2MSFTNGP12.phx.gbl...
> Simon Says wrote:
>> 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
>

6 Feb 2006 11:26 AM

Andrew Morton

> "Andrew Morton" wrote

>> Are A1 and A2 of trivial length?

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

7 Feb 2006 3:23 AM

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

Show quoteHide quote

"Andrew Morton" <a**@in-press.co.uk.invalid> wrote in message
news:e%23I27AxKGHA.2040@TK2MSFTNGP14.phx.gbl...
>> "Andrew Morton" wrote
>
>>> Are A1 and A2 of trivial length?
>
> 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
>

7 Feb 2006 9:12 AM

Andrew Morton

Simon Says wrote:

> 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

8 Feb 2006 2:16 AM

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.

Show quoteHide quote

"Andrew Morton" <a**@in-press.co.uk.invalid> wrote in message
news:uL5U2a8KGHA.2320@TK2MSFTNGP11.phx.gbl...
> Simon Says wrote:
>> 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
>

8 Feb 2006 1:51 PM

Andrew Morton

Simon Says wrote:

> 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

9 Feb 2006 2:59 AM

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

Show quoteHide quote

"Andrew Morton" <a**@in-press.co.uk.invalid> wrote in message
news:%239mCAbLLGHA.516@TK2MSFTNGP15.phx.gbl...
> Simon Says wrote:
>> 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
>