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

/*
 * Copyright (C) 2020 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 coupled
 * with a custom hashmap.
 */
public class SolverVariableValues implements ArrayRow.ArrayRowVariables {

    private static final boolean DEBUG = false;
    @SuppressWarnings("unused") private static final boolean HASH = true;
    private static float sEpsilon = 0.001f;
    private final int mNone = -1;
    private int mSize = 16;
    private int mHashSize = 16;

    int[] mKeys = new int[mSize];
    int[] mNextKeys = new int[mSize];

    int[] mVariables = new int[mSize];
    float[] mValues = new float[mSize];
    int[] mPrevious = new int[mSize];
    int[] mNext = new int[mSize];
    int mCount = 0;
    int mHead = -1;

    private final ArrayRow mRow; // our owner
    // pointer to the system-wide cache, allowing access to SolverVariables
    protected final Cache mCache;

    SolverVariableValues(ArrayRow row, Cache cache) {
        mRow = row;
        mCache = cache;
        clear();
    }

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

    @Override
    public SolverVariable getVariable(int index) {
        final int count = mCount;
        if (count == 0) {
            return null;
        }
        int j = mHead;
        for (int i = 0; i < count; i++) {
            if (i == index && j != mNone) {
                return mCache.mIndexedVariables[mVariables[j]];
            }
            j = mNext[j];
            if (j == mNone) {
                break;
            }
        }
        return null;
    }

    @Override
    public float getVariableValue(int index) {
        final int count = mCount;
        int j = mHead;
        for (int i = 0; i < count; i++) {
            if (i == index) {
                return mValues[j];
            }
            j = mNext[j];
            if (j == mNone) {
                break;
            }
        }
        return 0;
    }

    @Override
    public boolean contains(SolverVariable variable) {
        return indexOf(variable) != mNone;
    }

    @Override
    public int indexOf(SolverVariable variable) {
        if (mCount == 0 || variable == null) {
            return mNone;
        }
        int id = variable.id;
        int key = id % mHashSize;
        key = mKeys[key];
        if (key == mNone) {
            return mNone;
        }
        if (mVariables[key] == id) {
            return key;
        }
        while (mNextKeys[key] != mNone && mVariables[mNextKeys[key]] != id) {
            key = mNextKeys[key];
        }
        if (mNextKeys[key] == mNone) {
            return mNone;
        }
        if (mVariables[mNextKeys[key]] == id) {
            return mNextKeys[key];
        }
        return mNone;
    }

    @Override
    public float get(SolverVariable variable) {
        final int index = indexOf(variable);
        if (index != mNone) {
            return mValues[index];
        }
        return 0;
    }

    @Override
    public void display() {
        final int count = mCount;
        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(" }");
    }

    @Override
    public String toString() {
        String str = hashCode() + " { ";
        final int count = mCount;
        for (int i = 0; i < count; i++) {
            SolverVariable v = getVariable(i);
            if (v == null) {
                continue;
            }
            str += v + " = " + getVariableValue(i) + " ";
            int index = indexOf(v);
            str += "[p: ";
            if (mPrevious[index] != mNone) {
                str += mCache.mIndexedVariables[mVariables[mPrevious[index]]];
            } else {
                str += "none";
            }
            str += ", n: ";
            if (mNext[index] != mNone) {
                str += mCache.mIndexedVariables[mVariables[mNext[index]]];
            } else {
                str += "none";
            }
            str += "]";
        }
        str += " }";
        return str;
    }

    @Override
    public void clear() {
        if (DEBUG) {
            System.out.println(this + " <clear>");
        }
        final int count = mCount;
        for (int i = 0; i < count; i++) {
            SolverVariable v = getVariable(i);
            if (v != null) {
                v.removeFromRow(mRow);
            }
        }
        for (int i = 0; i < mSize; i++) {
            mVariables[i] = mNone;
            mNextKeys[i] = mNone;
        }
        for (int i = 0; i < mHashSize; i++) {
            mKeys[i] = mNone;
        }
        mCount = 0;
        mHead = -1;
    }

    private void increaseSize() {
        int size = this.mSize * 2;
        mVariables = Arrays.copyOf(mVariables, size);
        mValues = Arrays.copyOf(mValues, size);
        mPrevious = Arrays.copyOf(mPrevious, size);
        mNext = Arrays.copyOf(mNext, size);
        mNextKeys = Arrays.copyOf(mNextKeys, size);
        for (int i = this.mSize; i < size; i++) {
            mVariables[i] = mNone;
            mNextKeys[i] = mNone;
        }
        this.mSize = size;
    }

    private void addToHashMap(SolverVariable variable, int index) {
        if (DEBUG) {
            System.out.println(this.hashCode() + " hash add " + variable.id + " @ " + index);
        }
        int hash = variable.id % mHashSize;
        int key = mKeys[hash];
        if (key == mNone) {
            mKeys[hash] = index;
            if (DEBUG) {
                System.out.println(this.hashCode() + " hash add "
                        + variable.id + " @ " + index + " directly on keys " + hash);
            }
        } else {
            while (mNextKeys[key] != mNone) {
                key = mNextKeys[key];
            }
            mNextKeys[key] = index;
            if (DEBUG) {
                System.out.println(this.hashCode() + " hash add "
                        + variable.id + " @ " + index + " as nextkey of " + key);
            }
        }
        mNextKeys[index] = mNone;
        if (DEBUG) {
            displayHash();
        }
    }

    private void displayHash() {
        for (int i = 0; i < mHashSize; i++) {
            if (mKeys[i] != mNone) {
                String str = this.hashCode() + " hash [" + i + "] => ";
                int key = mKeys[i];
                boolean done = false;
                while (!done) {
                    str += " " + mVariables[key];
                    if (mNextKeys[key] != mNone) {
                        key = mNextKeys[key];
                    } else {
                        done = true;
                    }
                }
                System.out.println(str);
            }
        }
    }

    private void removeFromHashMap(SolverVariable variable) {
        if (DEBUG) {
            System.out.println(this.hashCode() + " hash remove " + variable.id);
        }
        int hash = variable.id % mHashSize;
        int key = mKeys[hash];
        if (key == mNone) {
            if (DEBUG) {
                displayHash();
            }
            return;
        }
        int id = variable.id;
        // let's first find it
        if (mVariables[key] == id) {
            mKeys[hash] = mNextKeys[key];
            mNextKeys[key] = mNone;
        } else {
            while (mNextKeys[key] != mNone && mVariables[mNextKeys[key]] != id) {
                key = mNextKeys[key];
            }
            int currentKey = mNextKeys[key];
            if (currentKey != mNone && mVariables[currentKey] == id) {
                mNextKeys[key] = mNextKeys[currentKey];
                mNextKeys[currentKey] = mNone;
            }
        }
        if (DEBUG) {
            displayHash();
        }
    }

    private void addVariable(int index, SolverVariable variable, float value) {
        mVariables[index] = variable.id;
        mValues[index] = value;
        mPrevious[index] = mNone;
        mNext[index] = mNone;
        variable.addToRow(mRow);
        variable.usageInRowCount++;
        mCount++;
    }

    private int findEmptySlot() {
        for (int i = 0; i < mSize; i++) {
            if (mVariables[i] == mNone) {
                return i;
            }
        }
        return -1;
    }

    private void insertVariable(int index, SolverVariable variable, float value) {
        int availableSlot = findEmptySlot();
        addVariable(availableSlot, variable, value);
        if (index != mNone) {
            mPrevious[availableSlot] = index;
            mNext[availableSlot] = mNext[index];
            mNext[index] = availableSlot;
        } else {
            mPrevious[availableSlot] = mNone;
            if (mCount > 0) {
                mNext[availableSlot] = mHead;
                mHead = availableSlot;
            } else {
                mNext[availableSlot] = mNone;
            }
        }
        if (mNext[availableSlot] != mNone) {
            mPrevious[mNext[availableSlot]] = availableSlot;
        }
        addToHashMap(variable, availableSlot);
    }

    @Override
    public void put(SolverVariable variable, float value) {
        if (DEBUG) {
            System.out.println(this + " <put> " + variable.id + " = " + value);
        }
        if (value > -sEpsilon && value < sEpsilon) {
            remove(variable, true);
            return;
        }
        if (mCount == 0) {
            addVariable(0, variable, value);
            addToHashMap(variable, 0);
            mHead = 0;
        } else {
            final int index = indexOf(variable);
            if (index != mNone) {
                mValues[index] = value;
            } else {
                if (mCount + 1 >= mSize) {
                    increaseSize();
                }
                final int count = mCount;
                int previousItem = -1;
                int j = mHead;
                for (int i = 0; i < count; i++) {
                    if (mVariables[j] == variable.id) {
                        mValues[j] = value;
                        return;
                    }
                    if (mVariables[j] < variable.id) {
                        previousItem = j;
                    }
                    j = mNext[j];
                    if (j == mNone) {
                        break;
                    }
                }
                insertVariable(previousItem, variable, value);
            }
        }
    }

    @Override
    public int sizeInBytes() {
        return 0;
    }

    @Override
    public float remove(SolverVariable v, boolean removeFromDefinition) {
        if (DEBUG) {
            System.out.println(this + " <remove> " + v.id);
        }
        int index = indexOf(v);
        if (index == mNone) {
            return 0;
        }
        removeFromHashMap(v);
        float value = mValues[index];
        if (mHead == index) {
            mHead = mNext[index];
        }
        mVariables[index] = mNone;
        if (mPrevious[index] != mNone) {
            mNext[mPrevious[index]] = mNext[index];
        }
        if (mNext[index] != mNone) {
            mPrevious[mNext[index]] = mPrevious[index];
        }
        mCount--;
        v.usageInRowCount--;
        if (removeFromDefinition) {
            v.removeFromRow(mRow);
        }
        return value;
    }

    @Override
    public void add(SolverVariable v, float value, boolean removeFromDefinition) {
        if (DEBUG) {
            System.out.println(this + " <add> " + v.id + " = " + value);
        }
        if (value > -sEpsilon && value < sEpsilon) {
            return;
        }
        final int index = indexOf(v);
        if (index == mNone) {
            put(v, value);
        } else {
            mValues[index] += value;
            if (mValues[index] > -sEpsilon && mValues[index] < sEpsilon) {
                mValues[index] = 0;
                remove(v, removeFromDefinition);
            }
        }
    }

    @Override
    public float use(ArrayRow definition, boolean removeFromDefinition) {
        float value = get(definition.mVariable);
        remove(definition.mVariable, removeFromDefinition);
        if (false) {
            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;
        }
        SolverVariableValues localDef = (SolverVariableValues) definition.variables;
        final int definitionSize = localDef.getCurrentSize();
        int j = localDef.mHead;
        if (false) {
            for (int i = 0; i < definitionSize; i++) {
                float definitionValue = localDef.mValues[j];
                SolverVariable definitionVariable =
                        mCache.mIndexedVariables[localDef.mVariables[j]];
                add(definitionVariable, definitionValue * value, removeFromDefinition);
                j = localDef.mNext[j];
                if (j == mNone) {
                    break;
                }
            }
        } else {
            j = 0;
            for (int i = 0; j < definitionSize; i++) {
                if (localDef.mVariables[i] != mNone) {
                    float definitionValue = localDef.mValues[i];
                    SolverVariable definitionVariable =
                            mCache.mIndexedVariables[localDef.mVariables[i]];
                    add(definitionVariable, definitionValue * value, removeFromDefinition);
                    j++;
                }
            }
        }
        return value;
    }

    @Override
    public void invert() {
        final int count = mCount;
        int j = mHead;
        for (int i = 0; i < count; i++) {
            mValues[j] *= -1;
            j = mNext[j];
            if (j == mNone) {
                break;
            }
        }
    }

    @Override
    public void divideByAmount(float amount) {
        final int count = mCount;
        int j = mHead;
        for (int i = 0; i < count; i++) {
            mValues[j] /= amount;
            j = mNext[j];
            if (j == mNone) {
                break;
            }
        }
    }

}