Merge Queue: Queue which merges Long ranges.

MergeQueue.scala

package mergequeue

class MergeQueue(initialSize: Int = 1) {
  private var array = if(initialSize <= 1) { Array.ofDim[(Long, Long)](1) } else { Array.ofDim[(Long, Long)](initialSize) }
  private var _size = 0

  def size = _size

  private def removeElement(i: Int): Unit = {
    if(i < _size - 1) {
      val result = array.clone
      System.arraycopy(array, i + 1, result, i, _size - i - 1)
      array = result
    }
    _size = _size - 1
  }

  private def insertElement(range: (Long, Long), i: Int): Unit = {
    ensureSize(_size + 1)
    if(i == _size) {
      array(i) = range
    } else {
      val result = array.clone
      System.arraycopy(array, 0, result, 0, i)
      System.arraycopy(array, i, result, i + 1, _size - i)
      result(i) = range
      array = result
    }
    _size += 1
  }


  /** Ensure that the internal array has at least `n` cells. */
  protected def ensureSize(n: Int) {
    // Use a Long to prevent overflows
    val arrayLength: Long = array.length
    if (n > arrayLength - 1) {
      var newSize: Long = arrayLength * 2
      while (n > newSize) {
        newSize = newSize * 2
      }
      // Clamp newSize to Int.MaxValue
      if (newSize > Int.MaxValue) newSize = Int.MaxValue

      val newArray: Array[(Long, Long)] = new Array(newSize.toInt)
      scala.compat.Platform.arraycopy(array, 0, newArray, 0, _size)
      array = newArray
    }
  }

  val ordering = implicitly[Ordering[(Long, Long)]]

  /** Inserts a single range into the priority queue.
   *
   *  @param  range        the element to insert.
   */
  @annotation.tailrec
  final def +=(range: (Long, Long)): Unit = {
    val res = if(_size == 0) { -1 } else { java.util.Arrays.binarySearch(array, 0, _size, range, ordering) }
    if(res < 0) {
      val i = -(res + 1)
      var (thisStart, thisEnd) = range
      var removeLeft = false

      var removeRight = false
      var rightRemainder: Option[(Long, Long)] = None

      // Look at the left range
      if(i != 0) {
        val (prevStart, prevEnd) = array(i - 1)
        if(prevStart == thisStart) {
          removeLeft = true
        }
        if (prevEnd + 1 >= thisStart) { 
          removeLeft = true
          thisStart = prevStart
          if(prevEnd > thisEnd) {
            thisEnd = prevEnd
          }
        }
      }

      // Look at the right range
      if(i < _size  && _size > 0) {
        val (nextStart, nextEnd) = array(i)
        if(thisStart == nextStart) {
          removeRight = true
          thisEnd = nextEnd
        } else {
          if(thisEnd + 1 >= nextStart) {
            removeRight = true
            if(nextEnd - 1 >= thisEnd) {
              thisEnd = nextEnd
            } else if (nextEnd < thisEnd - 1) {
              rightRemainder = Some((nextEnd + 1, thisEnd))
              thisEnd = nextEnd
            }
          }
        }
      }

      if(removeRight) { 
        if(!removeLeft) {
          array(i) = (thisStart, thisEnd)
        } else {
          array(i-1) = (thisStart, thisEnd)
          removeElement(i)
        }
      } else if(removeLeft) {
        array(i-1) = (thisStart, thisEnd)
      } else {
        insertElement(range, i)
      }
      
      rightRemainder match {
        case Some(r) => this += r
        case None =>
      }
    }
  }

  def toSeq: Seq[(Long, Long)] = {
    val result = Array.ofDim[(Long, Long)](size)
    System.arraycopy(array, 0, result, 0, size)
    result
  }
}

MergeQueueSpec.scala

class ExampleSuite extends FunSpec with Matchers {
  describe("mergequeue") {
    it("should merges two ranges that overlap") {
      val ranges =
        Seq(
          (4L, 6L),
          (5L, 7L)
        )

      val mq = new MergeQueue

      for(range <- ranges) { mq += range }

      mq.toSeq should be ( Seq((4L, 7L)) )
    }

    it("should merges seven ranges that overlap") {
      val ranges =
        Seq(
          (4L, 10L),
          (5L, 7L),
          (11L, 14L),
          (16L, 17L),
          (14L, 15L),
          (20L, 21L),
          (3L, 4L)
        )

      val mq = new MergeQueue

      for(range <- ranges) { mq += range }

      mq.toSeq should be ( Seq((3L, 17L), (20L, 21L)) )
    }
  }

  it("should merge a set of small ranges into one big range") {
      val ranges =
        Seq(
          (4L, 5L),
          (7L, 8L),
          (10L, 11L),
          (3L, 12L)
        )

      val mq = new MergeQueue

      for(range <- ranges) { mq += range }

      mq.toSeq should be ( Seq((3L, 12L)) )
  }
}