Diet

Diet is a Discrete Interval Encoding Tree. It stores subset of types that have a total order. The types are also required to have a successor and predecessor generator.

The discrete interval encoding tree is based on the observation that the set of integers { i | a<=i<=b } can be perfectly represented by the closed interval [a, b].

Diet is a binary search tree where each node contains a set of continuous values. If a value is inserted and it fills the hole between to nodes (sets) then the two set become one since all value in the new set are consecutive.

Best and Worst Case Analysis.

The best case is when there is no holes in the stored set, so the tree contains only one node (a single interval). In this case, it has O(1) space requirement, inserting, deleting and finding a value is in constant time.

In the worst case scenario, there is a hole of size one (1) between each node and each node is in fact a set on size one (1). Under these circumstances, operations in the tree required O(n).

Supported Operations

  • add: add a value to the tree
  • addRange: add the entire range to the tree
  • remove: remove a value from the tree
  • removeRange: remove a range from the tree
  • contains: verify is a value is on the tree
  • containsRange: verify that an interval is on the tree
  • (-) operator: remove a range from the tree
  • (&) operator: calculates the intersection with another Diet
  • (|) or (++) operator: calculates the union with another Diet
  • min: min value in the tree
  • max: max value in the tree
  • intervals: the list of all intervals (sets) in the tree. The sets are disjoint sets.
  • toList: list of sorted values in the tree

Diet is showable so we can call show on it.

Example usage:

Start by creating an empty Diet:

import cats._, cats.implicits._, cats.collections._, cats.collections.syntax.all._

val d: Diet[Int] = Diet.empty
// d: Diet[Int] = EmptyDiet
d.isEmpty
// res0: Boolean = true

d.show
// res1: String = "Diet( )"

And we can add an item:

val d2 = d.add(12)
// d2: Diet[Int] = DietNode(
//   focus = Range(start = 12, end = 12),
//   left = EmptyDiet,
//   right = EmptyDiet
// )
d2.isEmpty
// res2: Boolean = false

d2.show
// res3: String = "Diet( [12, 12] )"

And now we can check that it thinks 12 is in the set, but not other numbers

d2.contains(1)
// res4: Boolean = false
d2.contains(12)
// res5: Boolean = true

If we remove our only element, we get back to the empty Diet:

val d3 = d2.remove(12)
// d3: Diet[Int] = EmptyDiet
d3.isEmpty
// res6: Boolean = true

Asking to remove an element not in the set is a noop:

val s = Diet.empty[Int].remove(10)
// s: Diet[Int] = EmptyDiet

s.show
// res7: String = "Diet( )"

Diet excels at storing ranges, so there are also operations that work on ranges of values:

val d = Diet.empty[Int].addRange(1 toIncl 20)
// d: Diet[Int] = DietNode(
//   focus = Range(start = 1, end = 20),
//   left = EmptyDiet,
//   right = EmptyDiet
// )
d.contains(21)
// res8: Boolean = false
d.contains(20)
// res9: Boolean = true
d.contains(10)
// res10: Boolean = true

val d2 = d - (10 toIncl 12)
// d2: Diet[Int] = DietNode(
//   focus = Range(start = 1, end = 9),
//   left = EmptyDiet,
//   right = DietNode(
//     focus = Range(start = 13, end = 20),
//     left = EmptyDiet,
//     right = EmptyDiet
//   )
// )

d2.show
// res11: String = "Diet( [1, 9] [13, 20] )"

d2.contains(10)
// res12: Boolean = false
d2.containsRange(1 toIncl 5)
// res13: Boolean = true
d2.containsRange(11 toIncl 15) // fails since not the entire range is contained
// res14: Boolean = false

Given two Diets, we can find the union or the intersection:

val d1 = Diet.empty[Int] + (5 toIncl 10)
// d1: Diet[Int] = DietNode(
//   focus = Range(start = 5, end = 10),
//   left = EmptyDiet,
//   right = EmptyDiet
// )
val d2 = Diet.empty[Int] + (7 toIncl 12)
// d2: Diet[Int] = DietNode(
//   focus = Range(start = 7, end = 12),
//   left = EmptyDiet,
//   right = EmptyDiet
// )
(d1 & d2).show
// res15: String = "Diet( [7, 10] )"
(d1 | d2).show
// res16: String = "Diet( [5, 12] )"

Asking to remove non existing range yields the same diet

val d = Diet.empty[Int].addRange((5 toIncl 20))
// d: Diet[Int] = DietNode(
//   focus = Range(start = 5, end = 20),
//   left = EmptyDiet,
//   right = EmptyDiet
// )

val d1 = d.removeRange((1 toIncl 4))
// d1: Diet[Int] = DietNode(
//   focus = Range(start = 5, end = 20),
//   left = EmptyDiet,
//   right = EmptyDiet
// )
d1.show
// res17: String = "Diet( [5, 20] )"

Asking to remove a range yields a new Diet without the range

val d = Diet.empty[Int].addRange((5 toIncl 20)).addRange(22 toIncl 30)
// d: Diet[Int] = DietNode(
//   focus = Range(start = 5, end = 20),
//   left = EmptyDiet,
//   right = DietNode(
//     focus = Range(start = 22, end = 30),
//     left = EmptyDiet,
//     right = EmptyDiet
//   )
// )
val d2 = d.removeRange((5 toIncl 20))
// d2: Diet[Int] = DietNode(
//   focus = Range(start = 22, end = 30),
//   left = EmptyDiet,
//   right = EmptyDiet
// )

d2.show
// res18: String = "Diet( [22, 30] )"

Asking to remove a sub-range splits the Diet

val d = Diet.empty[Int].addRange((5 toIncl 20))
// d: Diet[Int] = DietNode(
//   focus = Range(start = 5, end = 20),
//   left = EmptyDiet,
//   right = EmptyDiet
// )
val d3 = d.removeRange((10 toIncl 15))
// d3: Diet[Int] = DietNode(
//   focus = Range(start = 5, end = 9),
//   left = EmptyDiet,
//   right = DietNode(
//     focus = Range(start = 16, end = 20),
//     left = EmptyDiet,
//     right = EmptyDiet
//   )
// )

(10 toIncl 15).toList.forall { i => d3.contains(i) }
// res19: Boolean = false
(5 toIncl 9).toList.forall {i => d3.contains(i) }
// res20: Boolean = true
(16 toIncl 20).toList.forall {i => d3.contains(i) }
// res21: Boolean = true

Adding a inverted range

val d = Diet.empty[Int] + Range(20, 10)
// d: Diet[Int] = DietNode(
//   focus = Range(start = 10, end = 20),
//   left = EmptyDiet,
//   right = EmptyDiet
// )

d.show
// res22: String = "Diet( [10, 20] )"