#include "stdafx.h"

#include <iostream>
#include <fstream>

#pragma comment(lib,"openbgi_vc90x.lib")
using namespace std;
const int LEN_STACK = 25;
bool FLAG = 1;

typedef char Elem;
struct node {//струтура элементов дерева
    Elem name;
    node *left;
    node *right;
    // constructor
    node() { left = NULL; right = NULL; }
};
struct les{
    Elem name;
    les* root_of_first_tree;
    les* next;
    les() { root_of_first_tree = NULL; next = NULL; }
};


typedef node *binTree;
typedef les *forest;
//Elem GetSimbol(std::istream & in);//получает символ из входного потока
//void ReadTree(binTree & y, std::istream & in);//обрабатывает символы скобочной записи
//void  MakeTree(binTree & y, std::istream & in);//создает элементы дерева
void Destroy(binTree &b);//удаляет дерево
inline bool IsEmpty(const binTree &b);//проверка на пустоту
inline bool IsEmptyF(const forest &f);
Elem Name(binTree b); //получает значение элемента дерева
void Les(binTree b, forest f);
void PaintLes(forest f, int level);

bool PaintLeafBT(int x1, int x2, int y, binTree leaf, int level, char f);//рисует элементы дерева
void PaintBT(binTree root);//рисует бинарное дерево
void BinTree(binTree root);
void PaintTree(binTree b, int level);
void PaintLes(binTree b, int level);

void BFS(binTree root);//делает обход в ширину дерева
void InFIFO(binTree* fifo, int & last, binTree y);//заносит элементы дерева  в очередь


int main()
{
    int i = 0;
    ifstream fin;
    binTree Root;
    forest LES = new les;
    char ch = 0;
    char name[50] = { 0 };


    cout << "1. Enter a list of console\n"
        << "2. enter a list of file\n"
        << "Number: ";
cin >> i;
    //cin.sync();
    switch (i)
    {
    case 1:
        cout << "Enter list:" << std::endl;
        cin >> ch;
        ReadTree(Root, cin);
        break;
    case 2:

        fin.open("BT.txt");
        if (!fin.is_open())
        {
            cout << "Error: can't open file " << '\n';
            return 1;
        }

        ReadTree(Root, fin);
        BinTree(Root);
        cout << "\nForest:\n";
        Les(Root, LES);
        PaintLes(LES, 50);
        fin.close();
        cout << "...............................\n";
        break;
    default:
        cout << "Error: wrong number!\n";
        return 1;
    }

    //BinTree(Root);
    //cout << "\nForest:\n";
    //Les(Root, LES);
    //PaintLes(LES, 50);
    //PaintBT(Root);


    BFS(Root);
    Destroy(Root);
    system("pause");
    return 0;
}
Elem RootBT(node* b){
    if (b == NULL) { cerr << "Error: RootBT(null) \n"; return 0; }
    else return b->name;

}
node* Left(node* b){
    if (b == NULL) { cerr << "Error: Left(null) \n"; return NULL; }
    else return b->left;
}
node* Right(node* b){
    if (b == NULL) { cerr << "Error: Right(null) \n"; return NULL; }
    else return b->right;
}

//блок создания дерева  и работы с ним
/*
Elem GetSimbol(istream & in)
{
    if (!FLAG) //если при считывании произошла ошибка или строка закончилась
    {
        return EOF;
    }

    Elem x = ' ';
    x = in.get();
    while (x == ' ' && in.good() && x != '\n')//до тех пор пока следующий символ не будет символом скобочной записи
    {
        x = in.get();
    }

    if (x != '\n' && in.good())
    {
        return x;
    }
    else
    {
        FLAG = false;
        return EOF;
    }
    return x;
}

void ReadTree(binTree & y, istream & in)
{
    Elem x = GetSimbol(in);

    if (x == '(')//если новая ветвь, то создаем узел
    {
        MakeTree(y, in);
        return;
    }
    else if (x != EOF && x != ')') //если нет, то выдаем ошибку
    {
        cout << "Error: incorrect symbol in expession\n";
        exit(1);
    }
    y = NULL;
}

void  MakeTree(binTree & y, istream & in)
{
    Elem x = GetSimbol(in);

    if (x == EOF)
    {
        cout << "Error: in fail\n";
        exit(1);
    }

    y = new node;
    if (y == NULL)
    {
        cout << "Error: memory\n";
        exit(1);
    }

    y->name = x;//заполняем дерево
    ReadTree(y->left, in);
    ReadTree(y->right, in);
}*/

void Destroy(binTree &b)
{
    if (!IsEmpty(b))    {
        Destroy(b->left);
        Destroy(b->right);
        delete b;
        b = NULL;
    }
}

bool IsEmpty(const binTree &b)
{
    return b == NULL;
}
bool IsEmptyF(const forest &f)
{
    if (f != NULL)
        return !f->name;
    return f == NULL;
}
Elem Name(binTree b)            // для непустого бин.дерева
{
    if (IsEmpty(b))
    {
        cerr << "Error: Name(null) \n";
        exit(1);
    }
    else
    {
        return b->name;
    }
}

/*
void BinTree(binTree root)
{
    cout << "\nBinTree:\n";
    if (IsEmpty(root))
    {
        cout << "\nBinTree is Empty\n";
    }
    else
    {
        PaintTree(root, 50);
    }
    cout << "...............................\n";
}*/
node* consoleEnter(){
    cout << "Введите бинарное дерево:\n";
    cin.clear();
    cin.sync();
    cin >> arr;

    ofstream fout("Data.txt");
    fout << arr;
    fout.close();

    ifstream fin("Data.txt");
    node* b = enterBT(fin);
    fin.close();
    return b;


}

node* enterBT(ifstream &infile)
{
    char ch;
    node* p, *q;
    if (!(infile >> ch)){
        if (flag) cout << "Файл пуст\n";
        return NULL;
    }
    while ((ch == '(') || (ch == ')')){
        if (!(infile >> ch)){
            if (flag) cout << "Ошибка входных данных\n";
            return NULL;
        }
    }
    if (ch == '^') return NULL;
    else {
        flag = false;
        p = enterBT(infile);
        q = enterBT(infile);
        return ConsBT(ch, p, q);
    }
}
//вывод дерева
void PaintTree(node* b, int n)
{
    tab(n);
    if (!IsEmpty(b))
    {

        cout << RootBT(b) << endl;
        //output << RootBT(b) << endl;
        if (!IsEmpty(b->left) || !IsEmpty(b->right)){
            PaintTree(Left(b), n + 1);
            PaintTree(Right(b), n + 1);
        }
    }
    else {
        cout << "^\n";
        //output << "^\n";
    }
}


/*
void PaintTree(binTree b, int level)
{
    int i = 0;
    if (IsEmpty(b))
    {
        return;
    }

    for (i = 0; i<level; i++)
    {
        cout << '|';
    }
    cout << Name(b) << '\n';
    PaintTree(b->left, level-5);
    PaintTree(b->right, level);
}*/
void PaintLes(forest f, int level)
{
    int i = 0;
    if (IsEmptyF(f))
    {
        return;
    }
    for (i = 0; i<level; i++)
    {
        cout << '|';
    }
    cout << f->name << '\n';
    PaintLes(f->root_of_first_tree, level - 5);
    PaintLes(f->next, level);
}
///////////// ??????

void Les(binTree b, forest f)
{
    //forest save = new les;
    //f = new les;
    if (IsEmpty(b))
    {
        //delete(f);
        f->name = NULL;
        return;
    }
    else
    {
        f->name=b->name;
        f->next = new les;
        Les(b->right, f->next);
        f->root_of_first_tree = new les;
        Les(b->left, f->root_of_first_tree);
    }

}

//блок обхода в ширину

void BFS(binTree root)
{
    cout << "\nBreadth-first search\n\n";
    binTree tmp = root;
    if (IsEmpty(root))
    {
        cout << "Forest is empty\n\n...............................\n";
        return;
    }
    int first = 0; //инициализируем очередь
    int last = 0;
    binTree fifo[LEN_STACK] = { 0 };

    InFIFO(fifo, last, tmp); //заполняем её вершинами деревьев
    while (first != last) //движемся по массивую, добавляя вершины поддеревьев
    {
        tmp = fifo[first];
        InFIFO(fifo, last, tmp->left);
        first++;
    }

cout << "Elemet of forest:\n";
    first = 0;


    while (fifo[first] != NULL) //выводим массив
    {
        cout << Name(fifo[first]) << ' ';
        first++;
    }
    cout << "\n...............................\n";
}

void InFIFO(binTree* fifo, int & last, binTree y)
{
    while (!IsEmpty(y) && last != LEN_STACK) //заносим в очередь все левые узлы
    {
        fifo[last] = y;
        last++;
        y = y->right;
    }

    if (last == LEN_STACK)
    {
        last = 0;
        cout << "Error: last=LEN\n";
    }
}