Рефакторинг: Замена рекурсии делегированием. Часть 1

Часто сталкиваюсь с проблемой, когда процедурный стиль программирования тянется в OOP код. Вот интерфейс бинарного дерева: добавили ноды, померяли глубину самого глубокого листика, напечатали на экране - все просто.

package com.binarytree;

public interface Node {

    int getMaxLeafDepth();

    void addValue(int value);

    String toString();

}

Вот пример кода класса, в котором используется рекурсия.

package com.binarytree.procedure;

import com.binarytree.Node;

public class ProcedureRecursionTree implements Node {

    private NodeElement root;

    public ProcedureRecursionTree(int rootValue) {
        root = new NodeElement(rootValue);
    }

    @Override
    public void addValue(int newValue) {
        addValue(root, newValue);
    }

    private void addValue(NodeElement node, int newValue) {
        if (newValue < node.value) {
            node.left = addTo(node.left, newValue);
        } else if (node.value < newValue) {
            node.right = addTo(node.right, newValue);
        }
    }

    private NodeElement addTo(NodeElement node, int newValue) {
        if (node != null) {
            addValue(node, newValue);
            return node;
        } else {
            return new NodeElement(newValue);
        }
    }

    @Override
    public int getMaxLeafDepth() {
        return getMaxLeafDepthFrom(0, root);
    }

    private int getMaxLeafDepthFrom(int depth, NodeElement node) {
        if (node == null) {
            return depth;
        }

        return 1 + Math.max(getMaxLeafDepthFrom(depth, node.left), 
                getMaxLeafDepthFrom(depth, node.right));
    }

    @Override
    public String toString() {
        return toString(root);
    }

    private String toStringSubnode(NodeElement node) {
        if (node != null) {
            return toString(node);
        }
        return null;
    }

    private String toString(NodeElement node) {
        return String.format("(%s, %s, %s)", 
            node.value, 
            toStringSubnode(node.left), 
            toStringSubnode(node.right));
    }

}

Это класс, в котором хранятся данные

package com.binarytree.procedure;

public class NodeElement {

    int value;
    int parentNodeValue;
    NodeElement left;
    NodeElement right;

    public NodeElement(int value) {
        this.value = value; 
    }

}

Ну и? Все нормально на первый взгляд. Методы маленькие, дублирования нет, все вполне читабельно. Да, но тут код пахнет другим - класс ProcedureRecursionTree инкапсулируя NodeElement root рекурсивно проходится по всем дочерним узлам/листьям root ноды. Это удобно - все ноды одного типа. Но это не по OOP. Правило простое.

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

Вот этой задачкой я и предлагаю заняться. Рефакторинг, как оказалось недавно, в более широком виде, Фаулеровский и называется "Преобразования процедурного проекта в объекты (Convert Procedural Design to Objects)", я же его раньше называл "замена рекурсии делегированием".

Вывод пока напрашивается громкий - там где OOP там не должно быть рекурсии с передачей данных.

Вот кстати тест:

package com.binarytree;

import static org.junit.Assert.assertEquals;
import org.junit.Test;
import com.binarytree.Node;

public  class TreeTest {
    
    Node createNode(int rootValue) {
        return new ProcedureRecursionTree(rootValue);
 }
    
    @Test
    public void testAddLeftToRoot() {
        Node node = createNode(5);
        node.addValue(4);
        
        assertEquals("(5, (4, null, null), null)", node.toString());
    }
    
    @Test
    public void testAddRightToRoot() {
        Node node = createNode(5);
        node.addValue(6);
        node.addValue(4);
        
        assertEquals("(5, (4, null, null), (6, null, null))", node.toString());
    }
    
    @Test
    public void testStartSecondLevel() {
        Node node = createNode(5);
        node.addValue(6);
        node.addValue(12);
        node.addValue(3);
        
        assertEquals("(5, (3, null, null), " +
                          "(6, null, (12, null, null)))", node.toString());
    }
    
    @Test
    public void testGetDepthFrom3LevelOnlyRightTree() {
        Node node = createNode(5);
        node.addValue(6);
        node.addValue(12);
        
        assertEquals(3, node.getMaxLeafDepth());
        assertEquals("(5, null, (6, null, (12, null, null)))", 
                node.toString());        
    }
    
    @Test
    public void testGetDepthFrom3LevelLeftRightTree() {
        Node node = createNode(5);
        node.addValue(1);
        node.addValue(2);
        
        assertEquals(3, node.getMaxLeafDepth());
        assertEquals("(5, (1, null, (2, null, null)), null)", 
                node.toString());        
    }
    
    @Test
    public void testGetDepthFrom4LevelleftRightTree() {
        Node node = createNode(5);
        node.addValue(6);
        node.addValue(12);
        node.addValue(16);
        node.addValue(3);
        node.addValue(1);
        node.addValue(0);    
        
        assertEquals(4, node.getMaxLeafDepth());
        assertEquals("(5, (3, (1, (0, null, null), null), null), " +
                         "(6, null, (12, null, (16, null, null))))", 
                node.toString());        
    }
    
    @Test
    public void testGetDepthFrom5LevelTree() {
        Node node = createNode(5);
        node.addValue(4);
        node.addValue(6);
        node.addValue(3);
        node.addValue(7);
        node.addValue(2);
        node.addValue(8);
        node.addValue(1);    
        node.addValue(9);
        
        assertEquals(5, node.getMaxLeafDepth());
        assertEquals("(5, (4, (3, (2, (1, null, null), null), null), null), " +
                         "(6, null, (7, null, (8, null, (9, null, null)))))", 
                node.toString());        
    }

}

Приятного аппетита. Продолжение следует.