#ifndef TREE_H

#include <vector>
#include <queue>
#include <string>

using namespace std;

/*
   Odwiedzający, którego funkcja składowa visit jest wywoływana dla każdego węzła
   odwiedzonego podczas przeglądania drzewa.
*/
class Visitor
{
public:   
   /**
      Ta funkcja składowa jest wywoływana dla każdego odwiedzonego węzła.
      @param data dane węzła
   */
   virtual void visit(string data);
};

class BreadthFirstIterator;

class Node
{
private:
   /**
      Oblicza rozmiar poddrzewa, którego korzeniem jest ten węzeł.
      @return liczba węzłów w poddrzewie
   */
   int size() const;

   string data;
   vector<Node*> children;
friend class BreadthFirstIterator;
friend class Tree;
};

/*
   Drzewo, w którym każdy węzeł ma dowolną liczbę dzieci.
*/
class Tree
{
public:
   /**
      Konstruuje puste drzewo.
   */
   Tree();

   /**
      Konstruuje drzewo z jednym węzłem i bez dzieci.
      @param root_data dane w korzeniu
   */
   Tree(string root_data);

   /**
      Dodaje poddrzewo jako ostatnie dziecko korzenia.
   */
   void add_subtree(const Tree& subtree);

   /**
      Oblicza rozmiar drzewa.
      @return liczba węzłów w drzewie
   */
   int size() const;

   /**
      Przegląda drzewo wzdłużnie.
      @param v odwiedzający wywoływany na każdym węźle
   */
   void preorder(Visitor& v) const;
   
   /**
      Przegląda drzewo wstecznie.
      @param v odwiedzający wywoływany na każdym węźle
   */
   void postorder(Visitor& v) const;

   /**
      Przegląda to drzewo wszerz.
      @param v odwiedzający wywoływany na każdym węźle
   */
   void breadth_first(Visitor& v) const;

   /**
      Zwraca iterator do przeglądania wszerz wskazujący
      pierwszy element drzewa.
      @return iterator
   */
   BreadthFirstIterator begin() const;
   
   /**
      Zwraca iterator do przeglądania wszerz wskazujący
      ostatni element drzewa.
      @return iterator
   */
   BreadthFirstIterator end() const;

 private:   
   /**
      Przegląda wzdłużnie drzewo o danym korzeniu.
      @param n korzeń drzewa
      @param v odwiedzający wywoływany na każdym węźle
   */
   void preorder(Node* n, Visitor& v) const;

   /**
      Przegląda wstecznie drzewo o danym korzeniu.
      @param n korzeń drzewa
      @param v odwiedzający wywoływany na każdym węźle
   */
   void postorder(Node* n, Visitor& v) const;
   
   Node* root;
};

/**
   Iterator ten odwiedza węzły drzewa
   wszerz.
*/
class BreadthFirstIterator
{
 public:
   /**
      Konstruuje iterator dla danego drzewa.
      @param root korzeń drzewa
   */
   BreadthFirstIterator(Node* root);
   /**
      Pobiera element wskazywany przez ten iterator.
      @return element
   */
   string get() const;
   /**
      Przesuwa iterator na następną pozycję.
   */
   void next();
   bool equals(const BreadthFirstIterator& other) const;
   
private:
   queue<Node*> q;
};

#endif

