Removing duplicate BitArrays in an ArrayList

G

Guest

Hi,
I would like to add BitArrays to an ArrayList and then remove any duplicates
- can someone please help me forward. I seem to have (at leaset ;-) )2
problems/lack of understanding (see test code below):
(a)When adding BitArrays to the ArrayList and then looping through the
ArrayList I seem to access only the latest added BitArray and I'm not exactly
clear on best way to access each BItArray in the ArrayList

(b)When I try to remove duplicate BItArrays, I seem only to identify the
current index as being "the duplicate" (I am assuming IndexOf and the Equals
which it uses should function here).

Thanks in advance,
Vjeko

using System;
using System.Collections;
namespace RemoveDuplicateBitArrays
{
class Class1
{
static void Main(string[] args)
{
ArrayList arr = new ArrayList();
BitArray myBA1 = new BitArray( 4 );
myBA1.SetAll(false);

myBA1.Set(0,false);
myBA1.Set(1,false);
myBA1.Set(2,false);
myBA1.Set(3,true);
arr.Add(myBA1);

myBA1.SetAll(false);
myBA1.Set(0,false);
myBA1.Set(1,true);
myBA1.Set(2,false);
myBA1.Set(3,false);
arr.Add(myBA1);


i = 0;
foreach (BitArray x in arr)
{
Console.WriteLine(i++);
DisplayBitArray(x);
}

//Alternative way to access the BitArrays in the ArrayList
// for(int j=0; j<(arr.Count-1); j++)
// {
// Console.WriteLine("Array element is {0}",????); Not sure
how to
// access bits of bitarray here
// }

Console.ReadLine();
}//Main



public static void DisplayBitArray(IEnumerable myList)
{
int i = 0;
System.Collections.IEnumerator myEnumerator =
myList.GetEnumerator();
while ( myEnumerator.MoveNext() )
{
Console.WriteLine( "\t[{0}]:\t{1}", i++,
myEnumerator.Current );
Console.WriteLine();
}
}//DisplayBitArray

public static void RemoveDuplicateBitArraysinArrayList(ArrayList arr)
{
//Step through ArrayList such that
//BitArray element is taken and XOR with each element further down
//the ArrayList if result is false, remove it as it is a duplicate

int index;

for(int i=0; i<(arr.Count-1); i++)
{
index=arr.IndexOf(arr, i+1);
while( index>i )
{
arr.Remove(index);
if( i<(arr.Count-1) )
{
index=arr.IndexOf(arr, i+1);
}
else
{
index=-1;
}
}
}
} //RemoveDuplicateBitArraysinArrayList

}//Class1

}//namespace RemoveDuplicateBitArrays
 
N

Nicholas Paldino [.NET/C# MVP]

vbportal,

The problem is that you are adding the same bit array over and over
again. What you need to do is create a new bit array before you set the
values again, like so:

ArrayList arr = new ArrayList();
BitArray myBA1 = new BitArray( 4 );
myBA1.SetAll(false);

myBA1.Set(0,false);
myBA1.Set(1,false);
myBA1.Set(2,false);
myBA1.Set(3,true);
arr.Add(myBA1);

// Need to create a new one here, or you will add the same reference to the
array list.
myBA1 = new BitArray(4);
myBA1.SetAll(false);

// Set values normally.
myBA1.SetAll(false);
myBA1.Set(0,false);
myBA1.Set(1,true);
myBA1.Set(2,false);
myBA1.Set(3,false);
arr.Add(myBA1);

Hope this helps.


--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)

vbportal said:
Hi,
I would like to add BitArrays to an ArrayList and then remove any
duplicates
- can someone please help me forward. I seem to have (at leaset ;-) )2
problems/lack of understanding (see test code below):
(a)When adding BitArrays to the ArrayList and then looping through the
ArrayList I seem to access only the latest added BitArray and I'm not
exactly
clear on best way to access each BItArray in the ArrayList

(b)When I try to remove duplicate BItArrays, I seem only to identify the
current index as being "the duplicate" (I am assuming IndexOf and the
Equals
which it uses should function here).

Thanks in advance,
Vjeko

using System;
using System.Collections;
namespace RemoveDuplicateBitArrays
{
class Class1
{
static void Main(string[] args)
{
ArrayList arr = new ArrayList();
BitArray myBA1 = new BitArray( 4 );
myBA1.SetAll(false);

myBA1.Set(0,false);
myBA1.Set(1,false);
myBA1.Set(2,false);
myBA1.Set(3,true);
arr.Add(myBA1);

myBA1.SetAll(false);
myBA1.Set(0,false);
myBA1.Set(1,true);
myBA1.Set(2,false);
myBA1.Set(3,false);
arr.Add(myBA1);


i = 0;
foreach (BitArray x in arr)
{
Console.WriteLine(i++);
DisplayBitArray(x);
}

//Alternative way to access the BitArrays in the ArrayList
// for(int j=0; j<(arr.Count-1); j++)
// {
// Console.WriteLine("Array element is {0}",????); Not sure
how to
// access bits of bitarray here
// }

Console.ReadLine();
}//Main



public static void DisplayBitArray(IEnumerable myList)
{
int i = 0;
System.Collections.IEnumerator myEnumerator =
myList.GetEnumerator();
while ( myEnumerator.MoveNext() )
{
Console.WriteLine( "\t[{0}]:\t{1}", i++,
myEnumerator.Current );
Console.WriteLine();
}
}//DisplayBitArray

public static void RemoveDuplicateBitArraysinArrayList(ArrayList
arr)
{
//Step through ArrayList such that
//BitArray element is taken and XOR with each element further down
//the ArrayList if result is false, remove it as it is a duplicate

int index;

for(int i=0; i<(arr.Count-1); i++)
{
index=arr.IndexOf(arr, i+1);
while( index>i )
{
arr.Remove(index);
if( i<(arr.Count-1) )
{
index=arr.IndexOf(arr, i+1);
}
else
{
index=-1;
}
}
}
} //RemoveDuplicateBitArraysinArrayList

}//Class1

}//namespace RemoveDuplicateBitArrays
Click to expand...
 
G

Guest

Hi Nicholas - thanks for the answer - this sorted out my first problem.
I'm still not sure how to solve (b) i.e. for the removal of duplicate
BitArrays
(see subroutine RemoveDuplicateBitArrays below)

I pinched this code from the net - here I assume "index=arr.IndexOf(arr,
i+1);" will check for duplicate BitArrays (where as I read IndexOf uses
Equals for the equality check)starting at present ArrayList index and
stepping one ahead till end of ArrayList (duplicates are identified by
"index" and removed - but it doesn't work - any clue (I must admit I'm quite
new to C# and my debugging skills are far from good - but we have to start
somewhere ;-) ?

If it's not too much bother could you also indicate if there is any good
source of info how BitArrays fit in ArrayLists from a Collections perspective
- I seem to have a problem understanding how to address the BItArray bits /
how IEnumerator ties in (have checked quite a few books etc but haven't found
a satisfactory explanation.

Thanks,Vjeko

Nicholas Paldino said:
vbportal,

The problem is that you are adding the same bit array over and over
again. What you need to do is create a new bit array before you set the
values again, like so:

ArrayList arr = new ArrayList();
BitArray myBA1 = new BitArray( 4 );
myBA1.SetAll(false);

myBA1.Set(0,false);
myBA1.Set(1,false);
myBA1.Set(2,false);
myBA1.Set(3,true);
arr.Add(myBA1);

// Need to create a new one here, or you will add the same reference to the
array list.
myBA1 = new BitArray(4);
myBA1.SetAll(false);

// Set values normally.
myBA1.SetAll(false);
myBA1.Set(0,false);
myBA1.Set(1,true);
myBA1.Set(2,false);
myBA1.Set(3,false);
arr.Add(myBA1);

Hope this helps.


--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)

vbportal said:
Hi,
I would like to add BitArrays to an ArrayList and then remove any
duplicates
- can someone please help me forward. I seem to have (at leaset ;-) )2
problems/lack of understanding (see test code below):
(a)When adding BitArrays to the ArrayList and then looping through the
ArrayList I seem to access only the latest added BitArray and I'm not
exactly
clear on best way to access each BItArray in the ArrayList

(b)When I try to remove duplicate BItArrays, I seem only to identify the
current index as being "the duplicate" (I am assuming IndexOf and the
Equals
which it uses should function here).

Thanks in advance,
Vjeko

using System;
using System.Collections;
namespace RemoveDuplicateBitArrays
{
class Class1
{
static void Main(string[] args)
{
ArrayList arr = new ArrayList();
BitArray myBA1 = new BitArray( 4 );
myBA1.SetAll(false);

myBA1.Set(0,false);
myBA1.Set(1,false);
myBA1.Set(2,false);
myBA1.Set(3,true);
arr.Add(myBA1);

myBA1.SetAll(false);
myBA1.Set(0,false);
myBA1.Set(1,true);
myBA1.Set(2,false);
myBA1.Set(3,false);
arr.Add(myBA1);


i = 0;
foreach (BitArray x in arr)
{
Console.WriteLine(i++);
DisplayBitArray(x);
}

//Alternative way to access the BitArrays in the ArrayList
// for(int j=0; j<(arr.Count-1); j++)
// {
// Console.WriteLine("Array element is {0}",????); Not sure
how to
// access bits of bitarray here
// }

Console.ReadLine();
}//Main



public static void DisplayBitArray(IEnumerable myList)
{
int i = 0;
System.Collections.IEnumerator myEnumerator =
myList.GetEnumerator();
while ( myEnumerator.MoveNext() )
{
Console.WriteLine( "\t[{0}]:\t{1}", i++,
myEnumerator.Current );
Console.WriteLine();
}
}//DisplayBitArray

public static void RemoveDuplicateBitArraysinArrayList(ArrayList
arr)
{
//Step through ArrayList such that
//BitArray element is taken and XOR with each element further down
//the ArrayList if result is false, remove it as it is a duplicate

int index;

for(int i=0; i<(arr.Count-1); i++)
{
index=arr.IndexOf(arr, i+1);
while( index>i )
{
arr.Remove(index);
if( i<(arr.Count-1) )
{
index=arr.IndexOf(arr, i+1);
}
else
{
index=-1;
}
}
}
} //RemoveDuplicateBitArraysinArrayList

}//Class1

}//namespace RemoveDuplicateBitArrays
Click to expand...
Click to expand...
 
N

Nicholas Paldino [.NET/C# MVP]

Vjeko,

I don't know if I would cycle through all of the duplicate bit arrays
the way you are. Since the sizes of the bit arrays are all the same, you
can just place it in a format that is easier to compare.

Basically, since it is four bits, you can copy that to a byte array with
one element. Then, you can just compare the bytes for equality.


--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)

vbportal said:
Hi Nicholas - thanks for the answer - this sorted out my first problem.
I'm still not sure how to solve (b) i.e. for the removal of duplicate
BitArrays
(see subroutine RemoveDuplicateBitArrays below)

I pinched this code from the net - here I assume
"index=arr.IndexOf(arr,
i+1);" will check for duplicate BitArrays (where as I read IndexOf uses
Equals for the equality check)starting at present ArrayList index and
stepping one ahead till end of ArrayList (duplicates are identified by
"index" and removed - but it doesn't work - any clue (I must admit I'm
quite
new to C# and my debugging skills are far from good - but we have to start
somewhere ;-) ?

If it's not too much bother could you also indicate if there is any good
source of info how BitArrays fit in ArrayLists from a Collections
perspective
- I seem to have a problem understanding how to address the BItArray bits
/
how IEnumerator ties in (have checked quite a few books etc but haven't
found
a satisfactory explanation.

Thanks,Vjeko

Nicholas Paldino said:
vbportal,

The problem is that you are adding the same bit array over and over
again. What you need to do is create a new bit array before you set the
values again, like so:

ArrayList arr = new ArrayList();
BitArray myBA1 = new BitArray( 4 );
myBA1.SetAll(false);

myBA1.Set(0,false);
myBA1.Set(1,false);
myBA1.Set(2,false);
myBA1.Set(3,true);
arr.Add(myBA1);

// Need to create a new one here, or you will add the same reference to
the
array list.
myBA1 = new BitArray(4);
myBA1.SetAll(false);

// Set values normally.
myBA1.SetAll(false);
myBA1.Set(0,false);
myBA1.Set(1,true);
myBA1.Set(2,false);
myBA1.Set(3,false);
arr.Add(myBA1);

Hope this helps.


--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)

vbportal said:
Hi,
I would like to add BitArrays to an ArrayList and then remove any
duplicates
- can someone please help me forward. I seem to have (at leaset ;-) )2
problems/lack of understanding (see test code below):
(a)When adding BitArrays to the ArrayList and then looping through the
ArrayList I seem to access only the latest added BitArray and I'm not
exactly
clear on best way to access each BItArray in the ArrayList

(b)When I try to remove duplicate BItArrays, I seem only to identify
the
current index as being "the duplicate" (I am assuming IndexOf and the
Equals
which it uses should function here).

Thanks in advance,
Vjeko

using System;
using System.Collections;
namespace RemoveDuplicateBitArrays
{
class Class1
{
static void Main(string[] args)
{
ArrayList arr = new ArrayList();
BitArray myBA1 = new BitArray( 4 );
myBA1.SetAll(false);

myBA1.Set(0,false);
myBA1.Set(1,false);
myBA1.Set(2,false);
myBA1.Set(3,true);
arr.Add(myBA1);

myBA1.SetAll(false);
myBA1.Set(0,false);
myBA1.Set(1,true);
myBA1.Set(2,false);
myBA1.Set(3,false);
arr.Add(myBA1);


i = 0;
foreach (BitArray x in arr)
{
Console.WriteLine(i++);
DisplayBitArray(x);
}

//Alternative way to access the BitArrays in the ArrayList
// for(int j=0; j<(arr.Count-1); j++)
// {
// Console.WriteLine("Array element is {0}",????); Not
sure
how to
// access bits of bitarray here
// }

Console.ReadLine();
}//Main



public static void DisplayBitArray(IEnumerable myList)
{
int i = 0;
System.Collections.IEnumerator myEnumerator =
myList.GetEnumerator();
while ( myEnumerator.MoveNext() )
{
Console.WriteLine( "\t[{0}]:\t{1}", i++,
myEnumerator.Current );
Console.WriteLine();
}
}//DisplayBitArray

public static void RemoveDuplicateBitArraysinArrayList(ArrayList
arr)
{
//Step through ArrayList such that
//BitArray element is taken and XOR with each element further down
//the ArrayList if result is false, remove it as it is a duplicate

int index;

for(int i=0; i<(arr.Count-1); i++)
{
index=arr.IndexOf(arr, i+1);
while( index>i )
{
arr.Remove(index);
if( i<(arr.Count-1) )
{
index=arr.IndexOf(arr, i+1);
}
else
{
index=-1;
}
}
}
} //RemoveDuplicateBitArraysinArrayList

}//Class1

}//namespace RemoveDuplicateBitArrays
Click to expand...
Click to expand...
Click to expand...
 
G

Guest

Hi Nicholas,
The actual BitArrays I need to use are 50bits wide and I need to do a lot
of searches for specific bit patterns in other ArrayLists i.e. I thought
XORing BitArrays would be the fastest. I will consider your advice for the
final solution but could you please indicate if you have any ideas re:
problems identified in my last e-mail ?

Nicholas Paldino said:
Vjeko,

I don't know if I would cycle through all of the duplicate bit arrays
the way you are. Since the sizes of the bit arrays are all the same, you
can just place it in a format that is easier to compare.

Basically, since it is four bits, you can copy that to a byte array with
one element. Then, you can just compare the bytes for equality.


--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)

vbportal said:
Hi Nicholas - thanks for the answer - this sorted out my first problem.
I'm still not sure how to solve (b) i.e. for the removal of duplicate
BitArrays
(see subroutine RemoveDuplicateBitArrays below)

I pinched this code from the net - here I assume
"index=arr.IndexOf(arr,
i+1);" will check for duplicate BitArrays (where as I read IndexOf uses
Equals for the equality check)starting at present ArrayList index and
stepping one ahead till end of ArrayList (duplicates are identified by
"index" and removed - but it doesn't work - any clue (I must admit I'm
quite
new to C# and my debugging skills are far from good - but we have to start
somewhere ;-) ?

If it's not too much bother could you also indicate if there is any good
source of info how BitArrays fit in ArrayLists from a Collections
perspective
- I seem to have a problem understanding how to address the BItArray bits
/
how IEnumerator ties in (have checked quite a few books etc but haven't
found
a satisfactory explanation.

Thanks,Vjeko

Nicholas Paldino said:
vbportal,

The problem is that you are adding the same bit array over and over
again. What you need to do is create a new bit array before you set the
values again, like so:

ArrayList arr = new ArrayList();
BitArray myBA1 = new BitArray( 4 );
myBA1.SetAll(false);

myBA1.Set(0,false);
myBA1.Set(1,false);
myBA1.Set(2,false);
myBA1.Set(3,true);
arr.Add(myBA1);

// Need to create a new one here, or you will add the same reference to
the
array list.
myBA1 = new BitArray(4);
myBA1.SetAll(false);

// Set values normally.
myBA1.SetAll(false);
myBA1.Set(0,false);
myBA1.Set(1,true);
myBA1.Set(2,false);
myBA1.Set(3,false);
arr.Add(myBA1);

Hope this helps.


--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)

Hi,
I would like to add BitArrays to an ArrayList and then remove any
duplicates
- can someone please help me forward. I seem to have (at leaset ;-) )2
problems/lack of understanding (see test code below):
(a)When adding BitArrays to the ArrayList and then looping through the
ArrayList I seem to access only the latest added BitArray and I'm not
exactly
clear on best way to access each BItArray in the ArrayList

(b)When I try to remove duplicate BItArrays, I seem only to identify
the
current index as being "the duplicate" (I am assuming IndexOf and the
Equals
which it uses should function here).

Thanks in advance,
Vjeko

using System;
using System.Collections;
namespace RemoveDuplicateBitArrays
{
class Class1
{
static void Main(string[] args)
{
ArrayList arr = new ArrayList();
BitArray myBA1 = new BitArray( 4 );
myBA1.SetAll(false);

myBA1.Set(0,false);
myBA1.Set(1,false);
myBA1.Set(2,false);
myBA1.Set(3,true);
arr.Add(myBA1);

myBA1.SetAll(false);
myBA1.Set(0,false);
myBA1.Set(1,true);
myBA1.Set(2,false);
myBA1.Set(3,false);
arr.Add(myBA1);


i = 0;
foreach (BitArray x in arr)
{
Console.WriteLine(i++);
DisplayBitArray(x);
}

//Alternative way to access the BitArrays in the ArrayList
// for(int j=0; j<(arr.Count-1); j++)
// {
// Console.WriteLine("Array element is {0}",????); Not
sure
how to
// access bits of bitarray here
// }

Console.ReadLine();
}//Main



public static void DisplayBitArray(IEnumerable myList)
{
int i = 0;
System.Collections.IEnumerator myEnumerator =
myList.GetEnumerator();
while ( myEnumerator.MoveNext() )
{
Console.WriteLine( "\t[{0}]:\t{1}", i++,
myEnumerator.Current );
Console.WriteLine();
}
}//DisplayBitArray

public static void RemoveDuplicateBitArraysinArrayList(ArrayList
arr)
{
//Step through ArrayList such that
//BitArray element is taken and XOR with each element further down
//the ArrayList if result is false, remove it as it is a duplicate

int index;

for(int i=0; i<(arr.Count-1); i++)
{
index=arr.IndexOf(arr, i+1);
while( index>i )
{
arr.Remove(index);
if( i<(arr.Count-1) )
{
index=arr.IndexOf(arr, i+1);
}
else
{
index=-1;
}
}
}
} //RemoveDuplicateBitArraysinArrayList

}//Class1

}//namespace RemoveDuplicateBitArrays
Click to expand...
Click to expand...
Click to expand...
 
J

Jon Skeet [C# MVP]

vbportal said:
The actual BitArrays I need to use are 50bits wide and I need to do a lot
of searches for specific bit patterns in other ArrayLists i.e. I thought
XORing BitArrays would be the fastest. I will consider your advice for the
final solution but could you please indicate if you have any ideas re:
problems identified in my last e-mail ?
Click to expand...

If your bit arrays are only 50 bits wide, why not just use a long
instead? That way you can just compare the longs directly. If you need
the convenience of bit array, you could always write a struct which
contains a long and provides methods for access.
 
G

Guest

Hi Jon and Nicholas,
Thanks a lot for the input - I see that I have overlooked
some obvious alternative solutions and I will dig in these directions
but before doing so, I really want to see at least some working test code
using the idea of BitArrays - for the sake of learning/knowledge/experience
- right now it doesn't work and I don't know why - you know
how that feels. If possible, please give me some pointers towards the
solution to the problems described in my last mail.

Thanks,Vjeko
 
J

Jon Skeet [C# MVP]

vbportal said:
Hi Jon and Nicholas,
Thanks a lot for the input - I see that I have overlooked
some obvious alternative solutions and I will dig in these directions
but before doing so, I really want to see at least some working test code
using the idea of BitArrays - for the sake of learning/knowledge/experience
- right now it doesn't work and I don't know why - you know
how that feels. If possible, please give me some pointers towards the
solution to the problems described in my last mail.
Click to expand...

Which problems, exactly? I'm not exactly sure which bit still needs
sorting out. One thing you might think of doing is deriving a class
from BitArray and overriding Equals and GetHashCode - that might make
the code doing the comparisons a bit easier.
 
G

Guest

Hi Jon,
The method "RemoveDuplicateBitArraysinArrayList" is not working (See first
post for test code I wrote)

Problem:
(a)"IndexOf" doesn't seem to be doing "what I expect" or maybe I'm not
addressing the BitArrays correctly (I thought BitArray was "inbuilt" so
Equals etc should work & IndexOf should work straight off)

(b)AND/OR your idea about deriving a class from BitArray
to get Equals working has something to do with it if I assumed wrong for (a)
but I'm afraid I'm not sure how to proceed.
 
J

Jon Skeet [C# MVP]

vbportal said:
The method "RemoveDuplicateBitArraysinArrayList" is not working (See first
post for test code I wrote)

Problem:
(a)"IndexOf" doesn't seem to be doing "what I expect" or maybe I'm not
addressing the BitArrays correctly (I thought BitArray was "inbuilt" so
Equals etc should work & IndexOf should work straight off)
Click to expand...

No - BitArray doesn't override Equals, which is why it's not working.
(Admittedly it's slightly odd that it doesn't - it could do a rather
more efficient job of it than you'll be able to.)
(b)AND/OR your idea about deriving a class from BitArray
to get Equals working has something to do with it if I assumed wrong for (a)
but I'm afraid I'm not sure how to proceed.
Click to expand...

Just derive your own class from BitArray which overrides Equals and
GetHashCode. Then you need to make sure you use that everywhere instead
of BitArray.
 
G

Guest

Hello,
You can't derive from BitArray it is a final class.

here is a way to compare 2 bitarrays:

public static bool CompareEqual(BitArray bita, BitArray bitb) {
int [] resa = new int [(bita.Length / 32) + (((bita.Length % 32) == 0) ? 0
: 1)];
int [] resb = new int [(bitb.Length / 32) + (((bitb.Length % 32) == 0) ? 0
: 1)];
bita.CopyTo(resa, 0);
bitb.CopyTo(resb, 0);
return CompareEqual(0, resa, resb);
}

// recursive call
public static bool CompareEqual(int index, int [] inta, int [] intb) {
if (index >= inta.Length)
return true;
if (inta[index] != intb[index])
return false;
index++;
return CompareEqual(index, inta, intb);
}
 

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

Similar Threads

Newbie: BitArray initilization 2
copying an arraylist of objects into an array of the objects themselves. 5
Passing an arraylist which contains a struct which contains an arraylist 3
ArrayList and its Insert method 5
what is the point when the ArrayList return an int 3
ArrayList help 2
about Collections 1
How to add object in an ArrayList in a foreach loop 1

Top