structure Tests =
struct

  type point = int * int
  type box = (int * int) * (int * int)

	fun rng s = ((s * 991) + 1) mod 5711

	structure Seq = ArraySequence

	(*Tweak these numbers*)
	val seed = 15210       (*Seed for RNG*)
	val points=10          (*Number of points*)
	val pointRange = 20    (*x and y coordinates will come from range*)
	val pointBias=10       (*Range is [0-pointBias,pointRange-pointBias)*)
	val weightRange = 100
	val bias = 50          (*Generated weight is from [0-bias,weightRange-bias) *)
	val tests = 100000     (*Number of tests run*)

	fun nums n = Seq.tabulate(fn i=>i-pointBias)(pointRange)

	fun shuffle S 0 s = (S,s)
	  | shuffle S i s =
		let
			val s' = rng s
			val ind = s' mod i
			val v = Seq.nth(S)(i-1)
			val S' = Seq.update(S,(i-1,Seq.nth(S)(ind)))
			val S'' = Seq.update(S',(ind,v))
		in
			shuffle S'' (i-1) s'
		end

	fun randW(s) =
		let
			val s' = rng s
		in
			((s' mod weightRange) - bias,s')
		end

	fun genPoints xl yl 0 s = ([],s)
	  | genPoints [] _ _ _ = raise Fail "List empty"
	  | genPoints _ [] _ _ = raise Fail "List empty"
	  | genPoints (x::xl) (y::yl) i s =
				let
					val (w,s') = randW(s)
					val (L,s'') = genPoints xl yl (i-1) s'
				in
					(((x,y),w)::L,s'')
				end

	fun genBox s =
		let
			val s1 = rng s
			val x1 = (s1 mod (pointRange+3))-pointBias-1
			val s2 = rng s1
			val y1 = (s2 mod (pointRange+3))-pointBias-1
			val s3 = rng s2
			val x2 = (s3 mod (pointRange+3))-pointBias-1
			val s4 = rng s3
			val y2 = (s4 mod (pointRange+3))-pointBias-1
			val s5 = rng s4
		in
			if x1=x2 orelse y1=y2 then
				genBox s5
			else
				(((Int.min(x1,x2),Int.max(y1,y2)),(Int.max(x1,x2),Int.min(y1,y2))),s5)
		end

	fun gen 0 s = ([],s)
	  | gen n s =
				let
					val s1 = rng s
					val (L,s2) = gen (n-1) s1
					val (xs,s3) = shuffle(nums points)(points)(s2)
					val (ys,s4) = shuffle(nums points)(points)(s3)
					val xl = Seq.toList(xs)
					val yl = Seq.toList(ys)
					val (points,s5) = genPoints xl yl points s4
					val (box,s6) = genBox s5
				in
					((points,box)::L,s6)
				end

  (* Each value is ((x, y), w), with x, y coordinates in a 2D space and w the
   * weight given to this point *)
  val points1 = [((0,0),2),((1,2),5),((3,3),7),((4,4),3),((5,1),9)]

  (* Each test is (points, box), where correctness is verified by calling
   * (rangeSum (Seq.fromList points) box) and comparing it with the result of
   * our reference solution. *)
	val (L,_) = (gen tests seed)

  val tests : ((point * int) list * box) list = [
    (points1, ((1,3),(5,1)))
	] @ L

end