public static void constructAliasTable()

in graphjet-core/src/main/java/com/twitter/graphjet/math/AliasTableUtil.java [46:114]
59 lines of code
13 McCabe index (conditional complexity)

  public static void constructAliasTable(int[] aliasTableArray) {
    int aliasTableSize = getAliasTableSize(aliasTableArray);
    int averageWeight = getAliasTableAverageWeight(aliasTableArray);

    // TODO(aneesh): both these arrays can be captured in a single array
    int[] belowAverageIndices = new int[aliasTableSize];
    int numBelowAverage = 0;
    int[] aboveAverageIndices = new int[aliasTableSize];
    int numAboveAverage = 0;

    // First pass through the list
    for (int i = 0; i < aliasTableSize; i++) {
      int weight = getWeight(aliasTableArray, i);
      if (weight == averageWeight) {
        setNextEntry(aliasTableArray, i, -1);
      } else if (weight < averageWeight) {
        if (numAboveAverage > 0) {
          int donatingItemIndex = aboveAverageIndices[--numAboveAverage];
          setNextEntry(aliasTableArray, i, getEntry(aliasTableArray, donatingItemIndex));
          int newWeight =
              getWeight(aliasTableArray, donatingItemIndex) - (averageWeight - weight);
          setWeight(aliasTableArray, donatingItemIndex, newWeight);
          if (newWeight == averageWeight) {
            setNextEntry(aliasTableArray, donatingItemIndex, -1);
          } else if (newWeight < averageWeight) {
            belowAverageIndices[numBelowAverage++] = donatingItemIndex;
          } else {
            aboveAverageIndices[numAboveAverage++] = donatingItemIndex;
          }
        } else {
          belowAverageIndices[numBelowAverage++] = i;
        }
      } else {
        aboveAverageIndices[numAboveAverage++] = i;
      }
    }

    // This is for balancing the below average elements, but due to limited precision there might
    // be some remaining elements
    // TODO (aneesh): convert to for loop
    while (numBelowAverage > 0 && numAboveAverage > 0) {
      int entryIndex = belowAverageIndices[--numBelowAverage];
      int weight = getWeight(aliasTableArray, entryIndex);
      int donatingElementIndex = aboveAverageIndices[--numAboveAverage];
      setNextEntry(aliasTableArray, entryIndex, getEntry(aliasTableArray, donatingElementIndex));
      int newWeight =
          getWeight(aliasTableArray, donatingElementIndex) - (averageWeight - weight);
      setWeight(aliasTableArray, donatingElementIndex, newWeight);
      if (newWeight == averageWeight) {
        setNextEntry(aliasTableArray, donatingElementIndex, -1);
      } else if (newWeight < averageWeight) {
        belowAverageIndices[numBelowAverage++] = donatingElementIndex;
      } else {
        aboveAverageIndices[numAboveAverage++] = donatingElementIndex;
      }
    }

    // Due to limited precision, it is possible we get here, so we do the final cleanup
    for (int i = numBelowAverage - 1; i >= 0; i--) {
      int index = belowAverageIndices[i];
      setWeight(aliasTableArray, index, averageWeight);
      setNextEntry(aliasTableArray, index, -1);
    }
    for (int i = numAboveAverage - 1; i >= 0; i--) {
      int index = aboveAverageIndices[i];
      setWeight(aliasTableArray, index, averageWeight);
      setNextEntry(aliasTableArray, index, -1);
    }
  }