/* Author: Tommi Junttila, Aalto University.
 * Only for the use on the Aalto course CS-A1140.
 * Redistribution not allowed.
 */

package object radixSort {
  /**
   * Least-significant-digit-first radix sort for integer arrays.
   * Sorts the argument array in ascending order.
   * Assumes that all the integers are non-negative.
   * Interpret 'digit' as 'byte' (8 bits) here and use bit-level operations
   *  such as shifting (>> and <<) and masking (&) to extract 'digits'.
   */
  def lsdRadixSort(a: Array[Int]): Unit = {
    val aLength = a.length
    var valueArray = a;

    val M1 = 255;
    val M2 = 65280;
    val M3 = 16711680;
    val M4 = -16777216;

    val masks = Array(M1, M2, M3, M4);
    var rounds = 0;
    while (rounds < 4) {
      val countArray = Array.fill(256) {0}

      var iterator = 0;
      val mask = masks(rounds);
      while (iterator < aLength) {
        val value = valueArray(iterator);
        val maskedValue = value & mask;
        val index = maskedValue >> (rounds * 8);
        countArray(index) += 1
        iterator += 1
      }

      val locationTable = new Array[Int](256)
      locationTable(0) = 0
      var z = 1
      while (z < 256) {
        locationTable(z) = locationTable(z-1) + countArray(z -1);
        z += 1
      }

      val temporaryArray = new Array[Int](aLength)
      var reverse = 0;
      while (reverse <= aLength - 1)
      {
        val value = valueArray(reverse);

        val maskedValue = value & mask;
        val index = maskedValue >> (rounds * 8);

        val offsetted = locationTable(index)
        locationTable(index) += 1

        temporaryArray(offsetted) = value;
        reverse += 1;
      }
      valueArray = temporaryArray;
      rounds += 1;
    }
    for (i <- a.indices) a(i) = valueArray(i)
  }
}