% Egy rekurziv fa tipus

% A rekurziv fa ugy ertendo, hogy a csomopontok teljesen egyformak,
% mindegyik reprezentalja az alatta levo reszfat, es a gyoker csak
% abban kulonbozik a tobbi csomoponttol, hogy nincs szuloje.
% Azaz egy csomopont ugyanolyan tipusu, mint egy egesz fa.

% Ennek a felepitesnek az az elonye, hogy egyszerre tetszolges szamu
% fa kezelheto, a fak kozott, vagy egy fan belul rugalmasan lehet
% reszfakat mozgatni, osszeolvasztani vagy szetvalasztani. Egy reszfan 
% pontosan ugy lehet muveleteket vegrehajtani, mint az egesz fan.
% Az eljarasok megvalositasa is rekurziv hivasokbol all ott, ahol
% egy reszfan kell muveletet vegrehajtani.
 
% Egy csomopont gyerekei kozott nincs meghatarozva valamifele sorrend,
% az egyetlen relacio a szulo-gyerek viszony. Minden muvelet ennek a 
% relacionak a kiterjesztese. (Pl. rendezeshez nem ilyen fat kell
% hasznalni.)

tree_type =  cluster [elem_type : type] is

  %%%%% Konstruktorok

  new,              % Letrehoz egy ures fat, gyoker van es van erteke
  new_child,        % Letrehoz egy gyereket, ertek van benne
  insert_to,        % Beilleszt egy reszfat egy csomopont ala
                    % (csak gyoker lehet, es nem illeszthet a sajat fajaba)
  extract,          % Kiemel egy reszfat a szuloje alol (csak gyerek lehet)
  move_to,          % Atvisz egy reszfat egy csomopont ala
                    % (nem illeszthet a sajat fajaba)
  set_value,        % A csomopont ertekenek felulirasa (tree.value := elem)

  %%%%% Fuggvenyek/iteraciok

  get_value,        % A csomopont erteke (elem := tree.value)
  is_root,          % Igaz, ha a csomopont gyoker
  root,             % A csomopont gyokere/faja
  is_parent_of,     % Igaz, ha a csomopont szuloje a masiknak
  parent,           % A csomopont szuloje/annak reszfaja (csak gyerek lehet)
  level,            % A csomopont szintje a fajaban/oseinek szama
  is_ancestor_of,   % Igaz, ha a csomopont ose a masiknak
  ancestors,        % A csomopont osei - iteracio
  is_empty,         % Igaz, ha a reszfa ures/csak gyoker/nincsenek gyerekei
  child_no,         % Csomopont gyerekeinek szama
  is_child_of,      % Igaz, ha a csomopont gyereke a masiknak
  children,         % Csomopont gyerekei/reszfai - iteracio
  size,             % Reszfa merete/csomopontok szama
  is_descendant_of, % Igaz, ha a csomopont utodja a masiknak      
  in_order,         % Reszfa csomopontjai in order bejarasban - iteracio
  pre_order,        % Reszfa csomopontjai pre order bejarasban - iteracio
  search,           % Egy ertek megkeresese a faban
  search_all,       % Egy ertek minden elofordulasanak megkeresese a faban
  search_by,        % Csomopontok, melyek teljesitik a feltetelt - iteracio

  %%%%% Standard muveletek

  equal, similar, copy,

  %%%%% Invarians teszteleshez

  invariant

  % A generalo tipusnak rendelkeznie kell egy equal (=) muvelettel
  % Erre csak a search es similar fuggvenyeknek van szuksege

  where elem_type has equal : proctype (elem_type, elem_type) returns (bool)

  %%%%% Reprezentacio

  rep = record[value : elem_type, parent, children : array[this]]
  this = tree_type[elem_type]

  %%%%% Konstruktorok

  % Letrehoz egy v gyokeru ures fat

  new = proc (v : elem_type) returns (this)

    return (up(rep${value : v,
                    parent : array[this]$new(),
                    children : array[this]$new()}))

  end new

  % Letrehoz egy v gyereket egy csomopont ala,
  % ezutan nem lesz ures, de a gyerek ures lesz

  new_child = proc (tree : this, v : elem_type) returns (this)

    tc : this := this$new(v)
    tc!insert_to(tree)
    return (tc)

  end new_child

  % A csomopont beillesztese a masik csomopont ala, ezzel gyerek lesz

  insert_to = proc (tree, ptree : this) signals (no_root, own_tree)

    if ~tree!is_root then signal no_root end
    if tree!is_ancestor_of(ptree) then signal own_tree end

    down(ptree).children!addh(tree)
    down(tree).parent!addh(ptree)

  end insert_to

  % A csomopont kivetele a szuloje alol, ezzel gyoker lesz

  extract = proc (tree : this) signals (is_root, bad_struct)

    if tree!is_root then signal is_root end

    ptree : this := tree!parent
    i : int := 1
    while i <= ptree!child_no cand ~down(ptree).children[i]!equal(tree) do
      i := i + 1
    end %while

    if i > ptree!child_no then signal bad_struct end

    while i < ptree!child_no do
      down(ptree).children[i] := down(ptree).children[i + 1]
      i := i + 1
    end %while
    ptree := down(ptree).children!remh
    ptree := down(tree).parent!remh

  end extract

  % A csomopont kivetele a szuloje alol, ha van,
  % es beillesztese a masik csomopont ala, ezzel gyerek lesz

  move_to = proc (tree, ptree : this) signals (own_tree)

    if tree!is_ancestor_of(ptree) then signal own_tree end

    if ~tree!is_root then
      tree!extract
    end %if
    tree!insert_to(ptree)

  end move_to

  % A csomopont ertekenek felulirasa

  set_value = proc (tree : this, e : elem_type)

    down(tree).value := e

  end set_value

  %%%%% Fuggvenyek/iteraciok

  % A csomopont erteke

  get_value = proc (tree : this) returns (elem_type)

    return (down(tree).value)

  end get_value

  % Ez a csomopont a gyoker?

  is_root = proc (tree : this) returns ( bool )

    return (down(tree).parent!empty)

  end is_root

  % A csomopont gyokere

  root = proc (tree : this) returns (this)

    t : this := tree
    while ~t!is_root do
      t := t!parent
    end %while
    return (t)

  end root

  % Ez a csomopont a szuloje a masiknak?

  is_parent_of = proc (tree, ctree : this) returns ( bool )

    return (~ctree!is_root cand tree = ctree!parent)

  end is_parent_of

  % A csomopont szuloje

  parent = proc (tree : this) returns (this) signals (is_root)

    if tree!is_root then signal is_root end

    return (down(tree).parent!top)

  end parent

  % A csomopont szintje a fajaban

  level = proc (tree : this) returns (int)

    l : int := 0
    for t : this in tree!ancestors do
      l := l + 1
    end %for
    return (l)

  end level

  % Ez a csomopont az ose a masiknak?

  is_ancestor_of = proc (tree, ctree : this) returns ( bool )

    for t : this in ctree!ancestors do
      if tree = t then
        return (true)
      end %if
    end %for
    return (false)

  end is_ancestor_of

  % A csomopont osei

  ancestors = iter (tree : this) yields (this)

    t : this := tree
    while ~t!is_root do
      t := t!parent
      yield (t)
    end %while

  end ancestors

  % A csomopontnak nincs gyereke?

  is_empty = proc (tree : this) returns (bool)

    return (down(tree).children!empty)

  end is_empty

  % A csomopont gyerekeinek szama

  child_no = proc (tree : this) returns (int)

    return (down(tree).children!size)

  end child_no

  % Ez a csomopont a gyereke a masiknak?

  is_child_of = proc (tree, ptree : this) returns ( bool )

    return (ptree!is_parent_of(tree))

  end is_child_of

  % A csomopont gyerekei

  children = iter (tree : this) yields (this)

    for t : this in down(tree).children!elements do
      yield (t)
    end %for

  end children

  % A csomopont reszfajanak merete

  size = proc (tree : this) returns (int)

    s : int := 1
    for t : this in tree!children do
      s := s + t!size
    end %for
    return (s)

  end size

  % Ez a csomopont az utodja a masiknak?

  is_descendant_of = proc (tree, ptree : this) returns ( bool )

    return (ptree!is_ancestor_of(tree))

  end is_descendant_of

  % A reszfa csomopontjai - in order

  in_order = iter (tree : this) yields (this)

    for t : this in tree!children do
      for tc : this in t!in_order do
        yield (tc)
      end %for
    end %for
    yield (tree)

  end in_order

  % A reszfa csomopontjai - pre order

  pre_order = iter (tree : this) yields (this)

    yield (tree)
    for t : this in tree!children do
      for tc : this in t!pre_order do
        yield (tc)
      end %for
    end %for

  end pre_order

  % Egy ertek megkeresese a faban

  search = proc (tree : this, v : elem_type) returns (this, bool)

    for t : this in tree!pre_order do
      if t.value = v then
        return (t, true)
      end %if
    end %for
    return (tree, false)

  end search

  % Egy ertek minden elofordulasanak megkeresese a faban

  search_all = iter (tree : this, v : elem_type) yields (this)

    for t : this in tree!pre_order do
      if t.value = v then
        yield (t)
      end %if
    end %for

  end search_all

  % Csomopontok, melyek teljesitik a feltetelt

  search_by = iter (tree : this, exp : proctype (this) returns (bool))
              yields (this)

    for t : this in tree!pre_order do
      if exp(t) then
        yield (t)
      end %if
    end %for

  end search_by

  %%%%% Standard muveletek

  % Igaz ha ugyanarra az objektumra mutatnak

  equal = proc (tree1, tree2 : this) returns (bool)

    return (down(tree1) = down(tree2))

  end equal

  % Igaz, ha szerkezetuk megegyezik es ugyanazokra az elemekre mutatnak

  similar = proc (tree1, tree2 : this) returns (bool)
    e1, e2 : int

    if tree1.value ~= tree2.value then return (false) end
    if tree1!child_no ~= tree2!child_no then return (false) end

    for t1 : this in tree1!children do
      e2 := 0
      for t2 : this in tree2!children do
        e2 := e2 + x(similar(t1, t2))
      end %for
      if e2 < 1 then
        return (false)
      end %if
      e1 := 0
      for t2 : this in tree1!children do
        e1 := e1 + x(similar(t1, t2))
      end %for
      if e1 ~= e2 then
        return (false)
      end %if
    end %for
    return (true)

  end similar

  % Keszit egy masolatot a szerkezetrol, az elemekrol nem

  copy = proc (tree : this) returns (this)

    t : this := this$new(tree.value)
    for tc : this in tree!children do
      tc!copy!insert_to(t)
    end %for
    return (t)

  end copy

  % Invarians ellenorzese a csomopontot tartalmazo fara
  % Azt kell ellenorizni, hogy a szulo-gyerek bejezesek stimmeljenek
  % Nem szuri ki, ha a fara van "kulso" hivatkozas
  % Parameterek: szulo fa, gyerek fa, hibauzenet
  % Ha csak egy csomopontban van gond, akkor a ket fa azonos
  % Nem hasznal ebben a tipusban megvalositott eljarast!

  invariant = proc (tree : this) signals (bad_struct(this, this, string))

    check_tree(check_ancestors(tree)) resignal bad_struct

  end invariant

  % Osok ellenorzese - a gyokeret adja vissza
  % Csak annyit ellenoriz, hogy a gyokerbol van-e hivatkozas ra,
  % s igy a teljes fa ellenorzese eljut majd hozza is

  check_ancestors = proc (tree : this) returns (this)
                    signals (bad_struct(this, this, string))

    if down(tree).parent!empty then
      return (tree)
    end %if
    for t : this in down(down(tree).parent!top).children!elements do
      if down(t) = down(tree) then
        return (check_ancestors(down(tree).parent!top)) resignal bad_struct
      end %if
    end %for 

    signal bad_struct(tree!parent, tree, "missing child in parent")

  end check_ancestors

  % Gyerekek ellenorzese
  % Reszletes ellenorzes

  check_tree = proc (tree : this) signals (bad_struct(this, this, string))
    tl : array[this]
    e : int

    tl := down(tree).parent
    if tl!low ~= 1 cor tl!high < 0 cor tl!high > 1 then
      signal bad_struct(tree, tree, "invalid parent list index")
    end %if 
    tl := down(tree).children
    if tl!low ~= 1 cor tl!high < 0 then
      signal bad_struct(tree, tree, "invalid children list index")
    end %if 
    for t1 : this in down(tree).children!elements do
      if down(t1).parent!empty cor
         down(down(t1).parent!top) ~= down(tree) then
        signal bad_struct(tree, t1, "invalid parent in child")
      end %if
      e := 0
      for t2 : this in down(tree).children!elements do
        e := e + x(down(t1) = down(t2))
      end %for
      if e ~= 1 then
        signal bad_struct(tree, t1, "multiplicated child in parent")
      end %if
      check_tree(t1) resignal bad_struct
    end %for 

  end check_tree

  % Logikai ertek karakterisztikus fuggvenye

  x = proc (b : bool) returns (int)
    if b then
      return (1)
    else
      return (0)
    end %if
  end x

end tree_type