100 задач для начинающего программиста на C#

Граф объектов – это, по сути, все объекты некоторой системы и их связи. Один объект может ссылать на другой, образуя связь has-a. Набор таких объектов и связей мы можем воспринимать как граф.

С точки зрения теории графов и их обходов, очень интересны ситуации, когда объекты имеют неопределённое количество уровней вложенности. Например, давайте представим систему комментариев, в которой можно давать ответы на комментарии. В итоге мы можем получить очень длинные ветви обсуждения, в каждой из которой может быть произвольное количество вложенных комментариев.

Их можно описать таким образом:

class Comment
{
    public string Text;
    public List<Comment> Childrens = new List<Comment>();
}

Это максимально примитивный вариант, чуть позже мы рассмотрим как его можно инкапсулировать. Теперь давайте представим с помощью такой модели следующую ветку комментариев:

-Книга говно

–Согласен!

—Ты ничего не понимаешь!

–Не согласен

-У вас ошибка во втором абзаце

–Исправил, спасибо!

var pageComments = new List<Comment>()
{
    new Comment()
    {
        Text = "Книга говно",
        Children = new List<Comment>()
        {
            new Comment
            {
                Text = "Согласен!",
                Children = new List<Comment>()
                {
                    new Comment()
                    {
                        Text = "Ты ничего не понимаешь!"
                    }
                }
            },
            new Comment
            {
                Text = "Не согласен"
            }
        }
    },
    new Comment
    {
        Text = "У вас ошибка во втором абзаце",
        Children = new List<Comment>()
        {
            new Comment()
            {
                Text = "Исправил, спасибо!"
            }
        }
    }
};

Как обращаться с такой структурой данных? Всё очень просто, если понимать принципы обхода графов. Давайте сделаем функцию, которая может отрисовать наши комменты. Для начала можно попробовать такой код:

public static void DrawComments(IEnumerable<Comment> comments)
{
    var open = new Stack<Comment>(comments.Reverse());
    var closed = new List<Comment>();
    var line = 0;

    while(open.Count > 0)
    {
        var comment = open.Pop();

        Console.SetCursorPosition(0, line++);
        Console.WriteLine(comment.Text);

        foreach (var childer in comment.Childrens.Reverse<Comment>())
            open.Push(childer);
    }
}

Он даёт такой вывод:

Книга говно
Согласен!
Ты ничего не понимаешь!
Не согласен
У вас ошибка во втором абзаце
Исправил, спасибо!

Все хорошо, но… А как же отображение вложенности? Мы отображаем комментарии в правильном порядке, но на момент отображения мы не знаем, на каком уровне он находится. В задаче всё-таки требовалось, чтобы перед комментарием отображались палочки по количеству уровней.

При обходе комментариев, при добавлении их в открытый список, нужно также записывать куда-то уровень вложенности. Самый простой способ – завести словарь.

public static void DrawComments(IEnumerable<Comment> comments)
{
    var open = new Stack<Comment>(comments.Reverse());
    var commentsDepth = new Dictionary<Comment, int>();
    var line = 0;

    while(open.Count > 0)
    {
        var comment = open.Pop();

        if (commentsDepth.ContainsKey(comment) == false)
            commentsDepth.Add(comment, 1);

        var depth = commentsDepth[comment];

        Console.SetCursorPosition(0, line++);
        Console.WriteLine($"{string.Empty.PadLeft(depth, '-')} {comment.Text}");

        foreach (var child in comment.Childrens.Reverse<Comment>())
        {
            commentsDepth.Add(child, depth + 1);
            open.Push(child);
        }
    }
}

- Книга говно
-- Согласен!
--- Ты ничего не понимаешь!
-- Не согласен
- У вас ошибка во втором абзаце
-- Исправил, спасибо!

Словарь позволил нам провести ассоциацию: комментарий – уровень вложенности. Мы также могли записывать его в поле объекта, но тогда мы бы немного нарушили модель. Дело в том, что комментарий ничего не знает о своих родителях, а посему не может сам контролировать этот вопрос.

Давайте переделаем модель на такой вариант:

class Comment
{
    public string Text;
    public Comment Parent;
}

Многое ли изменилось? И да и нет. Это всё ещё граф, но теперь мы провели чёткий формализм – у одного комментария может быть один родитель. Предыдущая ситуация позволяла относить один и тот же комментарий к разным родителям, что, конечно же, не корректно.

Как работать с такой моделью? Попробуем представить через неё прошлые данные:

class Program
{
    public static void Main(string[] args)
    {
        Comments comments = new Comments();
        var bookIsShit = comments.Reply("Книга говно!", null);
        var youHaveAnError = comments.Reply("У вас ошибка во втором абзаце", null);
        var iAgree = comments.Reply("Я согласен", bookIsShit);
        var youDoNotUnderstandAnything = comments.Reply("Ты ничего не понимаешь!", iAgree);
        var iDisagree = comments.Reply("Не согласен", bookIsShit);
        var fixedIt = comments.Reply("Я исправил, спасибо!", youHaveAnError);
    }

}

class Comments
{
    private readonly List<Comment> _allComments = new List<Comment>();

    public Comment Reply(string text, Comment target)
    {
        var newComment = new Comment()
        {
            Parent = target,
            Text = text
        };

        _allComments.Add(newComment);

        return newComment;
    }
}

Для простоты работы я завёл класс Comments, а также добавил в него хранилище всех комментариев, чтобы в дальнейшем с ними работать. Вернёмся к функции рисования, попробуем написать её с изменённой моделью.

Основную сложность вызывает тот факт, что раньше мы обходили граф с условного верха вниз, и модель уже была почти полностью отсортированной, поэтому то, в каком порядке мы обходим граф – уже было самодостаточным.

Теперь это не так. Если мы возьмём любой комментарий, мы больше опускаем снизу вверх, начиная с верхнего уровня, а поднимаемся от произвольного комментария вверх. Точнее, в принципе обходить такой граф нет смысла, класс Comments поставляет нам все возможные комментарии, и нам нужно их как-то отрисовать.

Вопрос отрисовки стал краеугольным. При переборе всех комментариев, мы больше не понимаем, в какой точке его нужно рисовать, так как перебор идёт в произвольном порядке. Как быть?

Самое просто решение – отсортировать комментарии, и получить модель по представлению близкой к той, что у нас была в прошлый раз. Это добавляет нам геморроя, но мы точней выразили контракт: 1 комментарий, 1 родитель.

Можем ли мы производить сортировку на момент добавления комментария? Да, на самом деле, без проблем. Мы можем предоставить одному классу права на редактирование списка дочерних комментариев, а другому дать их только на чтение.

Например так:

class Comments
{
    private readonly List<Comment> _allComments = new List<Comment>();

    public IEnumerable<Comment> AllComments => _allComments;

    public Comment Reply(string text, Comment target)
    {
        var newComment = new Comment(text, target);

        _allComments.Add(newComment);

        if(target is IWritableParent<Comment> parent)
            parent.AddChild(newComment);

        return newComment;
    }
}

interface IReadableParent<T>
{
    IEnumerable<T> Children { get; }
}

interface IWritableParent<T>
{
    void AddChild(T element);
}

class Comment : IWritableParent<Comment>, IReadableParent<Comment>
{
    public IEnumerable<Comment> Children => _children;

    private List<Comment> _children = new List<Comment>();
    private string _text;
    private Comment _parent;

    public Comment(string text, Comment parent)
    {
        _text = text;
        _parent = parent;
    }

    void IWritableParent<Comment>.AddChild(Comment element)
    {
        _childrens.Add(element);
    }
}

Теперь комментарий неявно реализует интерфейс IReadeableParent, и любой желающий может узнать список его дочерних объектов, но никто не может менять, так как реализация интерфейса IWritableParent явная и нужно сознательно сделать кастинг к этому типу, что делает класс Comments.

Эта связь хрупкая. Если кто-то уберёт у комментария этот интерфейс, то система сломается в процессе выполнения. Давайте немного доработаем метод Reply, чтобы нельзя было ответить на комментарий, который не может являться контейнером других комментариев.

public T Reply<T>(string text, T target) where T : Comment, IWritableParent<Comment>
{
    var newComment = new Comment(text, target);

    _allComments.Add(newComment);

    target.AddChild(newComment);

    return (T)newComment;
}

Не самое изящное использование Generic’ов, но нашу цель выполняет. Это небольшой хак, который позволяет закрепить ожидания от входных значений: комментарий, на который мы будем отвечать, для нас является контейнером.

В результате мы можем вернуться к предыдущей функции отрисовки. Но часто бывает, что модель, когда у нас есть только представление о родителе, является прямой проекций таблицы из базы данных, где, как раз-таки, в поле записи записывается родитель. И нам ничего не остаётся, как работать с объектами, которые знают только о своём родителе, но не о своих потомках, что делать в таком случае?

Нам нужно их сконвертировать, представим, что база представляет нам массив комментариев, каждый из которых знает только о своём родителе.

class Program
{
    public static void Main(string[] args)
    {
        Comments comments = new Comments();
        var bookIsShit = comments.Reply("Книга говно!", null);
        var youHaveAnError = comments.Reply("У вас ошибка во втором абзаце", null);
        var iAgree = comments.Reply("Я согласен", bookIsShit);
        var youDoNotUnderstandAnything = comments.Reply("Ты ничего не понимаешь!", iAgree);
        var iDisagree = comments.Reply("Не согласен", bookIsShit);
        var fixedIt = comments.Reply("Я исправил, спасибо!", youHaveAnError);

        Draw(comments.AllComments);
    }

    public static void Draw(IEnumerable<Comment> comments)
    {
        var children = GetChildren(comments);
        var open = new Stack<Comment>(comments.Reverse());
        var closed = new List<Comment>(comments.Count());
        var commentsDepth = new Dictionary<Comment, int>();
        var line = 0;

        while (open.Count > 0)
        {
            var comment = open.Pop();

            if (closed.Contains(comment))
                continue;

            closed.Add(comment);

            if (commentsDepth.ContainsKey(comment) == false)
                commentsDepth.Add(comment, 1);

            var depth = commentsDepth[comment];

            Console.SetCursorPosition(0, line++);
            Console.WriteLine($"{string.Empty.PadLeft(depth, '-')} {comment.Text}");

            foreach (var child in children[comment])
            {
                commentsDepth.Add(child, depth + 1);
                open.Push(child);
            }
        }
    }

    private static Dictionary<Comment, List<Comment>> GetChildren(IEnumerable<Comment> comments)
    {
        var children = new Dictionary<Comment, List<Comment>>();

        foreach (var comment in comments)
        {
            if (children.ContainsKey(comment) == false)
                children.Add(comment, new List<Comment>());

            if (comment.Parent == null)
                continue;

            if (children.ContainsKey(comment.Parent) == false)
                children.Add(comment.Parent, new List<Comment>());

            children[comment.Parent].Add(comment);
        }

        return children;
    }
}

class Comments
{
    private readonly List<Comment> _allComments = new List<Comment>();

    public IEnumerable<Comment> AllComments => _allComments;

    public Comment Reply(string text, Comment target)
    {
        var newComment = new Comment(text, target);

        _allComments.Add(newComment);

        return newComment;
    }
}

class Comment
{
    public readonly string Text;
    public readonly Comment Parent;

    public Comment(string text, Comment parent)
    {
        Text = text;
        Parent = parent;
    }
}