Venkat's Blog: 2015

Monday, July 13, 2015

A tryst with dozer custom converters

My experiments with dozer

Introduction

The object to object mapping activity happens to constitute a significant part during a front tier services hand-off of a request to the down-stream layers (be it DAO or another service). The major overhaul comes across as a substantial pain of using naive source getters and target setters in building the target objects of interest and confounds the developer and the maintainer alike. The often repeated transformations (during the mapping) such as formatting, composing, splitting, target attribute/field substitution are much left to the user's wisdom to handle in some non-descript isolated pockets of code. An ubiquitous example could be a phone number, or an address where different flavors of structures exist to cater to different locale. For instance in one flavour the road and the block name/numbers are captured in fields called address1 and address2 while an another flavor refers the same as street1/line1 and street2/line2 respectively. Further a state field in the address object can be referred to as province and zip can be substituted for pin.

Intent

The intent of reminiscing on this article and the work underneath it came about when this above stated problem started quickly getting out of hand in a recent situation at work.It was when the number of different objects to be mapped to one or the other type started to exceed beyond handful (say more than 25) where the semantics of the source and target objects remained same however the field names started out to be different(just like address1 and street1). It was an occasion where a classic remote proprietary service needed to pass a request object to a target type with many attributes synonym-ed to a different names.

The first thing that crossed my mind was to keep off from the lazy habit of jumping on the bandwagon of getters and setters(these days usually any half-good POJOs comes at-least with the gets, sets and default no-arg constructors without much effort). Ofcourse I am not whining at all on the POJO principles here; but just felt that life is too short for coding with POJO gets/sets and thus desired to have a bit more atop that can take care of mundane stuff in a declarative fashion than to just code. Infact this is the theme that is closer to my heart in embracing the project lombok annotations.

The real intent / reason on this article is by no means a rant on bean-bean mappers but as is explained further in the use cases section it is more about a few special situations that called in for a slightly general solution to be built forming the crux of this article. Please read further to know more on this.

Why dozer

Thus dawned a bright occasion on a winter morning of November 2014; where we decided to do some soul searching and figure out whats the best tool that is worth its salt for fitting the purpose we had. Tools / libraries such as commons convert from apache commons and spring libraries were looked upon as first choices for those libraries usually form the motherboard of many of the projects that we build. While the main aim of this transformation was about developer simplicity in not having to code and keep it mostly declarative; the approach was not desired to be entirely bereft of the coding.

So while commons / spring approaches needs still a fair amount of hand cranked code for every conversion type; the search continued on beyond the comfort zone of apache commons, spring . The web has many articles of comparison on bean-bean mapping and thus we will not go about comparing one library against another here. However on one such occasion when we chanced upon dozer; it sounded promising with its impressive feature set such as declarative xmlized way of defining the mapping and a great hook for plugging in custom converters that can be sewn together by using spring beans. After a quick check within organization for the yearned buy in; we quickly set out to find out the various bells and whistles it offered.

Use-cases

Most of the mundane mappings are handled by simplistic sensible defaults applied by dozer configurations. For instance the declarative xml pieces for a mapping did'nt needed any explicit mention of fields that are commonly available in source and target classes. Readers are encouraged to refer web articles on dozer to glean information. However, there were some peculiar use-cases that were frequented by us that couldn't be found in either dozer documentation or web and essentially are the reasons for opening this blog post.

These specific use cases were usually related to

1. An immutable/constant object or value to be substituted to a target field

2. In another case ; the target objects had one nagging pattern in that many of the fields such as address, phone were always requiring to be of list type(POJO generators for these third party target objects were designed to emit these fields as list and hence we had no choice). This usually meant such target fields not only had to be mapped but also need to be encapsulated to a list.

These specific use cases that needed building different custom converters purposed for as follows:

1. A field of target class that needs to be substituted by a type specific constant (mostly the primitives and date). Here the particular target field is simply substituted with a constant.

2. A field of target class that needs to be substituted by a pre-defined bean in the spring beans xml. Here the particular target field is a complex custom type which is a bean defined with appropriate values for its attributes.

3. A target field that needs to be populated as java collection type (for now List type is only supported). Here the source bean needs to be converted to a target type and further added as an element into a collection of the target type.

Implementation

A custom converter in dozer provides the following configurable keys (amongst many others) which could be utilized for the purpose at hand.

1. custom-converter-id : This is bean id straight out of a bean definition in the spring based beans.xml that is used in the project.

2. custom-converter-param : This is basically a helpful hint or a string parameter which is set post construction of the converter

A first implementation of the primitive converters, pre-defined bean substitutors and a source to target list mapper can be found in my github repository : dozer-experiments.

The first step in before building up the solution was to firm up the project based on spring and get up quickly with a workable beans.xml for the purpose.

Note:The rationale for adding beans.xml and even dozer bean configuration files to src/test/resources and primarily making test package as the go-to source for understanding is to keep the actual main classes light since the usage and configuration of converters can become very contextual. Basically the beans or dozer files primarily are data driven and are best served with test data in a demo environment rather than making them as part of main jar file. The readers are encouraged to understand README, test package, configuration samples and accordingly make up their configurations.

A note on content of beans.xml

Normally the spring based project i write would usually require some quintessentials listed below.

1. Need my beans xml to be sleak and hence require spring p-namespace and c-namespace.These allow p:<property-name> and c:<attribute-name> in the bean definition as an xml attribute.(half sanity may survive just because of this itself :) - as otherwise beans.xml too busy!).

2. Spring Annotation Processors(@PostConstruct etc) are usually made use of along with a few defalt values used from bean-default.properties so the following snippet.(I dont like repeating package names or base path names which increases the breadth and/or height of xml)

3. Using Slf4j logger (Please refer to logback.xml for log level and formats) and dozer related configurations in the beans.xml as follows.

<bean
	class="org.springframework.context.annotation.CommonAnnotationBeanPostProcessor"
	scope="singleton" />

	<bean
	class="org.springframework.beans.factory.config.PropertyPlaceholderConfigurer"
	scope="singleton">
	<description>This is a common properties file that may declare
	repetatively usable strings, constants and class/package names etc
	</description>
	<property name="location" value="bean-default.properties" />
	</bean> <bean id="system-properties-setup" class="org.springframework.beans.factory.config.MethodInvokingFactoryBean" p:targetObject="#{@systemProperties}" p:targetMethod="putAll"> <property name="arguments"> <util:properties> <!-- <prop key="java.util.logging.SimpleFormatter.format">%1$tF %1$tT [%4$s]: %5$s %n</prop> --> <prop key="dozer.configuration">dozer.properties</prop> <prop key="dozer.debug">false</prop> </util:properties> </property> </bean>

The rest of the beans project / problem specific:

1. Converters of primitive type: These deal with turning a string parsable value to a specific primitive type such as int, long, short etc. It can also support for date today with an assumed simple date format. These as it sounds are going to substitute a value specified in (as part of dozerBeanMapper.xml) the attribute custom-converter-param. The converter itself is as specified in custom-converter-id. Please refer to README for details.

2. Converters to substitute a pre-defined target bean : A fully defined target bean can act as a stand in while mapping some fields.

3. A source to target list converter: It is self explanatory.

4. The dozer mapper definition is completely done in beans xml. so its imperative to use this than create some default way for the mapper.

Most of the bean ids have self explanatory meaning and hence will not be explaining all beans here.

A note on dozerBeanMapping.xml

While there exists a good reference on bean mapping within the dozer user guide; here an attempt is made with a small snippets xml to explain the solution for the use cases addressed. The example objects/classes for conversion are declared in dozer bean mapping file housed in the examples package for demonstration purpose.

For instance ;a quick way to get up with an use of substitution of constant values is as follows; where the custom-converter-param has the actual value to be converted to desired primitive type.

<class-a>com.github.venkateshamurthy.dozer.converters.examples.SourceHolder</class-a>

<class-b>com.github.venkateshamurthy.dozer.converters.examples.TargetHolder</class-b>

<field map-id="source-to-target"><a>source</a>target</field>

<field custom-converter-id="to-double" custom-converter-param="500000.0"><a>salary</a>salary</field>

</mapping>

Where as a pre-defined bean substitution can be had by using the following snippet:

<class-a>com.github.venkateshamurthy.dozer.converters.examples.SourceHolder</class-a>

<class-b>com.github.venkateshamurthy.dozer.converters.examples.TargetHolder</class-b>

<a>source</a> target

</field>

</mapping>

Note: The custom-converter-param has a mandatory prefix bean: and suffixed with an actual bean id from the bean xml representing the pre-defined target bean. This structural constraint of prefix bean: is mandatory and is a personal convention

The other type is about source to target list type and requires a proper mapping to exist between a singular element of source class to target class. The snippet as follows as an example:

<class-a>com.github.venkateshamurthy.dozer.converters.examples.SourceHolder</class-a>

<class-b>com.github.venkateshamurthy.dozer.converters.examples.TargetListHolder</class-b>

<a>source</a> targets

</field>

</mapping>

Note: The custom-converter-param has a prefix map-id: and suffixed with an actual mapping id from the dozerBeanMapping xml (or some included dozer mapping config xml file). This basically makes sure to apply the correct mapping between singular element of source and target class and then subsequently return a list wrapping/including the singular target element. This structural constraint of prefix map-id: is mandatory and is a personal convention.

Usage:

In this section a few test code snippets are mentioned as follows. The reader can take que from this in order to make use of the new converters proposed here.

/** test a predefined target substitution */

@Test

public void testPreDefinedTargetSubstitution() throws NoSuchFieldException,

SecurityException {

SourceHolder sourceHolder = ctx.getBean("source-holder",

SourceHolder.class);

TargetHolder targetHolder = mapper.map(sourceHolder,

TargetHolder.class, "source-to-substitute-target");

Target expectedTarget = ctx.getBean("pre-defined-target", Target.class);

assertEquals(expectedTarget, targetHolder.getTarget());

}

/** test a field (of type date/int/long etc) for a constant substitution */

@Test

public void testTargetWithFewConstants() {

SourceHolder sourceHolder = ctx.getBean("source-holder",

SourceHolder.class);

TargetHolder targetHolder = mapper.map(sourceHolder,

TargetHolder.class, "source-to-target-with-few-constants");

log.info(targetHolder.toString());

}

/** test a singular element to a destination list type */

@Test

public void testTargetList() {

SourceHolder sourceHolder = ctx.getBean("source-holder",

SourceHolder.class);

Source source = sourceHolder.getSource();

TargetListHolder targetHolder = mapper.map(sourceHolder,

TargetListHolder.class, "source-to-target-list");

List<Target> targets = targetHolder.getTargets();

assertFalse(targets.isEmpty());

assertTrue(targets.size() == 1);

Target target = targets.get(0);

assertEquals(source.getAddress1(), target.getStreet1());

assertEquals(source.getAddress2(), target.getStreet2());

assertEquals(source.getPhone(), target.getPhone());

log.info(targetHolder.getTargets().toString());

}

While test code helps in understanding the usage; a good look at the actual converter classes in the main package helps deepen the understanding.

Summary:

In summary, though a set of peculiar use cases of bean to bean mapping are discussed within a context, it is largely felt that the general solution discussed here seems to be useful in a variety of similar situations arising in different contexts. This set of converters are set only to grow with different levels of customizations /enhancements applied to it . Thus I request earnestly all the readers to express their opinion/reviews on this to make this article and code a better experience for the users.

Saturday, February 21, 2015

Builder Pattern - Java

Builder pattern - Java

(Exploring in Java with few open source libraries)

Introduction

A few days back i was presented a situation; at work; related to constructing several POJO objects for some service orchestration. The orchestration of calls required us to build/construct the argument objects(which were POJO) for each call. In this context, neither the objects were simple nor the number of calls were less; meaning; the objects were non-trivial with fairly large set of attributes and such service api calls exceeded beyond ten. Now the interesting part was that these POJO objects were to be consumed from a dependency jar where the POJO objects itself was getting code-generated by some tool (a proprietary code generator tool) which i didn't have a control upon. Well, the utility/tool that generated this code obviously didn't provide any option for creation method support such as factory or builders; which is the subject of the discussion in the rest of paragraphs here.

What is a builder:

Builder is well discussed in wikipedia and is defined in GoF design patterns. it is basically a support class that has fluent setter methods for all the settable attributes of a class. It may be available as nested static class within a POJO or perhaps as a separate class.

When is a builder needed:

It is a common knowledge; that; once the object's state attributes increase (Refer to Effective Java on Builder); the user who wants to construct the object seeks refuge to some facility to construct such as a builder or prototype, factory pattern that requires logic just beyond plain-jane constructors. Of course; in this situation of mine; the POJO generated had just a zero argument constructor and hence user of this object is left with no choice to call several set methods. An interesting corollary to this use case is when developer or the user of this POJO is also the owner of POJO and has the choice of adding builder / factory classes along with the POJO.

This article discusses two use-cases on making use of a builder pattern in complex object construction and in specific a few open source libraries usage in this context.

Auto-generated POJO as third party dependency which doesn't provide builder/factory
The current user of the POJO is the owner of POJO creation and appreciates a need of builder.

Use case - Auto-generated POJO without any construction hooks

In this situation briefly discussed in the introduction; the POJO is typically available as a jar file and hence if a builder needs to be built; then a naive way of manually adding a <POJOName>Builder for every POJO proves futile two ways:

Manually inspecting the setter methods (and thus attributes) to build each builder seems to be ridden with non-productive, highly repetitive and effort intensive
Next, this activity may not be restricted to one time; as the POJO might change in its structure and now; aligning the builder with these changes is even more repetitive and highly ineffective.

These above consequences might at best discourage the developers in making use of builders.

A better way then; could be to study the POJO class structure for attributes, set methods and auto-create the builder source. If this activity can be automated by some program and aligned to pre-compile phase of the project build cycle; the builder class thus auto generated can be added as sources just before compilation of the project sources. The builder functionality is typically about providing fluent setter methods for each attribute of the object and can realized in two ways viz.,

Generate a PojoBuilder java class for each of the Pojo.
Generate an interface for the PojoBuilder and use some proxy technique to wire the interface to the Pojoclass for all the set methods call delegation.

It seemed that the option with interface was better alternative which allows any specific builder implementation to be envisaged in future (a proxy implementation is just one such).

Going ahead on the second option with interface approach; the tasks really boiled down to the following for any given POJO class named for e.g.; say PojoName

Figure out all the set methods (and thus settable attributes) of the POJO class PojoName by means of some libraries that understands class byte codes.
Create on the fly; an Interface with the name <PojoName>Builder and create method signatures that resemble all the set methods of the POJO class in question. Of course the set methods in this builder interface will return the <PojoName>Builder object in the true spirit of fluent pattern.
Create the Java source for this builder interface generated in step 2 and place the source newly generated into some source folder which is to be picked up for compilation later.

For step 1;, There are many byte code understanding libraries for various purposes; however the one i chose for the experiment is javassist which not only understands the class bytes but also helps in creating on-the-fly classes, interfaces etc. The first step is to figure out the setter methods and with javassist it becomes much simpler with illustrated method below.

private Set<CtMethod> getWritableMethods(final Class<?> 
            thisPojoClass)throws NotFoundException {
    final CtClass ctClass = ctPool.get(thisPojoClass.getName());
    final Set<CtMethod> ctMethodSet = new LinkedHashSet<>(); 
    final Set<Class<?>> propTypes =
        getPropertyClassTypes(thisPojoClass,
                ctClass, ctMethodSet);
    for (Method method : thisPojoClass.getDeclaredMethods()) {
        if (method.isSynthetic()) {
            LOGGER.warning(method.getName() + 
                " is synthetically added,so ignoring");
            continue;
        }
        final CtMethod ctMethod = ctClass.getDeclaredMethod(
                        method.getName());

        if (Modifier.isPublic(method.getModifiers())
        && setMethodNamePattern.matcher(method.getName())
        .matches() && !ctMethodSet.contains(ctMethod)) {
        // Make sure the types u get from method 
        //is really is of a field type
        boolean isAdded = /*
                * propTypes.containsAll(
                * Arrays.asList(method.
                * getParameterTypes())) &&
                */ctMethodSet.add(ctMethod);
            if (!isAdded) {
                LOGGER.warning(method.getName() +
                 " is not added");
            }
        }
    }
    return ctMethodSet;
}

(Note: This method is part of a class in FluentBuilders class)

In here, the ctClass is the javassist class object representing a java class. All the declared methods of the passed in Pojo class is examined and the ones which match the following conditions are considered for adding to the builder interface.

public mutator method
whose name matches an agrreed upon regex which is passed to the utilty
are not synthetic methods

An additional check can be that the arguments passed into such a setter method to be of field types as expected in the pojo class.

For Steps 2 and 3;, a base interface Builder from fluent-interface library is assumed and here is the snippet for getting the interface for the Pojo. The source code itself i generated using codemodel.

final Set<CtMethod> writableMethods = getWritableMethods(thisPojoClass);
final Set<Method> writableNormalMethods = getWritableNormalMethods(

thisPojoClass);

if (writableMethods.isEmpty()) {
    failedList.add(thisPojoClass);
} else {

    //Create the interface first

    final String interfaceName = String.format("%s.%sBuilder",

                                     thisPojoClass.getPackage().getName(),

                                         thisPojoClass.getSimpleName());

    //fluentBuilderClass represents the base builder from open source lib

    final CtClass pojoBuilderInterface = ctPool.makeInterface(interfaceName,

                                               fluentBuilderClass);

    // next add methods to this on the fly interface

    addMethodsToBuilder(pojoBuilderInterface, writableMethods);

    //next create source code model.

    JCodeModel codeModel = new JCodeModel();
    try {
        JClass builderInterface = new JCodeModel()
        ._class(Builder.class.getName(), ClassType.INTERFACE)
        .narrow(thisPojoClass);
        JDefinedClass definedClass = codeModel._class(interfaceName, 
        ClassType.INTERFACE)._extends(builderInterface);
        Class<?> builderClass = ctPool.toClass(pojoBuilderInterface);
        for (Method method : writableNormalMethods) {
            JMethod jMethod = definedClass.method(Modifier.PUBLIC, 
                builderClass, method.getName());
            for (int i = 0; i<method.getParameterTypes().length; i++) {
                jMethod.param(method.getParameterTypes()[i], 
                "arg" + i++);
            }
        }
        sourceFolderRoot.mkdirs();
        codeModel.build(sourceFolderRoot);
    } catch (Exception e) {
        throw new IOException(e);
    }
}

(Note: This method is part of a class i wrote in FluentBuilders class).

How to use this in a maven based set up:

I have added a small set of classes for creating builders using few open sources and is available

here in github. The following quick steps can get a first glimpse of how builders can be constructed

within maven set up.

First have a maven quick archetyped java project created where standard folders such as

src/main/java,
src/test/java and
src/main/resources folders are available under root folder builders-test.

Next, create a simple Pojo class such as Pojo1.java in builders-test/src/main/java/
This Pojo could be already made available to you in the form of dependency jar

dependency jar containing the pojo class is in the real situation and is usual
however for demo purpose assuming a java source code (Pojo1.java)

this java source will be compiled and for which subsequently a builder is generated

Next, create a text file class-listing.txt in builders-test/src/main/resources/
Next, create a pom.xml that has relevant sections to note below apart from dependencies

The builder needs to be generated when the Pojo1 is compiled

and hence in the maven-exec-plugin, i am triggering this in process-classes phase

The builder generated needs to be considered for adding it as a source and then compiled

and hence build-helper-maven-plugin runs add-source in process-classes phase

Next, the compile plugin itself being configured to trigger compilation in 2 phases

once during compile and second pass dueing process-class due to added source.

the maven test phase is assumed since builder interface is compiled in process-classes

@Test
public void test() throws ClassNotFoundException {
   Pojo1 pojo1=FluentBuilders.<Pojo1,Pojo1Builder>builder(

Pojo1.class).setI(10).setJ("Murthy").build();

   System.out.println(pojo1.toString());
}

Lastly, snapshot repositories for the builders and other libs

<repositories>
   <repository>
      <id>oss-snapshot</id>
      <url>https://oss.sonatype.org/content/repositories/snapshots/</url>
   </repository>
   <repository>
      <id>apache-snapshots</id>
      <url>https://repository.apache.org/content/repositories/snapshots</url>
   </repository>
</repositories>

 Please refer to the complete example in the readme snippet.

Usecase - Auto-generating builders as part of your POJO.

This use case is about when as a developer oneself owns the POJO creation and i have just explored
two libraries. Please let me know of others in this category

Google's AutoValue
Project lombok

While one can naively manually add builder class as a static nested class within the POJO, a
simple annotation based approach may reduce the mundane activity which is the reason to
discuss on this use case.

In case of auto value one needs to think in terms of abstract class for the POJO class and
expose the attributes as abstract get methods as shown below in their original example
[Courtesy: from AutoValue site]

public final class PojoClass {

    @AutoValue
    abstract static class Animal {
        static Animal create(String name, int numberOfLegs) {
            return new AutoValue_PojoClass_Animal(name, numberOfLegs);
        }
        abstract String name();
        abstract int numberOfLegs();
    }
}

AutoValue has other additional benefits; however in the context of experimenting for most basic

needs of a simple builder; i am leaving those details out here.

On the other hand project lombok has even more leaner annotation based intent as follows:

@Builder
@Data
@FieldDefaults(level = AccessLevel.PRIVATE, makeFinal = true)
class Example {
    int foo;
    String bar;
}

Now, you have here a full fledged class with all the fields as private and final and with getter(s) and
a static nested ExampleBuilder class with relevant setters already wired in the .class files.

Can you ask for anything simpler?

Note : Please note that the sole intent in this use case was to explore a few popular libraries use of automating,
simplyfing the construction and use of builders. It is by no means a comparison of features or limitations here
as i have not exhaustively demonstrated their abilities here.

Summary:

In summary, this was an attempt to understand how a builder can be created for dependent POJO
classes coming from third party. While nothing short of byte code reading and adding interface/class
on the fly is the approach in these cases; the use of annotation based libraries in the own POJO
case is heartening to note the simplicity and convenience it brings upon.

I am signing off finally by making a wish:

If only did the proprietary POJO code generators considered creating builders/factories/creation

methods along with generating POJO itself; i wouldn't have got a chance to write this post!.

Saturday, January 17, 2015

Visitor Pattern - Using Java

Visitor Pattern

Visitor pattern from my perspective does an important aspect of helping the evolution of heterogenous operations on a data structure and the structure of data independently. A formal definition of this pattern can be had from GoF Book on Design Pattern and other well known sources and authority on design pattern.

However this post is just a capture of snapshot of my thoughts on how we could implement with an intent defined in next section. I will be immensely happy for viewer's comments on how this could be improved.

Intent:

Sometime back; i was drawn to write some examples on few operations on trees and graphs. The moment that thought crossed my mind i wanted to model these operations as an entity or a hierarchy of entities and allow it to be passed inside the structure of interest. The intent was to have the following common behavioral methods in any of the operational entities such as

method(s) for when operating on whole of structure or on individual elements
method for when doing something with that element
A getter method to keep an audit trail/collection of results of interest accrued / accumulated over visiting trail. (Perhaps this behavior could be added as a decorator or some other pattern)

Example with trees

A basic entity for visiting a tree could perhaps be as follows:

/**
*
*/
package algos.trees.visitors;

import algos.trees.Element;
import algos.trees.Tree;

/**
* Visitor interface for a element of type T in a {@link Tree} that might return
* of type R and may have collected Results in a type of C.
*
* @author vmurthy
*
* @param <T>
* is the type of the node in the {@link Tree}
* @param <R>
* is the type of the result computed over each visit
* @param <C>
* is the collection of result accumulated over every visit of
* {@link Element} in {@link Tree}
*/
public interface Visitor<T extends Comparable<T>, R, C> {
/**
* Visiting at the top of the tree. Can be used for any action/function to
* be done at the start of visit
*
* @param t
* is the tree
* @return R the result type
*/
R visit(Tree<T> t);

/**
* Visiting an element
*
* @param e
* the {@link Element element}
* @return R the result type
*/
R visit(Element<T> e);

/**
* Do some operation on the data node itself
*
* @param e
* the {@link Element element} upon which to do something
* @return R the result type
*/
R doSomethingOnElement(Element<T> e);

/**
* Return a collection of some interesting results accumulated over the
* visiting trail.
*
* @return C collection of results perhaps different than R
*/
C collection();
}

A simple example of operation on tree could be such as printing all the vertical paths from root node leading to leaf node as follows. I have used lombok annotations to keep the code relatively clutter free.

package algos.trees.visitors;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

import lombok.AccessLevel;
import lombok.Data;
import lombok.EqualsAndHashCode;
import lombok.val;
import lombok.experimental.Accessors;
import lombok.experimental.FieldDefaults;
import lombok.experimental.NonFinal;

import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;
import org.apache.logging.log4j.message.StringFormatterMessageFactory;
import org.springframework.util.StringUtils;

import algos.trees.Element;
import algos.trees.Tree;

/**
* The Class PrintVerticalPathVisitor prints all vertical path from root of tree
* to each leaf node
*
* @param <T>
* the generic type
*/
@Data
@Accessors(fluent = true, chain = true)
@EqualsAndHashCode(callSuper = false)
@FieldDefaults(level = AccessLevel.PRIVATE, makeFinal = true)
public class PrintVerticalPathVisitor<T extends Comparable<T>> implements
Visitor<T, Void, List<List<T>>> {

public static <Y extends Comparable<Y>> PrintVerticalPathVisitor<Y> of(Boolean headToTail) {
return new PrintVerticalPathVisitor<Y>(headToTail);
}

static final Logger log = LogManager.getLogger(StringFormatterMessageFactory.INSTANCE);

Deque<T> queue = new ArrayDeque<T>();

// We need this collection Deque list for outside access so keep name
List<List<T>> collection = new ArrayList<List<T>>();

Boolean headToTail;

@NonFinal
static Void v;

@Override
public Void visit(Tree<T> t) {
visit(t.root());
return v;
}

@Override
public Void visit(Element<T> e) {
if (headToTail) queue.addLast(e.value());
else queue.addFirst(e.value());

if (e.isBachelor()) printStack();
else {
if (e.hasLeft()) visit(e.left());
if (e.hasRight()) visit(e.right());
}

if (headToTail) queue.removeLast();
else queue.removeFirst();
return v;
}

@Override
public Void doSomethingOnElement(Element<T> e) {
throw new UnsupportedOperationException();
}

/**
* print stack of collected
*/
private void printStack() {
collection.add(new ArrayList<T>(queue));
log.debug(StringUtils.collectionToDelimitedString(queue, " "));
}

}

NOTE: This code uses Lombok annotations and hence doesn't require get/set methods to be written explicitly while many of the mundane stuff such as declaring private, final, equals method etc are also automatically taken care. The instance variable collection is strategically named so that; lombok auto generates the getter method for the same which in turn satisfies interface requirements(therefore you don't see getCollection() or collection() method here in this code).

Also In this example doSomethingOnElement is not required as its just a matter of printing.

While PrintVerticalPath may be one use case there could be many. A few of which i have captured in my code repository for tree visitors.

Use in Graph

An another slight modification is to bring in a template for structure and call the structure as Visitable

public interface Visitable<T>{

//void pre();

void accept(Visitor<Visitable<T>,?,?> visitor);

//void post();

}

But here the Visitor could be simplified as now there is no tree look-alike graph. Perhaps may be we could generically use the below Visitor for both tree and graph.

public interface Visitor<T, R, C> {

/**

* visit an instance of {@link Visitable<T>}

* @param t

* an instance of Visitable

* @return a result R

R visit(T t);

/**

* @return a Collection/Aggregation of result accumulated over each visit

C collection();

}

A simple example of building Prim's algorithm as follows in the following code snippet in my repository :

@Accessors(fluent = true)

@Data//(staticConstructor = "of")

@FieldDefaults(level = AccessLevel.PRIVATE, makeFinal = true)

static class Prim<Type extends Comparable<Type>> implements

Visitor<VertexInterface<Type>, Void, Set<VertexInterface<Type>>> {

public static<Y extends Comparable<Y>> Prim<Y> of(GraphInterface<Y> g){

return new Prim<Y>(g);

}

/**

* Passed in Graph G

GraphInterface<Type> G;

/**

* Collected results. Keep it always named as collection so u dont have

* to code getCollection()/collection() method.

@NonFinal Set<VertexInterface<Type>> collection = new LinkedHashSet<VertexInterface<Type>>();

@Override public Void visit(VertexInterface<Type> s) {

/**

* The Breadth First {@link Queue}

Queue<VertexInterface<Type>> Q = new PriorityQueue<VertexInterface<Type>>(

G.verticies().size(),

new Comparator<VertexInterface<Type>>() {

@Override public int compare(VertexInterface<Type> o1,

VertexInterface<Type> o2) {

if (o1.weight() == o2.weight())

return 0;

else

return o1.weight() < o2.weight() ? -1 : 1;

}

});

// Initialize pi,and distance to INF

for (val u : G.verticies())

if(!u.equals(s))

u.weight(INFINITY).pi(null);

// Mark root alone to zero while all are INF add to priority

// queue

s.weight(0d);

Q.addAll(G.verticies());

while (!Q.isEmpty()) {

// Pick up the vertex u and find the adjV

val u = Q.remove(); // this is extract first or extract top

for (val v : G.adjV(u)) {

val edge = G.findEdge(u, v);

if (Q.contains(v) && edge != null

&& edge.cost() < v.weight())

v.pi(u).weight(edge.cost());

}

return v_o_i_d;

}

Conclusion:

The example of data structure/algorithmic cases are incidental here as my interests are more focused towards clear / clean design. As can be seen this template of visitor is re-usable in many cases such as traversals and many other interesting operations on trees and graphs. By no means this is a complete article; and wish to solicit other's opinion on the same.

References:

Git repo - https://github.com/venkateshamurthy/java-algorithms
GoF - GoF Book on Design Pattern