using System;
using System.Collections.Generic;
using System.IO;
namespace miew.BitArray
{
using String = System.String;
public class BitArr : IEquatable<BitArr>
{
const int IgnoreHintThreshold = 15;
const int bits_per_UInt64 = sizeof(UInt64) * 8;
const int bits_per_byte = sizeof(byte) * 8;
const int idx_mask = 0x0000003F;
const int idx_shift = 6;
// for hash code
const int NotCalculated = -1;
readonly UInt64[] m_arr;
readonly int m_c_bits;
readonly int m_c_qw;
readonly int m_c_dist;
int hash_code = NotCalculated;
public BitArr(int c_bits)
{
m_c_bits = c_bits;
m_c_qw = (c_bits / bits_per_UInt64) + 1;
m_c_dist = (m_c_qw / bits_per_UInt64) + 1;
m_arr = new UInt64[m_c_qw + m_c_dist];
}
public BitArr(BitArr arg)
: this(arg.m_c_bits)
{
this.CopyFrom(arg);
}
public void CopyFrom(BitArr arg)
{
#if DEBUG
if (m_c_bits != arg.m_c_bits)
throw new ArgumentException();
#endif
arg.m_arr.CopyTo(this.m_arr, 0);
this.hash_code = arg.hash_code;
}
public BitArr(int c_bits, BinaryReader br)
: this(c_bits)
{
for (int i = 0; i < m_c_qw + m_c_dist; i++)
m_arr[i] = br.ReadUInt64();
}
public void Write(BinaryWriter bw)
{
for (int i = 0; i < m_c_qw + m_c_dist; i++)
bw.Write(m_arr[i]);
}
public int Count { get { return m_c_bits; } }
public bool this[int idx]
{
get
{
if (idx >= m_c_bits)
throw new IndexOutOfRangeException();
int b_i = idx / bits_per_UInt64;
idx -= b_i * bits_per_UInt64;
return (m_arr[b_i] & ((UInt64)1 << idx)) > 0;
}
set
{
if (idx >= m_c_bits)
throw new IndexOutOfRangeException();
int b_i = idx >> idx_shift;
if (value)
{
if ((m_arr[b_i] |= ((UInt64)1 << (idx & idx_mask))) > 0)
{
int z = m_c_qw + (b_i >> idx_shift);
m_arr[z] |= ((UInt64)1 << (b_i & idx_mask));
}
}
else
{
if ((m_arr[b_i] &= ~((UInt64)1 << (idx & idx_mask))) == 0)
{
int z = m_c_qw + (b_i >> idx_shift);
m_arr[z] &= ~((UInt64)1 << (b_i & idx_mask));
}
}
hash_code = NotCalculated;
//Check();
}
}
public void SetAll()
{
int i = 0;
/// set all bits
while (i < m_c_qw - 1)
m_arr[i++] = 0xFFFFFFFFFFFFFFFF;
m_arr[i++] = (0xFFFFFFFFFFFFFFFF >> (bits_per_UInt64 - (m_c_bits & idx_mask)));
/// set all distilled bits
while (i < m_c_qw + m_c_dist - 1)
m_arr[i++] = 0xFFFFFFFFFFFFFFFF;
m_arr[i] = (0xFFFFFFFFFFFFFFFF >> (bits_per_UInt64 - (m_c_qw & idx_mask)));
hash_code = NotCalculated;
}
public static BitArr operator ~(BitArr arg)
{
#if CHECK_CBITS
if (arg1.m_c_bits != arg2.m_c_bits)
throw new ArgumentException();
#endif
BitArr ret = new BitArr(arg.m_c_bits);
int c_qw = ret.m_c_qw;
UInt64 m = 1;
for (int i = 0; i < c_qw; i++)
{
if ((ret.m_arr[i] = ~arg.m_arr[i]) != 0)
{
int z = c_qw + (i >> idx_shift);
ret.m_arr[z] |= m;
}
if ((m <<= 1) == 0)
m = 1;
}
//ret.Check();
return ret;
}
public static BitArr operator &(BitArr arg1, BitArr arg2)
{
#if CHECK_CBITS
if (arg1.m_c_bits != arg2.m_c_bits)
throw new ArgumentException();
#endif
BitArr ret = new BitArr(arg1.m_c_bits);
int c_qw = ret.m_c_qw;
UInt64 d = 0;
UInt64 di = 1;
for (int i = 0; i < c_qw; i++)
{
if ((ret.m_arr[i] = arg1.m_arr[i] & arg2.m_arr[i]) > 0)
d |= di;
if ((di <<= 1) == 0)
{
ret.m_arr[c_qw + (i >> idx_shift)] = d;
d = 0;
di = 1;
}
}
ret.m_arr[c_qw + ((c_qw - 1) >> idx_shift)] = d;
//ret.Check();
return ret;
}
public BitArr AndWithHash(BitArr arg)
{
#if CHECK_CBITS
if (this.m_c_bits != arg2.m_c_bits)
throw new ArgumentException();
#endif
BitArr ret = new BitArr(m_c_bits);
int c_qw = ret.m_c_qw;
UInt64 di = 1;
UInt64 v, d, h = d = v = 0;
for (int i = 0; i < c_qw; i++)
{
if ((v = ret.m_arr[i] = m_arr[i] & arg.m_arr[i]) > 0)
{
d |= di;
h += v;
}
if ((di <<= 1) == 0)
{
ret.m_arr[c_qw + (i >> idx_shift)] = d;
d = 0;
di = 1;
}
}
ret.m_arr[c_qw + ((c_qw - 1) >> idx_shift)] = d;
if ((ret.hash_code = (int)h ^ (int)(h >> 32)) == NotCalculated) // avoid special hash
ret.hash_code = 0;
//ret.Check();
return ret;
}
public bool AndGivesExact(BitArr arg)
{
int i_stop = m_c_qw + m_c_dist;
for (int i = m_c_qw; i < i_stop; i++)
{
UInt64 tx;
if (((tx = m_arr[i]) & arg.m_arr[i]) != tx)
return false;
else if (tx > 0)
{
int n = 0;
UInt64 t = tx;
int jx = (i - m_c_qw) * bits_per_UInt64;
do
{
UInt64 lowest_bit = t & (UInt64)(-(Int64)t);
int j = jx + lu64[(int)((lowest_bit * 0x07EDD5E59A4E28C2) >> 58)];
/// if more than a certain number of hint bits is set then we're wasting time finding
/// their logarithms, so just switch over to checking all of the actual bits and ignore
/// the current hint quad
if (++n > IgnoreHintThreshold)
{
for (; j < m_c_qw; j++)
if (((tx = m_arr[j]) & arg.m_arr[j]) != tx)
return false;
return true;
}
if (((tx = m_arr[j]) & arg.m_arr[j]) != tx)
return false;
t &= ~lowest_bit;
}
while (t > 0);
}
}
return true;
}
public void OrEq(BitArr arg)
{
#if CHECK_CBITS
if (m_c_bits != arg.m_c_bits)
throw new ArgumentException();
#endif
UInt64 di = 1;
UInt64 v, h = v = 0;
for (int i = 0; i < m_c_qw; i++)
{
if ((v = (m_arr[i] |= arg.m_arr[i])) > 0)
{
int z = m_c_qw + (i >> idx_shift);
m_arr[z] |= di;
h += v;
}
if ((di <<= 1) == 0)
di = 1;
}
if ((hash_code = (int)h ^ (int)(h >> 32)) == NotCalculated) // avoid special hash
hash_code = 0;
//Check();
}
public bool AndEq(BitArr arg)
{
#if CHECK_CBITS
if (m_c_bits != arg.m_c_bits)
throw new ArgumentException();
#endif
bool f_any = false;
UInt64 di = 1;
for (int i = 0; i < m_c_qw; i++)
{
if ((m_arr[i] &= arg.m_arr[i]) > 0)
f_any = true;
else
{
int z = m_c_qw + (i >> idx_shift);
m_arr[z] &= ~di;
}
if ((di <<= 1) == 0)
di = 1;
}
hash_code = NotCalculated;
//Check();
return f_any;
}
#if NEED_DISTILL
public static bool AndToDest(BitArr dest, BitArr arg1, BitArr arg2)
{
if (dest.m_c_bits != arg1.m_c_bits || dest.m_c_bits != arg2.m_c_bits)
throw new ArgumentException();
bool f_any = false;
for (int i = 0; i < dest.m_c_qw; i++)
if ((dest.m_arr[i] = arg1.m_arr[i] & arg2.m_arr[i]) > 0)
f_any = true;
dest.f_hash_valid = false;
return f_any;
}
#endif
public bool FastTest(BitArr arg)
{
int i_stop = m_c_qw + m_c_dist;
for (int i = m_c_qw; i < i_stop; i++)
{
/// any zero in the 'and' of the two any-ones hints positively rules out a
/// quad that doesn't need to be checked. we start by extracting only the 1-bits,
/// counting how many we do. If it looks like we might end up extracting almost
/// every bit, we switch to just checking all of the target quads.
UInt64 t = (m_arr[i] & arg.m_arr[i]);
if (t > 0)
{
int n = 0;
int jx = (i - m_c_qw) * bits_per_UInt64;
do
{
UInt64 lowest_bit = t & (UInt64)(-(Int64)t);
int j = jx + lu64[(int)((lowest_bit * 0x07EDD5E59A4E28C2) >> 58)];
/// if more than a certain number of hint bits is set then we're wasting time finding
/// their logarithms, so just switch over to checking all of the actual bits and ignore
/// the current hint quad
if (++n > IgnoreHintThreshold)
{
for (; j < m_c_qw; j++)
if ((m_arr[j] & arg.m_arr[j]) > 0)
return true;
return false;
}
if ((m_arr[j] & arg.m_arr[j]) > 0)
return true;
t &= ~lowest_bit;
}
while (t > 0);
}
}
return false;
}
public bool FastTestNotArg(BitArr arg)
{
//if (m_c_bits != arg.m_c_bits)
//throw new ArgumentException();
for (int i = 0; i < m_c_qw; i++)
if ((m_arr[i] & ~arg.m_arr[i]) > 0)
return true;
return false;
}
public IEnumerable<int> OnesPositions()
{
UInt64 ui64;
for (int i = 0; i < m_c_qw; i++)
if ((ui64 = m_arr[i]) > 0)
{
do
{
UInt64 lowest_bit = ui64 & (UInt64)(-(Int64)ui64);
yield return (i * bits_per_UInt64) + lu64[(int)((lowest_bit * 0x07EDD5E59A4E28C2) >> 58)];
ui64 &= ~lowest_bit;
}
while (ui64 > 0);
}
}
unsafe public int OnesCount()
{
int count = 0;
int c_bytes = (m_c_bits / bits_per_byte) + 1;
fixed (UInt64* pui64 = &m_arr[0])
{
byte* pb = (byte*)pui64;
for (int i = 0; i < c_bytes; i++)
count += BitsSetTable256[*pb++];
}
return count;
}
public void Check()
{
UInt64 di = 1;
for (int i = 0; i < m_c_qw; i++)
{
if (m_arr[i] > 0)
{
if ((m_arr[m_c_qw + (i >> idx_shift)] & di) == 0)
System.Diagnostics.Debugger.Break();
}
else
{
if ((m_arr[m_c_qw + (i >> idx_shift)] & di) > 0)
System.Diagnostics.Debugger.Break();
}
if ((di <<= 1) == 0)
di = 1;
}
}
#if false
public static String ConstrainedDisplay(this BitArr ba)
{
return ba.Count > 50 ? ba.ToHex() : ba.ToString();
}
public static BitArr AndAll(IEnumerable<BitArr> ieba)
{
BitArr ba = null;
return ba;
}
#endif
public override string ToString()
{
Char[] wc_arr = new Char[m_c_bits];
for (int i = 0; i < m_c_bits; i++)
wc_arr[i] = this[m_c_bits - i - 1] ? '1' : '0';
return new String(wc_arr);
}
public String ToHex(Char sep_char = default(Char))
{
int c = m_c_bits / bits_per_UInt64;
int cch = (m_c_bits / 8) + 1;
if (sep_char != default(Char))
cch += c;
int end = cch;
Char[] wc_arr = new Char[cch];
String s;
int i;
for (i = 0; i < c; i++)
{
if (sep_char != default(Char))
{
s = m_arr[i].ToString("X");
cch -= s.Length;
}
else
{
s = m_arr[i].ToString("X16");
cch -= 8;
}
s.ToCharArray().CopyTo(wc_arr, cch);
if (sep_char != default(Char))
wc_arr[--cch] = sep_char;
}
if (sep_char != default(Char))
s = m_arr[i].ToString("X");
else
s = m_arr[i].ToString("X" + cch.ToString());
cch -= s.Length;
s.ToCharArray().CopyTo(wc_arr, cch);
return new String(wc_arr, cch, end - cch);
}
public override bool Equals(object obj)
{
throw new NotImplementedException();
}
public bool Equals(BitArr arg)
{
#if DEBUG
if (m_c_bits != arg.m_c_bits)
throw new ArgumentException();
#endif
if (hash_code != arg.hash_code && hash_code != NotCalculated && arg.hash_code != NotCalculated)
return false;
#if true || unsafe_is_slower
for (int i = 0; i < m_c_qw; i++)
if (m_arr[i] != arg.m_arr[i])
return false;
#else
fixed (UInt64* _p0 = &m_arr[0], _p1 = &arg.m_arr[0])
{
UInt64* p0 = _p0;
UInt64* p1 = _p1;
for (int i = 0; i < m_c_qw; i++)
if (*p0++ != *p1++)
return false;
}
#endif
#if NEVER_NEEDED
if (f_hash_valid != arg.f_hash_valid)
{
if (f_hash_valid)
arg.hash_code = this.hash_code;
else
this.hash_code = arg.hash_code;
}
#endif
return true;
}
unsafe public override int GetHashCode()
{
if (hash_code == NotCalculated)
{
UInt64 h = 0;
fixed (UInt64* pui64 = &m_arr[0])
{
UInt64* pi = pui64, pi_end = pi + m_c_qw;
while (pi < pi_end)
h += *pi++;
}
if ((hash_code = (int)h ^ (int)(h >> 32)) == NotCalculated) // avoid special hash
hash_code = 0;
}
return hash_code;
}
static byte[] BitsSetTable256 =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
const String lu64 =
"\u003F\u0000\u003A\u0001\u003B\u002F\u0035\u0002\u003C\u0027\u0030\u001B\u0036\u0021\u002A\u0003\u003D\u0033\u0025" +
"\u0028\u0031\u0012\u001C\u0014\u0037\u001E\u0022\u000B\u002B\u000E\u0016\u0004\u003E\u0039\u002E\u0034\u0026\u001A" +
"\u0020\u0029\u0032\u0024\u0011\u0013\u001D\u000A\u000D\u0015\u0038\u002D\u0019\u001F\u0023\u0010\u0009\u000C\u002C" +
"\u0018\u000F\u0008\u0017\u0007\u0006\u0005";
static int LowestOne(UInt64 ui64)
{
ui64 &= (UInt64)(-(Int64)ui64);
return lu64[(int)((ui64 * 0x07EDD5E59A4E28C2) >> 58)];
}
static int HighestOne(UInt64 ui64)
{
int o = 0;
if (ui64 != 0)
{
if ((ui64 & 0xFFFFFFFF00000000) > 0)
{
ui64 >>= 32;
o += 32;
}
if ((ui64 & 0xFFFF0000) > 0)
{
ui64 >>= 16;
o += 16;
}
if ((ui64 & 0xFF00) > 0)
{
ui64 >>= 8;
o += 8;
}
if ((ui64 & 0xF0) > 0)
{
ui64 >>= 4;
o += 4;
}
if ((ui64 & 0xC) > 0)
{
ui64 >>= 2;
o += 2;
}
if ((ui64 & 0x2) > 0)
o++;
}
return o;
}
int HighestOne()
{
int c = m_c_bits / bits_per_UInt64;
int i;
UInt64 dw;
for (i = c; i >= 0; i--)
if ((dw = m_arr[i]) > 0)
{
int o = 0;
if ((dw & 0xFFFFFFFF00000000) > 0)
{
dw >>= 32;
o += 32;
}
if ((dw & 0xFFFF0000) > 0)
{
dw >>= 16;
o += 16;
}
if ((dw & 0xFF00) > 0)
{
dw >>= 8;
o += 8;
}
if ((dw & 0xF0) > 0)
{
dw >>= 4;
o += 4;
}
if ((dw & 0xC) > 0)
{
dw >>= 2;
o += 2;
}
if ((dw & 0x2) > 0)
o++;
return i * bits_per_UInt64 + o;
}
return -1;
}
int LowestOne()
{
int i;
UInt64 dw;
for (i = 0; i < m_c_qw; i++)
if ((dw = m_arr[i]) > 0)
return i * bits_per_UInt64 + LowestOne(dw);
return -1;
}
public IEnumerable<int> EnumerateOnesBits()
{
for (int b = 0, ix = 0; ix < m_c_qw; ix++, b += 64)
{
UInt64 v = m_arr[ix];
while (v != 0)
{
UInt64 z = v & (UInt64)(-(Int64)v);
int c = ((z & 0xAAAAAAAAAAAAAAAA) > 0) ? 1 : 0;
if ((z & 0xCCCCCCCCCCCCCCCC) > 0)
c |= 0x2;
if ((z & 0xF0F0F0F0F0F0F0F0) > 0)
c |= 0x4;
if ((z & 0xFF00FF00FF00FF00) > 0)
c |= 0x8;
if ((z & 0xFFFF0000FFFF0000) > 0)
c |= 0x10;
if ((z & 0xFFFFFFFF00000000) > 0)
c |= 0x20;
yield return b + c;
v &= ~z;
}
}
}
// not used by this module:
public static int HighestOne(UInt32 ui32)
{
int o = 0;
if (ui32 != 0)
{
if ((ui32 & 0xFFFF0000) > 0)
{
ui32 >>= 16;
o += 16;
}
if ((ui32 & 0xFF00) > 0)
{
ui32 >>= 8;
o += 8;
}
if ((ui32 & 0xF0) > 0)
{
ui32 >>= 4;
o += 4;
}
if ((ui32 & 0xC) > 0)
{
ui32 >>= 2;
o += 2;
}
if ((ui32 & 0x2) > 0)
o++;
}
return o;
}
public static int HighestOne(Int32 i32)
{
int o = 0;
if (i32 != 0)
{
if ((i32 & 0xFFFF0000) > 0)
{
i32 >>= 16;
o += 16;
}
if ((i32 & 0xFF00) > 0)
{
i32 >>= 8;
o += 8;
}
if ((i32 & 0xF0) > 0)
{
i32 >>= 4;
o += 4;
}
if ((i32 & 0xC) > 0)
{
i32 >>= 2;
o += 2;
}
if ((i32 & 0x2) > 0)
o++;
}
return o;
}
};
public static class Extensions
{
static readonly byte[] _bits_set_256 =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public static int OnesCount(this uint v)
{
int c = _bits_set_256[v & 0xFF];
v >>= 8;
c += _bits_set_256[v & 0xFF];
v >>= 8;
c += _bits_set_256[v & 0xFF];
v >>= 8;
return c + _bits_set_256[v & 0xFF];
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// ONLY WORKS WHEN THERE IS EXACTLY ONE BIT SET
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public static int OnlyBitPosition(this uint z)
{
int c = ((z & 0xAAAAAAAA) > 0) ? 1 : 0;
if ((z & 0xCCCCCCCC) > 0)
c |= 0x2;
if ((z & 0xF0F0F0F0) > 0)
c |= 0x4;
if ((z & 0xFF00FF00) > 0)
c |= 0x8;
if ((z & 0xFFFF0000) > 0)
c |= 0x10;
return c;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public static int LowestOne(this short z)
{
z = (short)(z & -z);
int c = ((z & 0xAAAA) > 0) ? 1 : 0;
if ((z & 0xCCCC) > 0)
c |= 0x2;
if ((z & 0xF0F0) > 0)
c |= 0x4;
if ((z & 0xFF00) > 0)
c |= 0x8;
return c;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public static bool IsOdd(this int i)
{
return (i & 1) == 1;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public static bool IsEven(this int i)
{
return (i & 1) == 0;
}
}
}