aboutsummaryrefslogtreecommitdiff
path: root/lab1/src/main/scala/jsy/lab1/Lab1.scala
diff options
context:
space:
mode:
Diffstat (limited to 'lab1/src/main/scala/jsy/lab1/Lab1.scala')
-rw-r--r--lab1/src/main/scala/jsy/lab1/Lab1.scala115
1 files changed, 115 insertions, 0 deletions
diff --git a/lab1/src/main/scala/jsy/lab1/Lab1.scala b/lab1/src/main/scala/jsy/lab1/Lab1.scala
new file mode 100644
index 0000000..d3a73b1
--- /dev/null
+++ b/lab1/src/main/scala/jsy/lab1/Lab1.scala
@@ -0,0 +1,115 @@
+package jsy.lab1
+
+object Lab1 {
+ /*
+ * CSCI 3155: Lab 1
+ * Jack Sangdahl
+ * 09 September 2024
+ *
+ * Partner: N/A
+ * Collaborators: N/A
+ */
+
+ /* Example: Test-driven development of `plus` */
+
+ def plus(x: Int, y: Int): Int = x + y
+
+ /* Exercises */
+
+ def repeat(s: String, n: Int): String = {
+ require(n >= 0)
+ if (n == 0) ""
+ else s + repeat(s, n - 1)
+ }
+
+ def sqrtStep(c: Double, xn: Double): Double = {
+ val n = (xn * xn) - c
+ val d = 2 * xn
+ xn - (n / d)
+ }
+
+ def sqrtN(c: Double, x0: Double, n: Int): Double = {
+ require(n >= 0 && c >= 0)
+ if (n == 0) x0
+ else sqrtN(c, sqrtStep(c, x0), n - 1)
+ }
+
+ def sqrtErr(c: Double, x0: Double, epsilon: Double): Double = {
+ require(epsilon > 0)
+ val next = sqrtStep(c, x0)
+ if (Math.abs((x0 * x0) - c) < epsilon) x0
+ else sqrtErr(c, next, epsilon)
+ }
+
+ def sqrt(c: Double): Double = {
+ require(c >= 0)
+ if (c == 0) 0 else sqrtErr(c, 1.0, 0.0001)
+ }
+
+ /* Search Tree */
+
+ sealed abstract class Tree
+ case object Empty extends Tree
+ case class Node(l: Tree, d: Int, r: Tree) extends Tree
+
+ def repOk(t: Tree): Boolean = {
+ def check(t: Tree, min: Int, max: Int): Boolean = t match {
+ case Empty => true
+ case Node(l, d, r) =>
+ d >= min && d < max && check(l, min, d) && check(r, d, max)
+ }
+ check(t, Int.MinValue, Int.MaxValue)
+ }
+
+ def insert(t: Tree, n: Int): Tree = t match {
+ case Empty => Node(Empty, n, Empty)
+ case Node(l, d, r) =>
+ if (n < d) Node(insert(l, n), d, r)
+ else Node(l, d, insert(r, n))
+ }
+
+ def deleteMin(t: Tree): (Tree, Int) = {
+ require(t != Empty)
+ (t: @unchecked) match {
+ case Node(Empty, d, r) => (r, d)
+ case Node(l, d, r) =>
+ val (l1, m) = deleteMin(l)
+ (Node(l1, d, r), m)
+ }
+ }
+
+ def delete(t: Tree, n: Int): Tree = t match {
+ case Empty => Empty
+ case Node(l, d, r) =>
+ if (n < d) Node(delete(l, n), d, r)
+ else if (n > d) Node(l, d, delete(r, n))
+ else if (l == Empty) r
+ else if (r == Empty) l
+ else {
+ val (r1, min) = deleteMin(r)
+ Node(l, min, r1)
+ }
+ }
+ /* Evaluate the JavaScripty Calculator Language */
+
+ /* We import `jsy.lab1.ast._` so that we can make use of the Expr type defined
+ * there. Take a look at ast.scala to see what the Expr type looks like, as well
+ * some helper functions for defining values (`isValue`) and pretty-printing
+ * (`pretty`) that you are welcome to use.
+ */
+ import jsy.lab1.ast._
+
+ def eval(e: Expr): Double = e match {
+ case N(n) => n
+ case Unary(Neg, e1) => -eval(e1)
+ case Binary(Plus, e1, e2) => eval(e1) + eval(e2)
+ case Binary(Minus, e1, e2) => eval(e1) - eval(e2)
+ case Binary(Times, e1, e2) => eval(e1) * eval(e2)
+ case Binary(Div, e1, e2) => eval(e1) / eval(e2)
+ }
+
+ /* We also overload `eval` to take a String and parse it into an Expr and then
+ * evaluate it using your `eval` function defined above.
+ */
+ def eval(e: String): Double = eval(Parser.parse(e))
+}