Elixir/test/data_structures/seg_tree_test.exs at 41cea21cd76631214d53dda87f822e7e7a21cc98 · TheAlgorithms/Elixir · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
defmodule Algorithms.DataStructures.SegTreeTest do
  use ExUnit.Case

  alias Algorithms.DataStructures.SegTree

  describe "Segment Tree basic functionality" do
    setup do
      op = fn a, b -> min(a, b) end
      e = fn -> :infinity end

      seg = SegTree.new([5, 3, 7, 9, 6], op, e)
      %{seg: seg, op: op, e: e}
    end

    test "prod returns correct range minimum", %{seg: seg} do
      assert SegTree.prod(seg, 0, 5) == 3
      assert SegTree.prod(seg, 1, 4) == 3
      assert SegTree.prod(seg, 2, 4) == 7
    end

    test "get returns correct value", %{seg: seg} do
      assert SegTree.get(seg, 0) == 5
      assert SegTree.get(seg, 1) == 3
      assert SegTree.get(seg, 4) == 6
    end

    test "set updates value and affects prod", %{seg: seg} do
      seg = SegTree.set(seg, 1, 10)
      assert SegTree.get(seg, 1) == 10
      assert SegTree.prod(seg, 0, 5) == 5

      seg = SegTree.set(seg, 0, 1)
      assert SegTree.prod(seg, 0, 5) == 1
    end

    test "all_prod returns correct result", %{seg: seg} do
      assert SegTree.all_prod(seg) == 3
    end
  end

  describe "Segment Tree with sum operation" do
    setup do
      op = fn a, b -> a + b end
      e = fn -> 0 end

      seg = SegTree.new([1, 2, 3, 4, 5], op, e)
      %{seg: seg}
    end

    test "prod returns correct range sum", %{seg: seg} do
      assert SegTree.prod(seg, 0, 5) == 15
      assert SegTree.prod(seg, 1, 3) == 5
      assert SegTree.prod(seg, 2, 4) == 7
    end
  end
end