<p align="center"><img src="logo.png" height="120" width="120"/>

</p> <hr />

Traverser: java library to walk object graph

<!-- add badges -->

[Traverser][Traverser] solves a one of the most common tasks to operate on tree or graph data structure:

• enumerate tree or graph nodes into a traverse sequence
• execute client actions on each enumerated node
• fine grained control of the traversal loop (continue, break, skip nodes)

It exposes rich and fine level of capabilities like:

• iterators
• both depth- and breadth- first search (DFS/BFS)
• pre- and post- order actions
• cycle detection
• visitors
• global and local node contexts

It helps in several areas:

• speed up implementation by re-using generic solution (stable, tested, well-performant solution)
• reduce codebase
• expand and adjust use cases with simple changes
• decouples traversing routine from data structure and client actions, which boosts maintenability

Getting Started

Add dependency on this module and traverse any complex data structure. Gradle:

 compile 'com.intuit.commons:traverser:1.0.0'

Maven:

<dependency>
    <groupId>com.intuit.commons</groupId>
    <artifactId>traverser</artifactId>
    <version>1.0.0</version>
    <type>pom</type>
</dependency>

Local Development

./gradlew build

Configuration

It is possible to override version and group of the artifact:

./gradlew clean -Pproject.version=1.0.0-SNAPSHOT -Pproject.group=com.intuit.commons  publishToMavenLocal

where project.version and project.group are used to control desired group and version. Artifact name is configured with rootProject.name property in settings.gradle.

Learn by example

Representing hierarchy of a medium-sized company is good example to illustrate key features of the traverser.

Company 
    Bussiness Entity
          Teams
                Members

Snapshot of a virtual company staff:

Company
     BU-Pacific  
         Product Development
              Sylvester Moonstone
              John Smith
              Lucy Gold
         Sales Department
              Nick Citrine 
              Kleo Ruby 
         Management
              Anna Peridot                  

Disclaimer: Names, characters and businesses are used in fictitious manner. Any resemblance to actual persons, living or dead is purely coincidental.

This company structure could be represented in Java as a set of classes that implement interface Node

Object structure

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;

/**
 * Defines the mimimalistic API to allow to form
 * Company structure tree
*/
public interface Node {
   /**
    * Name of a node
    */
   String getName ();
   /**
    * If Node is a leaf, returns an empty list
    * Otherwise returns the list of immediate chidren of the current
    * node.
    * This method is crucial to navigate the tree
    */
   List<Node> getChildren();
   /**
    * Visitor pattern support for Nodes 
    * to demonstrate double-dispatch mechanizm
    *
    * @see <a href="https://en.wikipedia.org/wiki/Visitor_Pattern">Visitor Pattern</a>
    * @see <a href="https://en.wikipedia.org/wiki/Double_dispatch">Double-Dispatch</a>
    */
   <U> U accept (U data, NodeVisitor<U> visitor);
}

/**
 * Visitor interface allows to decouple code that needs to be invoked
 * on Node instances from the various ways to enumerate Nodes in the tree
 *
 * Visitor pattern goes hand-in-hand with Double Dispatch pattern that 
 * allows to call Node-specific Visitor's method in a type safe manner, without need
 * to determine the type of Node. Node type is determined automatically when 
 * {@link Node.accept(U, NodeVisitor<U>) Node.accept} method is called.
 * Each Node implementation knows its own type and delegates the call to the corresponding
 * Visitor's method. 
 */
public interface NodeVisitor<U> {
   /**
    * Called when accepting Node is Company
    */
   U visitCompany (Company company, U data);
   /**
    * Called when accepting Node is BusinessEntity
    */
   U visitBusinessEntity (BusinessEntity businessEntity, U data);
   /**
    * Called when accepting Node is Team
    */
   U visitTeam (Team team, U data);
   /**
    * Called when accepting Node is Member
    */
   U visitMember (Member member, U data);
}

public class Company implements Node {
   String name;
   List<BusinessEntity> businessEntities = new ArrayList<>();
  
   public Company (String name) {
      this.name = name;
   }

   public Company businessEntity (BusinessEntity businessEntity) {
      businessEntities.add(businessEntity);
      return this;
   }

   public List<BusinessEntity> getBusinessEntities () {
      return businessEntities;
   }

   public String getName () {
      return name;
   }

   public List<Node> getChildren () {
      return (List<? extends Node>)getBusinessEntities();
   }

   public <U> U accept (U data, NodeVisitor<U> visitor) {
      // double-dispatch to the custom method for Company nodes 
      return visitor.visitCompany(this, data);
   }
}

public class BusinessEntity implements Node {
   String name;
   List<Team> teams = new ArrayList<>();

   public BusinessEntity (String name) {
      this.name = name;
   }

   public BusinessEntity team (Team team) {
      teams.add(team);
      return this;
   }

   public List<Team> getTeams () {
      return teams;
   }

   public String getName () {
      return name;
   }

   public List<Node> getChildren () {
      return (List<? extends Node>)getTeams();
   }

   public <U> U accept (U data, NodeVisitor<U> visitor) {
      // double-dispatch to the custom method for BusinessEntity nodes 
      return visitor.visitBusinessEntity(this, data);
   }
}

public class Team implements Node {
   String name;
   List<Member> members = new ArrayList<>();
 
   public Team (String name) {
      this.name = name;
   }

   public Team member (Member member) {
      members.add(member);
      return this;
   }

   public List<Member> getMembers () {
      return members;
   }

   public String getName () {
      return name;
   }

   public List<Node> getChildren () {
      return (List<? extends Node>)getMembers();
   }

   public <U> U visitTeam (U data, NodeVisitor<U> visitor) {
      // double-dispatch to the custom method for Team nodes 
      return visitor.visitTeam(this, data);
   }
}

public class Member implements Node {
   String name;

   public Member (String name) {
      this.name = name;
   }

   public String getName () {
      return name;
   }

   public List<Node> getChildren () {
      return Collections.emptyList();
   }

   public <U> U accept (U data, NodeVisitor<U> visitor) {
      // double-dispatch to the custom method for Member nodes 
      return visitor.visitMember(this, data);
   }
}

The same company structure could be represented in Scala as a set of classes that implement interface Node as below

import java.util

sealed trait Node {
  def getName: String

  def getChildren: java.util.ArrayList[Node]

  def accept[U](data: U, visitor: NodeVisitor[U]): U
}

sealed trait NodeVisitor[U] {
  def visitCompany(company: Company, data: U): U

  def visitBusinessEntity(businessEntity: BusinessEntity, data: U): U

  def visitTeam(team: Team, data: U): U

  def visitMember(member: Member, data: U): U
}

class Company(name: String) extends Node {
  val businessEntities = new util.ArrayList[BusinessEntity]

  def apply(name: String): Company = new Company(name)

  def businessEntity(businessEntity: BusinessEntity): Company = {
    businessEntities.add(businessEntity)
    this
  }

  def getName: String = name

  def getBusinessEntities: util.ArrayList[BusinessEntity] = businessEntities

  def getChildren: java.util.ArrayList[Node] = getBusinessEntities.asInstanceOf[java.util.ArrayList[Node]]

  def accept[U](data: U, visitor: NodeVisitor[U]): U = { // double-dispatch to the custom method for Company nodes
    visitor.visitCompany(this, data)
  }
}


class BusinessEntity(name: String) extends Node {
  val teams = new util.ArrayList[Team]

  def team(team: Team): BusinessEntity = {
    teams.add(team)
    this
  }

  def getTeams: util.ArrayList[Team] = teams

  def getName: String = name

  def getChildren: java.util.ArrayList[Node] = getTeams.asInstanceOf[java.util.ArrayList[Node]]

  def accept[U](data: U, visitor: NodeVisitor[U]): U = { // double-dispatch to the custom method for BusinessEntity nodes
    visitor.visitBusinessEntity(this, data)
  }
}

class Team(name: String) extends Node {
  val members = new util.ArrayList[Member]

  def member(member: Member): Team = {
    members.add(member)
    this
  }

  def getMembers: util.ArrayList[Member] = members

  def getName: String = name

  def getChildren: java.util.ArrayList[Node] = getMembers.asInstanceOf[java.util.ArrayList[Node]]

  def visitTeam[U](data: U, visitor: NodeVisitor[U]): U = { // double-dispatch to the custom method for Team nodes
    visitor.visitTeam(this, data)
  }

  def accept[U](data: U, visitor: NodeVisitor[U]): U = ???
}

class Member(name: String) extends Node {
  def getName: String = name

  def getChildren: java.util.ArrayList[Node] = new util.ArrayList[Node]()

  def accept[U](data: U, visitor: NodeVisitor[U]): U = { // double-dispatch to the custom method for Member nodes
    visitor.visitMember(this, data)
  }
}

The same company structure could be represented in Kotlin [Company Model](examples/src/m