I wrote a route search program in TDD and refactored it

To improve my TDD skills, I tried some of the themes summarized in this blog, and route search I personally made a refreshing refactoring, so I'll put it together for your records.

In addition, the task is to implement up to 4, and here we describe the refactoring in 3 to 4.

Preparation

Development environment

Java Uses OpenJDK 11. Since it is a mac, it was installed with home brew cask java

Maven Use 3.6.0. This was also installed with homebrew

IDE Use IntelliJ IDEA 2018.3.

In the project settings, set to run with the above OpenJDK and Maven

Project settings

Test set JUnit5, Pom to use AsserJ for assertions

pom.xml


<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>myTest</groupId>
    <artifactId>myTest</artifactId>
    <version>1.0-SNAPSHOT</version>
    <packaging>jar</packaging>
    <properties>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
        <java.version>11</java.version>
    </properties>
    <build>
        <plugins>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-compiler-plugin</artifactId>
                <version>3.8.0</version>
                <configuration>
                    <source>${java.version}</source>
                    <target>${java.version}</target>
                </configuration>
            </plugin>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-surefire-plugin</artifactId>
                <version>2.22.1</version>
            </plugin>
        </plugins>
    </build>
    <dependencies>
        <dependency>
            <groupId>org.junit.jupiter</groupId>
            <artifactId>junit-jupiter-api</artifactId>
            <version>5.3.2</version>
            <scope>test</scope>
        </dependency>
        <dependency>
            <groupId>org.junit.jupiter</groupId>
            <artifactId>junit-jupiter-engine</artifactId>
            <version>5.3.2</version>
            <scope>test</scope>
        </dependency>
        <dependency>
            <groupId>org.assertj</groupId>
            <artifactId>assertj-core</artifactId>
            <version>3.11.1</version>
            <scope>test</scope>
        </dependency>
    </dependencies>
</project>

Test code

Test code up to Exercise 4

TrainPathTest.java


import static org.assertj.core.api.Assertions.assertThat;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

class TrainPathTest {
  
  private TrainPath trainPath;
  
  @BeforeEach
  void createTrainPath() {
    trainPath = new TrainPath();
  }
  
  @Test
  @DisplayName("You can't go to Oshima from Yokohama by train")
  void cannotFromYokohamaToOshima() {
    assertThat(trainPath.exist("Yokohama", "Oshima")).as("YokohamaからOshimaへは行けない").isFalse();
  }
  
  @Test
  @DisplayName("You can't go from Oshima to Yokohama by train")
  void cannotFromOshimaToYokohama() {
    assertThat(trainPath.exist("Oshima", "Yokohama")).as("OshimaからYokohamaへは行けない").isFalse();
  }
  
  @Test
  @DisplayName("You can go from Yokohama to Tokyo by train")
  void canGoFromYokohamaToTokyo() {
    assertThat(trainPath.exist("Yokohama", "Tokyo")).as("YokohamaからTokyoへ行ける").isTrue();
  }
  
  @Test
  @DisplayName("You can go from Tokyo to Yokohama by train")
  void canGoFromTokyoToYokohama() {
    assertThat(trainPath.exist("Tokyo", "Yokohama")).as("TokyoからYokohamaへ行ける").isTrue();
  }
  
  @Test
  @DisplayName("Omiya can be reached by train from Tokyo")
  void canGoFromTokyoToOmiya() {
    assertThat(trainPath.exist("Tokyo", "Omiya")).as("TokyoからOmiyaへ行ける").isTrue();
  }
  
  @Test
  @DisplayName("You can go to Tokyo by train from Omiya")
  void canGoFromOmiyaToTokyo() {
    assertThat(trainPath.exist("Omiya", "Tokyo")).as("OmiyaからTokyoへ行ける").isTrue();
  }
  
  @Test
  @DisplayName("You can go to Yokohama by train from Omiya")
  void canGoFromOmiyaToYokohama() {
    assertThat(trainPath.exist("Omiya", "Yokohama")).as("OmiyaからYokohamaは行ける").isTrue();
  }
  
  @Test
  @DisplayName("Omiya can be reached by train from Yokohama")
  void canGoFromYokohamaToOmiya() {
    assertThat(trainPath.exist("Yokohama", "Omiya")).as("YokohamaからOmiyaは行ける").isTrue();
  }
  
  @Test
  @DisplayName("Akabane can be reached by train from Kawasaki")
  void canGoFromKawasakiToAkabane() {
    assertThat(trainPath.exist("Kawasaki", "Akabane")).as("KawasakiからAkabaneは行ける").isTrue();
  }
}

Production code

Two classes

  1. TrainPath.java Perform a route search
  2. Section.java has information on the route

Exercise 3 Even if there is no direct connection between Yokohama and Omiya, it will be reached because it is connected in Tokyo.

Points to worry about

――Since you can't reach it by one route, I searched repeatedly while taking a waypoint. --Do not re-search the route once searched

TrainPath.java


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

class TrainPath {
  
  private final List<Section> sectionList;
  
  TrainPath() {
    sectionList = new ArrayList<>();
    sectionList.add(new Section("Yokohama", "Tokyo"));
    sectionList.add(new Section("Tokyo", "Omiya"));
  }
  
  boolean exist(String departure, String destination) {
    
    List<String> stations = new ArrayList<>();
    stations.add(departure);
    
    while (true) {
      List<String> transitList = new ArrayList<>();
      
      for (String startStation : stations) {
        for (Section section : sectionList) {
          if (section.isSearched()) {
            continue;
          }
          if (section.exist(startStation, destination)) {
            return true;
          }
          String transit = section.getTargetStation(startStation);
          if (transit == null) {
            continue;
          }
          if (transitList.contains(transit)) {
            continue;
          }
          transitList.add(transit);
          section.setSearched();
        }
      }
      if (transitList.isEmpty()) {
        return false;
      }
      
      stations.clear();
      stations = new ArrayList<>(transitList);
    }
  }
}

Section.java


class Section {
  private String station1;
  private String station2;
  private boolean searched;
  
  Section(String station1, String station2) {
    this.station1 = station1;
    this.station2 = station2;
    this.searched = false;
  }
  
  boolean exist(String departure, String destination) {
    if (station1.equals(departure) && station2.equals(destination)) {
      return true;
    }
    return station2.equals(departure) && station1.equals(destination);
  }
  
  String getTargetStation(String station) {
    if (station.equals(this.station1)) {
      return this.station2;
    } else if (station.equals(this.station2)) {
      return this.station1;
    }
    return null;
  }
  
  boolean isSearched() {
    return searched;
  }
  
  void setSearched() {
    this.searched = true;
  }
}

Refactoring for Exercise 3

Method division of TrainPath While statement processing

--Separate the inside of the nest of for statements into existSection methods --Furthermore, the process of acquiring waypoints is also divided into existTransit methods.

I think it became easier to understand by dividing the method.

TrainPath.java


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

class TrainPath {
  
  private final List<Section> sectionList;
  private List<String> transitList;
  
  TrainPath() {
    sectionList = new ArrayList<>();
    initializeSection();
  }
  
  boolean exist(String departure, String destination) {
    
    List<String> stations = new ArrayList<>();
    stations.add(departure);
    
    while (true) {
      transitList = new ArrayList<>();
      for (String station : stations) {
        if (existSection(station, destination)) return true;
      }
      if (transitList.isEmpty()) return false;
      stations = new ArrayList<>(transitList);
    }
  }
  
  //Search for a direct route from your origin to your destination
  //If there is no direct route, search for a waypoint
  private boolean existSection(String departure, String destination) {
    for (Section section : sectionList) {
      if (section.isSearched()) continue;
      if (section.exist(departure, destination)) return true;
      existTransit(departure, section);
    }
    return false;
  }
  //Search for waypoints from the route
  private void existTransit(String departure, Section section) {
    String transit = section.getTargetStation(departure);
    if (transit == null) return;
    if (transitList.contains(transit)) return;
    transitList.add(transit);
    section.setSearched();
  }
  
  private void initializeSection() {
    sectionList.add(new Section("Yokohama", "Tokyo"));
    sectionList.add(new Section("Tokyo", "Omiya"));
  }
}

Exercise 4 Confirm that you can go to various places

At the time of Exercise 3, it was realized, so I was able to pass the test by adding the route list.

TrainPath.java


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

class TrainPath {
  
  private final List<Section> sectionList = new ArrayList<>();
  private List<String> transitList;
  
  TrainPath() {
    initializeSection();
  }
  
  boolean exist(String departure, String destination) {
  
    List<String> stations = Collections.singletonList(departure);
    
    while (true) {
      transitList = new ArrayList<>();
      for (String station : stations) {
        if (existSection(station, destination)) return true;
      }
      if (transitList.isEmpty()) return false;
      stations = new ArrayList<>(transitList);
    }
  }
  
  //Search for a direct route from your origin to your destination
  //If there is no direct route, search for a waypoint
  private boolean existSection(String departure, String destination) {
    for (Section section : sectionList) {
      if (section.isSearched()) continue;
      if (section.exist(departure, destination)) return true;
      existTransit(departure, section);
    }
    return false;
  }
  //Search for waypoints from the route
  private void existTransit(String departure, Section section) {
    String transit = section.getTargetStation(departure);
    if (transit == null) return;
    if (transitList.contains(transit)) return;
    transitList.add(transit);
    section.setSearched();
  }
  
  private void initializeSection() {
    sectionList.add(new Section("Yokohama", "Musashi Kosugi"));
    sectionList.add(new Section("Yokohama", "Kawasaki"));
    sectionList.add(new Section("Musashi Kosugi", "Nishikokubunji"));
    sectionList.add(new Section("Musashi Kosugi", "Shibuya"));
    sectionList.add(new Section("Musashi Kosugi", "Kawasaki"));
    sectionList.add(new Section("Kawasaki", "Tokyo"));
    sectionList.add(new Section("Nishikokubunji", "Minamiurawa"));
    sectionList.add(new Section("Nishikokubunji", "Shinjuku"));
    sectionList.add(new Section("Shibuya", "Shinjuku"));
    sectionList.add(new Section("Shibuya", "Tokyo"));
    sectionList.add(new Section("Tokyo", "Ochanomizu"));
    sectionList.add(new Section("Tokyo", "Akihabara"));
    sectionList.add(new Section("Shinjuku", "Ikebukuro"));
    sectionList.add(new Section("Shinjuku", "Ochanomizu"));
    sectionList.add(new Section("Ochanomizu", "Akihabara"));
    sectionList.add(new Section("Akihabara", "Tabata"));
    sectionList.add(new Section("Ikebukuro", "Akabane"));
    sectionList.add(new Section("Ikebukuro", "Tabata"));
    sectionList.add(new Section("Tabata", "Akabane"));
    sectionList.add(new Section("Akabane", "Minamiurawa"));
    sectionList.add(new Section("Minamiurawa", "Omiya"));
  }
}

Exercise 4 refactoring (current state of code)

Although I split the method, I couldn't deny the feeling of being aggressive, and I felt that the responsibility of the method was not clear.

As I researched, I learned about recursive calls to the code, and if I used this, wouldn't I need a list of via values? I thought and tried refactoring.

point

--Recursive calling eliminates the need for loop processing (while statement and outer for statement) using a waypoint list. --Reviewed the route search logic and used StreamAPI to create a list excluding unnecessary routes before the for statement.

I was able to write very clearly. By excluding routes that do not need to be searched in advance using the Stream API, the logic in the for statement of the search process can be reduced to only the judgment process.

For StreamAPI, I also considered using removeIf for Collection, but I chose this form because it deletes the necessary route when the waypoint changes.

TrainPath.java


import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

class TrainPath {
  
  private final List<Section> sectionList = new ArrayList<>();
  
  TrainPath() {
    initializeSection();
  }
  
  boolean exist(String departure, String destination) {
    //Exclude routes that are not searched
    List<Section> filteredSectionList = sectionList.stream()
        .filter(section -> section.isNeedSearch(departure))
        .collect(Collectors.toList());
    
    for (Section section : filteredSectionList) {
      if (section.exist(departure, destination)) return true;
      sectionList.remove(section);
      
      //Search again on the route that goes through the destination of the route
      String transit = section.getDestination(departure);
      if (exist(transit, destination)) return true;
    }
    return false;
  }
  
  private void initializeSection() {
   //abridgement
  }
}

In Section.java, the judgment logic of Filter processing of Stream API of TrainPath was added.

Section.java


class Section {
  private String station1;
  private String station2;
  
  Section(String station1, String station2) {
    this.station1 = station1;
    this.station2 = station2;
  }
  
  boolean exist(String departure, String destination) {
    if (station1.equals(departure) && station2.equals(destination)) {
      return true;
    }
    return station2.equals(departure) && station1.equals(destination);
  }
  
  String getDestination(String departure) {
    if (departure.equals(this.station1)) {
      return this.station2;
    } else if (departure.equals(this.station2)) {
      return this.station1;
    }
    return null;
  }
  
  boolean isNeedSearch(String departure) {
    return departure.equals(this.station1) || departure.equals(this.station2);
  }
}

Summary

You can refactor with confidence if you write test code. This time, I wrote the logic in reverse with the method that returns boolean, but I could easily find the mistake because the test failed. Until now, it took a long time to check by actually moving it or checking it in debug mode, and there were many omissions in the test. Also, running and checking the test code in debug mode was easier to fix because it narrowed down the points to check for problems compared to checking in traditional debug mode.

When processing with the same method while changing related parameters such as parent and child, recursive calling of the method simplifies the code and makes it easier to see. On the other hand, if you are not used to it, you will be confused about what the return value will be returned to the caller.

By processing the pre-processing that was done in the for statement in advance using the Stream API, the pre-processing can be branched, and the pre-processing that is done in the for statement becomes simple and easy to understand. Actually, it would be nice if all the processing of the for statement could be done with the Stream API, but I felt that it would be very effective just to divide only what can be done without overdoing it into the Stream API.

This time I tried refactoring through various trials and errors, but I feel that there is a better way to write it. However, I think I'm still immature to notice it, and I felt that I had to write more and more code and know a lot.

Recommended Posts

I wrote a route search program in TDD and refactored it
I wrote a primality test program in Java
I wrote a prime factorization program in Java
I wrote a Lambda function in Java and deployed it with SAM
I wrote a code to convert numbers to romaji in TDD
[Ruby] A program that uses search and each_with_index
[Ruby] A program / concept that combines each_with_index and search
Write a class in Kotlin and call it in Java
I made a Restful server and client in Spring.
[Beginner] I made a program to sell cakes in Java
I wrote a C parser (like) using PEG in Ruby
I wrote a Stalin sort that feels like a mess in Java
(Ruby on Rails6) Creating a database and displaying it in a view
Ruby: I made a FizzBuzz program!
Add a search function in Rails.
I created a PDF in Java.
I wrote Goldbach's theorem in java
Create a Servlet program in Eclipse
Load a 3D model in usdz format into SceneKit and animate it
Create a program to post to Slack with GO and make it a container
I tried running the route search engine (OSRM) easily with a container
I actually expressed the older sister problem in code and calculated it
When I defined a session scope bean in Spring Boot, it behaved strangely and needed to be adjusted.