Coordinates.java

package io.intercom.problems.proximity;

import static java.lang.Math.acos;
import static java.lang.Math.cos;
import static java.lang.Math.sin;
import static java.lang.Math.toRadians;

/**
 * <code>Coordinates</code> is a simple class to encapsulate a latitude and longitude and
 * the great circle based logic to calculate the distance between two instances.
 */
public class Coordinates {

  private Double latitude;

  private Double longitude;

  public final static Double MEAN_EARTH_RADIUS = 6371d;

  /**
   * Creates a new Coordinates object
   * @param latitude the latitude of the coordinates
   * @param longitude the longitude of the coordinates
   */
  public Coordinates(Double latitude, Double longitude) {
    this.latitude = latitude;
    this.longitude = longitude;
  }

  /**
   * Retrieve the latitude
   *
   * @return Double latitude of the coordinates
   */
  public Double getLatitude() {
    return latitude;
  }

  /**
   * Retrieve the longitude
   *
   * @return Double longitude of the coordinates
   */
  public Double getLongitude() {
    return longitude;
  }

  /**
   * Calculates the distance between two sets of Coordinates based on
   * the formula and mean earth radius value found here
   * <p>
   * https://en.wikipedia.org/wiki/Great-circle_distance#Computational_formulas
   *
   * @param there the other set of coordinates to find the distance to
   * @return the distance in kilometers between this set of coordinates and the given set
   */
  public Double distanceTo(Coordinates there) {

    Double lat1 = toRadians(this.latitude);
    Double lon1 = toRadians(this.longitude);
    Double lat2 = toRadians(there.latitude);
    Double lon2 = toRadians(there.longitude);

    Double deltaLongitude = Math.abs(lon1 - lon2);

    Double radians = acos(sin(lat1) * sin(lat2) +
        cos(lat1) * cos(lat2) * cos(deltaLongitude));

    return radians * MEAN_EARTH_RADIUS;
  }
}

CoordinatesTest.java

package io.intercom.problems.proximity;

import org.junit.Test;

import static io.intercom.problems.proximity.Coordinates.MEAN_EARTH_RADIUS;
import static java.lang.Math.PI;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

public class CoordinatesTest {

  @Test
  public void shouldBeNoDistanceBetweenIdenticalCoordinates() {
    Coordinates coords = new Coordinates(123.5678, 123.45678);
    assertEquals(new Double(0.0), coords.distanceTo(coords));
  }

  @Test
  public void shouldCorrectlyCalculateArcsOfKnownMultiplesOfPi() {

    // there are pi radians in a semi circle
    Double piTimeMeanRadius = PI * MEAN_EARTH_RADIUS;

    Coordinates zero = new Coordinates(0.0, 0.0);
    Coordinates equatorial180 = new Coordinates(180.0, 0.0);

    assertEquals(piTimeMeanRadius, zero.distanceTo(equatorial180));

    // there are pi/4 radians in an arc to (0, 45.0)
    Coordinates ninety = new Coordinates(90.0, 0.0);
    Double piOver2 = PI / 2 * MEAN_EARTH_RADIUS;
    assertEquals(new Double(piOver2), zero.distanceTo(ninety));

    // there are pi/6 radians in an arc to (0, 30.0) there is a slight
    // rounding effect with doubles but far beyond the precision required.
    // so two distances are the essentially the same if their difference is
    // negligable
    Double distance = zero.distanceTo(new Coordinates(0.0, -30.0));
    assertTrue(distance - PI / 6 * MEAN_EARTH_RADIUS < 0.0000001);


    distance = new Coordinates(0.0, 45.0).distanceTo(new Coordinates(0.0, -45.0));
    assertTrue(distance - piOver2 < 0.0000001);
  }


}

CustomerLocation.java

package io.intercom.problems.proximity;

import com.fasterxml.jackson.annotation.JsonProperty;

/**
 * <code>CustomerLocation</code> is a simple immutable model class to encapsulate details
 * of a Customer's global location. Instances are created automatically by Jackson as it
 * unmarshalls customer json.
 */
public class CustomerLocation {

  private Double latitude;

  private Double longitude;

  private String name;

  @JsonProperty("user_id")
  private Integer userId;

  public CustomerLocation(){ /* required for serialization */ }

  /**
   * Create a CustomerLocation instance for the given customer name and
   * latitude and longitude location data
   *
   * @param userId the user's id
   * @param name the customer's name
   * @param latitude the customer's latitude
   * @param longitude the customer's longitude
   */
  public CustomerLocation(Integer userId, String name, Double latitude, Double longitude){
    this.userId = userId;
    this.name = name;
    this.latitude = latitude;
    this.longitude = longitude;
    validate();
  }

  /**
   * Validates that a CustomerLocation has all the required fields name, latitude and longitude
   *
   * @throws java.lang.AssertionError if any of the required fields are missing.
   */
  public void validate(){
    StringBuilder b = new StringBuilder();
    if(userId == null) {
      b.append("'userId' is a required field in a CustomerLocation\n");
    }
    if(name == null) {
      b.append("'name' is a required field in a CustomerLocation\n");
    }
    if(latitude == null) {
      b.append("'latitude' is a required field in a CustomerLocation\n");
    }
    if(longitude == null) {
      b.append("'longitude' is a required field in a CustomerLocation\n");
    }

    if(b.length() > 0){
      throw new AssertionError(b.toString());
    }

  }

  /**
   * Retrieve the customers userId
   *
   * @return the customer's userId
   */
  public Integer getUserId() {
    return userId;
  }

  /**
   * Retieve the customer's latitude and longitude coordinates
   *
   * @return Coordinates the customers latitude and longitude coords
   */
  public Coordinates getCoordinates() {
    return new Coordinates(latitude, longitude);
  }

  /**
   * Retieve the customer's latitude
   *
   * @return Double latitude of the customer's location
   */
  public Double getLatitude() {
    return latitude;
  }

  /**
   * Retieve the customer's longitude
   *
   * @return Double latitude of the customer's location
   */
  public Double getLongitude() {
    return longitude;
  }


  /**
   * Retieve the customer's name
   *
   * @return String the customer's name
   */
  public String getName() {
    return name;
  }

}

CustomerLocationDataLoader.java

package io.intercom.problems.proximity;

import com.fasterxml.jackson.databind.ObjectMapper;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLConnection;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * <code>CustomerDataLoader</code> loads customer location data in Json format and
 * parses into a usable <code>CustomerLocation</code> objects.
 */
public class CustomerLocationDataLoader {

  private final Logger log = LoggerFactory.getLogger(getClass());

  /**
   * Reads location information from the given url and parses it into
   * CustomerLocation objects. Expects one full json location representation per
   * line and will ignore any lines that contain malformed input. All parsed locations are
   * validated to insure they contain all the required fields.
   *
   * @param customerLocationDetailsUrl the url of the json file containing the customer information.
   * @return List<CustomerLocation> a list of the CustomerLocations parsed from the contents of the URL.
   * @throws IOException if there is an error reading data from the url
   */
  public List<CustomerLocation> loadCustomerLocationDetails(URL customerLocationDetailsUrl) throws IOException {
    URLConnection con = customerLocationDetailsUrl.openConnection();
    con.setConnectTimeout(3000);
    try (InputStream in = con.getInputStream()) {
      return loadCustomerLocationDetails(in);
    } catch (IOException e) {
      throw new IOException("Could not load customer location details from '" + customerLocationDetailsUrl + "'", e);
    }
  }

  /**
   * Reads location information from the given <code>InputStream</code> and parses it into
   * CustomerLocation objects. Expects one full json location representation per
   * line and will ignore any lines that contain malformed input. All parsed locations are
   * validated to insure they contain all the required fields.
   *
   * @param customerJsonStream inputStream from which to read the customer information in json.
   * @return List<CustomerLocation> a list of the CustomerLocations parsed from the contents of the stream.
   * @throws IOException if there is an error reading data from the stream
   */
  protected List<CustomerLocation> loadCustomerLocationDetails(InputStream customerJsonStream) throws IOException {
    if (customerJsonStream == null) {
      return Collections.EMPTY_LIST;
    }

    ObjectMapper mapper = new ObjectMapper();

    try (InputStreamReader reader = new InputStreamReader(customerJsonStream)) {
      return new BufferedReader(reader).lines()
          .map(json -> parseObject(json, mapper))
          .filter(location -> location != null)
          .collect(Collectors.toList());
    }
  }

  private CustomerLocation parseObject(String line, ObjectMapper mapper) {
    try {
      CustomerLocation customer = mapper.readValue(line, CustomerLocation.class);
      customer.validate();
      return customer;
    } catch (IOException e) {
      log.error("Error parsing customer info '" + line + "', " + e.getMessage());
    }
    return null;
  }


}

CustomerLocationDataLoaderTest.java

package io.intercom.problems.proximity;


import org.junit.Rule;
import org.junit.Test;
import org.junit.rules.ExpectedException;
import org.junit.runner.RunWith;
import org.powermock.core.classloader.annotations.PrepareForTest;
import org.powermock.modules.junit4.PowerMockRunner;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.UncheckedIOException;
import java.net.URL;
import java.net.URLConnection;
import java.util.List;

import static org.junit.Assert.assertEquals;
import static org.powermock.api.mockito.PowerMockito.mock;
import static org.powermock.api.mockito.PowerMockito.when;

@RunWith(PowerMockRunner.class)
@PrepareForTest(URL.class)
public class CustomerLocationDataLoaderTest {

  @Rule
  public ExpectedException thrown = ExpectedException.none();

  private CustomerLocationDataLoader sut = new CustomerLocationDataLoader();

  @Test
  public void shouldLoadCustomersFromInputStream() throws Exception {

    String json = "{\"latitude\": \"52.986375\", \"user_id\": 12, \"name\": \"Christina McArdle\", \"longitude\": \"-6.043701\"}";
    List<CustomerLocation> loaded = sut.loadCustomerLocationDetails(new ByteArrayInputStream(json.getBytes()));
    assertEquals(1, loaded.size());
    CustomerLocation customer = loaded.get(0);
    assertEquals(new Double(52.986375), customer.getCoordinates().getLatitude());
    assertEquals(new Double(-6.043701), customer.getCoordinates().getLongitude());
    assertEquals(new Integer(12), customer.getUserId());
    assertEquals("Christina McArdle", customer.getName());

  }

  @Test(expected = AssertionError.class)
  public void shouldFailValidationIfNameMissing() throws Exception {
    new CustomerLocation(1, null, 123.123, 123.123).validate();
  }

  @Test(expected = AssertionError.class)
  public void shouldFailValidationIfUserIdMissing() throws Exception {
    new CustomerLocation(null, "Bob", 123.123, 123.123).validate();
  }

  @Test(expected = AssertionError.class)
  public void shouldFailValidationIfLatiudeMissing() throws Exception {
    new CustomerLocation(1, "bob", null, 123.123).validate();
  }

  @Test(expected = AssertionError.class)
  public void shouldFailValidationIfLongitudeMissing() throws Exception {
    new CustomerLocation(1, "bob", 123.123, null).validate();
  }

  @Test
  public void shouldHaveAccessToCoordinates(){
    CustomerLocation loc =  new CustomerLocation(1, "bob", 123.123, 123.123);
    loc.validate();
    assertEquals(new Integer(1), loc.getUserId());
    assertEquals("bob", loc.getName());
    assertEquals(new Double(123.123), loc.getLatitude());
    assertEquals(new Double(123.123), loc.getLongitude());
  }

  @Test
  public void shouldIgnoreMalformedJson() throws Exception {
    String malformed = "not json";
    List<CustomerLocation> loaded = sut.loadCustomerLocationDetails(new ByteArrayInputStream(malformed.getBytes()));
    assertEquals(0, loaded.size());

  }

  @Test
  public void shouldLoadCustomersFromUrl() throws Exception {
    CustomerLocationDataLoader sut = new CustomerLocationDataLoader();
    List<CustomerLocation> loaded = sut.loadCustomerLocationDetails(new URL("https://gist.githubusercontent.com/brianw/19896c50afa89ad4dec3/raw/6c11047887a03483c50017c1d451667fd62a53ca/gistfile1.txt"));
    assertEquals(32, loaded.size());
  }

  @Test(expected = IOException.class)
  public void shouldFailIfUrlInaccessible() throws Exception {
    new CustomerLocationDataLoader().loadCustomerLocationDetails(new URL("http://192.168.1.123/deosnotexist"));
  }

  @Test(expected = UncheckedIOException.class)
  public void shouldFailIfErrorReadingStreamContents() throws Exception {
    InputStream mockStream = mock(InputStream.class);
    when(mockStream.read()).thenThrow(new IOException("Something barfed"));
    new CustomerLocationDataLoader().loadCustomerLocationDetails(mockStream);
  }

  @Test(expected = UncheckedIOException.class)
  public void shouldFailIfErrorReadingURLContents() throws Exception {
    InputStream mockStream = mock(InputStream.class);
    when(mockStream.read()).thenThrow(new IOException("Something barfed"));

    URLConnection mockConnection = mock(URLConnection.class);
    when(mockConnection.getInputStream()).thenReturn(mockStream);

    URL mockUrl = mock(URL.class);
    when(mockUrl.openConnection()).thenReturn(mockConnection);
    new CustomerLocationDataLoader().loadCustomerLocationDetails(mockStream);
  }


  @Test
  public void shouldNotChokeIfInputStreamIsEmpty() throws Exception {
    List<CustomerLocation> loaded = new CustomerLocationDataLoader().loadCustomerLocationDetails((InputStream) null);
    assertEquals(0, loaded.size());

    loaded = new CustomerLocationDataLoader().loadCustomerLocationDetails(new ByteArrayInputStream(new byte[0]));
    assertEquals(0, loaded.size());
  }
}

Main.java

package io.intercom.problems.proximity;

import java.net.URL;
import java.util.List;

public class Main {

  public static void main(String[] args) throws Exception {
    URL customerData = new URL("https://gist.githubusercontent.com/brianw/19896c50afa89ad4dec3/raw/6c11047887a03483c50017c1d451667fd62a53ca/gistfile1.txt");
    List<CustomerLocation> customers = new CustomerLocationDataLoader().loadCustomerLocationDetails(customerData);

    ProximityCalculator calc = new ProximityCalculator(customers);
    List<CustomerLocation> invited = calc.calculateCustomersWithinRadius(100.0);

    System.out.println("Party Guest list (" + invited.size() + " customers)");
    System.out.println("-----------------------------------");

    invited.stream().forEach(customer -> {
      System.out.println("id: " + customer.getUserId() + ", name: " + customer.getName());
    });

  }
}

ProximityCalculator.java

package io.intercom.problems.proximity;

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

/**
 * <code>ProximityCalculator</code> determines the customers in a collection that are based within
 * a given radius of the Intercom Office.
 */
public class ProximityCalculator {

  private final List<CustomerLocation> customerLocations;

  public static final Coordinates IntercomOfficeDublin = new Coordinates(53.3381985, -6.2592576);

  /**
   * Creates a new ProximityCalculator with the given collection of customers
   *
   * @param customerLocations a List of customers whos proximity will be tested.
   */
  public ProximityCalculator(List<CustomerLocation> customerLocations) {
    if (customerLocations == null) {
      throw new IllegalArgumentException("Guest list calculator requires a valid list of customer locations");
    }
    this.customerLocations = customerLocations;
  }

  /**
   * Filter the loaded customer list for customers within the given distance radius. The resulting
   * filtered list is sorted by userId ascending.
   *
   * @param distance radius in kilometers within which customers have to be located to get included.
   * @return the list of customers that are based within the supplied radius of the office.
   */
  public List<CustomerLocation> calculateCustomersWithinRadius(Double distance) {

    return customerLocations.stream()
        .filter(customer -> customer.getCoordinates().distanceTo(IntercomOfficeDublin) <= distance)
        .sorted((customer1, customer2) -> customer1.getUserId() - customer2.getUserId())
        .collect(Collectors.toList());
  }

}

ProximityCalculatorTest.java

package io.intercom.problems.proximity;

import org.junit.Before;
import org.junit.Test;

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

import static io.intercom.problems.proximity.ProximityCalculator.IntercomOfficeDublin;
import static java.util.stream.IntStream.range;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

public class ProximityCalculatorTest {

  final double distanceInOneDegree = new Coordinates(0.0, 0.0).distanceTo(new Coordinates(1.0, 0.0));

  private List<CustomerLocation> customers;

  @Before
  public void createTestCustomerList() {

    // create customers each one degree further away from the office than the last
    customers = range(1, 6)
        .mapToObj(x -> new CustomerLocation(x, "Customer-" + x, IntercomOfficeDublin.getLatitude() + x, IntercomOfficeDublin.getLongitude()))
        .collect(Collectors.toList());
  }

  @Test(expected = IllegalArgumentException.class)
  public void shouldComplainAboutEmptyOrNullCustomerList(){
    new ProximityCalculator(null);
  }

  @Test
  public void shouldCorrectlyFilterCustomersByDistance() {

    ProximityCalculator sut = new ProximityCalculator(customers);

    // the 0.0001 added to the distance accounts for rounding errors
    assertEquals(0, sut.calculateCustomersWithinRadius(distanceInOneDegree * 0.0001).size());
    assertEquals(1, sut.calculateCustomersWithinRadius(distanceInOneDegree * 1.0001).size());
    assertEquals(2, sut.calculateCustomersWithinRadius(distanceInOneDegree * 2.0001).size());
    assertEquals(3, sut.calculateCustomersWithinRadius(distanceInOneDegree * 3.0001).size());
    assertEquals(4, sut.calculateCustomersWithinRadius(distanceInOneDegree * 4.0001).size());

  }

  @Test
  public void shouldReturnCustomersListWithUserIDAscending() {

    Collections.shuffle(customers);
    ProximityCalculator sut = new ProximityCalculator(customers);

    List<CustomerLocation> withinRadius = sut.calculateCustomersWithinRadius(distanceInOneDegree * 4.0001);
    assertEquals(4, withinRadius.size());

    // the id of each entry should be less than the subsequent one
    for (int x = 0; x < withinRadius.size() - 1; x++) {
      assertTrue(withinRadius.get(x).getUserId() < withinRadius.get(x + 1).getUserId());
    }

  }

}