Seminar6

// =================================================================
// Graph.hpp

#pragma once

#include <vector>

struct IGraph {
  virtual ~IGraph() = default;

  // Добавление ребра от from к to.
  virtual void AddEdge(size_t from, size_t to) = 0;

  virtual size_t VerticesCount() const = 0;

  virtual std::vector<int> FindAllAdjacentIn(size_t vertex) const = 0;
  virtual std::vector<int> FindAllAdjacentOut(size_t vertex) const = 0;
};

// =================================================================
// ListGraph.hpp

#include "Graph.hpp"

#include <vector>

class ListGraph : public IGraph {
 public:
  explicit ListGraph(int vertices_count);
  // Конструктор "копирования" по другому графу
  explicit ListGraph(const IGraph* other);

  // Dtor уже тут автоматически добавлен компилятором и уже является виртуальным.
  // ~ListGraph() {}
  // Добавление ребра от from к to.
  void AddEdge(size_t from, size_t to) override;

  size_t VerticesCount() const override;

  std::vector<int> FindAllAdjacentIn(size_t vertex) const override;
  std::vector<int> FindAllAdjacentOut(size_t vertex) const override;

 private:
  std::vector<std::vector<int>> in_edges_;
  std::vector<std::vector<int>> out_edges_;
};

// =================================================================
// ListGraph.cpp

#include "ListGraph.hpp"

ListGraph::ListGraph(int vertices_count) : in_edges_(vertices_count), out_edges_(vertices_count) {
}

ListGraph::ListGraph(const IGraph* other) : in_edges_(other->VerticesCount()), out_edges_(other->VerticesCount()) {
//  for (int i = 0; i < other->VerticesCount(); ++i) {  // virtual call too long
  for (int i = 0; i < in_edges_.size(); ++i) {
    in_edges_[i] = other->FindAllAdjacentIn(i);
    out_edges_[i] = other->FindAllAdjacentOut(i);
  }
}

void ListGraph::AddEdge(size_t from, size_t to) {
  in_edges_[to].push_back(from);
  out_edges_[from].push_back(to);
}

size_t ListGraph::VerticesCount() const {
  return in_edges_.size();
}

std::vector<int> ListGraph::FindAllAdjacentIn(size_t vertex) const {
  return in_edges_[vertex];
}
std::vector<int> ListGraph::FindAllAdjacentOut(size_t vertex) const {
  return out_edges_[vertex];
}

// =================================================================
// MatrixGraph.hpp

#include "Graph.hpp"

class MatrixGraph : public IGraph {
 public:
  explicit MatrixGraph(int vertices_count);
  // Конструктор "копирования" по другому графу
  explicit MatrixGraph(IGraph* other);

  // Dtor уже тут автоматически добавлен компилятором и уже является виртуальным.
  // ~ListGraph() {}
  // Добавление ребра от from к to.
  void AddEdge(size_t from, size_t to) override;

  size_t VerticesCount() const override;

  std::vector<int> FindAllAdjacentIn(size_t vertex) const override;
  std::vector<int> FindAllAdjacentOut(size_t vertex) const override;

 private:
  std::vector<std::vector<bool>> matrix;
};

// =================================================================
// MatrixGraph.hpp

//#include "Main.hpp"

#include <iostream>
#include <vector>

#include "ListGraph.hpp"

class Furniture {
 public:
//  Furniture() { std::cout << "Furniture ctor. " << Caller() << std::endl; }
  virtual ~Furniture() = default;
  virtual int Calories() const = 0;
  virtual int Caller() const { return Calories(); }
};

class Sofa : public Furniture {
 public:
  int Calories() const override { return 100000; }
  std::pair<int, int> Coord;
  std::vector<int> Uses = {2, 4, 5};
};

class IronChair : public Furniture {
 public:
  int Calories() const override { return 0; }
};

void Burn(Furniture& f) {
  std::cout << "OO, furniture is in fire, heats on " << f.Calories() << std::endl;
}

void Shift(Sofa& s, int x, int y) {
  s.Coord = {s.Coord.first + x, s.Coord.second + y};
}

int main1() {
  Sofa s;
  Furniture& f = s;
  Burn(f);
  Shift(dynamic_cast<Sofa&>(f), 3, 8);

  IronChair chair;
  Furniture& f2 = chair;
  Burn(f2);
  Sofa& s2 = dynamic_cast<Sofa&>(f2);
  std::cout << "s2 = " << &s2 << std::endl;
  Shift(s2, 3, 8);
  return 0;
}

int main2() {
  Sofa s;
  return 0;
}

Sofa* CreateSofa() {
  return new Sofa();
}

IronChair* CreateIronChair() {
  return new IronChair();
}

int main3() {
  std::vector<Furniture*> furnitures;
  furnitures.push_back(CreateSofa());
  furnitures.push_back(CreateIronChair());

  for (Furniture* f : furnitures) {
    Burn(*f);
  }
  for (Furniture* f : furnitures) {
    delete f;
  }
  return 0;
}

int Time = 0;

void DFS(size_t u, const IGraph* graph, std::vector<bool>& visited) {
  visited[u] = true;
  std::cout << "Entry " << u << ", time = " << Time++ << std::endl;
  for (size_t v : graph->FindAllAdjacentOut(u)) {
    if (!visited[v]) DFS(v, graph, visited);
  }
  std::cout << "Leave " << u << ", time = " << Time++ << std::endl;
}

void MainDFS(const IGraph* graph) {
  std::vector<bool> visited(graph->VerticesCount()/*, false*/);
  for (size_t v = 0; v < graph->VerticesCount(); ++v) {
    if (!visited[v]) DFS(v, graph, visited);
  }
}

int main() {
  ListGraph lg(9);
  lg.AddEdge(6, 0);
  lg.AddEdge(3, 2);
  lg.AddEdge(2, 1);
  lg.AddEdge(2, 5);
  lg.AddEdge(1, 5);
  lg.AddEdge(3, 4);
  lg.AddEdge(4, 7);
  lg.AddEdge(7, 8);
  lg.AddEdge(8, 4);
  lg.AddEdge(5, 7);

  for (int in : lg.FindAllAdjacentIn(5)) std::cout << in << " ";
  std::cout << std::endl;
  for (int out : lg.FindAllAdjacentOut(5)) std::cout << out << " ";
  std::cout << std::endl;

  ListGraph lg2(&lg);
  MainDFS(&lg2);
  return 0;
}