BitString.java

/*
 * Copyright (c) 2025, Stein Eldar Johnsen
 *
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements. See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership. The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License. You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied. See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */
package net.morimekta.collect.util;

import java.util.Arrays;
import java.util.Objects;

/**
 * A Bit String is an immutable sequence of single bit values represented by
 * a boolean array.
 */
public final class BitString extends BitSequence implements Comparable<BitString> {
    public static final BitString EMPTY = new BitString();

    /**
     * Create an empty bit string.
     */
    public BitString() {
        this.data = new boolean[0];
        this.size = 0;
    }

    /**
     * Create a bit string representing the given set of bit values.
     *
     * @param bits Boolean array to initialize bit string with.
     */
    public BitString(boolean... bits) {
        this(bits, 0, bits.length);
    }

    /**
     * Create a bit string represented by the specified section of the
     * boolean array.
     *
     * @param bits   The bit array to take values from.
     * @param offset The array offset to start at.
     * @param size   The number of values to include in the bit string.
     */
    public BitString(boolean[] bits, int offset, int size) {
        if (size < 0) {
            throw new IllegalArgumentException("Negative size: " + size);
        }
        if (offset < 0 || bits.length < offset + size) {
            throw new IllegalArgumentException(
                    "Invalid offset=" + offset + ", size=" + size + " of boolean[" + bits.length + "]");
        }
        this.data = new boolean[size];
        this.size = size;
        System.arraycopy(bits, offset, data, 0, size);
    }

    public static BitString fromByteArray(byte[] bits) {
        if (bits.length == 0) {
            return EMPTY;
        }
        var out = fromByteArrayInternal(bits, 0, bits.length);
        if (out.length == 0) {
            return EMPTY;
        }
        return new BitString(out);
    }

    // ---- BitString ----

    public BitString concat(BitString other) {
        if (other.size == 0) {
            return this;
        } else if (size == 0) {
            return other;
        }
        var sum = new boolean[size + other.size];
        System.arraycopy(data, 0, sum, 0, size);
        System.arraycopy(other.data, 0, sum, size, other.size);
        return new BitString(sum, 0, sum.length);
    }

    public BitString subString(int start) {
        return subString(start, size);
    }

    public BitString subString(int start, int end) {
        if (start < 0 || start > end || end > size) {
            throw new IndexOutOfBoundsException("Invalid range: [" + start + ".." + end + ")");
        } else if (start == end) {
            return EMPTY;
        } else if (start == 0 && end == size) {
            return this;
        }
        var part = new boolean[end - start];
        System.arraycopy(data, start, part, 0, end - start);
        return new BitString(part, 0, part.length);
    }

    // ---- BitSequence ----

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean bitAt(int pos) {
        if (pos < 0 || size <= pos) {
            throw new IndexOutOfBoundsException(pos + " outside [0.." + size + "]");
        }
        return data[pos];
    }

    @Override
    public boolean[] toBitArray() {
        var out = new boolean[size];
        System.arraycopy(data, 0, out, 0, size);
        return out;
    }

    @Override
    public byte[] toByteArray() {
        return toByteArrayInternal(data, size);
    }

    @Override
    public String toBitString() {
        if (string == null) {
            string = toStringFromBits(data, size);
        }
        return string;
    }

    @Override
    protected void writeTo(boolean[] out, int off) {
        System.arraycopy(data, 0, out, off, size);
    }

    // ---- Comparable ----

    @Override
    public int compareTo(BitString o) {
        return Arrays.compare(data, o.data);
    }

    // ---- Object ----

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof BitString)) {
            return false;
        }
        var other = (BitString) obj;
        return Arrays.equals(other.data, 0, other.size, data, 0, size);
    }

    @Override
    public int hashCode() {
        return Objects.hash(size, Arrays.hashCode(data));
    }

    // ---- Private ----

    final             boolean[] data;
    final             int       size;
    private transient String    string;
}