EfMsSeq.java
/*
* License : The MIT License
* Copyright(c) 2022 Olyutorskii
*/
package io.github.olyutorskii.aletojio.emergence;
import java.util.Arrays;
/**
* Ehrenfeucht-Mycielski random bits sequence.
*
* <p>Continue to generate random bits sequences acyclic and emergently
* until the memory capacity and indexing mechanism reach their limits.
*
* <p>This is Automatic sequence. This means infinite sequence from finite automaton.
*
* <p>It is only possible to add bit to the end of sequence.
*
* <p>TODO: use suffix tree.
*
* @see <a href="https://en.wikipedia.org/wiki/Ehrenfeucht%E2%80%93Mycielski_sequence">
* Ehrenfeucht Mycielski sequence.
* </a>
* @see <a href="https://oeis.org/A038219">A038219 sample list</a>
*/
public class EfMsSeq {
private static final int PRIMLEN = Long.SIZE;
private static final int INIT_VECLEN = 2;
private static final int GROWTH_RATE = 2;
private long[] vec;
private int capacity;
private int bitLength;
/**
* Constructor.
*
* <p>Bit sequence is empty.
*/
public EfMsSeq() {
super();
this.vec = new long[INIT_VECLEN];
this.capacity = PRIMLEN * this.vec.length;
this.bitLength = 0;
return;
}
/**
* Return length of bit sequence.
*
* @return length of bit sequence
*/
public int length() {
return this.bitLength;
}
/**
* Ensure min capacity of bit length.
*
* @param minCapacity min capacity of bit length
*/
private void ensureCapacity(int minCapacity) {
if (minCapacity <= this.capacity) {
return;
}
int newArraySize = this.vec.length * GROWTH_RATE;
while (PRIMLEN * newArraySize < minCapacity) {
newArraySize *= GROWTH_RATE;
}
this.vec = Arrays.copyOf(this.vec, newArraySize);
this.capacity = PRIMLEN * this.vec.length;
return;
}
/**
* Append new bit to tail of bit sequence.
*
* @param iVal bit. 0 means 0b0, not 0 means 0b1.
*/
public void append(int iVal) {
int newLength = this.bitLength + 1;
ensureCapacity(newLength);
if (iVal != 0) {
int vecIdx = this.bitLength / PRIMLEN;
int bitPos = this.bitLength % PRIMLEN;
this.vec[vecIdx] |= 1L << bitPos;
}
this.bitLength = newLength;
return;
}
/**
* Append new bits to tail of bit sequence.
*
* @param iVals bits. 0 means 0b0, not 0 means 0b1.
*/
public void append(int... iVals) {
ensureCapacity(this.bitLength + iVals.length);
for (int iVal : iVals) {
append(iVal);
}
return;
}
/**
* Get bit from bit sequence with index.
*
* <p>Index starts with 0 (oldest bit).
* Index ends with bit sequence length - 1 (recently added bit).
*
* @param idx bit position. 0 means oldest bit.
* @return bit. 0 means 0b0. 1 means 0b1.
* @throws IndexOutOfBoundsException illegal index
*/
public int get(int idx) throws IndexOutOfBoundsException {
if (idx >= this.bitLength || idx < 0) {
throw new IndexOutOfBoundsException();
}
int vecIdx = idx / PRIMLEN;
int bitPos = idx % PRIMLEN;
long lVal = this.vec[vecIdx];
lVal = (lVal >> bitPos) & 1L;
return (int) lVal;
}
/**
* Return last index of suffix pattern appeared in bit sequence.
*
* <p>Suffix never unmatch it self.
*
* <p>Suffix of "01010010101" with index 8 is "101".
*
* <p>"101" pattern appear 3-times in "01010010101".
* 3rd one is ignored because last one is suffix it self.
*
* <p>Therefore, last index of "01010010101" with suffix index 8 is position 6
*
* @param suffixIdx index of suffix starting
* @return last index of suffix pattern appeared in bit sequence. Negative if unmatched.
* @throws IndexOutOfBoundsException invalid index
*/
public int lastIdxSuffix(int suffixIdx) throws IndexOutOfBoundsException {
if (suffixIdx <= 0) throw new IndexOutOfBoundsException();
if (suffixIdx >= this.bitLength) throw new IndexOutOfBoundsException();
int suffixLen = this.bitLength - suffixIdx;
int revStart = this.bitLength - suffixLen - 1;
assert suffixLen > 0;
assert revStart >= 0;
assert revStart < this.bitLength - 1;
int lastIdx = -1;
for (int seqRevIdx = revStart; seqRevIdx >= 0; seqRevIdx--) {
boolean suffixMatched = true;
for (int offset = 0; offset < suffixLen; offset++) {
int bitSeq = get(seqRevIdx + offset);
int bitSfx = get(suffixIdx + offset);
if (bitSeq != bitSfx) {
suffixMatched = false;
break;
}
}
if (suffixMatched) {
lastIdx = seqRevIdx;
break;
}
}
return lastIdx;
}
/**
* Determin next random bit from past bits.
*
* @return next random bit. (0 or 1)
* @throws NullPointerException argument is null
*/
public int nextBool()
throws NullPointerException {
int targetLen = length();
if (targetLen <= 0) return 0;
int suffixNext = -1;
for (int suffixIdx = 1; suffixIdx < targetLen; suffixIdx++) {
int matchedPos = lastIdxSuffix(suffixIdx);
if (matchedPos >= 0) {
int suffixLen = targetLen - suffixIdx;
suffixNext = matchedPos + suffixLen;
break;
}
}
int resultPos;
if (suffixNext >= 0) resultPos = suffixNext;
else resultPos = length() - 1;
int resultNeg;
if (get(resultPos) == 0) resultNeg = 1;
else resultNeg = 0;
return resultNeg;
}
/**
* {@inheritDoc}
*
* @return {@inheritDoc}
*/
@Override
public int hashCode() {
long lVal1st = 0xdeadbeefaa554321L;
long lValLast = 0x1234aa55cafebabeL;
if (this.bitLength >= 1) {
int vecs = (this.bitLength - 1) / PRIMLEN + 1;
lVal1st ^= this.vec[0] * 23;
lValLast ^= this.vec[vecs - 1] * 29;
}
long lVal = lVal1st ^ lValLast;
int result = 0;
result ^= (int) lVal;
result ^= (int) (lVal >>> 32);
return result;
}
/**
* {@inheritDoc}
*
* @param obj {@inheritDoc}
* @return {@inheritDoc}
*/
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (!(obj instanceof EfMsSeq)) {
return false;
}
EfMsSeq other = (EfMsSeq) obj;
if (this.bitLength != other.bitLength) {
return false;
}
boolean result = Arrays.equals(this.vec, other.vec);
return result;
}
/**
* {@inheritDoc}
*
* <p>Output 0/1 sequence in historical order.
*
* @return bit sequence text. "nil" if empty.
*/
@Override
public String toString() {
if (this.bitLength <= 0) return "nil";
StringBuilder result = new StringBuilder();
result.ensureCapacity(this.bitLength);
for (int bitIdx = 0; bitIdx < this.bitLength; bitIdx++) {
char ch;
if (get(bitIdx) == 0) ch = '0';
else ch = '1';
result.append(ch);
}
return result.toString();
}
}