Еще одна статья про реактивное программирование. И только не надо на этой строчке закатывать глаза и томным голосом говорить вслух — "Ну что еще ты можешь мне рассказать про реактивное программирование… а?". Она немного отличается от кучи других, написаных словно под копирку, поэтому некоторые вещи в ней могут показаться… странными или даже совершенно неуместными, как сортирный юмор.

Совершенно не важно, знаешь ли ты наизусть reactive manifesto, присутствует ли в твоем утреннем кофе бекпрешур, трогаешь ли ты вот этими вот своими ручками всякие паблишеры и сабскрайберы или пишешь старый добрый синхронный, блокирующийся код. А может быть только недавно, кто-то своим откровенно рекламным докладом про светлое будущее и потоковый оргазм (ну или струйный, тут тонкости перевода решают все), от использования одной из реактивных библиотек конечно-же, зажег в твоих глазах интерес к новой технологии.

Будет интересно.

Возведение в абсолют

И так, представим, что мы совсем сошли с ума… Хотя слово представим здесь больше для политкорректности, потому что все, кто знает автора, в курсе того, что он сидит целыми днями в запертой квартире. Работает по ночам, выкуривает по три кальяна в день, и пару раз в неделю выходит на улицу. Обычно это происходит ради встречи со своим психотерапевтом, но иногда причина совсем другая — IKEA.

И так, мы берем старый синхронный, но работающий код:

int result = 1 + 2 * 4;

И пытаемся его отрефакторить, потому что нам кажется… Хотя нет, это слишком, никто же не будет так делать в здравом уме. Никто. В здравом уме.

Mono<Integer> result = Flux.concat(
    Mono.just(1), 
    Flux.concat(Mono.just(2), Mono.just(4))
        .reduce((a, b) -> a * b))
    .reduce((a, b) -> a + b);

StepVerifier.create(result)
    .expectNext(9)
    .expectComplete()
    .verify();

Но как вы уже могли заметить, я это сделяль. И прошу заметить! Я сдержал себя от того, чтобы использовать в этом примере пару микросервисов, один для сложения, а другой для умножения, с которыми пришлось бы общаться через rSocket и kafka.

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

Совет второй. Его я решил оставить в конце статьи. Но если после всего увиденного ты решишь, что тебе стоит держаться подальше от этого д%&@а, то ты знаешь где его искать.

Более реальный пример

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

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

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

У нас есть дерево, обычное, ничем не примечательное дерево, которое росло на лужайке нашего кода и мечтало когда-нибудь, когда оно вырастет, превратиться в BST:

public class TreeNode {
    public int val;
    public TreeNode left, right;

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public TreeNode(int val) {
        this(val, null, null);
    }

    // листинг этих методов будет приведен ниже
    TreeNode invert() {
        // ...
    }

    int sumOfLeftLeaves() {
        // ...
    } 

    TreeNode searchBST(int val) {
        // ..
    }

    public List<Integer> toList() {
        List<Integer> list = new ArrayList<>();

        if (left != null) list.addAll(left.toList());
        list.add(val);
        if (right != null) list.addAll(right.toList());

        return list;
    }    

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        TreeNode treeNode = (TreeNode) o;
        return val == treeNode.val;
    }

    @Override
    public int hashCode() {
        return val;
    }    

    @Override
    public String toString() {
        return toList().toString();
    }    
}

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

public class TreeNode {
    public final Mono<Integer> value;
    public final Mono<TreeNode> left;
    public final Mono<TreeNode> right;

    public TreeNode(Mono<Integer> value, Mono<TreeNode> left, Mono<TreeNode> right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public TreeNode(int value, TreeNode left, TreeNode right) {
        this(Mono.just(value), Mono.justOrEmpty(left), Mono.justOrEmpty(right));
    }

    public TreeNode(int value) {
        this(Mono.just(value), Mono.empty(), Mono.empty());
    }

    public Flux<TreeNode> flux() {
        return Flux.concat(
                left.flatMapMany(TreeNode::flux),
                Mono.just(this),
                right.flatMapMany(TreeNode::flux)
        );
    }

    @Override
    public String toString() {
        return flux()
                .flatMap(n -> n.value)
                .collectList()
                .map(Object::toString)
                .block();
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        TreeNode treeNode = (TreeNode) o;
        return Objects.equals(value.block(), treeNode.value.block());
    }

    @Override
    public int hashCode() {
        return value.block();
    }    

Чувствуете, как в воздухе повис вопрос — “Зачем?!”. Во-первых это красиво, а во-вторых очень скейлбл, так как асинхронно, также это безопасно для окружающей среды и Грета Тунберг не приедет к нам однажды на поезде с огромным страпоном… вы понимаете о чем я. И не стоит забывать о том, что теперь у нас появился бекпрешур. И кстати, напоминаю, что ни один рефакторинг нельзя проводить без тестового покрытия.

public class TreeNodeTest {

    @Test
    public void testFlux() {
        TreeNode tree = new TreeNode(4,
                new TreeNode(2,
                        new TreeNode(1),
                        new TreeNode(3)),

                new TreeNode(7,
                        new TreeNode(6),
                        new TreeNode(9)));

        StepVerifier.create(tree.flux().flatMap(n -> n.value))
                .expectNext(1, 2, 3, 4, 6, 7, 9)
                .expectComplete()
                .verify();
    }
}

Отлично. Начало положено, теперь нам осталось отрефакторить три простых метода invert, sumOfLeftLeaves и searchBST в старом, скучном, синхронном дереве и добавить немного тестов.

Invert

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

    public TreeNode invert() {
        return invert(this);
    }

    private TreeNode invert(TreeNode root) {
        if (root == null)
            return null;

        TreeNode swap = new TreeNode(root.val);

        swap.right = invert(root.left);
        swap.left = invert(root.right);

        return swap;
    }

Посмотрите что произошло, когда мы переписали его, он заиграл новыми красками, и как бонус, мы бесплатно добились null safety.

    public Mono<TreeNode> invert() {
        return Mono.just(this)
                .map(n -> new TreeNode(n.value,
                        n.right.flatMap(TreeNode::invert),
                        n.left.flatMap(TreeNode::invert)
                ));
    }

    @Test
    public void testInvert() {
        TreeNode tree = new TreeNode(4,
                new TreeNode(2,
                        new TreeNode(1),
                        new TreeNode(3)),

                new TreeNode(7,
                        new TreeNode(6),
                        new TreeNode(9)));

        Flux<Integer> inverted = tree.invert()
                .flatMapMany(TreeNode::flux)
                .flatMap(n -> n.value);

        StepVerifier.create(inverted)
                .expectNext(9, 7, 6, 4, 3, 2, 1)
                .expectComplete()
                .verify();
    }

sumOfLeftLeaves

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

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

Но к чему слова, давайте к делу, посмотри как было...

    public int sumOfLeftLeaves() {
        return sumOfLeftLeaves(false, this);
    }

    public int sumOfLeftLeaves(boolean left, TreeNode root) {
        if (root == null)
            return 0;

        if (root.left == null && root.right == null && left)
            return root.val;

        return sumOfLeftLeaves(true, root.left) + sumOfLeftLeaves(false, root.right);
    }   

… и как стало

    public Mono<Integer> sumOfLeftLeaves() {
        return sumOfLeftLeaves(Mono.just(this), false)
                .flatMap(n -> n.value)
                .reduce(Integer::sum);

    }

    private Flux<TreeNode> sumOfLeftLeaves(Mono<TreeNode> node, boolean left) {
        return node
                .flux()
                .concatMap(n -> Flux.concat(
                        sumOfLeftLeaves(n.left, true),

                        Flux.first(n.left, n.right)
                            .map(x -> new TreeNode(0))
                            .switchIfEmpty( Mono.just(n) )
                            .filter(x -> left),

                        sumOfLeftLeaves(n.right, false)
                ));
    }

    @Test
    public void testSumOfLeftLeaves() {
        TreeNode tree = new TreeNode(3,
                new TreeNode(9,
                        new TreeNode(11),
                        null),
                new TreeNode(20,
                        new TreeNode(15),
                        new TreeNode(7))
                );

        StepVerifier.create(tree.sumOfLeftLeaves())
                .expectNext(26)
                .expectComplete()
                .verify();
    }    

Wow! So reactive. Much async. Too awesome. So null safety. Much backpressure. So scalable...

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

searchBST

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

    public TreeNode searchBST(int val) {
        return searchBST(this, val);
    }

    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null)
            return null;
        if (val < root.val)
            return searchBST(root.left, val);
        else if (val > root.val)
            return searchBST(root.right, val);
        else return root;
    }

Просто прочувствуйте это:

    public Mono<TreeNode> testSearchBST(int val) {
        return searchBST(Mono.just(this), val);
    }

    private Mono<TreeNode> searchBST(Mono<TreeNode> root, int val) {
        return root.flatMap(node -> node.value
                .filter(v -> v > val)
                .flatMap(v -> searchBST(node.left, val))
                .switchIfEmpty(node.value
                        .filter(v -> v < val)
                        .flatMap(v -> searchBST(node.right, val))
                        .switchIfEmpty(node.value
                                        .filter(v -> v == val)
                                        .flatMap(v -> root)
                        )
                ));
    }

    @Test
    public void searchBST() {
        TreeNode tree = new TreeNode(4,
                new TreeNode(2,
                        new TreeNode(1),
                        new TreeNode(3)),
                new TreeNode(7));

        StepVerifier.create(tree.searchBST(3).flatMap(n -> n.value))
                .expectNext(3)
                .expectComplete()
                .verify();
    }    

Больше нечего добавить. Вот это и есть реактивное программирование, оно самое.

Еще не конец

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

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

public class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    public static ListNode of(int... array) {
        if (array.length < 1)
            return null;

        ListNode head = new ListNode(array[0]);
        ListNode tail = head;
        for (int i = 1; i < array.length; i++) {
            ListNode next = new ListNode(array[i]);
            tail.next = next;
            tail = next;
        }

        return head;
    }

    public ListNode last() {
        if (next != null)
            return next.last();

        return this;
    }
}

public class ListTestNode {
    public Mono<Boolean> hasCycle(ListNode head) {
        return Mono.justOrEmpty(head)
                .flatMapMany(node -> {
                    Flux<ListNode> flux = Flux.generate(() -> head, (n, sink) -> {
                        if (n == null) {
                            sink.complete();
                            return null;
                        }

                        sink.next(n);
                        return n.next;
                    });

                    Flux<ListNode> fast = flux.skip(1);
                    Flux<ListNode> slow = flux.flatMap(n -> Flux.just(n, n));
                    return fast.zipWith(slow);
                })
                .any(objects -> objects.getT1() == objects.getT2())
                .defaultIfEmpty(false);
    }

    @Test
    public void hasCycle() {
        StepVerifier.create(hasCycle(null))
                .expectNext(false)
                .expectComplete()
                .verify();

        ListNode withoutCycle = ListNode.of(1, 2, 3, 4, 5, 6);
        StepVerifier.create(hasCycle(withoutCycle))
                .expectNext(false)
                .expectComplete()
                .verify();

        ListNode withCycle = ListNode.of(1, 2, 3, 4, 5, 6);
        withCycle.last().next = withCycle.next.next;

        StepVerifier.create(hasCycle(withCycle))
                .expectNext(true)
                .expectComplete()
                .verify();
    }

Раз уж мы затронули тему технических собеседований, то не стоит и забывать про любимую всеми задачу на проверку вложенности скобок. Show must go on!

    public Mono<Boolean> isValidParentheses(String s) {
        return Flux.range(0, s.length())
                .map(s::charAt)
                .reduceWith(() -> "", (str, c) -> {
                    if (c == '{' || c == '[' || c == '(')
                        return str + c;

                    char last = str.charAt(str.length() - 1);
                    if (c == '}' && last != '{')
                        return str;

                    if (c == ']' && last != '[')
                        return str;

                    if (c == ')' && last != '(')
                        return str;

                    return str.substring(0, str.length() - 1);
                })
                .map(String::isEmpty);
    }

    @Test
    public void testIsValidParentheses() {
        StepVerifier.create(isValidParentheses("()"))
                .expectNext(true)
                .expectComplete()
                .verify();

        StepVerifier.create(isValidParentheses("()[]{}"))
                .expectNext(true)
                .expectComplete()
                .verify();

        StepVerifier.create(isValidParentheses("{()[]()}"))
                .expectNext(true)
                .expectComplete()
                .verify();

        StepVerifier.create(isValidParentheses("()"))
                .expectNext(true)
                .expectComplete()
                .verify();

        StepVerifier.create(isValidParentheses("(]"))
                .expectNext(false)
                .expectComplete()
                .verify();

        StepVerifier.create(isValidParentheses("([)]"))
                .expectNext(false)
                .expectComplete()
                .verify();
    }

Wow. So immutable… Much reactive.

Совет номер два

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