diff options
Diffstat (limited to 'test/files/scalacheck')
-rw-r--r-- | test/files/scalacheck/MutableTreeMap.scala | 345 | ||||
-rw-r--r-- | test/files/scalacheck/MutableTreeSet.scala | 216 | ||||
-rw-r--r-- | test/files/scalacheck/avl.scala | 112 | ||||
-rwxr-xr-x | test/files/scalacheck/concurrent-map.scala | 76 | ||||
-rw-r--r-- | test/files/scalacheck/parallel-collections/ParallelRangeCheck.scala | 2 | ||||
-rw-r--r-- | test/files/scalacheck/quasiquotes/TypecheckedProps.scala | 2 |
6 files changed, 639 insertions, 114 deletions
diff --git a/test/files/scalacheck/MutableTreeMap.scala b/test/files/scalacheck/MutableTreeMap.scala new file mode 100644 index 0000000000..42b88c56a7 --- /dev/null +++ b/test/files/scalacheck/MutableTreeMap.scala @@ -0,0 +1,345 @@ +import java.io._ + +import org.scalacheck._ +import org.scalacheck.Arbitrary._ +import org.scalacheck.Prop.forAll + +import scala.collection.generic.CanBuildFrom +import scala.collection.immutable +import scala.collection.mutable +import scala.util.Try +import scala.collection.mutable.{RedBlackTree => RB} + +package scala.collection.mutable { + + trait Generators { + + def genRedBlackTree[A: Arbitrary: Ordering, B: Arbitrary]: Gen[RB.Tree[A, B]] = { + import org.scalacheck.Gen._ + for { entries <- listOf(arbitrary[(A, B)]) } yield { + val tree = RB.Tree.empty[A, B] + entries.foreach { case (k, v) => RB.insert(tree, k, v) } + tree + } + } + + // Note: in scalacheck 1.12.2 tree maps can be automatically generated without the need for custom + // machinery + def genTreeMap[A: Arbitrary: Ordering, B: Arbitrary]: Gen[mutable.TreeMap[A, B]] = { + import org.scalacheck.Gen._ + for { + keys <- listOf(arbitrary[A]) + values <- listOfN(keys.size, arbitrary[B]) + } yield mutable.TreeMap(keys zip values: _*) + } + + implicit def arbRedBlackTree[A: Arbitrary: Ordering, B: Arbitrary] = Arbitrary(genRedBlackTree[A, B]) + implicit def arbTreeMap[A: Arbitrary: Ordering, B: Arbitrary] = Arbitrary(genTreeMap[A, B]) + } + + object RedBlackTreeProperties extends Properties("mutable.RedBlackTree") with Generators { + type K = String + type V = Int + + property("initial invariants") = forAll { (tree: RB.Tree[K, V]) => + RB.isValid(tree) + } + + property("insert") = forAll { (tree: RB.Tree[K, V], entries: Seq[(K, V)]) => + entries.foreach { case (k, v) => RB.insert(tree, k, v) } + RB.isValid(tree) && entries.toMap.forall { case (k, v) => RB.get(tree, k) == Some(v) } + } + + property("delete") = forAll { (tree: RB.Tree[K, V], ks: Seq[K]) => + ks.foreach { k => RB.delete(tree, k) } + RB.isValid(tree) && ks.toSet.forall { k => RB.get(tree, k) == None } + } + + property("insert & delete") = forAll { (tree: RB.Tree[K, V], ops: Seq[Either[(K, V), K]]) => + ops.foreach { + case Left((k, v)) => RB.insert(tree, k, v) + case Right(k) => RB.delete(tree, k) + } + RB.isValid(tree) + } + + property("min") = forAll { (entries: Seq[(K, V)]) => + val tree = RB.Tree.empty[K, V] + entries.foreach { case (k, v) => RB.insert(tree, k, v) } + RB.min(tree) == (if (entries.isEmpty) None else Some(entries.toMap.min)) + } + + property("max") = forAll { (entries: Seq[(K, V)]) => + val tree = RB.Tree.empty[K, V] + entries.foreach { case (k, v) => RB.insert(tree, k, v) } + RB.max(tree) == (if (entries.isEmpty) None else Some(entries.toMap.max)) + } + } + + object MutableTreeMapProperties extends Properties("mutable.TreeMap") with Generators { + type K = String + type V = Int + + property("get, contains") = forAll { (allEntries: Map[K, V]) => + val entries = allEntries.take(allEntries.size / 2) + + val map = mutable.TreeMap[K, V]() + map ++= entries + + allEntries.forall { case (k, v) => + map.contains(k) == entries.contains(k) && + map.get(k) == entries.get(k) + } + } + + property("size, isEmpty") = forAll { (entries: Map[K, V]) => + val map = mutable.TreeMap[K, V]() + map ++= entries + map.size == entries.size && map.isEmpty == entries.isEmpty + } + + property("+=") = forAll { (map: mutable.TreeMap[K, V], k: K, v: V) => + val oldSize = map.size + val containedKeyBefore = map.contains(k) + val newExpectedSize = if(containedKeyBefore) oldSize else oldSize + 1 + + map += (k -> v) + map.contains(k) && map.get(k) == Some(v) && map.size == newExpectedSize + } + + property("++=") = forAll { (map: mutable.TreeMap[K, V], entries: Seq[(K, V)]) => + val oldEntries = map.toMap + map ++= entries + (oldEntries ++ entries).forall { case (k, v) => map.get(k) == Some(v) } + } + + property("-=") = forAll { (map: mutable.TreeMap[K, V], k: K) => + val oldSize = map.size + val containedKeyBefore = map.contains(k) + val newExpectedSize = if(containedKeyBefore) oldSize - 1 else oldSize + + map -= k + !map.contains(k) && map.get(k) == None && map.size == newExpectedSize + } + + property("--=") = forAll { (map: mutable.TreeMap[K, V], ks: Seq[K]) => + val oldElems = map.toList + map --= ks + val deletedElems = ks.toSet + oldElems.forall { case (k, v) => map.get(k) == (if(deletedElems(k)) None else Some(v)) } + } + + property("iterator") = forAll { (entries: Map[K, V]) => + val map = mutable.TreeMap[K, V]() + map ++= entries + + map.iterator.toSeq == entries.toSeq.sorted + } + + property("iteratorFrom") = forAll { (entries: Map[K, V], k: K) => + val map = mutable.TreeMap[K, V]() + map ++= entries + + map.iteratorFrom(k).toSeq == entries.filterKeys(_ >= k).toSeq.sorted + } + + property("keysIteratorFrom") = forAll { (entries: Map[K, V], k: K) => + val map = mutable.TreeMap[K, V]() + map ++= entries + + map.keysIteratorFrom(k).toSeq == entries.keysIterator.filter(_ >= k).toSeq.sorted + } + + property("valuesIteratorFrom") = forAll { (entries: Map[K, V], k: K) => + val map = mutable.TreeMap[K, V]() + map ++= entries + + map.valuesIteratorFrom(k).toSeq == entries.filterKeys(_ >= k).toSeq.sorted.map(_._2) + } + + property("headOption") = forAll { (map: mutable.TreeMap[K, V]) => + map.headOption == Try(map.iterator.next()).toOption + } + + property("lastOption") = forAll { (map: mutable.TreeMap[K, V]) => + map.lastOption == Try(map.iterator.max).toOption + } + + property("clear") = forAll { (map: mutable.TreeMap[K, V]) => + map.clear() + map.isEmpty && map.size == 0 + } + + property("serializable") = forAll { (map: mutable.TreeMap[K, V]) => + val bytesOut = new ByteArrayOutputStream() + val out = new ObjectOutputStream(bytesOut) + out.writeObject(map) + val bytes = bytesOut.toByteArray + + val in = new ObjectInputStream(new ByteArrayInputStream(bytes)) + val sameMap = in.readObject().asInstanceOf[mutable.TreeMap[K, V]] + map.iterator.toSeq == sameMap.iterator.toSeq + } + + property("same behavior as immutable.TreeMap") = forAll { ops: Seq[Either[(K, V), K]] => + var imap = immutable.TreeMap[K, V]() + val mmap = mutable.TreeMap[K, V]() + + ops.foreach { + case Left((k, v)) => imap += k -> v; mmap += k -> v + case Right(k) => imap -= k; mmap -= k + } + + imap.toList == mmap.toList + } + } + + object MutableTreeMapViewProperties extends Properties("mutable.TreeMapView") with Generators { + type K = String + type V = Int + + implicit val ord = implicitly[Ordering[K]] + + def in(key: K, from: Option[K], until: Option[K]) = + from.fold(true)(_ <= key) && until.fold(true)(_ > key) + + def entriesInView[This <: TraversableOnce[(K, V)], That](entries: This, from: Option[K], until: Option[K])(implicit bf: CanBuildFrom[This, (K, V), That]) = { + (bf.apply(entries) ++= entries.filter { case (k, _) => in(k, from, until) }).result() + } + + property("get, contains") = forAll { (allEntries: Map[K, V], from: Option[K], until: Option[K]) => + val entries = allEntries.take(allEntries.size / 2) + + val map = mutable.TreeMap[K, V]() + map ++= entries + + val mapView = map.rangeImpl(from, until) + allEntries.forall { case (k, v) => + mapView.contains(k) == (in(k, from, until) && entries.contains(k)) && + mapView.get(k) == (if(in(k, from, until)) entries.get(k) else None) + } + } + + property("size, isEmpty") = forAll { (entries: Map[K, V], from: Option[K], until: Option[K]) => + val map = mutable.TreeMap[K, V]() + map ++= entries + + val mapView = map.rangeImpl(from, until) + mapView.size == entriesInView(entries, from, until).size && + mapView.isEmpty == !entries.exists { kv => in(kv._1, from, until) } + } + + property("+=") = forAll { (map: mutable.TreeMap[K, V], k: K, v: V, from: Option[K], until: Option[K]) => + val oldSize = map.size + val containedKeyBefore = map.contains(k) + val newExpectedSize = if(containedKeyBefore) oldSize else oldSize + 1 + val isInRange = in(k, from, until) + + val mapView = map.rangeImpl(from, until) + mapView += (k -> v) + + map.contains(k) && map.get(k) == Some(v) && map.size == newExpectedSize && + mapView.contains(k) == isInRange && + mapView.get(k) == (if(isInRange) Some(v) else None) + } + + property("++=") = forAll { (map: mutable.TreeMap[K, V], entries: Seq[(K, V)], from: Option[K], until: Option[K]) => + val mapView = map.rangeImpl(from, until) + mapView ++= entries + entries.toMap.forall { case (k, v) => + map.get(k) == Some(v) && + mapView.get(k) == (if (in(k, from, until)) Some(v) else None) + } + } + + property("-=") = forAll { (map: mutable.TreeMap[K, V], k: K, from: Option[K], until: Option[K]) => + val oldSize = map.size + val containedKeyBefore = map.contains(k) + val newExpectedSize = if(containedKeyBefore) oldSize - 1 else oldSize + + val mapView = map.rangeImpl(from, until) + mapView -= k + + !map.contains(k) && map.get(k) == None && map.size == newExpectedSize && + !mapView.contains(k) && + mapView.get(k) == None + } + + property("--=") = forAll { (map: mutable.TreeMap[K, V], ks: Seq[K], from: Option[K], until: Option[K]) => + val mapView = map.rangeImpl(from, until) + mapView --= ks + ks.toSet.forall { k => map.get(k) == None && mapView.get(k) == None } + } + + property("iterator") = forAll { (entries: Map[K, V], from: Option[K], until: Option[K]) => + val map = mutable.TreeMap[K, V]() + map ++= entries + + val mapView = map.rangeImpl(from, until) + mapView.iterator.toSeq == entriesInView(entries, from, until).toSeq.sorted + } + + property("iteratorFrom") = forAll { (entries: Map[K, V], k: K, from: Option[K], until: Option[K]) => + val map = mutable.TreeMap[K, V]() + map ++= entries + + val mapView = map.rangeImpl(from, until) + val newLower = Some(from.fold(k)(ord.max(_, k))) + mapView.iteratorFrom(k).toSeq == entriesInView(entries, newLower, until).toSeq.sorted + } + + property("keysIteratorFrom") = forAll { (entries: Map[K, V], k: K, from: Option[K], until: Option[K]) => + val map = mutable.TreeMap[K, V]() + map ++= entries + + val mapView = map.rangeImpl(from, until) + val newLower = Some(from.fold(k)(ord.max(_, k))) + mapView.keysIteratorFrom(k).toSeq == entriesInView(entries, newLower, until).toSeq.sorted.map(_._1) + } + + property("valuesIteratorFrom") = forAll { (entries: Map[K, V], k: K, from: Option[K], until: Option[K]) => + val map = mutable.TreeMap[K, V]() + map ++= entries + + val mapView = map.rangeImpl(from, until) + val newLower = Some(from.fold(k)(ord.max(_, k))) + mapView.valuesIteratorFrom(k).toSeq == entriesInView(entries, newLower, until).toSeq.sorted.map(_._2) + } + + property("headOption") = forAll { (map: mutable.TreeMap[K, V], from: Option[K], until: Option[K]) => + val mapView = map.rangeImpl(from, until) + mapView.headOption == Try(entriesInView(map.iterator, from, until).next()).toOption + } + + property("lastOption") = forAll { (map: mutable.TreeMap[K, V], from: Option[K], until: Option[K]) => + val mapView = map.rangeImpl(from, until) + mapView.lastOption == Try(entriesInView(map.iterator, from, until).max).toOption + } + + property("clear") = forAll { (map: mutable.TreeMap[K, V], from: Option[K], until: Option[K]) => + val mapView = map.rangeImpl(from, until) + mapView.clear() + map.isEmpty && mapView.isEmpty && map.size == 0 && mapView.size == 0 + } + + property("serializable") = forAll { (map: mutable.TreeMap[K, V], from: Option[K], until: Option[K]) => + val mapView = map.rangeImpl(from, until) + + val bytesOut = new ByteArrayOutputStream() + val out = new ObjectOutputStream(bytesOut) + out.writeObject(mapView) + val bytes = bytesOut.toByteArray + + val in = new ObjectInputStream(new ByteArrayInputStream(bytes)) + val sameMapView = in.readObject().asInstanceOf[mutable.TreeMap[K, V]] + mapView.iterator.toSeq == sameMapView.iterator.toSeq + } + } +} + +object Test extends Properties("mutable.TreeMap") { + import scala.collection.mutable._ + include(RedBlackTreeProperties) + include(MutableTreeMapProperties) + include(MutableTreeMapViewProperties) +} diff --git a/test/files/scalacheck/MutableTreeSet.scala b/test/files/scalacheck/MutableTreeSet.scala new file mode 100644 index 0000000000..bcb1d0ed94 --- /dev/null +++ b/test/files/scalacheck/MutableTreeSet.scala @@ -0,0 +1,216 @@ +import java.io._ + +import org.scalacheck._ +import org.scalacheck.Arbitrary._ +import org.scalacheck.Prop.forAll + +import scala.collection.generic.CanBuildFrom +import scala.collection.immutable +import scala.collection.mutable +import scala.util.Try + +package scala.collection.mutable { + + object MutableTreeSetProperties extends Properties("mutable.TreeSet") { + type K = String + + property("size, isEmpty") = forAll { (elems: Set[K]) => + val set = mutable.TreeSet[K]() + set ++= elems + set.size == elems.size && set.isEmpty == elems.isEmpty + } + + property("+=") = forAll { (set: mutable.TreeSet[K], k: K) => + val oldSize = set.size + val containedKeyBefore = set.contains(k) + val newExpectedSize = if(containedKeyBefore) oldSize else oldSize + 1 + + set += k + set.contains(k) && set.size == newExpectedSize + } + + property("++=") = forAll { (set: mutable.TreeSet[K], ks: Seq[K]) => + val oldElems = set.toList + set ++= ks + (oldElems ++ ks).forall(set.contains) + } + + property("-=") = forAll { (set: mutable.TreeSet[K], k: K) => + val oldSize = set.size + val containedKeyBefore = set.contains(k) + val newExpectedSize = if(containedKeyBefore) oldSize - 1 else oldSize + + set -= k + !set.contains(k) && set.size == newExpectedSize + } + + property("--=") = forAll { (set: mutable.TreeSet[K], ks: Seq[K]) => + val oldElems = set.toList + set --= ks + val deletedElems = ks.toSet + oldElems.forall { e => set.contains(e) == !deletedElems(e) } + } + + property("iterator") = forAll { (ks: Set[K]) => + val set = mutable.TreeSet[K]() + set ++= ks + + set.iterator.toSeq == ks.toSeq.sorted + } + + property("iteratorFrom, keysIteratorFrom") = forAll { (ks: Set[K], k: K) => + val set = mutable.TreeSet[K]() + set ++= ks + + set.iteratorFrom(k).toSeq == ks.filter(_ >= k).toSeq.sorted + set.keysIteratorFrom(k).toSeq == ks.filter(_ >= k).toSeq.sorted + } + + property("headOption") = forAll { (set: mutable.TreeSet[K]) => + set.headOption == Try(set.iterator.next()).toOption + } + + property("lastOption") = forAll { (set: mutable.TreeSet[K]) => + set.lastOption == Try(set.iterator.max).toOption + } + + property("clear") = forAll { (set: mutable.TreeSet[K]) => + set.clear() + set.isEmpty && set.size == 0 + } + + property("serializable") = forAll { (set: mutable.TreeSet[K]) => + val bytesOut = new ByteArrayOutputStream() + val out = new ObjectOutputStream(bytesOut) + out.writeObject(set) + val bytes = bytesOut.toByteArray + + val in = new ObjectInputStream(new ByteArrayInputStream(bytes)) + val sameSet = in.readObject().asInstanceOf[mutable.TreeSet[K]] + set.iterator.toSeq == sameSet.iterator.toSeq + } + + property("same behavior as immutable.TreeMap") = forAll { ops: Seq[Either[K, K]] => + var iset = immutable.TreeSet[K]() + val mset = mutable.TreeSet[K]() + + ops.foreach { + case Left(k) => iset += k; mset += k + case Right(k) => iset -= k; mset -= k + } + + iset.toList == mset.toList + } + } + + object MutableTreeSetViewProperties extends Properties("mutable.TreeSetView") { + type K = String + + implicit val ord = implicitly[Ordering[K]] + + def in(key: K, from: Option[K], until: Option[K]) = + from.fold(true)(_ <= key) && until.fold(true)(_ > key) + + def keysInView[This <: TraversableOnce[K], That](keys: This, from: Option[K], until: Option[K])(implicit bf: CanBuildFrom[This, K, That]) = { + (bf.apply(keys) ++= keys.filter(in(_, from, until))).result() + } + + property("size, isEmpty") = forAll { (keys: Set[K], from: Option[K], until: Option[K]) => + val map = mutable.TreeSet[K]() + map ++= keys + + val mapView = map.rangeImpl(from, until) + mapView.size == keysInView(keys, from, until).size && + mapView.isEmpty == !keys.exists(in(_, from, until)) + } + + property("+=") = forAll { (set: mutable.TreeSet[K], k: K, from: Option[K], until: Option[K]) => + val oldSize = set.size + val containedKeyBefore = set.contains(k) + val newExpectedSize = if(containedKeyBefore) oldSize else oldSize + 1 + val isInRange = in(k, from, until) + + val setView = set.rangeImpl(from, until) + setView += k + + set.contains(k) && set.size == newExpectedSize && setView.contains(k) == isInRange + } + + property("++=") = forAll { (set: mutable.TreeSet[K], ks: Seq[K], from: Option[K], until: Option[K]) => + val setView = set.rangeImpl(from, until) + setView ++= ks + ks.toSet.forall { k => + set.contains(k) && setView.contains(k) == in(k, from, until) + } + } + + property("-=") = forAll { (set: mutable.TreeSet[K], k: K, from: Option[K], until: Option[K]) => + val oldSize = set.size + val containedKeyBefore = set.contains(k) + val newExpectedSize = if(containedKeyBefore) oldSize - 1 else oldSize + + val setView = set.rangeImpl(from, until) + setView -= k + + !set.contains(k) && set.size == newExpectedSize && !setView.contains(k) + } + + property("--=") = forAll { (set: mutable.TreeSet[K], ks: Seq[K], from: Option[K], until: Option[K]) => + val setView = set.rangeImpl(from, until) + setView --= ks + ks.toSet.forall { k => !set.contains(k) && !setView.contains(k) } + } + + property("iterator") = forAll { (ks: Set[K], from: Option[K], until: Option[K]) => + val set = mutable.TreeSet[K]() + set ++= ks + + val setView = set.rangeImpl(from, until) + setView.iterator.toSeq == keysInView(ks, from, until).toSeq.sorted + } + + property("iteratorFrom, keysIteratorFrom") = forAll { (ks: Set[K], k: K, from: Option[K], until: Option[K]) => + val set = mutable.TreeSet[K]() + set ++= ks + + val setView = set.rangeImpl(from, until) + val newLower = Some(from.fold(k)(ord.max(_, k))) + setView.iteratorFrom(k).toSeq == keysInView(ks, newLower, until).toSeq.sorted + } + + property("headOption") = forAll { (set: mutable.TreeSet[K], from: Option[K], until: Option[K]) => + val setView = set.rangeImpl(from, until) + setView.headOption == Try(keysInView(set.iterator, from, until).next()).toOption + } + + property("lastOption") = forAll { (set: mutable.TreeSet[K], from: Option[K], until: Option[K]) => + val setView = set.rangeImpl(from, until) + setView.lastOption == Try(keysInView(set.iterator, from, until).max).toOption + } + + property("clear") = forAll { (set: mutable.TreeSet[K], from: Option[K], until: Option[K]) => + val setView = set.rangeImpl(from, until) + setView.clear() + set.isEmpty && setView.isEmpty && set.size == 0 && setView.size == 0 + } + + property("serializable") = forAll { (set: mutable.TreeSet[K], from: Option[K], until: Option[K]) => + val setView = set.rangeImpl(from, until) + + val bytesOut = new ByteArrayOutputStream() + val out = new ObjectOutputStream(bytesOut) + out.writeObject(setView) + val bytes = bytesOut.toByteArray + + val in = new ObjectInputStream(new ByteArrayInputStream(bytes)) + val sameSetView = in.readObject().asInstanceOf[mutable.TreeSet[K]] + setView.iterator.toSeq == sameSetView.iterator.toSeq + } + } +} + +object Test extends Properties("mutable.TreeSet") { + import scala.collection.mutable._ + include(MutableTreeSetProperties) + include(MutableTreeSetViewProperties) +} diff --git a/test/files/scalacheck/avl.scala b/test/files/scalacheck/avl.scala deleted file mode 100644 index 4cfacaf407..0000000000 --- a/test/files/scalacheck/avl.scala +++ /dev/null @@ -1,112 +0,0 @@ -import org.scalacheck.Gen -import org.scalacheck.Prop.forAll -import org.scalacheck.Properties - -package scala.collection.mutable { - - /** - * Property of an AVL Tree : Any node of the tree has a balance value beetween in [-1; 1] - */ - abstract class AVLTreeTest(name: String) extends Properties(name) { - - def `2^`(n: Int) = (1 to n).fold(1)((a, b) => b*2) - - def capacityMax(depth: Int): Int = `2^`(depth+1) - 1 - - def minDepthForCapacity(x: Int): Int = { - var depth = 0 - while(capacityMax(depth) < x) - depth += 1 - depth - } - - def numberOfElementsInLeftSubTree(n: Int): collection.immutable.IndexedSeq[Int] = { - val mid = n/2 + n%2 - ((1 until mid) - .filter { i => math.abs(minDepthForCapacity(i) - minDepthForCapacity(n-i)) < 2 } - .flatMap { i => Seq(i, n-(i+1)) }).toIndexedSeq.distinct - } - - def makeAllBalancedTree[A](elements: List[A]): List[AVLTree[A]] = elements match { - case Nil => Leaf::Nil - case first::Nil => Node(first, Leaf, Leaf)::Nil - case first::second::Nil => Node(second, Node(first, Leaf, Leaf), Leaf)::Node(first, Leaf, Node(second, Leaf, Leaf))::Nil - case first::second::third::Nil => Node(second, Node(first, Leaf, Leaf), Node(third, Leaf, Leaf))::Nil - case _ => { - val combinations = for { - left <- numberOfElementsInLeftSubTree(elements.size) - root = elements(left) - right = elements.size - (left + 1) - } yield (root, left, right) - (combinations.flatMap(triple => for { - l <- makeAllBalancedTree(elements.take(triple._2)) - r <- makeAllBalancedTree(elements.takeRight(triple._3)) - } yield Node(triple._1, l, r))).toList - } - } - - def genInput: org.scalacheck.Gen[(Int, List[AVLTree[Int]])] = for { - size <- org.scalacheck.Gen.choose(20, 25) - elements <- org.scalacheck.Gen.listOfN(size, org.scalacheck.Gen.choose(0, 1000)) - selected <- org.scalacheck.Gen.choose(0, 1000) - } yield { - // selected mustn't be in elements already - val list = makeAllBalancedTree(elements.sorted.distinct.map(_*2)) - (selected*2+1, list) - } - - def genInputDelete: org.scalacheck.Gen[(Int, List[AVLTree[Int]])] = for { - size <- org.scalacheck.Gen.choose(20, 25) - elements <- org.scalacheck.Gen.listOfN(size, org.scalacheck.Gen.choose(0, 1000)) - e = elements.sorted.distinct - selected <- org.scalacheck.Gen.choose(0, e.size-1) - } yield { - // selected must be in elements already - val list = makeAllBalancedTree(e) - (e(selected), list) - } - } - - trait AVLInvariants { - self: AVLTreeTest => - - def isBalanced[A](t: AVLTree[A]): Boolean = t match { - case node: Node[A] => math.abs(node.balance) < 2 && (List(node.left, node.right) forall isBalanced) - case Leaf => true - } - - def setup(invariant: AVLTree[Int] => Boolean) = forAll(genInput) { - case (selected: Int, trees: List[AVLTree[Int]]) => - trees.map(tree => invariant(tree)).fold(true)((a, b) => a && b) - } - - property("Every tree is initially balanced.") = setup(isBalanced) - } - - object TestInsert extends AVLTreeTest("Insert") with AVLInvariants { - import math.Ordering.Int - property("`insert` creates a new tree containing the given element. The tree remains balanced.") = forAll(genInput) { - case (selected: Int, trees: List[AVLTree[Int]]) => - trees.map(tree => { - val modifiedTree = tree.insert(selected, Int) - modifiedTree.contains(selected, Int) && isBalanced(modifiedTree) - }).fold(true)((a, b) => a && b) - } - } - - object TestRemove extends AVLTreeTest("Remove") with AVLInvariants { - import math.Ordering.Int - property("`remove` creates a new tree without the given element. The tree remains balanced.") = forAll(genInputDelete) { - case (selected: Int, trees: List[AVLTree[Int]]) => - trees.map(tree => { - val modifiedTree = tree.remove(selected, Int) - tree.contains(selected, Int) && !modifiedTree.contains(selected, Int) && isBalanced(modifiedTree) - }).fold(true)((a, b) => a && b) - } - } -} - -object Test extends Properties("AVL") { - include(scala.collection.mutable.TestInsert) - include(scala.collection.mutable.TestRemove) -} diff --git a/test/files/scalacheck/concurrent-map.scala b/test/files/scalacheck/concurrent-map.scala new file mode 100755 index 0000000000..7c9b8d4169 --- /dev/null +++ b/test/files/scalacheck/concurrent-map.scala @@ -0,0 +1,76 @@ + + + +import java.util.concurrent._ +import scala.collection._ +import scala.collection.JavaConverters._ +import org.scalacheck._ +import org.scalacheck.Prop._ +import org.scalacheck.Gen._ + + + +case class Wrap(i: Int) { + override def hashCode = i * 0x9e3775cd +} + + +object Test extends Properties("concurrent.TrieMap") { + + /* generators */ + + val sizes = choose(0, 20000) + + val threadCounts = choose(2, 16) + + val threadCountsAndSizes = for { + p <- threadCounts + sz <- sizes + } yield (p, sz); + + + /* helpers */ + + def inParallel[T](totalThreads: Int)(body: Int => T): Seq[T] = { + val threads = for (idx <- 0 until totalThreads) yield new Thread { + setName("ParThread-" + idx) + private var res: T = _ + override def run() { + res = body(idx) + } + def result = { + this.join() + res + } + } + + threads foreach (_.start()) + threads map (_.result) + } + + property("concurrent getOrElseUpdate insertions") = forAll(threadCounts, sizes) { + (p, sz) => + val chm = new ConcurrentHashMap[Wrap, Int]().asScala + + val results = inParallel(p) { + idx => + for (i <- 0 until sz) yield chm.getOrElseUpdate(new Wrap(i), idx) + } + + val resultSets = for (i <- 0 until sz) yield results.map(_(i)).toSet + val largerThanOne = resultSets.zipWithIndex.find(_._1.size != 1) + val allThreadsAgreeOnWhoInserted = { + largerThanOne == None + } :| s"$p threads agree on who inserted [disagreement (differentResults, position) = $largerThanOne]" + + allThreadsAgreeOnWhoInserted + } + + +} + + + + + + diff --git a/test/files/scalacheck/parallel-collections/ParallelRangeCheck.scala b/test/files/scalacheck/parallel-collections/ParallelRangeCheck.scala index f490d9490a..a80d1a27a1 100644 --- a/test/files/scalacheck/parallel-collections/ParallelRangeCheck.scala +++ b/test/files/scalacheck/parallel-collections/ParallelRangeCheck.scala @@ -27,7 +27,7 @@ class ParallelRangeCheck(val tasksupport: TaskSupport) extends ParallelSeqCheck[ def isCheckingViews = false - def ofSize(vals: Seq[Gen[Int]], sz: Int) = unsupported + def ofSize(vals: Seq[Gen[Int]], sz: Int) = throw new UnsupportedOperationException override def instances(vals: Seq[Gen[Int]]): Gen[Seq[Int]] = sized { start => sized { end => diff --git a/test/files/scalacheck/quasiquotes/TypecheckedProps.scala b/test/files/scalacheck/quasiquotes/TypecheckedProps.scala index f84df269ca..2c4d81f333 100644 --- a/test/files/scalacheck/quasiquotes/TypecheckedProps.scala +++ b/test/files/scalacheck/quasiquotes/TypecheckedProps.scala @@ -167,7 +167,7 @@ trait TypecheckedTypes { self: QuasiquoteProperties => property("applied type") = test { val tt = typecheckTyp(tq"Map[Int, Int]") val tq"$tpt[..$tpts]" = tt - val tq"scala.this.Predef.Map" = tpt + val tq"scala.Predef.Map" = tpt val List(tq"scala.Int", tq"scala.Int") = tpts } |