Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
 Рекурсивные итераторы (тяпничное)  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Привет котаны-братаны!

На сегодня тема - просто продолжение Тяпничная будущая мультипоточность

Я решил не флудить на мультипоточке. Там - более общие вопросы.

Здесь будет:
- итератор по дереву и по графу.
- итератор по кривым заполняющим пространство (вышеуказанный Гилберт, Пеано)
- прочие практически линейные штуки Z-кривая Мортона, прямоугольная спираль и прочее. Различные линейные обходы.
- обход лабиринта

Напомню что интерфейс итератор (во многих языках разработки имеет всего 2 метода) + произвольный конструктор
который в общем случае неформализован.

interface Iterator<T> {
   boolean hasNextElement();
   T nextElement();
}


Здесь будут:
- Разные ЯП. Каналы-шманалы. Пайплайны-шмалайны. Корутины-шморутины. Фучерсы. Промисы. Ленивые списки.
+Я обещал чортов Golang.
+Кто-то обещал Ф-Шарп.

Что здесь не будет:
- Вопросов "зачем". Это пятничный топик и поэтому "зачемы" - я проигнорирую.

Что надо?
- Заимплеменить итератор по рекурсивной структуре.
- Оценить красоту и изящество имплементации.

Gogo!
25 окт 19, 19:09    [22002984]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные итераторы (тяпничное)  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6382
Итератор по дереву.
C++11, Boost.Coroutine2.

#include <boost/coroutine2/all.hpp>

#include <functional>
#include <iostream>
#include <vector>

#define LOG_TRACE(x) do { std::cout << x << std::endl; } while (0)


// Some tree with a recursive walker
struct TreeNode {
    TreeNode(int value)
        : value(value) {}

    int value;
    std::vector<TreeNode> children;

    // recursive walk
    void walk_tree(std::function<void(const TreeNode& node, int level)> output, int level = 0) const
    {
        output(*this, level);
        for (auto& c: children) {
           c.walk_tree(output, level + 1);
        }
    }
};

// Implementation of iterator with coroutine
template <class T>
struct TreeIterator {
    // Wrapper for tree node + level
    struct TreeValue {
        TreeValue(int level, const T& node)
            : level(level)
            , node(node)
        {}
        int level;
        const T& node;
    };

    // C-tor from a tree
    TreeIterator(const T& node)
        : m_reader(make_coro_reader(node))
        , m_iterator(begin(m_reader))
    {}

    // Iterator interface

    bool has_next()
    {
        return m_iterator != end(m_reader);
    }

    TreeValue next()
    {
        auto rv = *m_iterator;
        ++m_iterator;
        return rv;
    }

private:
    // Coroutine helper class
    using CoroType = boost::coroutines2::coroutine<TreeValue>;

    // Reading coroutine (main)
    using CoroReader = typename CoroType::pull_type;

    // Reading coroutine iterator
    using CoroReaderIter = typename CoroReader::iterator;

    // Generating coroutine (walker)
    using CoroWalker = typename CoroType::push_type;

    static CoroReader make_coro_reader(const T& node)
    {
        CoroReader rv([&node](CoroWalker& sink){
            node.walk_tree([&sink](const T& node, int level) {
                sink(TreeValue(level, node));
            });
        });
        return  rv;
    }

private:
    CoroReader m_reader;
    CoroReaderIter m_iterator;
};

int main()
{
    // 1
    // |- 11
    // |- 12
    //     |-121
    //     |-122
    // |- 13
    TreeNode tree{1};
    tree.children.emplace_back(11);
    tree.children.emplace_back(12);
    tree.children.emplace_back(13);
    tree.children[1].children.emplace_back(121);
    tree.children[1].children.emplace_back(122);

    // print recursively
    tree.walk_tree([](const TreeNode& node, int level){
        LOG_TRACE(std::string(level*2, ' ') << node.value);
    });

    // print sequentially via iterator that flattens the tree using a coroutine
    for (auto it = TreeIterator<TreeNode>(tree); it.has_next(); ) {
        auto next = it.next();
        LOG_TRACE(std::string(next.level*2, ' ') << next.node.value);
    }
    return 0;
}
26 окт 19, 12:12    [22003158]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные итераторы (тяпничное)  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Шикарно. Сегодня попробую скомпилировать.

Репка нужна? Я не знаю пока.
26 окт 19, 13:32    [22003178]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные итераторы (тяпничное)  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6382
mayton
Репка нужна? Я не знаю пока.

Лень так далеко заходить ))

Итератор по дереву с явным стеком.
Чистый C++11 (без Boost)

#include <functional>
#include <iostream>
#include <stack>
#include <vector>

#define LOG_TRACE(x) do { std::cout << x << std::endl; } while (0)


// Some tree with a recursive walker
struct TreeNode {
    TreeNode(int value)
        : value(value) {}

    int value;
    std::vector<TreeNode> children;

    // recursive walk; support for CoroTreeIterator
    void walk_tree(std::function<void(const TreeNode& node, int level)> output, int level = 0) const
    {
        output(*this, level);
        for (auto& c: children) {
           c.walk_tree(output, level + 1);
        }
    }

    // Iterating over children; support for StackTreeIterator
    std::vector<TreeNode>::const_iterator begin() const
    {
        return children.begin();
    }

    std::vector<TreeNode>::const_iterator end() const
    {
        return children.end();
    }
};

// Implementation of iterator using explicit stack
template <class T>
struct StackTreeIterator {
    // Wrapper for tree node + level
    struct TreeValue {
        TreeValue(int level, const T& node)
            : level(level)
            , node(node)
        {}
        int level;
        const T& node;
    };

    // C-tor from a tree
    StackTreeIterator(const T& node)
    {
        m_stack.emplace(State(node));
    }

    // Iterator interface

    bool has_next()
    {
        return !m_stack.empty();
    }

    TreeValue next()
    {
        TreeValue rv(m_stack.size() - 1, m_stack.top().node);
        fetch_next();
        return rv;
    }

private:
    using ChildIterator = decltype(std::declval<T>().begin());

    struct State {
        State(const T& node)
            : node(node)
            , child_iter(node.begin())
        {}
        const T& node;
        ChildIterator child_iter;
    };

    void fetch_next()
    {
        pop_finished_nodes();
        if (!m_stack.empty()) {
            auto& parent_state = m_stack.top();
            State child_state(*parent_state.child_iter);
            ++parent_state.child_iter;
            m_stack.emplace(child_state);
        }
    }

    void pop_finished_nodes()
    {
        while (!m_stack.empty() && m_stack.top().child_iter == m_stack.top().node.end()) {
            m_stack.pop();
        }
    }

private:
    std::stack<State> m_stack;
};

int main()
{
    // 1
    // |- 11
    // |- 12
    //     |-121
    //     |-122
    // |- 13
    TreeNode tree{1};
    tree.children.emplace_back(11);
    tree.children.emplace_back(12);
    tree.children.emplace_back(13);
    tree.children[1].children.emplace_back(121);
    tree.children[1].children.emplace_back(122);

    // print recursively
    tree.walk_tree([](const TreeNode& node, int level){
        LOG_TRACE(std::string(level*2, ' ') << node.value);
    });

    // print sequentially via iterator that flattens the tree using a stack
    for (auto it = StackTreeIterator<TreeNode>(tree); it.has_next(); ) {
        auto next = it.next();
        LOG_TRACE(std::string(next.level*2, ' ') << next.node.value);
    }

    return 0;
}
26 окт 19, 15:17    [22003203]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные итераторы (тяпничное)  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Явный стек не надо. Мы не будем разваливать рекурсию в конечный автомат со стеком.

Попробуем возможности языка.
26 окт 19, 15:27    [22003204]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные итераторы (тяпничное)  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Рекурсивный итератор по такой вот кривой.

Картинка с другого сайта.

Спасибо fixxer. Я хотел избавиться от переменных класса glx, gly но не мог придумать как это сделать красиво.
Просто копипащу.

GilbertLazyStream.scala
+
case class Point(x: Int, y: Int)

case class Delta(dx: Int, dy: Int) {
  def applyTo(point: Point): Point = Point(point.x + dx, point.y + dy)
}

class GilbertLazyStream {

  val u = 1

  private def a(i: Int): Stream[Delta] = {
    if (i > 0) {
      d(i - 1) #::: Delta(u, 0) #:: a(i - 1) #::: Delta(0, u) #:: a(i - 1) #::: Delta(-u, 0) #:: c(i - 1)
    } else {
      Stream.empty
    }
  }

  private def b(i: Int): Stream[Delta] = {
    if (i > 0) {
      c(i - 1) #::: Delta(-u, 0) #:: b(i - 1) #::: Delta(0, -u) #:: b(i - 1) #::: Delta(u, 0) #:: d(i - 1)
    } else {
      Stream.empty
    }
  }

  private def c(i: Int): Stream[Delta] = {
    if (i > 0) {
      b(i - 1) #::: Delta(0, -u) #:: c(i - 1) #::: Delta(-u, 0) #:: c(i - 1) #::: Delta(0, u) #:: a(i - 1)
    } else {
      Stream.empty
    }
  }

  private def d(i: Int): Stream[Delta] = {
    if (i > 0) {
      a(i - 1) #::: Delta(0, u) #:: d(i - 1) #::: Delta(u, 0) #:: d(i - 1) #::: Delta(0, -u) #:: b(i - 1)
    } else {
      Stream.empty
    }
  }

  def nlz(xArg: Int): Int = {
    var x = xArg
    var n = 0
    if (x == 0) return 32
    n = 1
    if ((x >>> 16) == 0) {
      n += 16
      x <<= 16
    }
    if ((x >>> 24) == 0) {
      n += 8
      x <<= 8
    }
    if ((x >>> 28) == 0) {
      n += 4
      x <<= 4
    }
    if ((x >>> 30) == 0) {
      n += 2
      x <<= 2
    }
    n = n - (x >>> 31)
    n
  }

  def log2up(x: Int): Int = {
    if (x < 1) return 0
    32 - nlz(x - 1)
  }

  def gilbertPoinsStream(size : Int) : Stream[Point] = {
    val level = log2up(size)
    a(level).scanLeft(Point(0, 0))((point, delta) => delta.applyTo(point))
  }

}
26 окт 19, 17:00    [22003245]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные итераторы (тяпничное)  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Поскольку в java нет уступчивого yield return, я написал этот-же итератор на двух потоках.

Это некрасивое решение но другого у меня нет. Можно сделать без блокирующейся очереди но
решение будет медленно работать из за постоянной синхронизации потока потребителя.

+
public class GilbertPixelIterator implements IPixIterator {

    static Logger logger =  LoggerFactory.getLogger(GilbertPixelIterator.class);

    private BlockingQueue<Point> blockingQueue = new ArrayBlockingQueue<>(256, true); // TODO: Refactor with 'disruptor' queue

    private Thread worker;

    private int u = 1;

    private Point poisonedPill = new Point(Integer.MIN_VALUE, Integer.MIN_VALUE);

    private int glx;
    private int gly;

    private Point current = null;

    private boolean finished = false;

    private void a(int i) {
        if (i > 0) {
            d(i - 1);
            linerel(+u, 0);
            a(i - 1);
            linerel(0, u);
            a(i - 1);
            linerel(-u, 0);
            c(i - 1);
        }
    }

    private void b(int i) {
        if (i > 0) {
            c(i - 1);
            linerel(-u, 0);
            b(i - 1);
            linerel(0, -u);
            b(i - 1);
            linerel(u, 0);
            d(i - 1);
        }
    }

    private void c(int i) {
        if (i > 0) {
            b(i - 1);
            linerel(0, -u);
            c(i - 1);
            linerel(-u, 0);
            c(i - 1);
            linerel(0, u);
            a(i - 1);
        }
    }

    private void d(int i) {
        if (i > 0) {
            a(i - 1);
            linerel(0, u);
            d(i - 1);
            linerel(u, 0);
            d(i - 1);
            linerel(0, -u);
            b(i - 1);
        }
    }

    private void safePut(Point point) {
        try {
            blockingQueue.put(point); // TODO: Refactor with 'disruptor' queue
        } catch (InterruptedException ex) {
            Thread.currentThread().interrupt();
            logger.warn("Thread interrupted during put!");
        }
    }

    private void linerel(int x, int y) {
        glx += x;
        gly += y;
        safePut(new Point(glx, gly));
    }

    private void moveto(int x, int y) {
        glx = x;
        gly = y;
        safePut(new Point(glx, gly));
    }

    public GilbertPixelIterator(int size) {
        checkArgument(size >= 4 , "Impossible to create gilbert gurve less than 4x4 plane!");
        int level = Utils.log2up(size);
        logger.trace(":: level = {}", level);
        worker = new Thread(() -> {
            moveto(0, 0);
            a(level);
            safePut(poisonedPill);
        });
        worker.start();
    }


    @Override
    public int getX() {
        if (finished) throw new IllegalStateException("Iterator is finished!");
        return current.x;
    }

    @Override
    public int getY() {
        if (finished) throw new IllegalStateException("Iterator is finished!");
        return current.y;
    }

    @Override
    public boolean next() {
        if (finished) {
            return false;
        } else {
            try {
                current = blockingQueue.take(); // TODO: Refactor with 'disruptor' queue
                finished = (current == poisonedPill);
            } catch (InterruptedException ex) {
                Thread.currentThread().interrupt();
                logger.warn("Thread interrupted during take!");
                finished = true;
            }
            return !finished;
        }
    }

    @Override
    public void reset() {
        throw new RuntimeException("Not implemented for mt-iterator");
    }
}


Зато yield есть в Котлине. Можно попробовать потом.
26 окт 19, 17:05    [22003246]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные итераторы (тяпничное)  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3539
это кривая Гильберта, обычная L система, примеров 100500, можно даже без рекурсии
26 окт 19, 18:55    [22003298]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные итераторы (тяпничное)  [new]
Barlone
Member

Откуда:
Сообщений: 1347
Так в С++ в stl есть итератор по map. Я правда сам в исходники не заглядывал, но говорят внутри map дерево...
26 окт 19, 18:57    [22003299]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные итераторы (тяпничное)  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Roman Mejtes
это кривая Гильберта, обычная L система, примеров 100500, можно даже без рекурсии

Давайте ваш пример. Дерево. Граф.
26 окт 19, 19:59    [22003311]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные итераторы (тяпничное)  [new]
exp98
Member

Откуда:
Сообщений: 1843
Рискую быть посланным лесом, но спрошу.
Всё же, чем вызвано требование именно рекурсивной реализации?
И почему упор именно на структуры данных, почему, скажем не перестановки ...
Хочется увидеть некую "Проблемную записку", условия применимости ... Иначе выглядит как надуманная хотелка, в лучшем случае в надежде найти жемчужное зерно в кодовом навозе.
27 окт 19, 15:21    [22003653]     Ответить | Цитировать Сообщить модератору
Все форумы / Программирование Ответить