DefaultTreeNodeTest.java

/*
 * Copyright 2021 Red Hat, Inc. and/or its affiliates
 * and other contributors as indicated by the @author tags.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.keycloak.models.map.storage.tree;

import org.keycloak.models.map.storage.tree.TreeNode.PathOrientation;
import java.util.Date;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import org.junit.Test;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.contains;
import static org.hamcrest.Matchers.containsInAnyOrder;
import static org.hamcrest.Matchers.empty;
import static org.hamcrest.Matchers.hasKey;
import static org.hamcrest.Matchers.hasSize;
import static org.hamcrest.Matchers.is;
import static org.hamcrest.Matchers.lessThan;
import static org.hamcrest.Matchers.not;
import static org.hamcrest.Matchers.notNullValue;

/**
 *
 * @author hmlnarik
 */
public class DefaultTreeNodeTest {

    private class Node extends DefaultTreeNode<Node> {

        public Node() {
            super(DefaultTreeNodeTest.this.treeProperties);
        }

        public Node(String id) {
            super(DefaultTreeNodeTest.this.treeProperties);
            setId(id);
        }

        public Node(Node parent, String id) {
            super(DefaultTreeNodeTest.this.treeProperties);
            setId(id);
            setParent(parent);
        }

        @Override
        public String getLabel() {
            return this.getId() == null ? "Node:" + System.identityHashCode(this) : this.getId();
        }
    }

    private static final String KEY_1 = "key1";
    private static final String VALUE_1 = "value";
    private static final String KEY_2 = "key2";
    private static final Date VALUE_2 = new Date();
    private static final String KEY_3 = "key3";
    private static final Integer VALUE_3 = 12345;

    public Map<String, Object> treeProperties = new HashMap<>();

    {
        treeProperties.put(KEY_1, VALUE_1);
        treeProperties.put(KEY_2, VALUE_2);
    }

    @Test
    public void testSingleNodeTree() {
        Node root = new Node();
        root.setNodeProperty(KEY_1, VALUE_1);
        root.setEdgeProperty(KEY_2, VALUE_2);

        assertThat(root.getParent(), is(Optional.empty()));
        assertThat(root.getChildren(), empty());

        assertNodeProperty(root, KEY_1, VALUE_1);
        assertNodeProperty(root, KEY_2, null);
        assertEdgeProperty(root, KEY_1, null);
        assertEdgeProperty(root, KEY_2, VALUE_2);

        assertTreeProperties(root);
    }

    @Test
    public void testSimpleTwoNodeTree() {
        Node root = new Node();
        Node child = new Node();
        root.setNodeProperty(KEY_1, VALUE_1);

        child.setParent(root);
        child.setId("my-id");
        child.setEdgeProperty(KEY_2, VALUE_2);

        // check parent-child relationships
        assertThat(root.getParent(), is(Optional.empty()));
        assertThat(root.getChildren(), hasSize(1));

        assertThat(child.getParent(), is(Optional.of(root)));
        assertThat(child.getChildren(), empty());

        // check properties
        assertThat(root.getNodeProperties().keySet(), hasSize(1));
        assertThat(root.getEdgeProperties().keySet(), empty());
        assertThat(child.getNodeProperties().keySet(), empty());
        assertThat(child.getEdgeProperties().keySet(), hasSize(1));
        assertTreeProperties(root);
        assertTreeProperties(child);
    }

    @Test
    public void testSimpleTwoNodeTreeSwapped() {
        Node root = new Node();
        Node child = new Node();
        child.setParent(root);
        child.setId("my-id");

        // Now swap the roles
        root.setParent(child);

        // check parent-child relationships
        assertThat(child.getParent(), is(Optional.empty()));
        assertThat(child.getChildren(), hasSize(1));

        assertThat(root.getParent(), is(Optional.of(child)));
        assertThat(root.getChildren(), empty());

        // check properties have not changed
        root.setNodeProperty(KEY_1, VALUE_1);
        child.setEdgeProperty(KEY_2, VALUE_2);
        assertThat(root.getNodeProperties().keySet(), hasSize(1));
        assertThat(root.getEdgeProperties().keySet(), empty());
        assertThat(child.getNodeProperties().keySet(), empty());
        assertThat(child.getEdgeProperties().keySet(), hasSize(1));
        assertTreeProperties(root);
        assertTreeProperties(child);
    }

    @Test
    public void testStructureLinearThreeNodeSwapped() {
        Node level1 = new Node();
        Node level2 = new Node();
        Node level3 = new Node();

        level2.setParent(level1);
        level3.setParent(level2);

        // check parent-child relationships
        assertThat(level1.getParent(), is(Optional.empty()));
        assertThat(level1.getChildren(), containsInAnyOrder(level2));
        assertThat(level2.getParent(), is(Optional.of(level1)));
        assertThat(level2.getChildren(), containsInAnyOrder(level3));
        assertThat(level3.getParent(), is(Optional.of(level2)));
        assertThat(level3.getChildren(), empty());

        // Swap nodes
        level1.setParent(level3);

        // check parent-child relationships
        assertThat(level3.getParent(), is(Optional.empty()));
        assertThat(level3.getChildren(), containsInAnyOrder(level1));
        assertThat(level1.getParent(), is(Optional.of(level3)));
        assertThat(level1.getChildren(), containsInAnyOrder(level2));
        assertThat(level2.getParent(), is(Optional.of(level1)));
        assertThat(level2.getChildren(), empty());
    }

    @Test
    public void testStructureAThreeNodeSwapped() {
        Node level1 = new Node();
        Node level21 = new Node();
        Node level22 = new Node();
        Node level23 = new Node();

        level21.setParent(level1);
        level22.setParent(level1);
        level23.setParent(level1);

        // check parent-child relationships
        assertThat(level1.getParent(), is(Optional.empty()));
        assertThat(level1.getChildren(), containsInAnyOrder(level21, level22, level23));
        assertThat(level21.getParent(), is(Optional.of(level1)));
        assertThat(level21.getChildren(), empty());
        assertThat(level22.getParent(), is(Optional.of(level1)));
        assertThat(level22.getChildren(), empty());
        assertThat(level23.getParent(), is(Optional.of(level1)));
        assertThat(level23.getChildren(), empty());

        // Change parents
        level1.setParent(level22);

        // check parent-child relationships
        assertThat(level22.getParent(), is(Optional.empty()));
        assertThat(level22.getChildren(), containsInAnyOrder(level1));
        assertThat(level1.getParent(), is(Optional.of(level22)));
        assertThat(level1.getChildren(), containsInAnyOrder(level21, level23));
        assertThat(level21.getParent(), is(Optional.of(level1)));
        assertThat(level21.getChildren(), empty());
        assertThat(level23.getParent(), is(Optional.of(level1)));
        assertThat(level23.getChildren(), empty());

        // Change parents
        level21.setParent(level22);

        // check parent-child relationships
        assertThat(level22.getParent(), is(Optional.empty()));
        assertThat(level22.getChildren(), containsInAnyOrder(level1, level21));
        assertThat(level1.getParent(), is(Optional.of(level22)));
        assertThat(level1.getChildren(), containsInAnyOrder(level23));
        assertThat(level21.getParent(), is(Optional.of(level22)));
        assertThat(level21.getChildren(), empty());
        assertThat(level23.getParent(), is(Optional.of(level1)));
        assertThat(level23.getChildren(), empty());

        // Change parents
        level21.setParent(null);

        // check parent-child relationships
        assertThat(level22.getParent(), is(Optional.empty()));
        assertThat(level22.getChildren(), containsInAnyOrder(level1));
        assertThat(level1.getParent(), is(Optional.of(level22)));
        assertThat(level1.getChildren(), containsInAnyOrder(level23));
        assertThat(level21.getParent(), is(Optional.empty()));
        assertThat(level21.getChildren(), empty());
        assertThat(level23.getParent(), is(Optional.of(level1)));
        assertThat(level23.getChildren(), empty());
    }

    @Test
    public void testChangeId() {
        Node root = new Node();
        Node child1 = new Node();
        child1.setParent(root);
        child1.setId("my-id1");
        Node child2 = new Node();
        child2.setParent(root);
        child2.setId("my-id2");

        // check parent-child relationships
        assertThat(root.getChild("my-id1"), is(Optional.of(child1)));
        assertThat(root.getChild("my-id2"), is(Optional.of(child2)));

        child1.setId("my-id3");
        assertThat(root.getChild("my-id1"), is(Optional.empty()));
        assertThat(root.getChild("my-id3"), is(Optional.of(child1)));
    }

    @Test
    public void testRemoveChildDirectly() {
        Node root = new Node();
        Node child1 = new Node();
        child1.setParent(root);
        child1.setId("my-id1");
        Node child2 = new Node();
        child2.setParent(root);
        child2.setId("my-id2");

        // check parent-child relationships
        assertThat(root.getChild("my-id1"), is(Optional.of(child1)));
        assertThat(root.getChild("my-id2"), is(Optional.of(child2)));

        assertThat(root.removeChild(child1), is(Optional.of(child1)));

        assertThat(root.getChildren(), containsInAnyOrder(child2));
        assertThat(child1.getParent(), is(Optional.empty()));

        assertThat(root.removeChild(child1), is(Optional.empty()));

        // try to remove it once again
        assertThat(root.getChildren(), containsInAnyOrder(child2));
        assertThat(child1.getParent(), is(Optional.empty()));
    }

    @Test
    public void testRemoveChildViaPredicate() {
        Node root = new Node();
        Node child1 = new Node();
        child1.setParent(root);
        child1.setId("my-id1");
        Node child2 = new Node();
        child2.setParent(root);
        child2.setId("my-id2");
        Node child3 = new Node();
        child3.setParent(root);
        child3.setId("my-id3");

        // check removals
        assertThat(root.removeChild(node -> "my-id1".equals(node.getId())), is(1));

        assertThat(root.getChildren(), containsInAnyOrder(child2, child3));
        assertThat(child1.getParent(), is(Optional.empty()));
        assertThat(child2.getParent(), is(Optional.of(root)));
        assertThat(child3.getParent(), is(Optional.of(root)));

        assertThat(root.removeChild(node -> true), is(2));

        assertThat(root.getChildren(), empty());
        assertThat(child1.getParent(), is(Optional.empty()));
        assertThat(child2.getParent(), is(Optional.empty()));
        assertThat(child3.getParent(), is(Optional.empty()));
    }

    @Test
    public void testRemoveChild() {
        Node root = new Node();
        Node child1 = new Node();
        child1.setParent(root);
        child1.setId("my-id1");
        Node child2 = new Node();
        child2.setParent(root);
        child2.setId("my-id2");

        // check parent-child relationships
        assertThat(root.getChild("my-id1"), is(Optional.of(child1)));
        assertThat(root.getChild("my-id2"), is(Optional.of(child2)));

        root.removeChild(child1);

        assertThat(root.getChildren(), containsInAnyOrder(child2));
        assertThat(child1.getParent(), is(Optional.empty()));
    }

    @Test
    public void testDfs() {
        Node root = new Node("1");
        Node child11 = new Node(root, "1.1");
        Node child12 = new Node(root, "1.2");
        Node child111 = new Node(child11, "1.1.1");
        Node child112 = new Node(child11, "1.1.2");
        Node child121 = new Node(child12, "1.2.1");
        Node child122 = new Node(child12, "1.2.2");
        Node child123 = new Node(child12, "1.2.3");
        Node child1121 = new Node(child112, "1.1.2.1");

        List<Node> res = new LinkedList<>();
        assertThat(root.findFirstDfs(n -> {
            res.add(n);
            return false;
        }), is(Optional.empty()));
        assertThat(res, contains(root, child11, child111, child112, child1121, child12, child121, child122, child123));

        res.clear();
        assertThat(root.findFirstDfs(n -> {
            res.add(n);
            return n == child12;
        }), is(Optional.of(child12)));
        assertThat(res, contains(root, child11, child111, child112, child1121, child12));
    }

    @Test
    public void testDfsBottommost() {
        Node root = new Node("1");
        Node child11 = new Node(root, "1.1");
        Node child12 = new Node(root, "1.2");
        Node child13 = new Node(root, "1.3");
        Node child111 = new Node(child11, "1.1.1");
        Node child112 = new Node(child11, "1.1.2");
        Node child121 = new Node(child12, "1.2.1");
        Node child122 = new Node(child12, "1.2.2");
        Node child123 = new Node(child12, "1.2.3");
        Node child1121 = new Node(child112, "1.1.2.1");
        Node child131 = new Node(child13, "1.3.1");
        Node child132 = new Node(child13, "1.3.2");

        List<Node> res = new LinkedList<>();
        assertThat(root.findFirstBottommostDfs(n -> {
            res.add(n);
            return false;
        }), is(Optional.empty()));
        assertThat(res, contains(root, child11, child111, child112, child1121, child12, child121, child122, child123, child13, child131, child132));

        res.clear();
        assertThat(root.findFirstBottommostDfs(n -> {
            res.add(n);
            return n == child12;
        }), is(Optional.of(child12)));
        assertThat(res, contains(root, child11, child111, child112, child1121, child12, child121, child122, child123));

        res.clear();
        assertThat(root.findFirstBottommostDfs(n -> {
            res.add(n);
            return n.getId().startsWith("1.1.2");
        }), is(Optional.of(child1121)));
        assertThat(res, contains(root, child11, child111, child112, child1121));
    }

    @Test
    public void testBfs() {
        Node root = new Node("1");
        Node child11 = new Node(root, "1.1");
        Node child12 = new Node(root, "1.2");
        Node child111 = new Node(child11, "1.1.1");
        Node child112 = new Node(child11, "1.1.2");
        Node child121 = new Node(child12, "1.2.1");
        Node child122 = new Node(child12, "1.2.2");
        Node child123 = new Node(child12, "1.2.3");
        Node child1121 = new Node(child112, "1.1.2.1");

        List<Node> res = new LinkedList<>();
        assertThat(root.findFirstBfs(n -> {
            res.add(n);
            return false;
        }), is(Optional.empty()));
        assertThat(res, contains(root, child11, child12, child111, child112, child121, child122, child123, child1121));

        res.clear();
        assertThat(root.findFirstBfs(n -> {
            res.add(n);
            return n == child12;
        }), is(Optional.of(child12)));
        assertThat(res, contains(root, child11, child12));
    }

    @Test
    public void testWalkBfs() {
        Node root = new Node("1");
        Node child11 = new Node(root, "1.1");
        Node child12 = new Node(root, "1.2");
        Node child111 = new Node(child11, "1.1.1");
        Node child112 = new Node(child11, "1.1.2");
        Node child121 = new Node(child12, "1.2.1");
        Node child122 = new Node(child12, "1.2.2");
        Node child123 = new Node(child12, "1.2.3");
        Node child1121 = new Node(child112, "1.1.2.1");

        List<Node> res = new LinkedList<>();
        root.walkBfs(res::add);
        assertThat(res, contains(root, child11, child12, child111, child112, child121, child122, child123, child1121));
    }

    @Test
    public void testWalkDfs() {
        Node root = new Node("1");
        Node child11 = new Node(root, "1.1");
        Node child12 = new Node(root, "1.2");
        Node child111 = new Node(child11, "1.1.1");
        Node child112 = new Node(child11, "1.1.2");
        Node child121 = new Node(child12, "1.2.1");
        Node child122 = new Node(child12, "1.2.2");
        Node child123 = new Node(child12, "1.2.3");
        Node child1121 = new Node(child112, "1.1.2.1");

        List<Node> uponEntry = new LinkedList<>();
        List<Node> afterChildren = new LinkedList<>();
        root.walkDfs(uponEntry::add, afterChildren::add);
        assertThat(uponEntry, contains(root, child11, child111, child112, child1121, child12, child121, child122, child123));
        assertThat(afterChildren, contains(child111, child1121, child112, child11, child121, child122, child123, child12, root));
    }

    @Test
    public void testForEachParent() {
        Node root = new Node("1");
        Node child11 = new Node(root, "1.1");
        Node child12 = new Node(root, "1.2");
        Node child111 = new Node(child11, "1.1.1");
        Node child112 = new Node(child11, "1.1.2");
        Node child121 = new Node(child12, "1.2.1");
        Node child122 = new Node(child12, "1.2.2");
        Node child123 = new Node(child12, "1.2.3");
        Node child1121 = new Node(child112, "1.1.2.1");

        List<Node> res = new LinkedList<>();
        res.clear();
        root.forEachParent(res::add);
        assertThat(res, empty());

        res.clear();
        child1121.forEachParent(res::add);
        assertThat(res, contains(child112, child11, root));

        res.clear();
        child123.forEachParent(res::add);
        assertThat(res, contains(child12, root));
    }

    @Test
    public void testPathToRoot() {
        Node root = new Node("1");
        Node child11 = new Node(root, "1.1");
        Node child12 = new Node(root, "1.2");
        Node child111 = new Node(child11, "1.1.1");
        Node child112 = new Node(child11, "1.1.2");
        Node child121 = new Node(child12, "1.2.1");
        Node child122 = new Node(child12, "1.2.2");
        Node child123 = new Node(child12, "1.2.3");
        Node child1121 = new Node(child112, "1.1.2.1");

        assertThat(child1121.getPathToRoot(PathOrientation.TOP_FIRST), contains(root, child11, child112, child1121));
        assertThat(child123.getPathToRoot(PathOrientation.TOP_FIRST), contains(root, child12, child123));
        assertThat(root.getPathToRoot(PathOrientation.TOP_FIRST), contains(root));

        assertThat(child1121.getPathToRoot(PathOrientation.BOTTOM_FIRST), contains(child1121, child112, child11, root));
        assertThat(child123.getPathToRoot(PathOrientation.BOTTOM_FIRST), contains(child123, child12, root));
        assertThat(root.getPathToRoot(PathOrientation.BOTTOM_FIRST), contains(root));
    }

    @Test
    public void testToStringStackOverflow() {
        Node n = new Node("1");
        n.setNodeProperty("prop", n);
        assertThat(n.toString().length(), lessThan(255));
    }

    private void assertTreeProperties(Node node) {
        assertThat(node.getTreeProperty(KEY_1, String.class), notNullValue());
        assertThat(node.getTreeProperty(KEY_1, Date.class), notNullValue());

        assertThat(node.getTreeProperty(KEY_1, String.class), is(Optional.of(VALUE_1)));
        assertThat(node.getTreeProperty(KEY_1, Date.class), is(Optional.empty()));

        assertThat(node.getTreeProperty(KEY_2, String.class), is(Optional.empty()));
        assertThat(node.getTreeProperty(KEY_2, Date.class), is(Optional.of(VALUE_2)));

        assertThat(node.getTreeProperties().size(), is(2));

        treeProperties.put(KEY_3, VALUE_3);
        assertThat(node.getTreeProperties().size(), is(3));
        assertThat(node.getTreeProperty(KEY_3, String.class), is(Optional.empty()));
        assertThat(node.getTreeProperty(KEY_3, Integer.class), is(Optional.of(VALUE_3)));

        treeProperties.remove(KEY_3);
        assertThat(node.getTreeProperties().size(), is(2));
        assertThat(node.getTreeProperties(), not(hasKey(KEY_3)));
    }

    private void assertNodeProperty(Node node, String key, Object value) {
        if (value != null) {
            assertThat(node.getNodeProperty(key, value.getClass()), is(Optional.of(value)));
            assertThat(node.getNodeProperty(key, Object.class), is(Optional.of(value)));
            assertThat(node.getNodeProperty(key, Throwable.class), is(Optional.empty()));
        } else {
            assertThat(node.getNodeProperty(key, Object.class), is(Optional.empty()));
        }
    }

    private void assertEdgeProperty(Node node, String key, Object value) {
        if (value != null) {
            assertThat(node.getEdgeProperty(key, value.getClass()), is(Optional.of(value)));
            assertThat(node.getEdgeProperty(key, Object.class), is(Optional.of(value)));
            assertThat(node.getEdgeProperty(key, Throwable.class), is(Optional.empty()));
        } else {
            assertThat(node.getEdgeProperty(key, Object.class), is(Optional.empty()));
        }
    }
}