post-order traversing on mid-sized graphs

TraverseContextBuilderTest.java

package com.intuit.commons.traverser;

import org.junit.Test;

import java.util.Map;
import java.util.Optional;
import java.util.function.Function;

public class TraverseContextBuilderTest {

    @Test
    public void testNormalStrategy() {
        TestContextBuilder builder = new TestContextBuilder() ;
        builder.build(); // initialize root context strategy
        for(int i=0; i < 1_000_000; i++) {
            TestContextBuilder tmp = builder;
            builder = new TestContextBuilder().parentContext(tmp);
            builder.build(); // initialize normal context strategy
        }

        builder.getResult(); // StackOverflowError if linked list is > 15K on a standard JVM
    }


    @Test
    public void testCustomNormalStrategy() {
        TestAnotherContextBuilder builder = new TestAnotherContextBuilder() ;
        builder.build(); // initialize root context strategy
        for(int i=0; i < 1_000_000; i++) {
            TestAnotherContextBuilder tmp = builder;
            builder = new TestAnotherContextBuilder().parentContext(tmp);
            builder.build();
        }

        builder.getResult();
    }




    static class TestContextBuilder extends TraverseContextBuilder<Void,VoidContext,TestContextBuilder> {
        protected TestContextBuilder() {
            super(Traverser.ContextType.POST_ORDER);
        }

        @Override
        public VoidContext build() {
            return build((x) -> new VoidContext());
        }


    }



    static class TestAnotherContextBuilder extends TraverseContextBuilder<Void,VoidContext,TestAnotherContextBuilder> {
        protected TestAnotherContextBuilder() {
            super(Traverser.ContextType.POST_ORDER);
        }

        @Override
        public VoidContext build() {
            return build((x) -> new VoidContext());
        }

        @Override
        protected TestAnotherContextBuilder preConstruct() {
            // use custom context strategy only for child context
            return Optional
                    .ofNullable(parentContext)
                    .map(o -> this.contextStrategy(CUSTOM_NORMAL_STRATEGY).vars(initVars(vars)))
                    .orElseGet(super::preConstruct);

        }

        private static final ContextStrategy CUSTOM_NORMAL_STRATEGY = new ContextStrategy() {
            @Override
            public <U> void setResult(TraverseContextBuilder<?, ?, ?> outer, U result) {
                outer.result = result;
                rootContext(outer).setResult(result);
            }

            @Override
            public <U> U getResult(TraverseContextBuilder<?, ?, ?> outer) {
                return rootContext(outer).getResult();
            }

            private TraverseContextBuilder<?, ?, ?> rootContext(TraverseContextBuilder<?, ?, ?> outer) {
                TraverseContextBuilder<?, ?, ?> parent = outer.parentContext;
                while(parent.contextStrategy == CUSTOM_NORMAL_STRATEGY) {
                    parent = parent.parentContext;
                }
                return parent;
            }

            @Override
            public <U> U getVar(TraverseContextBuilder<?, ?, ?> outer, Class<? super U> key) {
                U value;
                return ((value = (U)outer.vars.get(key)) != null || outer.vars.containsKey(key))
                        ? value
                        : outer.parentContext.getVar(key);
            }

            @Override
            public <U> U setVar(TraverseContextBuilder<?, ?, ?> outer, Class<? super U> key, U newValue) {
                return outer.vars.containsKey(key)
                        ? (U)outer.vars.put(key, newValue)
                        : outer.parentContext.setVar(key, newValue);
            }

            @Override
            public String toString() {
                return "CUSTOM_NORMAL_STRATEGY";
            }
        };
    }




    static class VoidContext implements TraverseContext<Void> {
        @Override
        public Void thisNode() {
            return null;
        }

        @Override
        public TraverseContext<Void> parentContext() {
            return null;
        }

        @Override
        public <U> void setResult(U o) {

        }

        @Override
        public <U> U getResult() {
            return null;
        }

        @Override
        public <U> U getContextResult() {
            return null;
        }

        @Override
        public Object initialData() {
            return null;
        }

        @Override
        public Map<Class<?>, Object> getContextVars() {
            return null;
        }

        @Override
        public boolean isPostOrder() {
            return false;
        }

        @Override
        public boolean isBackRef(Function<? super TraverseContext<Void>, ? extends Optional<Object>> visitedTracker) {
            return false;
        }

        @Override
        public <U> U getBackRefResult() {
            return null;
        }
    }
}