PriorityQueue.scala

/**
  * Created by uenyioha on 5/16/2016.
  */

import scalaz.FingerTree._
import scalaz._
import scalaz.syntax.Ops

sealed abstract class PriorityQueue[A]() extends Ops[FingerTree[Int, A]] {

  import PriorityQueue._

  def dequeue() : (A, PriorityQueue[A]) = {
    val (left, elem, right) = self.split1(x => x == self.measure)
    (elem, priorityQueue(left <++> right))
  }

  def enqueue(elem: A) : PriorityQueue[A]  = priorityQueue(self.+:(elem))
}

object PriorityQueue {

  private implicit val monoid: Monoid[Int]  = new Monoid[Int]{
    override def zero: Int = Int.MinValue
    override def append(f1: Int, f2: => Int): Int = Math.max(f1, f2)
  }

  private def priorityQueue[A](t: FingerTree[Int, A]) : PriorityQueue[A] = new PriorityQueue[A] {
    override def self: FingerTree[Int, A] = t
  }

  def apply[A](xs : A*)(implicit reducer: Reducer[A, Int]) : PriorityQueue[A] = {
    val z : PriorityQueue[A] = {
      priorityQueue(empty(reducer))
    }

    xs.foldLeft(z)((x, y) => x enqueue y )
  }
}