Здравствуйте, Erop, Вы писали:

CS>>Думаю про решение которое и красивое и эффективное.

E>Мне эффективно и поддерживаемо...

typedef unsigned value_t;

struct node
{
   node* left_;
   node* right_;
   value_t value_;
};

generator(iterate_tree_t) 
{
    node* curr;
    std::vector<node*> node_queue;

    iterate_tree_t(node* root) : curr (root) {}

    /** Depth-first iteration over tree
     *  Time complexity: O(N)
     *  Average space complexity: O(log N)
     *  Worst space complexity: O(N)
     */
    emit(node*)
        if (curr)
        {
            node_queue.clear();
            node_queue.reserve(128);
            
            for (;;)
            {
                yield(curr);

               if (curr->left_ && curr->right_)
               {
                   node_queue.push_back(curr->right_);
                   curr = curr->left_;
               }
               else if (curr->left_)
               {
                   curr = curr->left_;
               }
               else if (curr->right_)
               {
                   curr = curr->right_;
               }
               else
               {
                   if (node_queue.empty())
                       break;
                   curr = node_queue.back();
                   node_queue.pop_back();
               }
            }
       }
    stop(0);
};

int main()
{
    node tree [4] = {};
    
    tree[0].value_ = 11;
    tree[0].left_ = &tree[1];
    tree[0].right_ = &tree[2];

    tree[1].value_ = 21;
    tree[1].left_ = &tree[3];
    tree[1].right_ = 0;

    tree[2].value_ = 22;
    tree[2].left_ = 0;
    tree[2].right_ = 0;

    tree[3].value_ = 31;
    tree[3].left_ = 0;
    tree[3].right_ = 0;

    iterate_tree_t iter (&tree[0]);
    do
    {
        node* n = iter();
        if (n)
            std::cout << "node: " << n->value_ << std::endl;
        else
            std::cout << "[end]" << std::endl;
    }
    while (iter);
}

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

Здравствуйте, remark, Вы писали:

R>Здравствуйте, Erop, Вы писали:

CS>>>Думаю про решение которое и красивое и эффективное.

E>>Мне эффективно и поддерживаемо...

R>Переделать на массив дочерних узлов, я надеюсь, особого труда не составит...


Кстати, в результате попытки использовать эту штуку в реальной ситуации вскрылось несколько проблем.

1. Почему "do {...} while (gen);", а не "while (gen) {...};"? А если последовательность пустая?!

2. Попытка вызвать в теле цикла gen() несколько раз приводит в очень неинтуитивному результату. Хотелось бы что бы новый элемент получался только после прохождения итерации, т.е. после вызова gen.operator bool().

3. Необходимость передавать в макрос stop() реальный элемент. Очень не удобно. Очень. Выход из функции должен означать конец последовательности, никаких элементов уже не должно быть.


R>

Здравствуйте, gear nuke, Вы писали:

GN>Здравствуйте, remark, Вы писали:

R>>Но там используется специальный препроцессор, который генерирует код для запоминания/восстановления стековых переменных.

GN>SwitchToFiber решает именно эту задачу в виндовсе. Решения здесь пробегали...


Можно ли создать несколько десятков миллионов фиберов? Что бы каждый фибер занимал не более 32 байт? Что-то я сомневаюсь. Всё-таки на роль очень легковесных потоков фиберы не тянут.

Здравствуйте, remark, Вы писали:

R>Переделать на массив дочерних узлов, я надеюсь, особого труда не составит...

R>

И где тут рекурсия?..

Здравствуйте, remark, Вы писали:

R>2. Попытка вызвать в теле цикла gen() несколько раз приводит в очень неинтуитивному результату. Хотелось бы что бы новый элемент получался только после прохождения итерации, т.е. после вызова gen.operator bool().

как это не интуитивный? генератор на каждый вызов должен новый элемент выдавать.

R>3. Необходимость передавать в макрос stop() реальный элемент. Очень не удобно. Очень. Выход из функции должен означать конец последовательности, никаких элементов уже не должно быть.

Ну я вижу только один достаточно простой выход — кидать эксепшн в конце. как итераторы в питоне.

Здравствуйте, Erop, Вы писали:

R>>Переделать на массив дочерних узлов, я надеюсь, особого труда не составит...

E>И где тут рекурсия?..

С рекурсией ещё проще:

generator(iterate_tree_rec_t, node*) 
{
    node* root;
    std::vector<iterate_tree_rec_t> iter_queue;

public:
    iterate_tree_rec_t(node* root)
        : root (root)
    {}

    emit(node*)
        if (0 == root)
            return;

        yield(root);

        {
            for (size_t i = 0; i != root->children_.size(); ++i)
                iter_queue.push_back(root->children_[i]);
        }

        while (iter_queue.size())
        {
            while (iter_queue.back().next())
                yield(iter_queue.back().value());
            iter_queue.pop_back();
        }

    stop_emit();
};

Это на основе немного пропатченой версии — сейчас я её запосчу.

Здравствуйте, dotidot, Вы писали:

D> Ну я вижу только один достаточно простой выход — кидать эксепшн в конце. как итераторы в питоне.
Для С++ это слишком жёстко

Здравствуйте, remark, Вы писали:

R>С рекурсией ещё проще:

А разве так

struct waw {
    std::vector<waw> Oh;
};

можно?

Здравствуйте, dotidot, Вы писали:

D>Здравствуйте, remark, Вы писали:

R>>2. Попытка вызвать в теле цикла gen() несколько раз приводит в очень неинтуитивному результату. Хотелось бы что бы новый элемент получался только после прохождения итерации, т.е. после вызова gen.operator bool().

D> как это не интуитивный? генератор на каждый вызов должен новый элемент выдавать.


Я, честно говоря, не очень знаком с концепцией генераторов. Зато я, как и любой другой С++ программист, знаком с концепцией итераторов (на которую, кстати, генераторы очень похожи). У С++ итератор функция получения текущего элемента не сдвигает итератор. Поэтому для меня такое поведение генератора *ОЧЕНЬ* не интуитивно.


R>>3. Необходимость передавать в макрос stop() реальный элемент. Очень не удобно. Очень. Выход из функции должен означать конец последовательности, никаких элементов уже не должно быть.

D> Ну я вижу только один достаточно простой выход — кидать эксепшн в конце. как итераторы в питоне.

http://gzip.rsdn.ru/forum/message/2967473.1.aspx

Автор: remark
Дата: 28.05.08

Там можно так же писать просто return посередине функции генерации — это будет означать конец последовательности.

Здравствуйте, remark, Вы писали:

E>>И где тут рекурсия?..

R>С рекурсией ещё проще:

R>Это на основе немного пропатченой версии — сейчас я её запосчу.

http://gzip.rsdn.ru/forum/message/2967473.1.aspx

Автор: remark
Дата: 28.05.08

R>

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, remark, Вы писали:

R>>С рекурсией ещё проще:

E>А разве так

struct waw {
E>    std::vector<waw> Oh;
E>};

можно?


Тебе какие-то религиозные убеждения запрещают так делать? Или что-то более материальное?

Здравствуйте, remark, Вы писали:

E>>А разве так

struct waw {
E>>    std::vector<waw> Oh;
E>>};

можно?

R>Тебе какие-то религиозные убеждения запрещают так делать? Или что-то более материальное?
Кажется, по стандарту, std::vector требует, чтобы его первый параметр был уже полностью определён?
Например, он имеет вроде бы имеет право иметь в себе поле этого типа, скажем, или буффер размера sizeof(тот самый тип)
Соответсвенно такая конструкция, кажется, может быть совместима не со всеми версиями STL...

Здравствуйте, remark, Вы писали:

R>Можно ли создать несколько десятков миллионов фиберов? Что бы каждый фибер занимал не более 32 байт?

Количество создаваемых системой фиберов ограничивается из-за выделения отдельных стеков (менее 8-12KB резервировать не удастся, да еще думать о требованиях к стеку у вызываемых API...) Всегда можно найти неприемлимые условия, так что это не аргумент. Вот на что тянет ручное копирование стековых переменных? Минимум — оверхед в рантайме да еще с генерацией какого-то кода препроцессором... процитирую: "только для С".

Fiber — архитектурно правильное решение. Если локальные переменные аллоцируются в стеке, то они там и хранятся. Плюс сохраняется состояние переменных аллоцированных в регистрах. Время переключения контекстов пренебрежительно мало.

R> Всё-таки на роль очень легковесных потоков фиберы не тянут.

Дык не надо стрелять из пушки по воробьям. Для 32х байт состояния нужны не фиберы, а функторы — и вперёд, синтаксический подсластив генератором c-smile Они тоже не перетасовывают 320Mb на каждый чих

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, remark, Вы писали:

E>>>А разве так

struct waw {
E>>>    std::vector<waw> Oh;
E>>>};

можно?

R>>Тебе какие-то религиозные убеждения запрещают так делать? Или что-то более материальное?

E>Кажется, по стандарту, std::vector требует, чтобы его первый параметр был уже полностью определён?
E>Например, он имеет вроде бы имеет право иметь в себе поле этого типа, скажем, или буффер размера sizeof(тот самый тип)
E>Соответсвенно такая конструкция, кажется, может быть совместима не со всеми версиями STL...


Да... я думаю, что ты прав... хотя вопрос занятный.
Вроде как требования Assignable и CopyConstructible можно удовлетворить и для "не полного" типа — достаточно поместить объявления соотв. функций перед определением переменной vector. А то, что sizeof от типа можно брать — так такого требования к элементам не предъявляется

В любом случае — ну замени ты std::vector<iterate_tree_rec_t> на std::vector<iterate_tree_rec_t*>, чего ты придираешься — рекурсия на лицо.

Здравствуйте, gear nuke, Вы писали:

R>> Всё-таки на роль очень легковесных потоков фиберы не тянут.

GN>Дык не надо стрелять из пушки по воробьям. Для 32х байт состояния нужны не фиберы, а функторы — и вперёд, синтаксический подсластив генератором c-smile Они тоже не перетасовывают 320Mb на каждый чих


Ну так там именно "воробьи" и есть. Поэтому и препроцессор.

Здравствуйте, remark, Вы писали:


R>В любом случае — ну замени ты std::vector<iterate_tree_rec_t> на std::vector<iterate_tree_rec_t*>, чего ты придираешься — рекурсия на лицо.

Просто интересно зачем там массив. IMHO и auto_ptr<iterate_tree_rec_t> хватит

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, remark, Вы писали:


R>>В любом случае — ну замени ты std::vector<iterate_tree_rec_t> на std::vector<iterate_tree_rec_t*>, чего ты придираешься — рекурсия на лицо.

E>Просто интересно зачем там массив. IMHO и auto_ptr<iterate_tree_rec_t> хватит


Если подумать, то должно прокатить прямо так:

generator(iterate_tree_rec_t, node*) 
{
    node* root;

public:
    iterate_tree_rec_t(node* root)
        : root (root)
    {}

    emit(node*)
        if (0 == root)
            return;

        yield(root);

        for (size_t i = 0; i != root->children_.size(); ++i)
        {
               iterate_tree_rec_t inner (root->children_[i]);
               while (inner.next())
                    yield(inner.value());
        }
    stop_emit();
};

По-моему вполне читаемо и поддерживаемо...

Здравствуйте, remark, Вы писали:


R>

R>        for (size_t i = 0; i != root->children_.size(); ++i)
R>        {
R>               iterate_tree_rec_t inner (root->children_[i]);
R>               while (inner.next())
R>                    yield(inner.value());
R>        }
R>

А во что это, по твоему, должно развернуться?

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, remark, Вы писали:


R>>

R>>        for (size_t i = 0; i != root->children_.size(); ++i)
R>>        {
R>>               iterate_tree_rec_t inner (root->children_[i]);
R>>               while (inner.next())
R>>                    yield(inner.value());
R>>        }
R>>

E>А во что это, по твоему, должно развернуться?

А ну да. i и inner надо вынести в переменные класса

Здравствуйте, remark, Вы писали:

R>А ну да. i и inner надо вынести в переменные класса

Ну вот это-то мне тут и не нравится..
Но дальше миссер, дальше...

class CPlusPlusPorno {
    CPlusPlusPorno inner;
};

точно не скомпилируется...