<commit_before>package org.tmoerman.lab

import org.scalatest.{Matchers, FlatSpec}

import scalaz.Tree._
import scalaz._
import Scalaz._
import scalaz.syntax._

/**
  * @author <NAME>
  */
class TreeLab extends FlatSpec with Matchers with ToTreeOps {

  sealed trait Orientation
  case object L extends Orientation
  case object R extends Orientation

  case class Interval[@specialized(Int, Double) T](val o: Orientation,
                                                   val lo: T,
                                                   val hi: T,
                                                   val v:  T) {

    def intersectsWith(that: Interval[T]): Boolean = ???

  }

  val myTree =
    Interval(L, 17, 19, 24).node(
      Interval(L, 5, 8, 18).node(
        Interval(L, 4, 8, 8).leaf,
        Interval(R, 15, 18, 18).node(
          Interval(L, 7, 10, 10).leaf)),
      Interval(R, 21, 24, 24).leaf)

  /**
    * See video by <NAME> https://www.youtube.com/watch?v=q0QOYtSsTg4
    *
    * @param query Interval to find intersections with.
    * @param tree The tree of Intervals that is queried.
    * @tparam T Generic type
    * @return Returns an Iterable of Intervals in the tree that intersect the query Interval.
    */
  def search[@specialized(Int, Double) T](query: Interval[T], tree: Tree[Interval[T]]): Iterable[Interval[T]] = {

    val zipperAtRoot: TreeLoc[Interval[T]] = tree.loc.firstChild.get



    ???
  }

  behavior of "interval tree"

  it should "meh" in {

    val zipper = myTree.loc

    zipper.firstChild.get.toTree.rootLabel  shouldBe Interval(L, 17, 19, 24)

    zipper.lastChild.get.toTree.rootLabel   shouldBe Interval(L, 17, 19, 24)

    zipper.getChild(1).get.toTree.rootLabel shouldBe Interval(L, 17, 19, 24)

  }

  it should "be searchable for intersections" in {

    

  }

}<commit_msg>query an Interval Tree for all intersecting intervals recursively<commit_after>package org.tmoerman.lab

import org.scalatest.{FlatSpec, Matchers}

import scalaz._
import scalaz.syntax._

/**
  * @author <NAME>
  */
class TreeLab extends FlatSpec with Matchers with ToTreeOps {

  sealed trait Orientation
  case object ? extends Orientation
  case object L extends Orientation
  case object R extends Orientation

  case class Interval[T](val o: Orientation,
                         val lo: T,
                         val hi: T,
                         val max:  T) {

  }

  case object Interval {

    def apply[T](lo: T, hi: T): Interval[T] = Interval(?, lo, hi, hi)

  }

  def intersects[T](a: Interval[T], b: Interval[T])(implicit num: Numeric[T]): Boolean = {
    import num._

    b.lo <= a.hi && a.lo <= b.hi
  }

  /**
    * See video by <NAME> https://www.youtube.com/watch?v=q0QOYtSsTg4
    *
    * Search algorithm:
    *
    *   - if interval in node intersects query, return it
    *   - else if left subtree is null, go right
    *   - else if max endpoint in left subtree is less than lo, go right
    *   - else go left
    *
    * @param query Interval to find intersections with.
    * @param tree The tree of Intervals that is queried.
    * @tparam T Generic type
    * @return Returns an Iterable of Intervals in the tree that intersect the query Interval.
    */
  def search[T](query: Interval[T], tree: Tree[Interval[T]])(implicit num: Numeric[T]): Iterable[Interval[T]] = {
    import num._

    def inner(zipOpt: Option[TreeLoc[Interval[T]]]): List[Interval[T]] = {

      zipOpt match {
        case Some(loc) => {
          val currentInterval = loc.getLabel

          val acc = if (intersects(currentInterval, query)) currentInterval :: Nil else Nil

          val leftOpt  = loc.findChild(_.loc.getLabel.o == L)
          val rightOpt = loc.findChild(_.loc.getLabel.o == R)

          leftOpt match {
            case None => acc ::: inner(rightOpt)

            case Some(left) => {
              if (left.getLabel.max < query.lo)
                acc ::: inner(rightOpt) // skip left tree
              else
                acc ::: inner(leftOpt) ::: inner(rightOpt)
            }
          }
        }

        case None => Nil
      }
    }

    inner(Some(tree.loc))
  }

  /**
    * Overloaded function to query on singular instance of T
    * @param query
    * @param tree
    * @param num
    * @tparam T
    * @return
    */
  def search[T](query: T, tree: Tree[Interval[T]])(implicit num: Numeric[T]): Iterable[Interval[T]] = search(Interval(query, query), tree)

  val myTree =
    Interval(?, 17, 19, 24).node(
      Interval(L, 5, 8, 18).node(
        Interval(L, 4, 8, 8).leaf,
        Interval(R, 15, 18, 18).node(
          Interval(L, 7, 10, 10).leaf)),
      Interval(R, 21, 24, 24).leaf)

  behavior of "Interval"

  it should "calculate intersections correctly" in {
    intersects(Interval(0, 2), Interval(5, 8)) shouldBe false

    intersects(Interval(0, 5), Interval(2, 8)) shouldBe true
    intersects(Interval(0, 8), Interval(2, 5)) shouldBe true
    intersects(Interval(2, 5), Interval(0, 8)) shouldBe true
    intersects(Interval(2, 8), Interval(0, 5)) shouldBe true

    intersects(Interval(5, 8), Interval(0, 2)) shouldBe(false)
  }

  behavior of "search"

  it should "find the intersections with a query interval" in {
    search(Interval(23, 25), myTree) shouldBe Interval(R,21,24,24) :: Nil

    search(Interval(7, 16), myTree) shouldBe Interval(L,5,8,18) :: Interval(L,4,8,8) :: Interval(R,15,18,18) :: Interval(L,7,10,10) :: Nil

    search(Interval(23,23), myTree) shouldBe Interval(R,21,24,24) :: Nil

    search(Interval(18, 21), myTree) shouldBe Interval(?,17,19,24) :: Interval(R,15,18,18) :: Interval(R,21,24,24) :: Nil
  }

  it should "find the intersections with a query value" in {
    search(18, myTree) shouldBe Interval(?,17,19,24) :: Interval(R,15,18,18) :: Nil
  }

}
{'fraction_non_alphanumeric': 0.1259502418797512, 'fraction_numerical': 0.03178991015894955, 'mean_word_length': 2.534188034188034, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 11, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '829053', 'n_tokens_mistral': 2102, 'n_tokens_neox': 1856, 'n_words': 545}