Skip to content

Instantly share code, notes, and snippets.

@lossyrob
Last active August 29, 2015 14:12
Show Gist options
  • Save lossyrob/a60e2a8981990feaa7fc to your computer and use it in GitHub Desktop.
Save lossyrob/a60e2a8981990feaa7fc to your computer and use it in GitHub Desktop.
Merge Queue: Queue which merges Long ranges.
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
}
}
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)) )
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment