In-Place Initializable Arrays

[andrej-sajenko]

Implement an array that can be

• read in O(1) time
• written in O(1) time
• and initialised in O(1) time
  with O(1) extra bit.

[jmeintrup]

@andrej-sajenko Do you still have the java implementation of this feature available on gitlab/github?

[andrej-sajenko]

Yes I do. Albeit it is clear, however, I will mention it: we implement only the n + O(log n) bit version.

package de.thm.mni.sea.collection;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import javafx.beans.property.IntegerProperty;
import javafx.beans.property.SimpleIntegerProperty;

/**
 * Instant initializable array. Array of an specific length and a init value which
 * initialize the array in constant time.
 *
 * @author Andrej Sajenko
 */
public class InitArray {
  private IntegerProperty A[];
  private IntegerProperty b = new SimpleIntegerProperty(0);
  private int initv;

  private ArrayList<ChainListener> chainListeners = new ArrayList<>();

  /**
   * @param length The array length
   * @param initv  The initial value
   */
  public InitArray(int length, int initv) {
    A = new IntegerProperty[length % 2 == 0 ? length : length + 1];
    this.initv = initv;

    // Randomize
    Random random = new Random();
    for (int i = 0; i < A.length; i++) {
      A[i] = new SimpleIntegerProperty(random.nextInt(A.length));
    }
  }

  /**
   * @return The array length
   */
  public int length() {
    return A.length;
  }

  @Override
  public String toString() {
    return "InitArray{" +
        "\n\tA = " + Arrays.toString(A) +
        "\n\tb = " + b +
        "\n\tinitv = " + initv +
        "\n}";
  }

  /**
   * Reset the complete array to a new initial value.
   *
   * @param value new value
   */
  public void init(int value) {
    b.set(0);
    this.initv = value;
  }

  /**
   * Read the i^th value of the array.
   *
   * @param i index
   * @return The value under index i
   */
  public int read(int i) {
    int _i = i / 2;
    int k = chainWith(_i);
    if (i < 2 * b.get()) {
      if (k != NONE) {
        return this.initv;
      } else {
        return A[i].get();
      }
    } else {
      if (k != NONE) {
        if (i % 2 == 0) {
          return A[A[i].get() + 1].get();
        } else {
          return A[i].get();
        }
      } else {
        return this.initv;
      }
    }
  }

  /**
   * Write a new value under the index i
   *
   * @param i     index
   * @param value value to write
   */
  public void write(int i, int value) {
    int _i = i / 2;
    int k = chainWith(_i);
    if (_i < b.get()) {
      if (k == NONE) {
        setA(i, value);
        breakChain(_i);
      } else {
        int j = extend();
        if (_i == j) {
          setA(i, value);
          breakChain(_i);
        } else {
          setA(2 * j, A[2 * _i].get());
          setA(2 * j + 1, A[2 * _i + 1].get());
          makeChain(j, k);
          initBlock(_i);
          setA(i, value);
          breakChain(_i);
        }
      }
    } else {
      if (k != NONE) {
        if (i % 2 == 0) {
          setA(2 * k + 1, value);
        } else {
          setA(i, value);
        }
      } else {
        k = extend();
        if (_i == k) {
          setA(i, value);
          breakChain(_i);
        } else {
          initBlock(_i);
          makeChain(k, _i);
          if (i % 2 == 0) {
            setA(2 * k + 1, value);
          } else {
            setA(i, value);
          }
        }
      }
    }
  }

  // tools

  private final int NONE = -1;

  private int chainWith(int i) {
    int _k = A[2 * i].get();
    int k = _k / 2;
    if (_k % 2 == 0 && _k >= 0
        && _k < A.length && A[_k].get() == 2 * i
        && ((i < b.get() && b.get() <= k) || (k < b.get() && b.get() <= i))) {
      return k;
    }
    return NONE;
  }

  private void makeChain(int i, int j) {
    setA(2 * i, 2 * j);
    setA(2 * j, 2 * i);

    this.chainListeners.forEach(listener -> listener.onMakeChain(i, j));
  }

  private void breakChain(int i) {
    int k = chainWith(i);
    if (k != NONE) {
      setA(2 * k, 2 * k);
      this.chainListeners.forEach(listener -> listener.onBreakChain(k));
    }
  }

  private void initBlock(int i) {
    setA(2 * i, initv);
    setA(2 * i + 1, initv);
  }

  private int extend() {
    int k = chainWith(b.get());

    b.set(b.get() + 1);

    this.chainListeners.forEach(listener -> listener.onBreakChain(b.get() - 1));

    if (k == NONE) {
      k = b.get() - 1;
    } else {
      setA(2 * (b.get() - 1), A[2 * k + 1].get());
      // setA(2 * (b.get() - 1) + 1, A[2 * b.get() + 1].get()); Not Needed
      breakChain(b.get() - 1);
    }
    initBlock(k);
    breakChain(k);
    return k;
  }

  private void setA(int i, int v) {
    A[i].set(v);
  }

  public void registerChainListener(ChainListener listener) {
    this.chainListeners.add(listener);
  }

  public void innerBindAi(int i, IntegerProperty p) {
    p.bind(A[i]);
  }

  public void innerBindB(IntegerProperty p) {
    p.bind(b);
  }
}