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;
}
}
}
}