xref: /constraintlayout/constraintlayout-core/src/main/java/androidx/constraintlayout/core/ArrayLinkedVariables.java

/*
 * Copyright (C) 2016 The Android Open Source Project
 *
 * Licensed 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 androidx.constraintlayout.core;

import java.util.Arrays;

/**
 * Store a set of variables and their values in an array-based linked list.
 *
 * The general idea is that we want to store a list of variables that need to be ordered,
 * space efficient, and relatively fast to maintain (add/remove).
 *
 * ArrayBackedVariables implements a sparse array, so is rather space efficient, but maintaining
 * the array sorted is costly,
 * as we spend quite a bit of time recopying parts of the array on element deletion.
 *
 * LinkedVariables implements a standard linked list structure,
 * and is able to be faster than ArrayBackedVariables
 * even though it's more costly to set up (pool of objects...),
 * as the elements removal and maintenance of the structure is a lot more efficient.
 *
 * This ArrayLinkedVariables class takes inspiration from both of the above,
 * and implement a linked list stored in several arrays.
 * This allows us to be a lot more efficient in terms of setup (no need to deal with pool
 * of objects...), resetting the structure, and insertion/deletion of elements.
 */
public class ArrayLinkedVariables implements ArrayRow.ArrayRowVariables {
    private static final boolean DEBUG = false;

    static final int NONE = -1;
    // private static final boolean FULL_NEW_CHECK = false   full validation (debug purposes)

    int mCurrentSize = 0; // current size, accessed by ArrayRow and LinearSystem

    private final ArrayRow mRow; // our owner

    // pointer to the system-wide cache, allowing access to SolverVariables
    protected final Cache mCache;

    private int mRowSize = 8; // default array size

    private SolverVariable mCandidate = null;

    // mArrayIndices point to indexes in mCache.mIndexedVariables (i.e., the SolverVariables)
    private int[] mArrayIndices = new int[mRowSize];

    // mArrayNextIndices point to indexes in mArrayIndices
    private int[] mArrayNextIndices = new int[mRowSize];

    // mArrayValues contain the associated value from mArrayIndices
    private float[] mArrayValues = new float[mRowSize];

    // mHead point to indexes in mArrayIndices
    private int mHead = NONE;

    // mLast point to indexes in mArrayIndices
    //
    // While mDidFillOnce is not set, mLast is simply incremented
    // monotonically in order to be sure to traverse the entire array; the idea here is that
    // when we clear a linked list, we only set the counters to zero without traversing the array
    // to fill it with NONE values, which would be costly.
    // But if we do not fill the array with NONE values, we cannot safely simply check if an entry
    // is set to NONE to know if we can use it or not, as it might contains a previous value...
    // So, when adding elements, we first ensure with this mechanism of mLast/mDidFillOnce
    // that we do traverse the array linearly,
    // avoiding for that first pass the need to check for the value of the item in mArrayIndices.
    // This does mean that removed elements will leave empty spaces,
    // but we /then/ set the removed element to NONE,
    // so that once we did that first traversal filling the array,
    // we can safely revert to linear traversal
    // finding an empty spot by checking the values of mArrayIndices
    // (i.e. finding an item containing NONE).
    private int mLast = NONE;

    // flag to keep trace if we did a full pass of the array or not, see above description
    private boolean mDidFillOnce = false;
    private static float sEpsilon = 0.001f;

    // Example of a basic loop
    // current or previous point to mArrayIndices
    //
    // int current = mHead;
    // int counter = 0;
    // while (current != NONE && counter < currentSize) {
    //  SolverVariable currentVariable = mCache.mIndexedVariables[mArrayIndices[current]];
    //  float currentValue = mArrayValues[current];
    //  ...
    //  current = mArrayNextIndices[current]; counter++;
    // }

    /**
     * Constructor
     *
     * @param arrayRow the row owning us
     * @param cache    instances cache
     */
    ArrayLinkedVariables(ArrayRow arrayRow, Cache cache) {
        mRow = arrayRow;
        mCache = cache;
        if (DEBUG) {
            for (int i = 0; i < mArrayIndices.length; i++) {
                mArrayIndices[i] = NONE;
            }
        }
    }

    /**
     * Insert a variable with a given value in the linked list
     *
     * @param variable the variable to add in the list
     * @param value    the value of the variable
     */
    @Override
    public final void put(SolverVariable variable, float value) {
        if (value == 0) {
            remove(variable, true);
            return;
        }
        // Special casing empty list...
        if (mHead == NONE) {
            mHead = 0;
            mArrayValues[mHead] = value;
            mArrayIndices[mHead] = variable.id;
            mArrayNextIndices[mHead] = NONE;
            variable.usageInRowCount++;
            variable.addToRow(mRow);
            mCurrentSize++;
            if (!mDidFillOnce) {
                // only increment mLast if we haven't done the first filling pass
                mLast++;
                if (mLast >= mArrayIndices.length) {
                    mDidFillOnce = true;
                    mLast = mArrayIndices.length - 1;
                }
            }
            return;
        }
        int current = mHead;
        int previous = NONE;
        int counter = 0;
        while (current != NONE && counter < mCurrentSize) {
            if (mArrayIndices[current] == variable.id) {
                mArrayValues[current] = value;
                return;
            }
            if (mArrayIndices[current] < variable.id) {
                previous = current;
            }
            current = mArrayNextIndices[current];
            counter++;
        }

        // Not found, we need to insert

        // First, let's find an available spot
        int availableIndice = mLast + 1; // start from the previous spot
        if (mDidFillOnce) {
            // ... but if we traversed the array once, check the last index, which might have been
            // set by an element removed
            if (mArrayIndices[mLast] == NONE) {
                availableIndice = mLast;
            } else {
                availableIndice = mArrayIndices.length;
            }
        }
        if (availableIndice >= mArrayIndices.length) {
            if (mCurrentSize < mArrayIndices.length) {
                // find an available spot
                for (int i = 0; i < mArrayIndices.length; i++) {
                    if (mArrayIndices[i] == NONE) {
                        availableIndice = i;
                        break;
                    }
                }
            }
        }
        // ... make sure to grow the array as needed
        if (availableIndice >= mArrayIndices.length) {
            availableIndice = mArrayIndices.length;
            mRowSize *= 2;
            mDidFillOnce = false;
            mLast = availableIndice - 1;
            mArrayValues = Arrays.copyOf(mArrayValues, mRowSize);
            mArrayIndices = Arrays.copyOf(mArrayIndices, mRowSize);
            mArrayNextIndices = Arrays.copyOf(mArrayNextIndices, mRowSize);
        }

        // Finally, let's insert the element
        mArrayIndices[availableIndice] = variable.id;
        mArrayValues[availableIndice] = value;
        if (previous != NONE) {
            mArrayNextIndices[availableIndice] = mArrayNextIndices[previous];
            mArrayNextIndices[previous] = availableIndice;
        } else {
            mArrayNextIndices[availableIndice] = mHead;
            mHead = availableIndice;
        }
        variable.usageInRowCount++;
        variable.addToRow(mRow);
        mCurrentSize++;
        if (!mDidFillOnce) {
            // only increment mLast if we haven't done the first filling pass
            mLast++;
        }
        if (mCurrentSize >= mArrayIndices.length) {
            mDidFillOnce = true;
        }
        if (mLast >= mArrayIndices.length) {
            mDidFillOnce = true;
            mLast = mArrayIndices.length - 1;
        }
    }

    /**
     * Add value to an existing variable
     *
     * The code is broadly identical to the put() method, only differing
     * in in-line deletion, and of course doing an add rather than a put
     *
     * @param variable             the variable we want to add
     * @param value                its value
     * @param removeFromDefinition if a variable's value becomes zero, it is removed. This parameter
     *                             is whether the removal is deep now or left shallow until cleanup
     */
    @Override
    public void add(SolverVariable variable, float value, boolean removeFromDefinition) {
        if (value > -sEpsilon && value < sEpsilon) {
            return;
        }
        // Special casing empty list...
        if (mHead == NONE) {
            mHead = 0;
            mArrayValues[mHead] = value;
            mArrayIndices[mHead] = variable.id;
            mArrayNextIndices[mHead] = NONE;
            variable.usageInRowCount++;
            variable.addToRow(mRow);
            mCurrentSize++;
            if (!mDidFillOnce) {
                // only increment mLast if we haven't done the first filling pass
                mLast++;
                if (mLast >= mArrayIndices.length) {
                    mDidFillOnce = true;
                    mLast = mArrayIndices.length - 1;
                }
            }
            return;
        }
        int current = mHead;
        int previous = NONE;
        int counter = 0;
        while (current != NONE && counter < mCurrentSize) {
            int idx = mArrayIndices[current];
            if (idx == variable.id) {
                float v = mArrayValues[current] + value;
                if (v > -sEpsilon && v < sEpsilon) {
                    v = 0;
                }
                mArrayValues[current] = v;
                // Possibly delete immediately
                if (v == 0) {
                    if (current == mHead) {
                        mHead = mArrayNextIndices[current];
                    } else {
                        mArrayNextIndices[previous] = mArrayNextIndices[current];
                    }
                    if (removeFromDefinition) {
                        variable.removeFromRow(mRow);
                    }
                    if (mDidFillOnce) {
                        // If we did a full pass already, remember that spot
                        mLast = current;
                    }
                    variable.usageInRowCount--;
                    mCurrentSize--;
                }
                return;
            }
            if (mArrayIndices[current] < variable.id) {
                previous = current;
            }
            current = mArrayNextIndices[current];
            counter++;
        }

        // Not found, we need to insert

        // First, let's find an available spot
        int availableIndice = mLast + 1; // start from the previous spot
        if (mDidFillOnce) {
            // ... but if we traversed the array once, check the last index, which might have been
            // set by an element removed
            if (mArrayIndices[mLast] == NONE) {
                availableIndice = mLast;
            } else {
                availableIndice = mArrayIndices.length;
            }
        }
        if (availableIndice >= mArrayIndices.length) {
            if (mCurrentSize < mArrayIndices.length) {
                // find an available spot
                for (int i = 0; i < mArrayIndices.length; i++) {
                    if (mArrayIndices[i] == NONE) {
                        availableIndice = i;
                        break;
                    }
                }
            }
        }
        // ... make sure to grow the array as needed
        if (availableIndice >= mArrayIndices.length) {
            availableIndice = mArrayIndices.length;
            mRowSize *= 2;
            mDidFillOnce = false;
            mLast = availableIndice - 1;
            mArrayValues = Arrays.copyOf(mArrayValues, mRowSize);
            mArrayIndices = Arrays.copyOf(mArrayIndices, mRowSize);
            mArrayNextIndices = Arrays.copyOf(mArrayNextIndices, mRowSize);
        }

        // Finally, let's insert the element
        mArrayIndices[availableIndice] = variable.id;
        mArrayValues[availableIndice] = value;
        if (previous != NONE) {
            mArrayNextIndices[availableIndice] = mArrayNextIndices[previous];
            mArrayNextIndices[previous] = availableIndice;
        } else {
            mArrayNextIndices[availableIndice] = mHead;
            mHead = availableIndice;
        }
        variable.usageInRowCount++;
        variable.addToRow(mRow);
        mCurrentSize++;
        if (!mDidFillOnce) {
            // only increment mLast if we haven't done the first filling pass
            mLast++;
        }
        if (mLast >= mArrayIndices.length) {
            mDidFillOnce = true;
            mLast = mArrayIndices.length - 1;
        }
    }

    /**
     * Update the current list with a new definition
     *
     * @param definition           the row containing the definition
     * @param removeFromDefinition if a variable's value becomes zero, it is removed. This parameter
     *                             is whether the removal is deep now or left shallow until cleanup
     */
    @Override
    public float use(ArrayRow definition, boolean removeFromDefinition) {
        float value = get(definition.mVariable);
        remove(definition.mVariable, removeFromDefinition);
        ArrayRow.ArrayRowVariables definitionVariables = definition.variables;
        int definitionSize = definitionVariables.getCurrentSize();
        for (int i = 0; i < definitionSize; i++) {
            SolverVariable definitionVariable = definitionVariables.getVariable(i);
            float definitionValue = definitionVariables.get(definitionVariable);
            this.add(definitionVariable, definitionValue * value, removeFromDefinition);
        }
        return value;
    }

    /**
     * Remove a variable from the list
     *
     * @param variable             the variable we want to remove
     * @param removeFromDefinition if a variable's value becomes zero, it is removed. This parameter
     *                             is whether the removal is deep now or left shallow until cleanup
     * @return the value of the removed variable
     */
    @Override
    public final float remove(SolverVariable variable, boolean removeFromDefinition) {
        if (mCandidate == variable) {
            mCandidate = null;
        }
        if (mHead == NONE) {
            return 0;
        }
        int current = mHead;
        int previous = NONE;
        int counter = 0;
        while (current != NONE && counter < mCurrentSize) {
            int idx = mArrayIndices[current];
            if (idx == variable.id) {
                if (current == mHead) {
                    mHead = mArrayNextIndices[current];
                } else {
                    mArrayNextIndices[previous] = mArrayNextIndices[current];
                }

                if (removeFromDefinition) {
                    variable.removeFromRow(mRow);
                }
                variable.usageInRowCount--;
                mCurrentSize--;
                mArrayIndices[current] = NONE;
                if (mDidFillOnce) {
                    // If we did a full pass already, remember that spot
                    mLast = current;
                }
                return mArrayValues[current];
            }
            previous = current;
            current = mArrayNextIndices[current];
            counter++;
        }
        return 0;
    }

    /**
     * Clear the list of variables
     */
    @Override
    public final void clear() {
        int current = mHead;
        int counter = 0;
        while (current != NONE && counter < mCurrentSize) {
            SolverVariable variable = mCache.mIndexedVariables[mArrayIndices[current]];
            if (variable != null) {
                variable.removeFromRow(mRow);
            }
            current = mArrayNextIndices[current];
            counter++;
        }

        mHead = NONE;
        mLast = NONE;
        mDidFillOnce = false;
        mCurrentSize = 0;
    }

    /**
     * Returns true if the variable is contained in the list
     *
     * @param variable the variable we are looking for
     * @return return true if we found the variable
     */
    @Override
    public boolean contains(SolverVariable variable) {
        if (mHead == NONE) {
            return false;
        }
        int current = mHead;
        int counter = 0;
        while (current != NONE && counter < mCurrentSize) {
            if (mArrayIndices[current] == variable.id) {
                return true;
            }
            current = mArrayNextIndices[current];
            counter++;
        }
        return false;
    }

    @Override
    public int indexOf(SolverVariable variable) {
        if (mHead == NONE) {
            return -1;
        }
        int current = mHead;
        int counter = 0;
        while (current != NONE && counter < mCurrentSize) {
            if (mArrayIndices[current] == variable.id) {
                return current;
            }
            current = mArrayNextIndices[current];
            counter++;
        }
        return -1;
    }


    /**
     * Returns true if at least one of the variable is positive
     *
     * @return true if at least one of the variable is positive
     */
    boolean hasAtLeastOnePositiveVariable() {
        int current = mHead;
        int counter = 0;
        while (current != NONE && counter < mCurrentSize) {
            if (mArrayValues[current] > 0) {
                return true;
            }
            current = mArrayNextIndices[current];
            counter++;
        }
        return false;
    }

    /**
     * Invert the values of all the variables in the list
     */
    @Override
    public void invert() {
        int current = mHead;
        int counter = 0;
        while (current != NONE && counter < mCurrentSize) {
            mArrayValues[current] *= -1;
            current = mArrayNextIndices[current];
            counter++;
        }
    }

    /**
     * Divide the values of all the variables in the list
     * by the given amount
     *
     * @param amount amount to divide by
     */
    @Override
    public void divideByAmount(float amount) {
        int current = mHead;
        int counter = 0;
        while (current != NONE && counter < mCurrentSize) {
            mArrayValues[current] /= amount;
            current = mArrayNextIndices[current];
            counter++;
        }
    }

    public int getHead() {
        return mHead;
    }

    @Override
    public int getCurrentSize() {
        return mCurrentSize;
    }

    /**
     * get Id in mCache.mIndexedVariables given the index
     */
    public final int getId(int index) {
        return mArrayIndices[index];
    }

    /**
     * get value in mArrayValues given the index
     */
    public final float getValue(int index) {
        return mArrayValues[index];
    }

    /**
     * Get the next index in mArrayIndices given the current one
     */
    public final int getNextIndice(int index) {
        return mArrayNextIndices[index];
    }

    /**
     * TODO: check if still needed
     * Return a pivot candidate
     *
     * @return return a variable we can pivot on
     */
    SolverVariable getPivotCandidate() {
        if (mCandidate == null) {
            // if no candidate is known, let's figure it out
            int current = mHead;
            int counter = 0;
            SolverVariable pivot = null;
            while (current != NONE && counter < mCurrentSize) {
                if (mArrayValues[current] < 0) {
                    // We can return the first negative candidate as in ArrayLinkedVariables
                    // they are already sorted by id

                    SolverVariable v = mCache.mIndexedVariables[mArrayIndices[current]];
                    if (pivot == null || pivot.strength < v.strength) {
                        pivot = v;
                    }
                }
                current = mArrayNextIndices[current];
                counter++;
            }
            return pivot;
        }
        return mCandidate;
    }

    /**
     * Return a variable from its position in the linked list
     *
     * @param index the index of the variable we want to return
     * @return the variable found, or null
     */
    @Override
    public SolverVariable getVariable(int index) {
        int current = mHead;
        int counter = 0;
        while (current != NONE && counter < mCurrentSize) {
            if (counter == index) {
                return mCache.mIndexedVariables[mArrayIndices[current]];
            }
            current = mArrayNextIndices[current];
            counter++;
        }
        return null;
    }

    /**
     * Return the value of a variable from its position in the linked list
     *
     * @param index the index of the variable we want to look up
     * @return the value of the found variable, or 0 if not found
     */
    @Override
    public float getVariableValue(int index) {
        int current = mHead;
        int counter = 0;
        while (current != NONE && counter < mCurrentSize) {
            if (counter == index) {
                return mArrayValues[current];
            }
            current = mArrayNextIndices[current];
            counter++;
        }
        return 0;
    }

    /**
     * Return the value of a variable, 0 if not found
     *
     * @param v the variable we are looking up
     * @return the value of the found variable, or 0 if not found
     */
    @Override
    public final float get(SolverVariable v) {
        int current = mHead;
        int counter = 0;
        while (current != NONE && counter < mCurrentSize) {
            if (mArrayIndices[current] == v.id) {
                return mArrayValues[current];
            }
            current = mArrayNextIndices[current];
            counter++;
        }
        return 0;
    }

    /**
     * Show size in bytes
     *
     * @return size in bytes
     */
    @Override
    public int sizeInBytes() {
        int size = 0;
        size += 3 * (mArrayIndices.length * 4);
        size += 9 * 4;
        return size;
    }

    /**
     * print out the variables and their values
     */
    @Override
    public void display() {
        int count = mCurrentSize;
        System.out.print("{ ");
        for (int i = 0; i < count; i++) {
            SolverVariable v = getVariable(i);
            if (v == null) {
                continue;
            }
            System.out.print(v + " = " + getVariableValue(i) + " ");
        }
        System.out.println(" }");
    }

    /**
     * Returns a string representation of the list
     *
     * @return a string containing a representation of the list
     */
    @Override
    public String toString() {
        String result = "";
        int current = mHead;
        int counter = 0;
        while (current != NONE && counter < mCurrentSize) {
            result += " -> ";
            result += mArrayValues[current] + " : ";
            result += mCache.mIndexedVariables[mArrayIndices[current]];
            current = mArrayNextIndices[current];
            counter++;
        }
        return result;
    }

}