Дерево - найти потомков для каждого узла

[Antonshka]

Привет всем, снова есть вот такая задача. Для тех кому интересно.

В интернете решения не нашел. Как только сам решу, обязательно выложу.

Есть произвольное дерево

Спойлер

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

Есть условие. Узлы 3, 6, и 10, - имеют женский род, к примеру. Узлы 4 и 7, - это домашнее животное. Остальные - мужской род. Узлы домашнего животного нужно пропускать.

Вот что в ответе должно быть:

- Узел 1, имеет 4 узла М и 3 узла Ж

- Узел 2, имеет 1 узел М и 1 узел Ж

- Узлы 5, 6, 8, 9, 10 не имеют потомков узлов, у них по нолям, и М и Ж

- Узел 3, имеет 1 узел М

- Узел 4, хоть и имеет 1 узел М и 1 узел Ж, но так как это ДЖ узел, то он не важен, подсчет для него пропускается

- Узел 7, это ДЖ, подсчет для него пропускается

 

Дерево на рисунке имеет всего три уровня, но в реальности их больше.

 

Изменено 19 марта, 2022 пользователем Antonshka

[Antonshka]

Получилось таким способом

Спойлер

#include <windows.h>
#include <iostream>
#include <string>
#include <queue>


enum class Type : INT { Man, Woman, Pet };

class Container 
{
public:
    Container* child{ nullptr };
    Container* brotherAtRight{ nullptr };
    INT index{ 0 };
    INT manCount{ 0 };
    Type type{ Type::Man };
    INT womanCount{ 0 };
};

int main()
{
	//Create a tree.
    //1
    Container* rootCnt = new Container();
    rootCnt->type = Type::Man;
    rootCnt->index = 1;
    //2
    rootCnt->child = new Container();;
    rootCnt->child->type = Type::Man;
    rootCnt->child->index = 2;
    //3
    rootCnt->child->brotherAtRight = new Container();
    rootCnt->child->brotherAtRight->type = Type::Woman;
    rootCnt->child->brotherAtRight->index = 3;
    //4
    rootCnt->child->brotherAtRight->brotherAtRight = new Container();
    rootCnt->child->brotherAtRight->brotherAtRight->type = Type::Pet;
    rootCnt->child->brotherAtRight->brotherAtRight->index = 4;
    //5
    rootCnt->child->child = new Container();
    rootCnt->child->child->type = Type::Man;
    rootCnt->child->child->index = 5;
    //6
    rootCnt->child->child->brotherAtRight = new Container();
    rootCnt->child->child->brotherAtRight->type = Type::Woman;
    rootCnt->child->child->brotherAtRight->index = 6;
    //7
    rootCnt->child->child->brotherAtRight->brotherAtRight = new Container();
    rootCnt->child->child->brotherAtRight->brotherAtRight->type = Type::Pet;
    rootCnt->child->child->brotherAtRight->brotherAtRight->index = 7;
    //8
    rootCnt->child->brotherAtRight->child = new Container();
    rootCnt->child->brotherAtRight->child->type = Type::Man;
    rootCnt->child->brotherAtRight->child->index = 8;
    //9
    rootCnt->child->brotherAtRight->brotherAtRight->child = new Container();
    rootCnt->child->brotherAtRight->brotherAtRight->child->type = Type::Man;
    rootCnt->child->brotherAtRight->brotherAtRight->child->index = 9;
    //10
    rootCnt->child->brotherAtRight->brotherAtRight->child->brotherAtRight = new Container();
    rootCnt->child->brotherAtRight->brotherAtRight->child->brotherAtRight->type = Type::Woman;
    rootCnt->child->brotherAtRight->brotherAtRight->child->brotherAtRight->index = 10;

	Container* currCnt = nullptr;
    Container* currChild = nullptr;
    std::deque<Container*> queue;
    DWORD_PTR nextItem = 0;
    DWORD_PTR maxItems = 0;

    //Disassemble a tree.
	queue.push_back(rootCnt);
    currCnt = queue.front();
    while (TRUE) 
    {
        if (currCnt->child)
        {
            currChild = currCnt->child;
            while (currChild)
            {
                queue.push_back(currChild);
                currChild = currChild->brotherAtRight;
                maxItems++;
            }
        }
        currCnt = queue[++nextItem];
        if (nextItem == maxItems)
            break;
    }

    //Get counts.
    currCnt = queue.back();
    while (TRUE)
    {
        if (currCnt->child)
        {
            currChild = currCnt->child;
            while (currChild)
            {
                if (currChild->type == Type::Man)
                    currCnt->manCount++;
                if (currChild->type == Type::Woman)
                    currCnt->womanCount++;
                currCnt->manCount += currChild->manCount;
                currCnt->womanCount += currChild->womanCount;
                currChild = currChild->brotherAtRight;
            }
            if (currCnt->type != Type::Pet)
            {
                std::wcout << "index = " << currCnt->index << "\n";
                std::wcout << "manCount = " << currCnt->manCount << "\n";
                std::wcout << "womanCount = " << currCnt->womanCount << "\n";
            }
        }
        if (!maxItems)
            break;
        currCnt = queue[--maxItems];
    }
    return 0;
}

 

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

 

Второе условие задачи, которое конкретно относится ко мне, - есть два вида мужского и женского родов (например до 30 и после 30 лет). Но считать их нужно за одно. То есть, и до 30, и после 30 лет, это один род, хотя и разные типы.

Вот пример решения для этого условия

Спойлер

#include <windows.h>
#include <iostream>
#include <string>
#include <queue>


enum class Type : INT { Man1, Man2, Woman1, Woman2, Pet };
enum class Relation : INT { Child, Brother };

class Container 
{
public:
    Container* child{ nullptr };
    Container* brotherAtRight{ nullptr };
    INT index{ 0 };
    INT manCount{ 0 };
    Type type{ Type::Man1 };
    INT womanCount{ 0 };
};

VOID AddRelative(Container* _rootCnt, Relation _relation, INT _cntIndex, INT _newCntIndex, Type _newType)
{
    Container* currCnt = nullptr;
    Container* currChild = nullptr;
    std::deque<Container*> queue;
    //View a tree.
    queue.push_back(_rootCnt);
    while (!queue.empty())
    {
        currCnt = queue.front();
        //---------------------------------------
        if (currCnt->index == _cntIndex)
        {
            if (_relation == Relation::Child)
            {
                currCnt->child = new Container();
                currCnt->child->index = _newCntIndex;
                currCnt->child->type = _newType;
            }
            else
            {
                currCnt->brotherAtRight = new Container();
                currCnt->brotherAtRight->index = _newCntIndex;
                currCnt->brotherAtRight->type = _newType;
            }
            break;
        }
        //---------------------------------------
        queue.pop_front();
        if (currCnt->child)
        {
            currChild = currCnt->child;
            while (currChild)
            {
                queue.push_back(currChild);
                currChild = currChild->brotherAtRight;
            }
        }
    }
}

VOID GetCounts(Container* _rootCnt)
{
    Container* currCnt = nullptr;
    Container* currChild = nullptr;
    std::deque<Container*> queue;
    DWORD_PTR nextItem = 0;
    DWORD_PTR maxItems = 0;

    //Disassemble a tree.
    queue.push_back(_rootCnt);
    currCnt = queue.front();
    while (TRUE)
    {
        if (currCnt->child)
        {
            currChild = currCnt->child;
            while (currChild)
            {
                queue.push_back(currChild);
                currChild = currChild->brotherAtRight;
                maxItems++;
            }
        }
        currCnt = queue[++nextItem];
        if (nextItem == maxItems) //If the counter (nextItem) of the next element reaches the end of the dynamic queue.
            break;
    }

    //Get counts.
    currCnt = queue.back();
    while (TRUE)
    {
        if (currCnt->child)
        {
            currChild = currCnt->child;
            while (currChild)
            {
                if (currChild->type == Type::Man1 || currChild->type == Type::Man2)
                    currCnt->manCount++;
                if (currChild->type == Type::Woman1 || currChild->type == Type::Woman2)
                    currCnt->womanCount++;
                currCnt->manCount += currChild->manCount;
                currCnt->womanCount += currChild->womanCount;
                currChild = currChild->brotherAtRight;
            }
            if (currCnt->type != Type::Pet)
            {
                std::wcout << "index = " << currCnt->index << "\n";
                std::wcout << "manCount = " << currCnt->manCount << "\n";
                std::wcout << "womanCount = " << currCnt->womanCount << "\n\n";
            }
        }
        if (!maxItems)
            break;
        currCnt = queue[--maxItems]; //First reduce the maxItems, then get the queue element.
    }
}

int main()
{
	//Create a tree.
    //1
    Container* rootCnt = new Container();
    rootCnt->type = Type::Man1;
    rootCnt->index = 1;
    //2
    AddRelative(rootCnt, Relation::Child, 1, 2, Type::Woman2);
    //3
    AddRelative(rootCnt, Relation::Brother, 2, 3, Type::Woman1);
    //4
    AddRelative(rootCnt, Relation::Brother, 3, 4, Type::Man2);
    //5
    AddRelative(rootCnt, Relation::Child, 2, 5, Type::Woman1);
    //6
    AddRelative(rootCnt, Relation::Brother, 5, 6, Type::Pet);
    //7
    AddRelative(rootCnt, Relation::Brother, 6, 7, Type::Man1);
    //8
    AddRelative(rootCnt, Relation::Child, 3, 8, Type::Man1);
    //9
    AddRelative(rootCnt, Relation::Child, 4, 9, Type::Pet);
    //10
    AddRelative(rootCnt, Relation::Brother, 9, 10, Type::Man2);
    //11
    AddRelative(rootCnt, Relation::Brother, 10, 11, Type::Man2);
    //12
    AddRelative(rootCnt, Relation::Child, 6, 12, Type::Man2);
    //13
    AddRelative(rootCnt, Relation::Child, 8, 13, Type::Woman2);
    //14
    AddRelative(rootCnt, Relation::Brother, 13, 14, Type::Woman2);
    //15
    AddRelative(rootCnt, Relation::Child, 12, 15, Type::Woman1);
    //16
    AddRelative(rootCnt, Relation::Brother, 15, 16, Type::Pet);
    //17
    AddRelative(rootCnt, Relation::Child, 14, 17, Type::Man1);
    //18
    AddRelative(rootCnt, Relation::Brother, 17, 18, Type::Woman1);
    //19
    AddRelative(rootCnt, Relation::Brother, 18, 19, Type::Pet);
    //20
    AddRelative(rootCnt, Relation::Child, 16, 20, Type::Woman1);
    //21
    AddRelative(rootCnt, Relation::Child, 18, 21, Type::Pet);
    //22
    AddRelative(rootCnt, Relation::Brother, 21, 22, Type::Man1);
    //23
    AddRelative(rootCnt, Relation::Child, 20, 23, Type::Man2);
    //24
    AddRelative(rootCnt, Relation::Brother, 23, 24, Type::Man1);

    //Get counts.
    GetCounts(rootCnt);
    return 0;
}

 

Здесь добавлена примитивная функция для создания дерева. Сама суть подсчета прежняя.

Это дерево для второго условия

Спойлер

 

Изменено 19 марта, 2022 пользователем Antonshka

[Xipho]

Зачем такие сложности? Чем рекурсия не угодила?

[Antonshka]

6 часов назад, Xipho сказал:

Зачем такие сложности? Чем рекурсия не угодила?

Рекурсия в этом случае не работает, как я понял. Здесь произвольное дерево, которое нужно обойти в ширину.

С помощью рекурсии обход в ширину возможен только для бинарных деревьев. Так я читал в книге.

А так, если и правда есть способ с рекурсией, я бы с большим интересом его посмотрел.

[Xipho]

40 минут назад, Antonshka сказал:

С помощью рекурсии обход в ширину возможен только для бинарных деревьев. Так я читал в книге.

А можешь привести ссылку на эту часть текста, где подобное утверждается? Потому что сомнительно, что вдруг какой-то вид дерева невозможно обойти с помощью рекурсии.

[Xipho]

В 19.03.2022 в 2:02 PM, Antonshka сказал:

Узлы домашнего животного нужно пропускать

Тут, кстати, не сказано, сами узлы пропускаем, а их дочерние элементы считаем, или тоже пропускаем?

 

Не уверен, что правильно понял задачу, конечно, но набросал на коленке решение с рекурсией. Язык - котлин, но разобраться и перенести на плюсы не составит труда. Есть некоторая избыточность в классах, но это для читаемости, чтобы было понимание, почему тот или иной счетчик увеличивается. Код под спойлером, и будет ссылка на плейграунд, чтобы поиграться с кодом

Спойлер

package ru.xipho.tree.tree

open class Node(
    private val child: Node? = null,
    private val brother:  Node? = null
) {
    private var counter = TreeCounter()
    private var exclude: Boolean = false

    private fun countChildren(cnt: TreeCounter) {
        if (!exclude) {
            when (this) {
                is MaleNode -> cnt.males++
                is FemaleNode -> cnt.females++
            }
        }
        child?.countChildren(cnt)
        brother?.countChildren(cnt)
    }

    fun printCounts() {
        exclude = true
        countChildren(counter)
        println("Males: ${counter.males}, females: ${counter.females}")
        exclude = false
    }

}

class MaleNode(c: Node? = null, b: Node? = null): Node(c, b)
class FemaleNode(c: Node? = null, b: Node? = null): Node(c, b)
class MFNode(c: Node? = null, b: Node? = null): Node(c, b)

data class TreeCounter(
    var males: Int = 0,
    var females: Int = 0
)

fun main() {
    val m1 = MaleNode()
    val m2 = MaleNode()
    val m3 = MaleNode()
    val mf1 = MFNode(m3)
    val f1 = FemaleNode(m1, mf1)
    val f2 = FemaleNode(f1, m2)

    val tree = Node(f2)
    tree.printCounts()
}

 

Ссылка на плейграунд https://pl.kotl.in/iN0ndHZF2

[Xipho]

Кстати, если дочерние узлы объединить в коллекцию, а не как сейчас (у ноды один потомок и один брат), то рекурсивный вызов будет один, а эффект не изменится. Это как вариант

[Antonshka]

2 часа назад, Xipho сказал:

А можешь привести ссылку на эту часть текста, где подобное утверждается? Потому что сомнительно, что вдруг какой-то вид дерева невозможно обойти с помощью рекурсии.

Не могу найти, но помню, что натыкался на это. Я сразу стал искать примеры обхода в ширину с помощью очереди. Вот сайт, который я добавил в закладки.

Спойлер

Алгоритм BFS

 

2 часа назад, Xipho сказал:

Тут, кстати, не сказано, сами узлы пропускаем, а их дочерние элементы считаем, или тоже пропускаем?

Да, извиняюсь, тоже заметил, выразился неправильно.

Нужно для всякого узла, который является родителем, получить количество его потомков, М и Ж. Узел типа ДЖ, под номером 4,

является родителем, и для него, как и для других не ДЖ родителей, тоже нужно получить количество своих потомков.

17 минут назад, Xipho сказал:

Кстати, если дочерние узлы объединить в коллекцию, а не как сейчас (у ноды один потомок и один брат), то рекурсивный вызов будет один, а эффект не изменится. Это как вариант

Один потомок и один брат в моем случае не сработает.

2 часа назад, Xipho сказал:

Не уверен, что правильно понял задачу, конечно, но набросал на коленке решение с рекурсией. Язык - котлин, но разобраться и перенести на плюсы не составит труда. Есть некоторая избыточность в классах, но это для читаемости, чтобы было понимание, почему тот или иной счетчик увеличивается. Код под спойлером, и будет ссылка на плейграунд, чтобы поиграться с кодом

Спасибо, попробую сейчас разобраться.

*********************************************************

 

Сложно, незнакомый язык Kotlin.

Там на сайте на выходе -Males: 3, females: 2. Я думал будет что-то вроде:

- Узел 1, имеет 4 узла М и 3 узла Ж

- Узел 2, имеет 1 узел М и 1 узел Ж

Изменено 20 марта, 2022 пользователем Antonshka

[Xipho]

16 часов назад, Antonshka сказал:

Там на сайте на выходе -Males: 3, females: 2. Я думал будет что-то вроде:

Males - это узлы типа М, females  - Ж. Код написан так, чтобы считать потомком у узла, у которого запрошен метод printCounts

 

16 часов назад, Antonshka сказал:

 

Сложно, незнакомый язык Kotlin.

Если будет время и желание, перепишу на плюсы. 

 

16 часов назад, Antonshka сказал:

Один потомок и один брат в моем случае не сработает.

Не совсем понял, почему. Что, например, в коллекции из двух элементов не может выступать в качестве "один потомок и один брат"?

 

[Antonshka]

1 час назад, Xipho сказал:

Males - это узлы типа М, females  - Ж. Код написан так, чтобы считать потомком у узла, у которого запрошен метод printCounts

Получается что каждый узел-родитель должен вызвать для себя рекурсивную функцию подсчета собственных потомков? Каждый раз обходя дерево, начиная со своего личного уровня и до самого нижнего?

Я никак не пойму тот код на Kotlin, потому не знаю даже того алгоритма. Но если так, как я написал выше, то не получится ли что некоторые узлы будут посещаться более одного раза?

Спойлер

P - это узел-родитель. Ветвь на рисунке слева, где 35 сравнений, это при рекурсии. Где 10 сравнений, это при использовании очереди, без рекурсии.

35 или 10 сравнений, это сравнения "if", на то какого типа данный узел.

 

Помимо всего прочего, при рекурсии, нужно же еще обойти дерево для определения кто есть узел-потомок, чтобы вызвать для него/них рекурсивный подсчет?

 

1 час назад, Xipho сказал:

Не совсем понял, почему. Что, например, в коллекции из двух элементов не может выступать в качестве "один потомок и один брат"?

Я не совсем понимаю что такое коллекция. Это контейнер с одним потомком и одним братом? Если так, то у меня ситуация немного иная, - у меня у родителя может быть два разных потомка, у которых имеются свои братья, числом более одного.

Например, родитель имеет потомка childL и childR, но childL и childR между собой не братья, хотя у них и один родитель. У childL и у childR есть свои братья, много братьев. И childL и childR и их братья, сами могут быть для кого-то родителями. И так далее.

Изменено 21 марта, 2022 пользователем Antonshka

[Xipho]

20 минут назад, Antonshka сказал:

нужно же еще обойти дерево для определения кто есть узел-потомок

Вообще не понял. В общем, распиши постановку задачи нормально, так будет куда проще понять. Например, чем отличается в твоем дереве потомок от брата. Имеется в виду, концептуально.

[Antonshka]

1 час назад, Xipho сказал:

Вообще не понял. В общем, распиши постановку задачи нормально, так будет куда проще понять. Например, чем отличается в твоем дереве потомок от брата. Имеется в виду, концептуально.

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

Вот схема обычного произвольного дерева, в моем представлении

Спойлер

На этой схеме, у родителя может быть только один потомок. Родитель и потомок могут иметь своих братьев. Тот потомок или брат, у которого есть свой потомок, является также и родителем.

 

Но в моем случае, мне пришлось сделать так, что у родителя может быть и два потомка (максимум). Более того, родитель у меня может быть двух видов, V и H.

- У родителя V могут быть только потомки типа L и R.

- У родителя H могут быть только потомки типа T и B.

- У родителя L или R могут быть только потомки типа L.

- У родителя T или B могут быть только потомки типа T.

Это так я составил схему, алгоритм, по которым работает Docking система

Спойлер

 

Когда я добавляю или удаляю окно в Docking систему, мне нужно пересчитывать количество потомков для всех узлов-родителей во всем дереве.

Сейчас перерасчет работает при помощи очереди. Особо не видно чтобы тормозило, но не знаю, может с рекурсией будет и быстрее.

А так, все работает как надо. Остались мелкие доработки. Рисовать заголовки у окон, кнопки на них, и т.д.

Спойлер

 

Изменено 21 марта, 2022 пользователем Antonshka

[Xipho]

15 часов назад, Antonshka сказал:

Вот схема обычного произвольного дерева, в моем представлении

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

Ты не объяснил, чем концептуально брат отличается от потомка. Из схемы эту разницу вывести не представляется возможным. 

И я немного не понимаю, зачем тебе такая сложность с Docking системой. Закрадывается ощущение, что ты занимаешься каким-то диким оверинжинирингом. 

[Antonshka]

2 часа назад, Xipho сказал:

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

Я опять извиняюсь за свою косноязычность. Я неправильно нарисовал схему. Я не написал что братья сами также являются потомками.

Просто метод построения произвольного дерева, согласно этому источнику, - у узла-родителя есть один потомок, самый левый, а у этого самого левого потомка, братья. Эти браться являются также потомками этого родителя, но связь с родителем идет через самого левого потомка.

 

Вот, а у меня, два потомка, "самых левых", у родителя, с братьями у каждого.

А так, если вернуться к задаче этого поста, то нужно взять дерево, и для всех узлов-родителей, найти количество их потомков.

Спойлер

Вот что в ответе должно быть:

- Узел 1, имеет 4 узла М и 3 узла Ж

- Узел 2, имеет 1 узел М и 1 узел Ж

- Узел 3, имеет 1 узел М

- Узел 4, имеет 1 узел М и 1 узел Ж

 

2 часа назад, Xipho сказал:

И я немного не понимаю, зачем тебе такая сложность с Docking системой. Закрадывается ощущение, что ты занимаешься каким-то диким оверинжинирингом. 

Самому тяжело это все реализовывать, сам удивляюсь этой сложности. Но как я писал ранее, слишком много разных взаимодействий и влияний одних окон на другие, при вставке, изменении размера главного окна. Чтобы сохранялись/восстанавливались пропорции. Пока я не начинал писать код, мне тоже казалось что будет легко. Но на самом деле, там все по хитрому.

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

Спойлер

 

 

Изменено 22 марта, 2022 пользователем Antonshka

[Xipho]

1 час назад, Antonshka сказал:

слишком много разных взаимодействий и влияний одних окон на другие, при вставке, изменении размера главного окна

Ну вот это, уж извини, полная фигня. Родительское окно должно давать сигнал об изменении своих размеров только дочерним окнам первого уровня. А они уже, при изменении своих - своим дочерним при изменении своего размера. В феодальном государственном строе это называлось "Вассал моего вассала - не мой вассал". Это разные ответственности, но сразу проглядывается общность. А ты взваливаешь все ответственности на главное окно, сам себе усложняя жизнь.

 

Вот небольшая схемка отношений между окнами.

Спойлер

Пунктиром помечена общая архитектурная часть, которую необходимо реализовать. И если ты реализуешь ее достаточно гибко, у тебя система будет самоподдерживающейся для любого количества дочерних окон. А то, что пытаешься сделать ты - громоздко и неуниверсально.

В общем, срочно читать про паттерны проектирования (книгу банды четырех прямо непременно. Они там как раз при проектирования редактора схожие проблемы решают), и перестать стрелять себе в ногу.

[Antonshka]

2 часа назад, Xipho сказал:

Ну вот это, уж извини, полная фигня. Родительское окно должно давать сигнал об изменении своих размеров только дочерним окнам первого уровня. А они уже, при изменении своих - своим дочерним при изменении своего размера.

У меня почти так.

Каждая полоса-разделитель имеет в своем классе указатель на то окно, с которым она ассоциирована. А окно в свою очередь, имеет указатель на контейнер, с которым оно ассоциировано.

При смещении полосы, изменяется размер контейнера, а затем, по всем правилам, нужно было бы подкорректировать размеры всех нижележащих контейнеров-потомков, как ты пишешь. Но, у меня не так, в моем случае я беру самый корень дерева, и корректирую размеры вообще всех контейнеров. Это конечно не правильно, это излишне. Но я так делаю вот по какой причине.

Спойлер

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

 

Я нигде не смог найти алгоритма, по которому можно сделать Docking систему, вообще ноль информации. Есть уже готовая система и исходники, для Imgui, но во первых она работает коряво, мне не нравится поведение окон, во вторых я не могу разобраться в коде, что там и к чему.

Есть еще своя родная Docking система в Imgui, но там я тоже не могу разобраться в коде, что там и к чему.

Мне проще было придумать и написать свою, двигая и анализирую окна в VS.

Про шаблон подписки я прочитал, видел и код примера.

 

Что по поводу рекурсивной функции, для задачи поста? Есть ли возможность использовать ее, или оставить очередь?

 

Изменено 22 марта, 2022 пользователем Antonshka

[Xipho]

Для задачи поста можно использовать рекурсию, но не думаю, что это будет рационально в твоем случае. Я бы всё-таки предложил пересмотреть архитектуру. При изменении одного окна (сплиттер, кстати, тоже можно считать окном, просто специфичным, что облегчит задачу) перебирать всё дерево - это стопроцентный оверинжиниринг. И если бы ты эту библиотеку делал опенсорсной, и я был бы ревьюером, я бы такой код ни за что не пропустил.

[Antonshka]

45 минут назад, Xipho сказал:

При изменении одного окна (сплиттер, кстати, тоже можно считать окном, просто специфичным, что облегчит задачу)

Вначале я делал сплиттер из статического текстового контрола, перехватывая WM_PAINT и заполняя цветом фон. Но, способ оказался глючным. Неполное закрашивание.

Сейчас сплиттеры это простые окошки, как ты пишешь.

45 минут назад, Xipho сказал:

 перебирать всё дерево - это стопроцентный оверинжиниринг.

Вообще да, лишние телодвижения ни к чему. Сейчас полный перебор дерева происходит только при изменении размеров главного окна, когда в любом случае все окна и контейнеры нужно как-то корректировать. При смещениях полосок, - я пока не знаю как это все будет. Я только сейчас начал заниматься ими. Надеюсь будет достаточно изменить только размеры нижележащих потомков.

Все упирается в эти полоски, точнее в эти относительные размеры потомков к их родителю.

Кстати Imgui в этом плане не следит за оставшимися промежутками между окнами при полном их сжатии. Видны разные по ширине промежутки, это некрасиво. Также в Imgui неудобно изменять размеры окон при перетаскивании полосок. В VS при перемещении полоски родителя, вообще все потомки также смещаются, и это удобно, в Imgui же не так, в Imgu изменяется размер только соседнего окна, и при вставке нового окна с внешней стороны, то есть в главное окно, приходится каждое окно обратно возвращать на свое место, вместо того чтобы взять и один раз сместить полоску нового вставленного окна. Не знаю, зачем он так сделал.

Изменено 22 марта, 2022 пользователем Antonshka

[Xipho]

14 часов назад, Antonshka сказал:

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

Еще раз. Обновление размеров дочерних окон - не ответственность главного (родительского для любого уровня) окна. Его ответственность - сгенерировать событие изменения размера. А те, кто в этом заинтересован - они должны это событие мониторить. Тогда у тебя не будет проблем с "братьями" (это окна, находящиеся на одном уровне, если я правильно понял твою концепцию). Каждое из окон, помимо возможности генерации события изменения собственного размера должно само быть подписано на события родительского окна, и такие же события "братьев". И всё. Архитектурно это решается достаточно просто, и на выходе ты получишь нормальную гибкую систему, которую и хочешь получить. Причем, кода для этого придется написать немного, и он будет универсальным. Под изменением размера, кстати, подразумевается и изменение положения окна относительно родительского, конечно же. Но можно это разбить на два события, тут уж на твое усмотрение (хотя я бы объединил - типа изменение координат и там и там получается).

[Antonshka]

3 часа назад, Xipho сказал:

Еще раз. Обновление размеров дочерних окон - не ответственность главного (родительского для любого уровня) окна. Его ответственность - сгенерировать событие изменения размера. А те, кто в этом заинтересован - они должны это событие мониторить.

Кажется теперь я понял, что ты имеешь ввиду.

Действительно, у меня сейчас не так, как ты пишешь. У меня окно-родитель/контейнер-родитель, после изменения своего размера, начинает перебирать всех своих личных потомков (непосредственных), корректируя их размеры, а те, после корректировки, делают тоже самое со своими личными потомками, и так до самого последнего потомка, для этой ветви.

Как мне кажется, по сути это ни чем не отличается от твоего варианта. У тебя сами личные потомки должны как-то отреагировать на событие, причем они должны соблюсти еще и последовательность, - вначале самый крайний изменяет свой размер, затем по очереди соседи, так как сосед справа равняется на соседа слева.

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

Что-то вроде урока физкультуры, - учитель говорит "равняйсь", а ученики по очереди начинают равняться друг на друга.

Что плохого в этом моей способе?

 

[Xipho]

1 час назад, Antonshka сказал:

Что плохого в этом моей способе?

1. Ты размазываешь ответственности, то есть, у тебя "родители" делают работу, которую не должны делать (Нарушение принципа единственной ответственности)

2. Ты открываешь детали объекта наружу - родительский объект ничего не должен знать о размера потомка. Размеры потомка - дело самого потомка  (Нарушение принципа инкапсуляции  + изменение состояния объекта извне - антипаттерн)

3. Ты усложняешь систему там, где в этом нет необходимости (нарушение принципа KISS - keep it simple, stupid)

4. Сложность твоего алгоритма в лучшем случае будет O(n), в худшем, даже без использования рекурсии может стремиться к O(n!). Тут, правда, это не сильно актуально, поскольку у дочерних окон будет все равно не больше 3-4 уровней вложенности (иначе это уже ошибка UI дизайна)

 

Это то, что сходу в голову пришло. Уверен, если ты мне дашь свой код на ревью, я еще с десяток пунктов найду.

 

[Antonshka]

1 час назад, Xipho сказал:

1. Ты размазываешь ответственности, то есть, у тебя "родители" делают работу, которую не должны делать (Нарушение принципа единственной ответственности)

2. Ты открываешь детали объекта наружу - родительский объект ничего не должен знать о размера потомка. Размеры потомка - дело самого потомка  (Нарушение принципа инкапсуляции  + изменение состояния объекта извне - антипаттерн)

3. Ты усложняешь систему там, где в этом нет необходимости (нарушение принципа KISS - keep it simple, stupid)

4. Сложность твоего алгоритма в лучшем случае будет O(n), в худшем, даже без использования рекурсии может стремиться к O(n!). Тут, правда, это не сильно актуально, поскольку у дочерних окон будет все равно не больше 3-4 уровней вложенности (иначе это уже ошибка UI дизайна)

 

Это то, что сходу в голову пришло. Уверен, если ты мне дашь свой код на ревью, я еще с десяток пунктов найду.

 

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

currChildCnt = parent->childT;
while (currChildCnt)
{
	currChildCnt->bottomDiv->Top = ...
	currChildCnt = currChildCnt->brotherAtRight;
}

Я часто путаюсь, извиняюсь.

[Xipho]

Вдобавок к паттернам обязательно читать дядюшку Боба (Роберт Мартин) "Чистый код" (примеры на Java, но суть уловить несложно), и его же "Чистая архитектура" (книга более-менее абстрактная без привязок к коду). 

Прямо настоятельно рекомендую отложить код в сторону до полного прочтения книг, которые предлагал выше и предлагаю сейчас.

[Antonshka]

5 часов назад, Xipho сказал:

Вдобавок к паттернам обязательно читать дядюшку Боба (Роберт Мартин) "Чистый код" (примеры на Java, но суть уловить несложно), и его же "Чистая архитектура" (книга более-менее абстрактная без привязок к коду). 

Прямо настоятельно рекомендую отложить код в сторону до полного прочтения книг, которые предлагал выше и предлагаю сейчас.

У меня на очереди была книга Рихтера. Добавлю и эти к ней. Спасибо.

Не могу отложить код, он не завершен. Доведу до рабочего состояния только Docking, и приступлю к книгам.

[KRYPTOPUNK]

У меня есть система UI, которая считает свои размеры относительно родительского "окна" в процентах на каждом "эвенте" OnResize
Правда там система скорее как в вебе, где отношения размеров "родитель"->"потомок" указывается в процентном соотношении. 
Так вот, на каждый ресайз вызывается OnResize для каждого элемента системы и он пересчитывает свои размеры на основе размеров родителя и своих отступов от границ родительского окна. 
Удобно, достаточно, и не сильно сложно по big-O. 

И да, там уже можно не строить дерево руками, а у каждого элемента просто хранить вектор с детьми проходясь range-based циклом

Изменено 24 марта, 2022 пользователем KRYPTOPUNK