Displaying programming languages on a timeline

Question

I did the following two exercises in Programming: Principles and Practice Using C++ (2nd Edition), by Stroustrup, which build upon each other:

From Chapter 22 (Ideals and History),

15. Write a program that given a file of (name,year) pairs, such as (Algol,1960) and (C,1974), graphs the names on a timeline.
16. Modify the program from the previous exercise so that it reads a file of (name,year,(ancestor)) tuples, such as (Fortran,1956,()), (Algol,1960,(Fortran)), and (C++,1985,(C,Simula)), and graphs them on a timeline with arrows from ancestor to descendants.

The result I got looks like this:

I used FLTK on Visual Studio to draw this with the support files of the book. I will only post the code I added to these files to solve the exercise to not blow up this post too much.

Here my approach to solve this Excercise:

First of all I created a file which contains languages and ancestors:

languages.txt

(Plankalkül,1948,()),
(Assembly,1949,()),
(Fortran,1956,()),
(LISP,1958,()),
(Algol58,1958,(Plankalkül,Fortran)),
(COBOL,1959,()),
(Algol60,1960,(Algol58)),
(CPL,1963,(Algol60)),
(PL/I,1964,(COBOL,Fortran,Algol60)),
(BASIC,1964,(Algol60,Fortran)),
(P'',1964,()),
(Simula,1965,(Algol60)),
(Euler,1965,(Algol60)),
(IMP,1965,(Algol60)),
(Algol-W,1966,(Algol60)),
(BCPL,1967,(CPL)),
(Logo,1967,(LISP)),
(Algol68,1968,(Algol60)),
(Planner,1969,()),
(B,1969,(BCPL,PL/I)),
(Pascal,1970,(Algol W)),
(PLEX,1970,()),
(Smalltalk,1972,(LISP,Simula,Euler,IMP,Planner,Logo)),
(C,1972,(B,Algol68,Assembly,PL/I,Fortran)),
(Prolog,1972,(Planner)),
(Modula-2,1978,(Algol-W,Pascal)),
(C with Classes,1980,(C,BCPL,Simula)),
(ADA,1980,(Algol68,Pascal,Modula-2)),
(Turbo Pascal,1983,(Pascal)),
(Objective C,1984,(C,Smalltalk)),
(ABC,1985,()),
(Early C++,1985,(C with Classes)),
(Erlang,1986,(Prolog,Smalltalk,PLEX,LISP)),
(Eiffel,1986,(Ada,Algol68,Simula)),
(Object Pascal,1986,(Turbo Pascal,Simula,Smalltalk)),
(Perl,1987,(C,Early C++,LISP,Pascal)),
(C89,1989,(C,C with Classes)),
(ARM C++,1989,(Early C++,C89)),
(Python,1990,(ABC,C89,ARM C++)),
(Visual Basic,1991,(BASIC)),
(Brainfuck,1993,(P'')),
(Java,1995,(ARM C++,Smalltalk,Objective C)),
(C95,1995,(C89)),
(C++98,1998,(ARM C++,C89)),
(C99,1999,(C95,ARM C++)),
(C#,2001,(Java,C++98,Objective Pascal)),
(D,2001,(C99,C++98,C#,Eiffel,Java,Python)),
(Visual Basic .NET,2001,(Visual Basic)),
(LOLCODE,2007,()),
(Go,2009,(C99,BCPL,Pascal,Smalltalk)),
(C11,2011,(C99)),
(C++11,2011,(C++98)),
(C++14,2014,(C++11)),
(C++17,2017,(C++14)),
(C18,2018,(C11)),

For the file i/o i defined a class Programming_language to read in the data of the file.

Programming_language.h

#ifndef PROGRAMMING_LANGUAGE_GUARD_29082018
#define PROGRAMMING_LANGUAGE_GUARD_29082018

#include <string>
#include <vector>

namespace programming_language 
{
    using Name = std::string;
    using Year = size_t;
    using Position = size_t;

    class Programming_language {
    public:
        Programming_language() = default;
        Programming_language(const Name& name, const Year& year, const std::vector<Name>& name_of_presessors)
            :m_name{ name }, m_year{ year }, m_position{ 0 },m_name_of_predessors{ name_of_presessors }
        {
        }

        Name get_name() const { return m_name; }
        Year get_year() const { return m_year; }

        void set_position(Position position) { m_position = position; }
        Position get_position() const { return m_position; }

        std::vector<Name> get_name_of_predessors() const { return m_name_of_predessors;}

    private:
        Name m_name;
        Year m_year;                // position on x-graph
        Position m_position;        // position on y-graph
        std::vector<Name> m_name_of_predessors;
    };

    bool read_sign(std::istream& is, char expected_sign);
    std::istream& operator>>(std::istream& is, Programming_language& obj);

    std::vector<Programming_language> read_from_file(const std::string& filename);
}

#endif

Programming_language.cpp

#include "Programming_language.h"

#include <cctype>
#include <exception>
#include <fstream>
#include <filesystem>

namespace programming_language
{
    bool read_sign(std::istream& is, char expected_sign)
    {
        char sign = is.get();
        if (sign != expected_sign) {
            is.putback(sign);
            is.setstate(std::ios::failbit);
            return false;
        }
        return true;
    }

    std::istream& operator>>(std::istream& is, Programming_language& obj)
        // valid formats:  
        // (Algol58,1958,(Plankalkül,Fortran),
        // (Assembly,1949,()),
    {
        is >> std::ws;

        if (!read_sign(is, '(')) {
            return is;
        }

        Name name;
        for (char c; c = is.get();) {
            if (c == ',') break;
            name.push_back(c);
        }

        if (!is) {
            is.setstate(std::ios::failbit);
            return is;
        }

        std::string str_number;

        for (char c; is >> c;) {
            if (c == ',') break;
            str_number.push_back(c);
        }

        Year number{};
        try {
            number = std::stoi(str_number);
        }
        catch (...) {
            is.setstate(std::ios::failbit);
            return is;
        }

        if (!read_sign(is, '(')) {
            return is;
        }

        std::vector<Name> predessor_names;

        Name current_name;
        for (char c; c=is.get();) {
            if (c == ')') {
                predessor_names.push_back(current_name);
                break;
            }
            else if (c == ',') {
                predessor_names.push_back(current_name);
                current_name.clear();
            }
            else {
                current_name.push_back(c);
            }
        }

        if (!is) {
            is.setstate(std::ios::failbit);
            return is;
        }

        if (!read_sign(is, ')')) {
            return is;
        }

        if (!read_sign(is, ',')) {
            return is;
        }

        obj = Programming_language{ name ,number,predessor_names };
        return is;
    }

    std::vector<Programming_language> read_from_file(const std::string& filename)
    {
        std::ifstream ifs{ filename };
        if (!ifs) {
            throw std::filesystem::filesystem_error(
                "std::vector<Programming_language> read_from_file(const std::string& filename)\n"
                "File could not be opened", std::error_code{});
        }

        std::vector<Programming_language> languages;

        for (Programming_language p; ifs >> p;) {
            languages.push_back(p);
        }

        return languages;
    }
}

Now to display the data on the Screen I used the libraries from stroustrup as a base. He already provides some Shapes so i derived from them to create a Text_ellipse.class and a Arrow.class. These are used to draw the languages and the arrows between them.

Arrow.h

#ifndef ARROW_GUARD_300820181840
#define ARROW_GUARD_300820181840

#include "Graph.h"

namespace Graph_lib 
{
    class Arrow : public Shape {
    public:
        Arrow(Point p1, Point p2, int arrow_height, int arrow_width);
        void draw_lines() const;
    private:
        int m_arrow_height;
        int m_arrow_width;
    };

    inline bool line_pointing_down(const Point& p_start, const Point& p_end)
    {
        return p_end.x == p_start.x && p_end.y > p_start.y;
    }

    inline bool line_pointing_up(const Point& p_start, const Point& p_end)
    {
        return p_end.x == p_start.x && p_start.y > p_end.y;
    }

    inline bool line_pointing_left(const Point& p_start, const Point& p_end)
    {
        return p_end.y == p_start.y && p_start.x > p_end.x;
    }

    inline bool line_pointing_right(const Point& p_start, const Point& p_end)
    {
        return p_end.y == p_start.y && p_start.x < p_end.x;
    }

    inline bool line_pointing_up_right(const Point& p_start, const Point& p_end)
    {
        return p_start.x < p_end.x && p_end.y < p_start.y;
    }

    inline bool line_pointing_up_left(const Point& p_start, const Point& p_end)
    {
        return p_start.x > p_end.x && p_end.y < p_start.y;
    }

    inline bool line_pointing_down_right(const Point& p_start, const Point& p_end)
    {
        return p_start.x < p_end.x && p_end.y > p_start.y;
    }

    inline bool line_pointing_down_left(const Point& p_start, const Point& p_end)
    {
        return p_start.x > p_end.x && p_end.y > p_start.y;
    }

    double calculate_alpha(const Point& p_start, const Point& p_end);

    inline double calculate_triangle_side_a(double alpha, double side_c)
    {
        return side_c * std::sin(alpha);
    }

    inline double calculate_triangle_side_b(double alpha, double side_c)
    {
        return side_c * std::cos(alpha);
    }

    std::pair<Point, Point> calculate_arrow_points(const int arrow_height, const int arrow_width, const Point p_start, const Point p_end);
}
#endif

Arrow.cpp

#include "Arrow.h"

#include <cmath>
#include <utility>

namespace Graph_lib 
{
    Arrow::Arrow(Point p_start, Point p_end, int arrow_height, int arrow_width)    // construct a line from two points
        : m_arrow_height{ arrow_height }, m_arrow_width{ arrow_width }
    {
        add(p_start);    // add p_start to this shape
        add(p_end);    // add p_end to this shape
    }

    void Arrow::draw_lines() const
    {
        Shape::draw_lines();

        auto arrow_points_left_right = calculate_arrow_points(m_arrow_height, m_arrow_width, point(0), point(1));
        Point p_arrow_left = arrow_points_left_right.first;
        Point p_arrow_right = arrow_points_left_right.second;

        Fl_Color oldc = fl_color();
        // there is no good portable way of retrieving the current style
        fl_color(color().as_int());            // set color
        fl_line_style(style().style(), style().width()); // set style

        if (color().visibility()) {    // draw sole pixel?
            fl_line(p_arrow_left.x, p_arrow_left.y, p_arrow_right.x, p_arrow_right.y);
            fl_line(p_arrow_right.x, p_arrow_right.y, point(1).x, point(1).y);
            fl_line(point(1).x, point(1).y, p_arrow_left.x, p_arrow_left.y);
        }

        fl_color(oldc);      // reset color (to previous)
        fl_line_style(0);    // reset line style to default

        if (fill_color().visibility()) {
            fl_color(fill_color().as_int());

            fl_begin_complex_polygon();
            fl_vertex(p_arrow_left.x, p_arrow_left.y);
            fl_vertex(p_arrow_right.x, p_arrow_right.y);
            fl_vertex(point(1).x, point(1).y);
            fl_end_complex_polygon();

            fl_color(color().as_int());    // reset color
        }
    }

    double calculate_alpha(const Point& p_start, const Point& p_end)
    {
        double alpha = 0;
        if (line_pointing_up_right(p_start, p_end)) {
            return std::atan(static_cast<double>(p_start.y - p_end.y) / static_cast<double>(p_end.x - p_start.x));
        }
        else if (line_pointing_up_left(p_start, p_end)) {
            return std::atan(alpha = static_cast<double>(p_start.y - p_end.y) / static_cast<double>(p_start.x - p_end.x));
        }
        else if (line_pointing_down_right(p_start, p_end)) {
            return std::atan(static_cast<double>(p_end.y - p_start.y) / static_cast<double>(p_end.x - p_start.x));
        }
        else if (line_pointing_down_left(p_start, p_end)) {
            return std::atan(static_cast<double>(p_end.y - p_start.y) / static_cast<double>(p_start.x - p_end.x));
        }
        else {
            throw std::runtime_error(
                "double calculate_alpha(const Point& p_start, const Point& p_end)\n"
                "Invalid posiition of line\n");
        }
    }

    std::pair<Point, Point> calculate_arrow_points(const int arrow_height, const int arrow_width, const Point p_start, const Point p_end)
    {
        if (line_pointing_down(p_start,p_end)) {        
            Point p_arrow_left{ p_end.x + arrow_width / 2 ,p_end.y - arrow_height };
            Point p_arrow_right{ p_end.x - arrow_width / 2 ,p_arrow_left.y };
            return std::make_pair(p_arrow_left, p_arrow_right);
        }
        else if (line_pointing_up(p_start, p_end)) {        
            Point p_arrow_left{ p_end.x - arrow_width / 2 , p_end.y + arrow_height };
            Point p_arrow_right{ p_end.x + arrow_width / 2 ,p_arrow_left.y };
            return std::make_pair(p_arrow_left, p_arrow_right);
        }
        else if (line_pointing_left(p_start, p_end)) {      
            Point p_arrow_left{ p_end.x + arrow_height,p_end.y + arrow_width / 2 };
            Point p_arrow_right{ p_arrow_left.x,p_end.y - arrow_width / 2 };
            return std::make_pair(p_arrow_left, p_arrow_right);
        }
        else if (line_pointing_right(p_start, p_end)) {     
            Point p_arrow_left{ p_end.x - arrow_height,p_end.y - arrow_width / 2 };
            Point p_arrow_right{ p_arrow_left.x,p_end.y + arrow_width / 2 };
            return std::make_pair(p_arrow_left, p_arrow_right);
        }
        else {
            auto alpha = calculate_alpha(p_start, p_end);

            auto length_p_end_to_arrow_bottom_x = calculate_triangle_side_b(alpha, arrow_height);
            auto length_p_end_to_arrow_bottom_y = calculate_triangle_side_a(alpha, arrow_height);

            const double pi = std::atan(1) * 4;
            double alpha1 = pi / 2.0 - alpha;

            auto length_arrow_bottom_to_left_right_x = calculate_triangle_side_b(alpha1, arrow_width / 2.0);
            auto length_arrow_bottom_to_left_right_y = calculate_triangle_side_a(alpha1, arrow_width / 2.0);

            if (line_pointing_up_right(p_start, p_end)) {
                Point p_arrow_left{
                    p_end.x - static_cast<int>(length_p_end_to_arrow_bottom_x + length_arrow_bottom_to_left_right_x),
                    p_end.y + static_cast<int>(length_p_end_to_arrow_bottom_y - length_arrow_bottom_to_left_right_y)
                };
                Point p_arrow_right{
                    p_end.x - static_cast<int>(length_p_end_to_arrow_bottom_x - length_arrow_bottom_to_left_right_x),
                    p_end.y + static_cast<int>(length_p_end_to_arrow_bottom_y + length_arrow_bottom_to_left_right_y)
                };
                return std::make_pair(p_arrow_left, p_arrow_right);
            }
            else if (line_pointing_up_left(p_start, p_end)) {
                Point p_arrow_left{
                    p_end.x + static_cast<int>(length_p_end_to_arrow_bottom_x - length_arrow_bottom_to_left_right_x),
                    p_end.y + static_cast<int>(length_p_end_to_arrow_bottom_y + length_arrow_bottom_to_left_right_y)
                };
                Point p_arrow_right{
                    p_end.x + static_cast<int>(length_p_end_to_arrow_bottom_x + length_arrow_bottom_to_left_right_x),
                    p_end.y + static_cast<int>(length_p_end_to_arrow_bottom_y - length_arrow_bottom_to_left_right_y)
                };
                return std::make_pair(p_arrow_left, p_arrow_right);
            }
            else if (line_pointing_down_right(p_start, p_end)) {
                Point p_arrow_left{
                    p_end.x - static_cast<int>(length_p_end_to_arrow_bottom_x + length_arrow_bottom_to_left_right_x),
                    p_end.y - static_cast<int>(length_p_end_to_arrow_bottom_y - length_arrow_bottom_to_left_right_y)
                };
                Point p_arrow_right{
                    p_end.x - static_cast<int>(length_p_end_to_arrow_bottom_x - length_arrow_bottom_to_left_right_x),
                    p_end.y - static_cast<int>(length_p_end_to_arrow_bottom_y + length_arrow_bottom_to_left_right_y)
                };
                return std::make_pair(p_arrow_left, p_arrow_right);
            }
            else if (line_pointing_down_left(p_start, p_end)) {
                Point p_arrow_left{
                    p_end.x + static_cast<int>(length_p_end_to_arrow_bottom_x - length_arrow_bottom_to_left_right_x),
                    p_end.y - static_cast<int>(length_p_end_to_arrow_bottom_y + length_arrow_bottom_to_left_right_y)
                };
                Point p_arrow_right{
                    p_end.x + static_cast<int>(length_p_end_to_arrow_bottom_x + length_arrow_bottom_to_left_right_x),
                    p_end.y - static_cast<int>(length_p_end_to_arrow_bottom_y - length_arrow_bottom_to_left_right_y)
                };
                return std::make_pair(p_arrow_left, p_arrow_right);
            }
        }
    }
}

Text_ellipse.h

#ifndef TEXT_ELLIPSE_GUARD_300820182217
#define TEXT_ELLIPSE_GUARD_300820182217

#include "Graph.h"

namespace Graph_lib
{ 
    class Text_ellipse : public Ellipse {
    public:
        Text_ellipse(Point p, const std::string& text_label, int font_size);
        void draw_lines() const override;

        std::string label() { return text.label(); }
    private:
        Text text;
    };

    int calculate_ellipse_width(const std::string& text_label, int font_size);
    int calculate_ellipse_height(int font_size);
    Point calculate_ellipse_text_position(Point p, const std::string& text_label, int font_size);

    Point north(Text_ellipse& text_ellipse);
    Point east(Text_ellipse& text_ellipse);
    Point south(Text_ellipse& text_ellipse);
    Point west(Text_ellipse& text_ellipse);
}
#endif

Text_ellipse.cpp

#include "Text_ellipse.h"

namespace Graph_lib
{
    Text_ellipse::Text_ellipse(Point p, const std::string& text_label, int font_size)
        :
        Ellipse(
            p,
            calculate_ellipse_width(text_label, font_size),
            calculate_ellipse_height(font_size)
        ),
        text{
            calculate_ellipse_text_position(p,text_label,font_size),
            text_label
    }
    {
        text.set_font_size(font_size);
    }

    void Text_ellipse::draw_lines() const
    {
        Ellipse::draw_lines();
        text.draw_lines();
    }

    int calculate_ellipse_width(const std::string& text_label, int font_size)
    {
        return static_cast<int>(text_label.size()*font_size * 0.4);
    }

    int calculate_ellipse_height(int font_size)
    {
        return static_cast<int>(font_size * 0.7);
    }

    Point calculate_ellipse_text_position(Point p, const std::string& text_label, int font_size)
    {
        return Point{
            p.x - static_cast<int>(calculate_ellipse_width(text_label, font_size) * 0.8),
            p.y + static_cast<int>(calculate_ellipse_height(font_size) * 0.55)
        };
    }

    Point north(Text_ellipse& text_ellipse)
    {
        return Point{ text_ellipse.point(0).x + text_ellipse.major(), text_ellipse.point(0).y };
    }

    Point east(Text_ellipse& text_ellipse)
    {
        return Point{ text_ellipse.point(0).x + text_ellipse.major() * 2, text_ellipse.point(0).y + text_ellipse.minor() };
    }

    Point south(Text_ellipse& text_ellipse)
    {
        return Point{ text_ellipse.point(0).x + text_ellipse.major(), text_ellipse.point(0).y + text_ellipse.minor() * 2 };
    }

    Point west(Text_ellipse& text_ellipse)
    {
        return Point{ text_ellipse.point(0).x, text_ellipse.point(0).y + text_ellipse.minor() };
    }
}

I used a small helper class to scale the x and the y axis:

Scale.h

#ifndef SCALE_GUARD_310820181451
#define SCALE_GUARD_310820181451

namespace programming_language 
{
    class Scale {
    public:
        Scale(int coordinate_base, int base_of_values, double scale)
            :m_coordinate_base{ coordinate_base }, m_base_of_values{ base_of_values }, m_scale{ scale }
        {
        }

        int operator()(int value) const { return static_cast<int>(m_coordinate_base + (value - m_base_of_values)*m_scale); }
    private:
        int     m_coordinate_base;
        int     m_base_of_values;
        double  m_scale;
    };
}

#endif

Now the biggest headache i had during implementation, was how to place the elements on the y-axis. The x-axis is pretty clear It is just by the years in the file. The y-axis should place the text_ellipse objects on thescreen that they dont overlap. I created a class Grid_y and a class Grid to assign the languages the y position. The Goal here was that the objects dont intersect with each other.

The first object is always put in the middle of the y_grid. If more objects are added and intersect with the previous objects they get put out of the middle. See the code of the classes.

Grid_y.h

#ifndef GRID_Y_GUARD_160820181608
#define GRID_Y_GUARD_160820181608

#include <vector>

namespace programming_language {

    class Grid_y {
    public:
        explicit Grid_y(int size) 
            :positions_occupied(size,false)
        {
        }

        int next_free_position();

        void occupy(int position)
        {
            positions_occupied[position] = true;
        }

        void release(int position)
        {
            positions_occupied[position] = false;
        }

        bool is_free(int position)
        {
            return !positions_occupied[position];
        }
    private:
        std::vector<bool> positions_occupied;
    };
}
#endif

Grid_y.cpp

#include "Grid_y.h"

namespace programming_language
{
    int Grid_y::next_free_position()
        // returns the next free position on the grid
        // first it is always occupied the middle
        // if already occupied take middle +1  
        // if middle + 1 occupied  try middle -1
        // then middle +2 and so on...
        // return -1 to indicate whole grid is full
    {
        auto start = 0;
        if (positions_occupied.size() / 2 == 0) {
            start = (positions_occupied.size() / 2) - 1;
        }
        else {
            start = (positions_occupied.size() / 2);
        }
        auto highest = start;
        auto lowest = start;

        if (!positions_occupied[start]) {
            return start;
        }
        else {
            ++highest;
        }

        for (;;) {
            if (!positions_occupied[highest]) {
                return highest;
            }
            else {
                if (lowest == 0) {
                    return -1;
                }
                --lowest;
            }

            if (!positions_occupied[lowest]) {
                return lowest;
            }
            else {
                if (highest == positions_occupied.size() - 1) {
                    return -1;
                }
                ++highest;
            }
        }
    }
}

Grid.h

#ifndef GRID_GUARD_310820181828
#define GRID_GUARD_310820181828

#include "Grid_y.h"

#include <vector>

namespace programming_language 
{
    class Grid {
    public:
        Grid(int x_begin, int x_end, int y_begin, int y_end);

        int occupy(int x_value, double length);
    private:
        std::vector<Grid_y> x_axis;

        int m_x_begin;
        int m_x_end;
    };
}

#endif

Grid.cpp

#include "Grid.h"

#include <cmath>

namespace programming_language
{
    Grid::Grid(int x_begin,int x_end, int y_begin, int y_end)
        :m_x_begin{x_begin},m_x_end{x_end}
    {
        if (x_begin > x_end) {
            throw std::range_error(
                "Grid(int x_begin,int x_end, int y_begin, int y_end)\n"
                "x_begin > x_end");
        }

        if (y_begin > y_end) {
            throw std::range_error(
                "Grid(int x_begin,int x_end, int y_begin, int y_end)\n"
                "y_begin > y_end");
        }

        for (int i = 0; i < (x_end-x_begin)+1; ++i) {
            x_axis.push_back(Grid_y{ y_end - y_begin+1});
        }
    }

    int Grid::occupy(int x_position, double length)
    {
        length = std::ceil(length); // round up to the next notch

        int x_position_begin = x_position - length - m_x_begin;
        if (x_position_begin < 0) {
            x_position_begin = 0;
        }
        int x_position_end = x_position + length - m_x_begin;
        if (x_position_end >= x_axis.size()) {
            x_position_end = x_axis.size() - 1;
        }

        x_position = x_position - m_x_begin;

        std::vector<int> marked_elements;
        for (;;) {
            auto free_position_y = x_axis[x_position].next_free_position();

            if (free_position_y == -1) {

                for (auto& x : marked_elements) {
                    x_axis[x_position].release(x);
                }

                return free_position_y;
            }

            // range is free
            bool range_is_free = true;
            for (int i = x_position_begin; i <= x_position_end; ++i) {
                if (!x_axis[i].is_free(free_position_y)) {
                    range_is_free = false;
                    break;
                }
            }
            // install element on grid
            if (range_is_free) {
                for (int i = x_position_begin; i <= x_position_end; ++i) {
                    x_axis[i].occupy(free_position_y);
                }

                for (auto& x : marked_elements) {
                    x_axis[x_position].release(x);
                }

                return free_position_y;
            }
            else {
                // mark the element in center to get a new free element on next iteration
                x_axis[x_position].occupy(free_position_y);
                marked_elements.push_back(free_position_y);
            }
        }
    }
}

The Window is drawn and the presented classes are used in Programming_language_gui.

Programming_language_gui.h

#ifndef PROGRAMMING_LANGUAGE_GUI_GUARD_300820181737
#define PROGRAMMING_LANGUAGE_GUI_GUARD_300820181737

#include "Programming_language.h"

#include "Grid.h"
#include "Scale.h"
#include "Text_ellipse.h"

namespace programming_language
{
    int gui_display_languages();

    Year find_min_year(const std::vector<Programming_language>& languages);
    Year find_max_year(const std::vector<Programming_language>& languages);
    Year first_year_of_decade(const Year& year);
    Year first_year_of_next_decade(const Year& year);

    std::string make_x_axis_label(const Year& start_year, const Year& end_year, int x_axis_length);

    std::vector<Programming_language> put_on_grid(const std::vector<Programming_language>& languages, Grid grid, int font_size, double x_scale);

    Graph_lib::Color get_shuffled_color();
}

#endif

Programming_language_gui.cpp

#include "Programming_language_gui.h"

#include "Window.h"
#include "Graph.h"
#include "Arrow.h"

#include <algorithm>
#include <random>
#include <cmath>

namespace programming_language
{
    int gui_display_languages()
    {
        auto programming_languages = read_from_file("languages.txt");

        constexpr int xmax = 1600;
        constexpr int ymax = 900;

        constexpr int xoffset = 100; 
        constexpr int yoffset = 60;

        constexpr int xspace = 40;
        constexpr int yspace = 40;

        constexpr int xlength = xmax - xoffset - xspace;
        constexpr int ylength = ymax - yoffset - yspace;

        const int start_year = first_year_of_decade(find_min_year(programming_languages));
        const int end_year = first_year_of_next_decade(find_max_year(programming_languages));

        const int x_count = (end_year - start_year);
        constexpr int y_count = 20;

        const double xscale = double(xlength) / x_count;
        const double yscale = double(ylength) / y_count;

        Scale xs{ xoffset,start_year,xscale };
        Scale ys{ ymax - yoffset,0,-yscale };

        Graph_lib::Window win{ Point{100,100},xmax,ymax,"Programming Languages" };

        Graph_lib::Axis x{ Graph_lib::Axis::x, Point{xoffset,ymax - yoffset},xlength,(end_year - start_year) / 1,
            make_x_axis_label(start_year,end_year,xlength) };
        x.label.move(static_cast<int>(-xlength / 3.6), 0);      // position to begin of axis

        Graph_lib::Axis y{ Graph_lib::Axis::y, Point{xoffset,ymax - yoffset},ylength,20,"" };

        x.set_color(Graph_lib::Color::black);
        y.set_color(Graph_lib::Color::black);

        win.attach(x);
        win.attach(y);

        auto language_font_size = static_cast<int>(yscale*0.5);

        programming_languages = put_on_grid(programming_languages, Grid{ start_year,end_year,0,y_count }, language_font_size, xscale);

        Graph_lib::Vector_ref<Graph_lib::Text_ellipse> gui_languages;
        for (const auto& language : programming_languages) {
            gui_languages.push_back(
                new Graph_lib::Text_ellipse{
                    Point{
                        xs(language.get_year()),
                        ys(language.get_position())
                    },
                    language.get_name(),
                    language_font_size
                }
            );

            gui_languages[gui_languages.size() - 1].set_fill_color(Graph_lib::Color::yellow);
            gui_languages[gui_languages.size() - 1].set_color(Graph_lib::Color::black);
        }

        const int arrow_height = static_cast<int>(xscale / 2);
        const int arrow_width = static_cast<int>(xscale / 2);
        Graph_lib::Vector_ref<Graph_lib::Arrow> gui_arrows;

        for (auto target = 0; target < gui_languages.size(); ++target) {
            std::string name = gui_languages[target].label();

            auto it = std::find_if(programming_languages.begin(), programming_languages.end(),
                [&name](const Programming_language& pl) { return pl.get_name() == name; });

            if (it != programming_languages.end()) {

                auto name_of_predessors = it->get_name_of_predessors();
                auto color = get_shuffled_color();

                for (const auto& predessor : name_of_predessors) {

                    for (auto source = 0; source < gui_languages.size(); ++source) {

                        if (predessor == gui_languages[source].label()) {

                            gui_arrows.push_back(
                                new Graph_lib::Arrow{
                                    east(gui_languages[source]),
                                    west(gui_languages[target]),
                                    arrow_height,
                                    arrow_width
                                }
                            );

                            gui_arrows[gui_arrows.size() - 1].set_color(color);
                            gui_arrows[gui_arrows.size() - 1].set_fill_color(color);
                        }
                    }
                }
            }
        }

        for (auto i = 0; i < gui_arrows.size(); ++i) {
            win.attach(gui_arrows[i]);
        }

        for (auto i = 0; i < gui_languages.size(); ++i) {
            win.attach(gui_languages[i]);
        }

        return Graph_lib::gui_main();
    }

    Year find_min_year(const std::vector<Programming_language>& languages)
    {
        auto it = std::min_element(
            languages.begin(), languages.end(),
            [](const Programming_language& a, const Programming_language& b)
        {
            return a.get_year() < b.get_year();
        }
        );
        return it->get_year();
    }

    Year find_max_year(const std::vector<Programming_language>& languages)
    {
        auto it = std::max_element(
            languages.begin(), languages.end(),
            [](const Programming_language& a, const Programming_language& b)
        {
            return a.get_year() < b.get_year();
        }
        );
        return it->get_year();
    }

    Year first_year_of_decade(const Year& year)
        // calculates out of year the first year of the decade
        // e.g. 1958 -> 1950
    {
        auto decade_year = year;

        while (decade_year % 10 != 0) {
            --decade_year;
        }
        return decade_year;
    }

    Year first_year_of_next_decade(const Year& year)
        // calculates out of year the first year of the next decade
        // e.g. 1958 -> 1960
    {
        auto decade_year = year;

        while (decade_year % 10 != 0) {
            ++decade_year;
        }
        return decade_year;
    }

    std::string make_x_axis_label(const Year& start_year, const Year& end_year, int x_axis_length)
    {
        std::string label;
        constexpr auto offset = 5;
        constexpr auto sign_len = 4;
        constexpr auto letter_len = 7.0 * sign_len;
        const auto notch_len = x_axis_length / ((end_year - start_year)/offset);

        const auto remaining_len = notch_len - letter_len;
        const int count_of_space = static_cast<int>(remaining_len / sign_len);

        std::string space(count_of_space,' ' );

        for (auto year = start_year; year <= end_year; year += offset){
            if (year != start_year) {
                label += space;
            }
            label += std::to_string(year);
        }

        return label;
    }

    std::vector<Programming_language> put_on_grid(const std::vector<Programming_language>& languages,Grid grid,int font_size,double x_scale)
    {
        auto languages_on_grid = languages;

        for (auto& language : languages_on_grid)
        {
            double length = Graph_lib::calculate_ellipse_width(language.get_name(), font_size);
            length /= x_scale;

            auto position = grid.occupy(language.get_year(), length);
            language.set_position(position);
        }
        return languages_on_grid;
    }

    Graph_lib::Color get_shuffled_color()
    {
        static int selection = 0;

        auto color = Graph_lib::Color::black;

        switch (selection)
        {
        case 0:
            color = Graph_lib::Color::red;
            break;
        case 1:
            color = Graph_lib::Color::blue;
            break;
        case 2:
            color = Graph_lib::Color::dark_green;
            break;
        case 3:
            color = Graph_lib::Color::magenta;
            break;
        case 4:
            color = Graph_lib::Color::dark_magenta;
            break;
        case 5:
            color = Graph_lib::Color::dark_yellow;
            break;
        case 6:
            color = Graph_lib::Color::dark_blue;
            break;
        case 7:
            color = Graph_lib::Color::black;
            break;
        default:
            color = Graph_lib::Color::red;
            selection = 0;
        }

        ++selection;

        return color;
    }
}

main.cpp

#include "Programming_language_gui.h"

int main()
{
    return programming_language::gui_display_languages();
}

Now I would like to know the following.

Is the Code easy to read / understandable? What would you do to improve readability? Any bad practices?

Which stuff could get solved easier?

How can the display of the languages be improved. As we can see in the screenshot above the arrows get placed quite messy. Is there a better algorithm to place the languages?

I think the most painful parts in this program are the placement of the languages and the calculation of the arrows.

Answer 1

First of all, congratulations, the result looks really good and that's a lot of work for an exercise! I particularly like how you frequently used standard algorithms.

That is also quite a lot of code to review! You'll excuse me if I don't review it all, actually a tiny part of it. But rather than getting into the details, I'll underline an important principle: what isn't relevant for one program only should be written as a library. A programmer should strive to minimize the code related only to the problem at hand, so that he, or others, can re-use what he's done of his time and sweat. So let's examine how your concrete problem presents itself: you have to 1) read/parse input, 2) build a graph-like structure from the input and 3) display that structure. That could (should?) have been 3 different code reviews.

Input parsing

There are of course many ways to read input and parse it. Yours isn't bad, but isn't good either because it is too specific for the task at hand. The format is LISP-like (with the addition of a comma between the elements of a list), and it would be a good exercise to write a parser for such a format. If I remember correctly, writing a parser for a simple calculator is the theme of the first few chapters of the book, and you could draw inspiration from it. Write a function Token get_next_token(std::istream& is), and functions to consume the token list according to a BNF grammar that might look like this:

List : ( Atom, ... ) | Nil
Atom : int | string | List

Or you could have tried to write an efficient csv-reader, because your input is very close to this format once you've got rid of the parenthesis:

name, year, predecessor1, ... predecessorN,

But try to find a more general angle to tackle the problem, rather than checking manually is's state n times in your operator >>.

If input reading / parsing isn't something you're interested in, then go for the quick and dirty, instead of submitting 200 lines of code for the same effect (a non-reusable piece of code). With modern C++ you can prototype more or less the same way you'd do with Python:

struct Language : std::vector<std::string> {};
std::istream& operator>>(std::istream& is, Language& language) {
    std::string line;
    if (!std::getline(is, line)) return is;
    language.clear();
    auto wb = line.begin();
    while (true) {
        auto we = std::find(wb, line.end(), ',');
        if (we == line.end()) break;
        language.emplace_back(wb, std::remove_if(wb, we, [](unsigned char c) {
            return std::isspace(c) || c == '(' || c == ')';
        }));
        wb = ++we;
    }
    return is;
}

auto parse_languages(std::istream& is) {
    std::vector<Language> res;
    std::copy(std::istream_iterator<Language>(is), std::istream_iterator<Language>(),
              std::back_inserter(res));
    return res;
}

Then you go on to the things that are of enough interest to warrant generalized code.

Graph-like structure

You have chosen to put your languages directly onto a grid, with connections between languages looking just like an after-thought. It can work in this example because layers are chronological, and because connections aren't too many nor too concentrated. But if you want to improve the lay-out of your languages, you should try to organize them into a data structure reflecting the connections.

Something as simple as std::map<std::string, Language> could be used to that effect. You can then explore the hierarchical links to determine the height of your grid (for now you just have a magical constant, 20, which you probably chose after trial-and-error but would fail in other circumstances), but also to compute a weight for each language: then the heaviest language (the weight being the cumulated number of ascendants and descendants) can be displayed more centrally to avoid ungraceful crossings as much as possible.

You can then distribute your language into decade-layers, with heaviest languages in the middle. That's the occasion to write an algorithm that can be reused to. For instance:

template <typename RandomIterator, typename Comp>
auto heaviest_in_the_middle(RandomIterator first, RandomIterator last, Comp comp) {
    if (std::distance(first, last) < 3) return;
    std::sort(first, last, comp);
    const auto begin = first;
    const auto end = last;
    while (first < last) {
        std::iter_swap(first++, --last);
        ++first, --last;
    }
    std::sort(begin, --first, comp);
    std::sort(first, end, std::not_fn(comp)); // C++17. else std::not2
}

Drawing figures

Drawing an arrow and drawing an ellipsis around a text aren't trivial tasks either and would justify a review on their own. I don't know the library you relied upon but by its name, so I can't review your code (which seems a bit complicated to be honest, unless FLTK is really, really low level).

Again, congratulations, and I'm aware that my review only scratches at the surface of your code, but it surely deserves a review and I have only so much time to spare.