// Original Author: Christian Bender

// Class: BitArray

//

// implements IComparable, ICloneable, IEnumerator, IEnumerable

//

// This class implements a bit-array and provides some

// useful functions/operations to deal with this type of

// data structure. You see a overview about the functionality, below.

//

//

// Overview

//

// Constructor (N : int)

// The constructor receives a length (N) of the to create bit-field.

//

// Constructor (sequence : string)

// setups the array with the input sequence.

// assumes: the sequence may only be allowed contains onese or zeros.

//

// Constructor (bits : bool[] )

// setups the bit-field with the input array.

//

// Compile(sequence : string)

// compiles a string sequence of 0's and 1's in the inner structure.

// assumes: the sequence may only be allowed contains onese or zeros.

//

// Compile (number : int)

// compiles a positive integer number in the inner data structure.

//

// Compile (number : long)

// compiles a positive long integer number in the inner data structure.

//

// ToString ()

// returns a string representation of the inner structure.

// The returned string is a sequence of 0's and 1's.

//

// Length : int

// Is a property that returns the length of the bit-field.

//

// Indexer : bool

// indexer for selecting the individual bits of the bit array.

//

// NumberOfOneBits() : int

// returns the number of One-bits.

//

// NumberOfZeroBits() : int

// returns the number of Zero-Bits.

//

// EvenParity() : bool

// returns true if parity is even, otherwise false.

//

// OddParity() : bool

// returns true if parity is odd, otherwise false.

//

// ToInt64() : long

// returns a long integer representation of the bit-array.

// assumes: the bit-array length must been smaller or equal to 64 bit.

//

// ToInt32() : int

// returns a integer representation of the bit-array.

// assumes: the bit-array length must been smaller or equal to 32 bit.

//

// ResetField() : void

// sets all bits on false.

//

// SetAll(flag : bool) : void

// sets all bits on the value of the flag.

//

// GetHashCode() : int

// returns hash-code (ToInt32())

//

// Equals (other : Object) : bool

// returns true if there inputs are equal otherwise false.

// assumes: the input bit-arrays must have same length.

//

// CompareTo (other : Object) : int (interface IComparable)

// output: 0 - if the bit-arrays a equal.

// -1 - if this bit-array is smaller.

// 1 - if this bit-array is greater.

// assumes: bit-array lentgh must been smaller or equal to 64 bit

//

// Clone () : object

// returns a copy of this bit-array

//

// Current : object

// returns the current selected bit.

//

// MoveNext() : bool

// purpose: increases the position of the enumerator

// returns true if 'position' successful increased otherwise false.

//

// Reset() : void

// resets the position of the enumerator.

//

// GetEnumerator() : IEnumerator

// returns a enumerator for this BitArray-object.

//

// Operations:

//

// & bitwise AND

// | bitwise OR

// ~ bitwise NOT

// >> bitwise shift right

// >> bitwise shift left

// ^ bitwise XOR

//

// Each operation (above) returns a new BitArray-object.

//

// == equal operator. : bool

// returns true if there inputs are equal otherwise false.

// assumes: the input bit-arrays must have same length.

//

// != not-equal operator : bool

// returns true if there inputs aren't equal otherwise false.

// assumes: the input bit-arrays must have same length.

using System.Collections;

namespace DataStructures;

/// <summary>

/// This class implements a bit-array and provides some

/// useful functions/operations to deal with this type of

/// data structure.

/// </summary>

public sealed class BitArray : ICloneable, IEnumerator<bool>, IEnumerable<bool>

{

private readonly bool[] field; // the actual bit-field

private int position = -1; // position for enumerator

/// <summary>

/// Initializes a new instance of the <see cref="BitArray" /> class.

/// setups the array with false-values.

/// </summary>

/// <param name="n">length of the array.</param>

public BitArray(int n)

{

field = n <= 0 ? new bool[0] : new bool[n];

}

/// <summary>

/// Initializes a new instance of the <see cref="BitArray" /> class.

/// Setups the array with the input sequence.

/// purpose: Setups the array with the input sequence.

/// assumes: sequence must been greater or equal to 1.

/// the sequence may only contain ones or zeros.

/// </summary>

/// <param name="sequence">A string sequence of 0's and 1's.</param>

public BitArray(string sequence)

{

// precondition I

if (sequence.Length <= 0)

{

throw new ArgumentException("Sequence must been greater than or equal to 1");

}

// precondition II

ThrowIfSequenceIsInvalid(sequence);

field = new bool[sequence.Length];

Compile(sequence);

}

/// <summary>

/// Initializes a new instance of the <see cref="BitArray" /> class.

/// Setups the bit-array with the input array.

/// </summary>

/// <param name="bits">A boolean array of bits.</param>

public BitArray(bool[] bits) => field = bits;

/// <summary>

/// Gets the length of the current bit array.

/// </summary>

private int Length => field.Length;

/// <summary>

/// Gets element given an offset.

/// </summary>

/// <param name="offset">Position.</param>

/// <returns>Element on array.</returns>

public bool this[int offset]

{

get => field[offset];

private set => field[offset] = value;

}

/// <summary>

/// Returns a copy of the current bit-array.

/// </summary>

/// <returns>Bit-array clone.</returns>

public object Clone()

{

var theClone = new BitArray(Length);

for (var i = 0; i < Length; i++)

{

theClone[i] = field[i];

}

return theClone;

}

/// <summary>

/// Gets a enumerator for this BitArray-Object.

/// </summary>

/// <returns>Returns a enumerator for this BitArray-Object.</returns>

public IEnumerator<bool> GetEnumerator() => this;

/// <summary>

/// Gets a enumerator for this BitArray-Object.

/// </summary>

/// <returns>Returns a enumerator for this BitArray-Object.</returns>

IEnumerator IEnumerable.GetEnumerator() => this;

/// <summary>

/// Gets a value indicating whether the current bit of the array is set.

/// </summary>

public bool Current => field[position];

/// <summary>

/// Gets a value indicating whether the current bit of the array is set.

/// </summary>

object IEnumerator.Current => field[position];

/// <summary>

/// MoveNext (for interface IEnumerator).

/// </summary>

/// <returns>Returns True if 'position' successful increased; False otherwise.</returns>

public bool MoveNext()

{

if (position + 1 >= field.Length)

{

return false;

}

position++;

return true;

}

/// <summary>

/// Resets the position of the enumerator.

/// Reset (for interface IEnumerator).

/// </summary>

public void Reset() => position = -1;

/// <summary>

/// Disposes object, nothing to dispose here though.

/// </summary>

public void Dispose()

{

// Done

}

/// <summary>

/// Returns a bit-array that represents the bit by bit AND (&amp;).

/// Assumes arrays have the same length.

/// </summary>

/// <param name="one">First bit-array.</param>

/// <param name="two">Second bit-array.</param>

/// <returns>bit-array.</returns>

public static BitArray operator &(BitArray one, BitArray two)

{

var sequence1 = one.ToString();

var sequence2 = two.ToString();

var result = new StringBuilder();

var tmp = new StringBuilder();

// for scaling of same length.

if (one.Length != two.Length)

{

int difference;

if (one.Length > two.Length)

{

// one is greater

difference = one.Length - two.Length;

// fills up with 0's

for (var i = 0; i < difference; i++)

{

tmp.Append('0');

}

tmp.Append(two);

sequence2 = tmp.ToString();

}

else

{

// two is greater

difference = two.Length - one.Length;

// fills up with 0's

for (var i = 0; i < difference; i++)

{

tmp.Append('0');

}

tmp.Append(one);

sequence1 = tmp.ToString();

}

} // end scaling

var len = one.Length > two.Length ? one.Length : two.Length;

var ans = new BitArray(len);

for (var i = 0; i < one.Length; i++)

{

result.Append(sequence1[i].Equals('1') && sequence2[i].Equals('1') ? '1' : '0');

}

ans.Compile(result.ToString().Trim());

return ans;

}

/// <summary>

/// Returns a bit-array that represents the bit by bit OR.

/// Assumes arrays have the same length.

/// </summary>

/// <param name="one">First bit-array.</param>

/// <param name="two">Second bit-array.</param>

/// <returns>bit-array that represents the bit by bit OR.</returns>

public static BitArray operator |(BitArray one, BitArray two)

{

var sequence1 = one.ToString();

var sequence2 = two.ToString();

var result = new StringBuilder();

// for scaling of same length.

if (one.Length != two.Length)

{

var tmp = new StringBuilder();

int difference;

if (one.Length > two.Length)

{

// one is greater

difference = one.Length - two.Length;

// fills up with 0's

tmp.Append('0', difference);

tmp.Append(two.ToString());

sequence2 = tmp.ToString();

}

else

{

// two is greater

difference = two.Length - one.Length;

// fills up with 0's

tmp.Append('0', difference);

tmp.Append(one.ToString());

sequence1 = tmp.ToString();

}

} // end scaling

var len = one.Length > two.Length ? one.Length : two.Length;

var ans = new BitArray(len);

for (var i = 0; i < len; i++)

{

result.Append(sequence1[i].Equals('0') && sequence2[i].Equals('0') ? '0' : '1');

}

ans.Compile(result.ToString());

return ans;

}

/// <summary>

/// Returns a bit-array that represents the operator ~ (NOT).

/// Assumes arrays have the same length.

/// </summary>

/// <param name="one">Bit-array.</param>

/// <returns>bitwise not.</returns>

public static BitArray operator ~(BitArray one)

{

var ans = new BitArray(one.Length);

var sequence = one.ToString();

var result = new StringBuilder(sequence.Length);

foreach (var ch in sequence)

{

result.Append(ch == '1' ? '0' : '1');

}

ans.Compile(result.ToString());

return ans;

}

/// <summary>

/// Returns a bit-array that represents bitwise shift left (&gt;&gt;).

/// Assumes arrays have the same length.

/// </summary>

/// <param name="other">Bit-array.</param>

/// <param name="n">Number of bits.</param>

/// <returns>Bitwise shifted BitArray.</returns>

public static BitArray operator <<(BitArray other, int n)

{

var ans = new BitArray(other.Length + n);

// actual shifting process

for (var i = 0; i < other.Length; i++)

{

ans[i] = other[i];

}

return ans;

}

/// <summary>

/// Returns a bit-array that represents the bit by bit XOR.

/// Assumes arrays have the same length.

/// </summary>

/// <param name="one">First bit-array.</param>

/// <param name="two">Second bit-array.</param>

/// <returns>bit-array.</returns>

public static BitArray operator ^(BitArray one, BitArray two)

{

var sequence1 = one.ToString();

var sequence2 = two.ToString();

// for scaling of same length.

if (one.Length != two.Length)

{

var tmp = new StringBuilder();

int difference;

if (one.Length > two.Length)

{

// one is greater

difference = one.Length - two.Length;

// fills up with 0's

tmp.Append('0', difference);

tmp.Append(two.ToString());

sequence2 = tmp.ToString();

}

else

{

// two is greater

difference = two.Length - one.Length;

// fills up with 0's

tmp.Append('0', difference);

tmp.Append(one.ToString());

sequence1 = tmp.ToString();

}

} // end scaling

var len = one.Length > two.Length ? one.Length : two.Length;

var ans = new BitArray(len);

var sb = new StringBuilder(len);

for (var i = 0; i < len; i++)

{

sb.Append(sequence1[i] == sequence2[i] ? '0' : '1');

}

ans.Compile(sb.ToString());

return ans;

}

/// <summary>

/// Returns a bit-array that represents bitwise shift right (>>).

/// Assumes arrays have the same length.

/// </summary>

/// <param name="other">Bit-array.</param>

/// <param name="n">Number of bits.</param>

/// <returns>Bitwise shifted BitArray.</returns>

public static BitArray operator >>(BitArray other, int n)

{

var ans = new BitArray(other.Length - n);

// actual shifting process.

for (var i = 0; i < other.Length - n; i++)

{

ans[i] = other[i];

}

return ans;

}

/// <summary>

/// Checks if both arrays are == (equal).

/// The input assumes arrays have the same length.

/// </summary>

/// <param name="one">First bit-array.</param>

/// <param name="two">Second bit-array.</param>

/// <returns>Returns True if there inputs are equal; False otherwise.</returns>

public static bool operator ==(BitArray one, BitArray two)

{

if (ReferenceEquals(one, two))

{

return true;

}

if (one.Length != two.Length)

{

return false;

}

var status = true;

for (var i = 0; i < one.Length; i++)

{

if (one[i] != two[i])

{

status = false;

break;

}

}

return status;

}

/// <summary>

/// Checks if both arrays are != (not-equal).

/// The input assumes arrays have the same length.

/// </summary>

/// <param name="one">First bit-array.</param>

/// <param name="two">Second bit-array.</param>

/// <returns>Returns True if there inputs aren't equal; False otherwise.</returns>

public static bool operator !=(BitArray one, BitArray two) => !(one == two);

/// <summary>

/// Compiles the binary sequence into the inner data structure.

/// The sequence must have the same length, as the bit-array.

/// The sequence may only be allowed contains ones or zeros.

/// </summary>

/// <param name="sequence">A string sequence of 0's and 1's.</param>

public void Compile(string sequence)

{

// precondition I

if (sequence.Length > field.Length)

{

throw new ArgumentException($"{nameof(sequence)} must be not longer than the bit array length");

}

// precondition II

ThrowIfSequenceIsInvalid(sequence);

// for appropriate scaling

if (sequence.Length < field.Length)

{

var difference = field.Length - sequence.Length;

sequence = new string('0', difference) + sequence;

}

// actual compile procedure.

for (var i = 0; i < sequence.Length; i++)

{

field[i] = sequence[i] == '1';

}

}

/// <summary>

/// Compiles integer number into the inner data structure.

/// Assumes: the number must have the same bit length.

/// </summary>

/// <param name="number">A positive integer number.</param>

public void Compile(int number)

{

// precondition I

if (number <= 0)

{

throw new ArgumentException($"{nameof(number)} must be positive");

}

// converts to binary representation

var binaryNumber = Convert.ToString(number, 2);

// precondition II

if (binaryNumber.Length > field.Length)

{

throw new ArgumentException("Provided number is too big");

}

// for appropriate scaling

if (binaryNumber.Length < field.Length)

{

var difference = field.Length - binaryNumber.Length;

binaryNumber = new string('0', difference) + binaryNumber;

}

// actual compile procedure.

for (var i = 0; i < binaryNumber.Length; i++)

{

field[i] = binaryNumber[i] == '1';

}

}

/// <summary>

/// Compiles integer number into the inner data structure.

/// The number must have the same bit length.

/// </summary>

/// <param name="number">A positive long integer number.</param>

public void Compile(long number)

{

// precondition I

if (number <= 0)

{

throw new ArgumentException($"{nameof(number)} must be positive");

}

// converts to binary representation

var binaryNumber = Convert.ToString(number, 2);

// precondition II

if (binaryNumber.Length > field.Length)

{

throw new ArgumentException("Provided number is too big");

}

// for appropriate scaling

if (binaryNumber.Length < field.Length)

{

var difference = field.Length - binaryNumber.Length;

binaryNumber = new string('0', difference) + binaryNumber;

}

// actual compile procedure.

for (var i = 0; i < binaryNumber.Length; i++)

{

field[i] = binaryNumber[i] == '1';

}

}

/// <summary>

/// Is the opposit of the Compile(...) method.

/// </summary>

/// <returns>Returns a string representation of the inner data structure.</returns>

public override string ToString()

{

// creates return-string

return field.Aggregate(string.Empty, (current, t) => current + (t ? "1" : "0"));

}

/// <summary>

/// Gets the number of one-bits in the field.

/// </summary>

/// <returns>quantity of bits in current bit-array.</returns>

public int NumberOfOneBits()

{

// counting one-bits.

return field.Count(bit => bit);

}

/// <summary>

/// Gets the number of zero-bits in the field.

/// </summary>

/// <returns>quantity of bits.</returns>

public int NumberOfZeroBits()

{

// counting zero-bits

return field.Count(bit => !bit);

}

/// <summary>

/// To check for even parity.

/// </summary>

/// <returns>Returns True if parity is even; False otherwise.</returns>

public bool EvenParity() => NumberOfOneBits() % 2 == 0;

/// <summary>

/// To check for odd parity.

/// </summary>

/// <returns>Returns True if parity is odd; False otherwise.</returns>

public bool OddParity() => NumberOfOneBits() % 2 != 0;

/// <summary>

/// Returns a long integer representation of the bit-array.

/// Assumes the bit-array length must been smaller or equal to 64 bit.

/// </summary>

/// <returns>Long integer array.</returns>

public long ToInt64()

{

// Precondition

if (field.Length > 64)

{

throw new InvalidOperationException("Value is too big to fit into Int64");

}

var sequence = ToString();

return Convert.ToInt64(sequence, 2);

}

/// <summary>

/// Returns a long integer representation of the bit-array.

/// Assumes the bit-array length must been smaller or equal to 32 bit.

/// </summary>

/// <returns>integer array.</returns>

public int ToInt32()

{

// Precondition

if (field.Length > 32)

{

throw new InvalidOperationException("Value is too big to fit into Int32");

}

var sequence = ToString();

return Convert.ToInt32(sequence, 2);

}

/// <summary>

/// Sets all bits on false.

/// </summary>

public void ResetField()

{

for (var i = 0; i < field.Length; i++)

{

field[i] = false;

}

}

/// <summary>

/// Sets all bits on the value of the flag.

/// </summary>

/// <param name="flag">Bollean flag (false-true).</param>

public void SetAll(bool flag)

{

for (var i = 0; i < field.Length; i++)

{

field[i] = flag;

}

}

/// <summary>

/// Checks if bit-array are equal.

/// Assumes the input bit-arrays must have same length.

/// </summary>

/// <param name="obj">Bit-array object.</param>

/// <returns>Returns true if there inputs are equal otherwise false.</returns>

public override bool Equals(object? obj)

{

if (obj is null)

{

return false;

}

var otherBitArray = (BitArray)obj;

if (Length != otherBitArray.Length)

{

return false;

}

for (var i = 0; i < Length; i++)

{

if (field[i] != otherBitArray[i])

{

return false;

}

}

return true;

}

/// <summary>

/// Gets has-code of bit-array.

/// Assumes bit-array length must been smaller or equal to 32.

/// </summary>

/// <returns>hash-code for this BitArray instance.</returns>

public override int GetHashCode() => ToInt32();

private static void ThrowIfSequenceIsInvalid(string sequence)

{

if (!Match(sequence))

{

throw new ArgumentException("The sequence may only contain ones or zeros");

}

}

/// <summary>

/// Utility method for checking a given sequence contains only zeros and ones.

/// This method will used in Constructor (sequence : string) and Compile(sequence : string).

/// </summary>

/// <param name="sequence">String sequence.</param>

/// <returns>returns True if sequence contains only zeros and ones; False otherwise.</returns>

private static bool Match(string sequence) => sequence.All(ch => ch == '0' || ch == '1');

}