defmodule Dp.Tree do

  @moduledoc """
  Fák

  @author "hanak@emt.bme.hu"
  @date   "$LastChangedDate: 2024-10-07 14:00:10 +0200 (Mon, 07 Oct 2024) $$"
  """

  @type btree() :: :lf | {btree(), any(), btree()}
  @spec bt_to_list(btr :: btree()) :: xs :: [any()]
  # A btr fa preorder bejárásának eredménye az xs lista 
  def bt_to_list(:lf),         do: []
  def bt_to_list({bt, v, jt}), do: [ v | bt_to_list(bt) ] ++ bt_to_list(jt)

  @type ttree() :: :lf | {ttree(), ttree(), ttree(), any()}
  @spec tt_to_list(ttr :: ttree()) :: xs :: [any()]
  # A ttr fa preorder bejárásának eredménye az xs lista
  def tt_to_list(:lf),             do: []
  def tt_to_list({bt, mt, jt, v}), do: [ v | tt_to_list(bt) ] ++ tt_to_list(mt) ++ tt_to_list(jt)

  @type ltree() :: :lf | {any(), [ltree()]}
  @spec lt_to_list(ltr :: ltree()) :: xs :: [any()]
  # Az ltr fa preorder bejárásának eredménye az xs lista 
  def lt_to_list(:lf),     do: []
  # def lt_to_list({v, ts}), do: [ v | Enum.concat(Enum.map(ts, &lt_to_list/1)) ]
  def lt_to_list({v, ts}), do: [ v | ts |> (Enum.map &lt_to_list/1) |> Enum.concat ]

  ################
  #---------------
  ################
    
  @type btree2():: :lf | {any(), btree2(), btree2()}

  @spec empty() :: btr::(:lf)
  # btr az egyetlen levélből álló üres fa
  def empty(), do: :lf

  @spec node(v::any(), lt::btree2(), rt::btree2()) :: btr::btree2()
  # btr a v értékből, az lt és az rt fákból összerakott fa
  def node(v, lt, rt), do: {v, lt, rt}

  @spec depth(btr::btree2()) :: d::integer()
  # d a btr fa mélysége
  def depth(:lf),     do: 0
  def depth({_,lt,rt}), do: 1 + max(depth(lt), depth(rt))

  @spec leaves_cnt(btr::btree2()) :: n::integer()
  # n a btr fa leveleinek száma
  def leaves_cnt(:lf),     do: 1
  def leaves_cnt({_,lt,rt}), do: leaves_cnt(lt) + leaves_cnt(rt)

  @spec to_list_inord(btr::btree2()) :: xs::[any()]
  # A btr fa inorder bejárásának eredménye az xs lista
  def to_list_inord(:lf),     do: []
  def to_list_inord({v,lt,rt}), do:
        to_list_inord(lt) ++ ( [v] ++ to_list_inord(rt) )

  @spec to_list_preord(btr::btree2()) :: xs::[any()]
  # A btr fa preorder bejárásának eredménye az xs lista
  def to_list_preord(:lf),    do: []
  def to_list_preord({v,lt,rt}) do
        [v] ++ to_list_preord(lt) ++ to_list_preord(rt)
  end

  @spec from_list_inord(xs::[any()]) :: btr::btree2()
  # btr az xs listából inorder sorrendben felépített fa
  def from_list_inord([]), do: empty()
  def from_list_inord(xs)   do
    {ls1, [x|ls2]} = Enum.split(xs, div(length(xs), 2))
    node(x, from_list_inord(ls1), from_list_inord(ls2))
  end

  @spec from_list_preord(xs::[any()]) :: btr::btree2()
  # btr az xs listából preorder sorrendben felépített fa
  def from_list_preord([]),    do:    empty()
  def from_list_preord([x|xs]) do
    {ls1, ls2} = Enum.split(xs, div(length(xs), 2))
    node(x, from_list_preord(ls1), from_list_preord(ls2))
  end

  def test(0) do
    bt1 = {:lf,:a,:lf}
    bt2a = {
      {:lf,:c,:lf},
      :b,
      :lf
    }
    bt2b = {
      :lf,
      :e,
      {:lf,:f,:lf}
    }
    bt2c = {
      {:lf,:h,:lf},
      :g,
      {:lf,:i,:lf}
    }
    bt2 = {
      bt2a,
      :a,
      {
	bt2b,
	:d,
	bt2c
      }
    }
    tt1 = {:lf,:lf,:lf,:a}
    tt2a = {
      {:lf,:lf,:lf,:c},
      :lf,
      :lf,
      :b
    }
    tt2b = {
      :lf,
      {:lf,:lf,:lf,:f},
      :lf,
      :e
    }
    tt2c = {
      {:lf,:lf,:lf,:h},
      :lf,
      {:lf,:lf,:lf,:i},
      :g
    }
    tt2 = {
      tt2a,
      tt2b,
      tt2c,
      :a
    }
    lt1 =  {:a, []}
    lt2a = {:b, [{:c, [:lf,:lf,:lf]}, :lf, :lf]}
    lt2b = {:e, [:lf, {:f, [:lf,:lf,:lf]}, :lf]}
    lt2c = {:g, [{:h, [:lf,:lf,:lf]}, :lf, {:i, [:lf,:lf,:lf]}]}
    lt2 =  {:a, [lt2a, lt2b, lt2c]}
    [ bt_to_list(bt1),
      bt_to_list(bt2),
      tt_to_list(tt1),
      tt_to_list(tt2),
      lt_to_list(lt1),
      lt_to_list(lt2)
    ]
  end

  def test(1) do
    #                 1
    #             2       5
    #           3   4   6   7
    #          - - - - - - - -
    node(1,
      node(2,
        node(3,empty(),empty()),
        node(4,empty(),empty())
      ),
      node(5,
        node(6,empty(),empty()),
        node(7,empty(),empty())
      )
    )
  end
def test(2), do:
    from_list_inord([:a,:b,:c,:d,:e,:f,:g])
def test(3), do:
    to_list_inord(test(2))
def test(4), do:
    from_list_preord([:a,:b,:c,:d,:e,:f,:g])
def test(5), do:
    to_list_preord(test(4))

end