Instantly share code, notes, and snippets.

# NightOwl888/BitSet.cs Last active Jan 16, 2020

C# port of the java.util.BitSet class
public override int GetHashCode()
/// {
///   long h = 1234;
///   for (int i = bits.length-1; i >= 0; i--)
///   {
///     h ^= bits[i] * (i + 1);
///   }
///
///   return (int)((h >> 32) ^ h);
/// }
/// /// Note that the hash code values changes, if the set is changed. ///
/// the hash code value for this bit set. public override int GetHashCode() { long h = 1234; for (int i = bits.Length; i > 0; ) h ^= i * bits[--i]; return (int) ((h >> 32) ^ h); } /// /// Returns true if the specified BitSet and this one share at least one /// common true bit. /// /// the set to check for intersection /// true if the sets intersect public bool Intersects(BitSet set) { int i = Math.Min(bits.Length, set.bits.Length); while (--i >= 0) { if ((bits[i] & set.bits[i]) != 0) return true; } return false; } /// /// Returns true if this set contains no true bits. /// /// true if all bits are false public bool IsEmpty() { for (int i = bits.Length - 1; i >= 0; i--) { if (bits[i] != 0) return false; } return true; } /// /// Gets the logical number of bits actually used by this bit /// set. It returns the index of the highest set bit plus one. /// Note that this method doesn't return the number of set bits. /// /// Returns the index of the highest set bit plus one. /// public int Length { get { // Set i to highest index that contains a non-zero value. int i; for (i = bits.Length - 1; i >= 0 && bits[i] == 0; --i){} // if i < 0 all bits are cleared. if (i < 0) return 0; // Now determine the exact length. long b = bits[i]; int len = (i + 1) * 64; // b >= 0 checks if the highest bit is zero. while (b >= 0) { --len; b <<= 1; } return len; } } /// /// Returns the index of the next false bit, from the specified bit /// (inclusive). /// /// the start location /// the first false bit public int NextClearBit(int from) { int offset = from >> 6; long mask = 1L << from; while (offset < bits.Length) { long h = bits[offset]; do { if ((h & mask) == 0) return from; mask <<= 1; from++; } while (mask != 0); mask = 1; offset++; } return from; } /// /// Returns the index of the next true bit, from the specified bit /// (inclusive). If there is none, -1 is returned. You can iterate over /// all true bits with this loop:
/// ///
for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1))
/// {
///   // operate on i here
/// }
///
///
/// the start location /// the first true bit, or -1 public int NextSetBit(int from) { int offset = from >> 6; long mask = 1L << from; while (offset < bits.Length) { long h = bits[offset]; do { if ((h & mask) != 0) return from; mask <<= 1; from++; } while (mask != 0); mask = 1; offset++; } return -1; } /// /// Performs the logical OR operation on this bit set and the /// given set. This means it builds the union /// of the two sets. The result is stored into this bit set, which /// grows as necessary. /// /// the second bit set public void Or(BitSet bs) { Ensure(bs.bits.Length - 1); for (int i = bs.bits.Length - 1; i >= 0; i--) bits[i] |= bs.bits[i]; } /// /// Add the integer bitIndex to this set. That is /// the corresponding bit is set to true. If the index was already in /// the set, this method does nothing. The size of this structure /// is automatically increased as necessary. /// /// a non-negative integer. public void Set(int pos) { int offset = pos >> 6; Ensure(offset); bits[offset] |= 1L << pos; } /// /// Sets the bit at the given index to the specified value. The size of /// this structure is automatically increased as necessary. /// /// the position to set /// the value to set it to public void Set(int index, bool value) { if (value) this.Set(index); else this.Clear(index); } /// /// Sets the bits between from (inclusive) and to (exclusive) to true. /// /// the start range (inclusive) /// the end range (exclusive) public void Set(int from, int to) { if (from < 0 || from > to) throw new ArgumentOutOfRangeException(); if (from == to) return; uint lo_offset = (uint)from >> 6; uint hi_offset = (uint)to >> 6; Ensure((int)hi_offset); if (lo_offset == hi_offset) { bits[hi_offset] |= (-1L << from) & ((1L << to) - 1); return; } bits[lo_offset] |= -1L << from; bits[hi_offset] |= (1L << to) - 1; for (int i = (int)lo_offset + 1; i < hi_offset; i++) bits[i] = -1; } /// /// Sets the bits between from (inclusive) and to (exclusive) to the /// specified value. /// /// the start range (inclusive) /// the end range (exclusive) /// the value to set it to public void Set(int from, int to, bool value) { if (value) this.Set(from, to); else this.Clear(from, to); } /// /// Returns the number of bits actually used by this bit set. Note /// that this method doesn't return the number of set bits, and that /// future requests for larger bits will make this automatically grow. /// /// Returns the number of bits currently used. /// public int Size { get { return bits.Length * 64; } } /// /// Returns the string representation of this bit set. This /// consists of a comma separated list of the integers in this set /// surrounded by curly braces. There is a space after each comma. /// A sample string is thus "{1, 3, 53}". /// /// the string representation. public override string ToString() { var r = new StringBuilder("{"); bool first = true; for (int i = 0; i < bits.Length; ++i) { long bit = 1; long word = bits[i]; if (word == 0) continue; for (int j = 0; j < 64; ++j) { if ((word & bit) != 0) { if (!first) r.Append(", "); r.Append(64 * i + j); first = false; } bit <<= 1; } } return r.Append("}").ToString(); } /// /// Performs the logical XOR operation on this bit set and the /// given set. This means it builds the symmetric /// remainder of the two sets (the elements that are in one set, /// but not in the other). The result is stored into this bit set, /// which grows as necessary. /// /// the second bit set public void XOr(BitSet bs) { Ensure(bs.bits.Length - 1); for (int i = bs.bits.Length - 1; i >= 0; i--) bits[i] ^= bs.bits[i]; } /// /// Make sure the vector is big enough. /// /// the size needed for the bits array private void Ensure(int lastElt) { if (lastElt >= bits.Length) { long[] nd = new long[lastElt + 1]; Array.Copy(bits, 0, nd, 0, bits.Length); bits = nd; } } // This is used by EnumSet for efficiency. public bool ContainsAll(BitSet other) { for (int i = other.bits.Length - 1; i >= 0; i--) { if ((bits[i] & other.bits[i]) != other.bits[i]) return false; } return true; } } }
 namespace Util { using System; using System.IO; using System.Runtime.Serialization; using System.Runtime.Serialization.Formatters.Binary; /// /// Reference Article http://www.codeproject.com/KB/tips/SerializedObjectCloner.aspx /// Provides a method for performing a deep copy of an object. /// Binary Serialization is used to perform the copy. /// public static class ObjectCopier { /// /// Perform a deep Copy of the object. /// /// The type of object being copied. /// The object instance to copy. /// The copied object. public static T Clone(T source) { if (!typeof(T).IsSerializable) { throw new ArgumentException("The type must be serializable.", "source"); } // Don't serialize a null object, simply return the default for that object if (Object.ReferenceEquals(source, null)) { return default(T); } IFormatter formatter = new BinaryFormatter(); Stream stream = new MemoryStream(); using (stream) { formatter.Serialize(stream, source); stream.Seek(0, SeekOrigin.Begin); return (T)formatter.Deserialize(stream); } } } }