Cache.scala

/**
 * To remove duplicate elements from verArr and compacting the array, the algo
 * uses two hash maps:
 * uniqueMap, contains all the unique vertices as key and their respective
 *            indices in final compacted verArr as value.
 * redirectionMap, duplicate vertex entries go in this map, with their indices
 *                 as key and value would be their index in final compacted
 *                 verArr.
 * using these two maps, verArr is compacted and entries would be unique.
 * similarly facArr is changed to point to correct indices corresponding to
 * compacted verArr.
 *
 * Time Complexity: O(n + m), where n and m are lengths of verArr and facArr.
 * Assuming array index starting from 0.
 */

import scala.collection.mutable.HashMap

// Vertex and Face classes.
case class Vertex(a: Int, b: Int, c: Int)
case class Face(var a: Int, var b: Int, var c: Int)

class Duplicates(verArr: Array[Vertex], facArr: Array[Face]) {
  private val uniqueMap = new HashMap[Vertex, Int]
  private val redirectionMap = new HashMap[Int, Int]
  // diff is used to get the new index in the compact verArr for the unique
  // verices.
  private var diff = 0

  // Compacts the verArr and changes the facArr correspondingly.
  def remove = {
    for (i <- verArr.indices) {
      val vertex = verArr(i)
      if (uniqueMap contains vertex) {
        // vertex is not unique, put it in redirection map with correct
        // redirection.
        redirectionMap += (i -> uniqueMap.apply(vertex))
        diff += 1
      }
      // vertex is unique, put it in unique map with corresponding final verArr
      // index.
      else uniqueMap += (vertex -> (i - diff))
    }

    // Change the facArr to point to correct entries in compacted verArr.
    for (face <- facArr) {
      face.a = if (redirectionMap contains face.a) redirectionMap.apply(face.a) else uniqueMap.apply(verArr(face.a))
      face.b = if (redirectionMap contains face.b) redirectionMap.apply(face.b) else uniqueMap.apply(verArr(face.b))
      face.c = if (redirectionMap contains face.c) redirectionMap.apply(face.c) else uniqueMap.apply(verArr(face.c))
    }

    // Change the values in verArr, first verArrLength entries would be unique
    // and corresponding to comapcted verArr. These values can be stored in some
    // other collection also.
    for ((k, v) <- uniqueMap) verArr(v) = k
  }

  // Returns the facArr corresponding to squeezed verArr.
  def getFacArr = facArr
  // Length of this array would be same as i/p verArr but first verArrLength
  // entries would be unique and stored in the order according to required
  // compact verArr.
  def getVerArr = verArr
  def verArrLength = uniqueMap.size
}