package movingMinMax
import java.util.TreeMap;

abstract class Filter[A <% Ordered[A]](val windowSize: Int) {
  def insert(value: A): (A, A)
}

/**
 * The slow moving min-max filter class given as a reference.
 * Each apply call takes time \Omega(windowSize).
 * Do not modify the code in this class.
 */
class SlowFilter[A <% Ordered[A]](windowSize: Int) extends Filter[A](windowSize) {
  val queue = new scala.collection.mutable.Queue[A]()

  /**
   * Insert the value to the moving window, remove the earliest one, and
   * return the minimum and maximum values in the current window.
   */
  def insert(value: A): (A, A) = {
    if (queue.size == windowSize) queue.dequeue
    queue.enqueue(value)
    // The following is faster than just saying (queue.min, queue.max)
    // because only one pass over the queue is made
    var min = queue.head
    var max = queue.head
    for (v <- queue) {
      if (v < min) min = v
      if (v > max) max = v
    }
    (min, max)
  }
}

/**
 * The faster moving min-max filter class.
 * Each apply should run in time O(log windowSize).
 */
class FastFilter[A <% Ordered[A]](windowSize: Int) extends Filter[A](windowSize) {
  val queue = new scala.collection.mutable.Queue[A]()
  /* Insert additional data structures here */
  val tree = new java.util.TreeMap[A, Int]()
  /**
   * Insert the value to the moving window, remove the earliest one, and
   * return the minimum and maximum values in the current window.
   */
  def insert(value: A): (A, A) = {

    if (queue.size == windowSize) {         // jos frame on täynnä, pitää perästä poistaa
      if (tree.containsKey(value)) {       // jos sisältää jo ennestään lisättävän arvon, tulee arvoa lisätä

        tree.put(value, tree.get(value) + 1) //arvon lisäys
        if (tree.get(queue.head) > 1) { tree.put(queue.head, tree.get(value) - 1); queue.dequeue } // jos ensimmäinen jonossa (poistettava) on kopio toisesta jonossa, tulee puun vastaavan mapin arvoa vähentää
        else {
          tree.remove(queue.head); queue.dequeue;
        }
      } else                             // Jos viimeinen jonossa on uniikki, poistetaan vain puusta jonon kärkeä vastaava map ja poistetaan jonon kärki.
      { queue.enqueue(value) }           // Jos jonossa ei ole jos instanssia lisättävästä valuea, lisätään jonoon

    }                                     // jos frame ei ole täynnä, pitää tsekata löytyykö avain jo mutta poistoa ei tehdä
    else {
      if (tree.containsKey(value)) {     // jos puu sisältää jo ennestään lisättävän valuen, tulee int-arvoa kasvattaa
        tree.put(value, tree.get(value) + 1)
      } else { tree.put(value, 1) }

      queue.enqueue(value)

    }

    (tree.firstKey, tree.lastKey)

  }
}