Esercizi_20170224

/*
Copyright (C) 2015 [MAIONE MIKY]
This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.
*/
using System.Collections.Generic;

namespace Alberi
{
    class Esercizi_20170224 : BST
    {

        public Esercizi_20170224(int k) : base(k) { }


        private static int funzione(BST T, BST P, int x, int r_sx, int r_dx)
        {
            var ret = r_sx + r_dx + 1;

            System.Console.WriteLine($"n: {T.key} | ret: {ret}");

            if (T.key % 2 == 0 && ret < x && P != null)
            {
                if (T == P.dx)
                    P.dx = Cancella(T);
                else
                    P.sx = Cancella(T);
            }

            return ret;
        }

        public static int Algo(BST T, BST P, int x)
        {
            var ret = 0;

            if (T != null)
            {
                var r_sx = Algo(T.sx, T, x);
                var r_dx = Algo(T.dx, T, x);

                ret = funzione(T, P, x, r_sx, r_dx);
            }

            return ret;
        }

        public static int Algo_Miky(BST T, BST P, int x)
        {
            var RS = new Stack<int>();
            var ret = 0;

            BST last = null;
            var S = new Stack<BST>();

            while (S.Count > 0 || T != null)
                if (T != null)
                {
                    S.Push(T);
                    T = T.Sx;
                }
                else
                {
                    T = S.Peek();

                    if (T.Dx != null && T.Dx != last)
                    {
                        if (T.Sx != null)
                            RS.Push(ret);

                        T = T.Dx;
                    }
                    else
                    {
                        var r_sx = 0;
                        var r_dx = 0;

                        if (T.Sx != null && T.Dx == null)
                            r_sx = ret;
                        else if (T.Sx != null && T.Dx != null)
                            r_sx = RS.Pop();

                        if (T.Dx != null)
                            r_dx = ret;

                        S.Pop();
                        P = (S.Count > 0 ? S.Peek() : null);

                        ret = funzione(T, P, x, r_sx, r_dx);

                        last = T;
                        T = null;
                    }
                }

            return ret;
        }


    }
}