blob: e58244834290004f86828ec45ef66d261bc32aa6 (
plain) (
tree)
|
|
import scala.collection.mutable.PriorityQueue
// populate a priority queue a few different ways and make sure they all seem equal
object Test {
def main(args: Array[String]) {
testInsertionsAndEqualities
testIntensiveEnqueueDequeue
testIndexing
testTails
testInits
testFilters
testDrops
testUpdates
testEquality
testSeq
}
def testInsertionsAndEqualities {
import scala.util.Random.nextInt
val pq1 = new PriorityQueue[String]
val pq2 = new PriorityQueue[String]
val pq3 = new PriorityQueue[String]
val pq4 = new PriorityQueue[String]
val strings = (1 to 20).toList map (i => List.fill((Math.abs(nextInt % 20)) + 1)("x").mkString)
pq1 ++= strings
pq2 ++= strings.reverse
for (s <- strings) pq3 += s
for (s <- strings.reverse) pq4 += s
val pqs = List(pq1, pq2, pq3, pq4, pq1.clone, pq2.clone)
for (queue1 <- pqs ; queue2 <- pqs) {
assert(queue1 == queue2)
assert(queue1.max == queue2.max)
}
assertPriority(pq1)
}
def testIndexing {
val pq = new PriorityQueue[Char]
"The quick brown fox jumps over the lazy dog".foreach(pq += _)
// val iter = pq.iterator
// while (iter.hasNext) println("`" + iter.next + "`")
assert(pq(0) == 'z')
assert(pq(1) == 'y')
assert(pq(2) == 'x')
assert(pq(3) == 'w')
assert(pq(4) == 'v')
assert(pq(5) == 'u')
assert(pq(7) == 't')
assert(pq(8) == 's')
assert(pq(9) == 'r')
assert(pq(10) == 'r')
pq.clear
"abcdefghijklmnopqrstuvwxyz".foreach(pq += _)
for (i <- 0 until 26) assert(pq(i) == ('z' - i))
val intpq = new PriorityQueue[Int]
val intlst = new collection.mutable.ArrayBuffer ++ (0 until 100)
val random = new util.Random(101)
while (intlst.nonEmpty) {
val idx = random.nextInt(intlst.size)
intpq += intlst(idx)
intlst.remove(idx)
}
for (i <- 0 until 100) assert(intpq(i) == (99 - i))
}
def testTails {
val pq = new PriorityQueue[Int]
for (i <- 0 until 10) pq += i * 4321 % 200
assert(pq.size == 10)
assert(pq.nonEmpty)
val tailpq = pq.tail
// pq.printstate
// tailpq.printstate
assert(tailpq.size == 9)
assert(tailpq.nonEmpty)
assertPriorityDestructive(tailpq)
}
def assertPriorityDestructive[A](pq: PriorityQueue[A])(implicit ord: Ordering[A]) {
import ord._
var prev: A = null.asInstanceOf[A]
while (pq.nonEmpty) {
val curr = pq.dequeue
if (prev != null) assert(curr <= prev)
prev = curr
}
}
def assertPriority[A](pq: PriorityQueue[A])(implicit ord: Ordering[A]) {
import ord._
var prev: A = null.asInstanceOf[A]
val iter = pq.iterator
while (iter.hasNext) {
val curr = iter.next
if (prev != null) assert(curr <= prev)
prev = curr
}
}
def testInits {
val pq = new PriorityQueue[Long]
for (i <- 0 until 20) pq += (i + 313) * 111 % 300
assert(pq.size == 20)
val initpq = pq.init
assert(initpq.size == 19)
assertPriorityDestructive(initpq)
}
def testFilters {
val pq = new PriorityQueue[String]
for (i <- 0 until 100) pq += "Some " + (i * 312 % 200)
val filpq = pq.filter(_.indexOf('0') != -1)
assertPriorityDestructive(filpq)
}
def testIntensiveEnqueueDequeue {
val pq = new PriorityQueue[Int]
testIntensive(1000, pq)
pq.clear
testIntensive(200, pq)
}
def testIntensive(sz: Int, pq: PriorityQueue[Int]) {
val lst = new collection.mutable.ArrayBuffer[Int] ++ (0 until sz)
val rand = new util.Random(7)
while (lst.nonEmpty) {
val idx = rand.nextInt(lst.size)
pq.enqueue(lst(idx))
lst.remove(idx)
if (rand.nextDouble < 0.25 && pq.nonEmpty) pq.dequeue
assertPriority(pq)
}
}
def testDrops {
val pq = new PriorityQueue[Int]
pq ++= (0 until 100)
val droppq = pq.drop(50)
assertPriority(droppq)
pq.clear
pq ++= droppq
assertPriorityDestructive(droppq)
assertPriority(pq)
assertPriorityDestructive(pq)
}
def testUpdates {
val pq = new PriorityQueue[Int]
pq ++= (0 until 36)
assertPriority(pq)
pq(0) = 100
assert(pq(0) == 100)
assert(pq.dequeue == 100)
assertPriority(pq)
pq.clear
pq ++= (1 to 100)
pq(5) = 200
assert(pq(0) == 200)
assert(pq(1) == 100)
assert(pq(2) == 99)
assert(pq(3) == 98)
assert(pq(4) == 97)
assert(pq(5) == 96)
assert(pq(6) == 94)
assert(pq(7) == 93)
assert(pq(98) == 2)
assert(pq(99) == 1)
assertPriority(pq)
pq(99) = 450
assert(pq(0) == 450)
assert(pq(1) == 200)
assert(pq(99) == 2)
assertPriority(pq)
pq(1) = 0
assert(pq(1) == 100)
assert(pq(99) == 0)
assertPriority(pq)
assertPriorityDestructive(pq)
}
def testEquality {
val pq1 = new PriorityQueue[Int]
val pq2 = new PriorityQueue[Int]
pq1 ++= (0 until 50)
var i = 49
while (i >= 0) {
pq2 += i
i -= 1
}
assert(pq1 == pq2)
assertPriority(pq2)
pq1 += 100
assert(pq1 != pq2)
pq2 += 100
assert(pq1 == pq2)
pq2 += 200
assert(pq1 != pq2)
pq1 += 200
assert(pq1 == pq2)
assertPriorityDestructive(pq1)
assertPriorityDestructive(pq2)
}
def testSeq {
val pq = new PriorityQueue[Int]
pq ++= (0 until 100)
val (p1, p2) = pq.partition(_ < 50)
assertPriorityDestructive(p1)
assertPriorityDestructive(p2)
val spq = pq.slice(25, 75)
assertPriorityDestructive(spq)
pq.clear
pq ++= (0 until 10)
pq += 5
//val ind = pq.lastIndexWhere(_ == 5)
//println(ind)
//println(pq)
//assert(ind == 5)
//assertPriorityDestructive(pq)
//pq.clear
//pq ++= (0 until 10)
}
}
|