I wanted to post this on SO, but it says my account I’m not allowed to post questions there anymore due to probably less than good questions I posted in the past. I realise this site is for reviews of working code, but my code does work, I just need to know how to finish it.
I have a program that takes in 3 arguments: width, height and a csv file. The CSV file has 3 fields: id, name and date.
The width and height are used to build a grid containing width*height
number of cells (or as they’re called in the example, Geos). I then populate the grid with the data from the CSV, where each row is one object, it’s cell id on the grid is the id from the csv. My goal is to find the biggest grouping of occupied cells in the grid. For example, given a grid of 4*5 shown below:
+----+----+----+----+ | 16 | 17 | 18 | 19 | +----+----+----+----+ | 12 | 13 | 14 | 15 | +----+----+----+----+ | 8 | 9 | 10 | 11 | +----+----+----+----+ | 4 | 5 | 6 | 7 | +----+----+----+----+ | 0 | 1 | 2 | 3 | +----+----+----+----+
If cells 1, 2, 3, 5, 7, 8, 12, 13 and 19 are populated (i.e. the csv contains those ids), then there are three blocks 5,1,2,3,7
, 8,12,13
and 19
. In this case, the first block is the largest.
Right now, I have working code that has a list containing Geo
objects and their point/coordinate on the grid. And for each Geo
object I also have each one of its neighbours on the grid. I’m stuck now trying to figure out exactly how to consolidate all this information, to determine the biggest grouping.
Can anyone offer me advice on this? Also, as a review, my code is supposed to run in under 1s given a 10000*10000 grid that is fully populated with 99999999 objects. Right now it doesn’t, and I was going to refactor it once I had this part finished. But if anyone knows a way I could speed up the program, please let me know too!
Also the way I execute the program is by compiling it into a jar and running it via the command line, passing it in the arguments, just in case you can’t replicate it.
Code below:
Geo.java
import java.awt.Point; import java.util.ArrayList; import java.util.List; public class Geo { private Integer id; private String name; private String date; private Point coordinate; private List<Geo> neighboursList = new ArrayList<Geo>(); public Geo (String id, String name, String date) { this.id = Integer.parseInt(id); this.name = name; this.date = date; this.coordinate = new Point(); } public Integer getId() { return id; } public String getName() { return name; } public String getDate() { return date; } public void setCoordinates(int x, int y) { coordinate.setLocation(x, y); } public Point getCoordinates() { return coordinate; } public String toString() { return "" + id + ", " + name + ", " + date; } public void populateNeighbourList(Geo g) { neighboursList.add(g); } public List<Geo> getNeighbours() { return neighboursList; } }
GeoBlock.java
import java.awt.Point; import java.io.BufferedReader; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; public class GeoBlock { private static BufferedReader br = null; private static String line = ""; private static String cvsSplitBy = ","; private static List<Geo> geoList; private static String file; private static int height; private static int width; private static HashSet<Point> coordList; private static File f; private static Point extraPoint; private GeoBlock() { geoList = new ArrayList<Geo>(); coordList = new HashSet<Point>(); extraPoint = new Point(0,0); } public static void main(String[] args) { long startTime = System.currentTimeMillis(); GeoBlock gb = new GeoBlock(); width = Integer.parseInt(args[0]); height = Integer.parseInt(args[1]); file = args[2]; gb.readCSVFile(file); gb.populateGeoCoordinates(); gb.determineGeoNeighbours(); gb.printNeighbours(); long endTime = System.currentTimeMillis(); System.out.println("Execution time: " + (endTime - startTime) + " ms"); } /** * Takes in a CSV and stores creates new geo objects for each row Stores * these objects in an arraylist. * If the file does not exist or there is missing data in the csv, it will * display the error and end the program * * @param csvFile */ private void readCSVFile(String csvFile) { try { f = new File(csvFile); if(!f.exists() || f.isDirectory()) { throw new FileNotFoundException(); } br = new BufferedReader(new FileReader(f)); int csvLine = 0; while ((line = br.readLine()) != null) { csvLine++; String[] geoData = line.split(cvsSplitBy); //Handle for empty csv cells for(int i = 0; i < geoData.length; i++) { if (geoData[i].isEmpty() || geoData.length > 3) { System.out.println("There is missing data in the csv file at line: " + csvLine); throw new IOException(); } } geoList.add(new Geo(geoData[0], geoData[1], geoData[2])); } } catch (FileNotFoundException fnfe) { System.out.println("The file : " + f.getName() + " does not exist" ); fnfe.printStackTrace(); System.exit(0); } catch (IOException ioe) { ioe.printStackTrace(); System.exit(0); } } /** * Populates the geo objects list with their coordinates on the grid */ private void populateGeoCoordinates() { // Using the geo id, calculate its point on the grid for (int i = height - 1; i >= 0; i--) { int blockId = (i * width); for (int j = 0; j < width; j++) { for (Geo geo : geoList) { if (blockId == geo.getId().intValue()) { geo.setCoordinates(i,j); } } blockId++; } } removeExtraGeos(); } /** * Determines each Geo the list's neighbour */ private void determineGeoNeighbours() { for (Geo geo : geoList) { coordList.add(geo.getCoordinates()); } for (Geo geo : geoList) { addNeighboursToGeo(geo); } } /** * Used to track what neighbours each Geo has * @param geo */ private void addNeighboursToGeo(Geo geo) { int x = geo.getCoordinates().x; int y = geo.getCoordinates().y; Point[] tempArray = { new Point(x, y+1), new Point(x-1, y), new Point(x+1, y), new Point(x, y-1) }; for (Point p : tempArray) { if (coordList.contains(p)) { Geo g = getGeoByCoordinates(p); if(g != null) { geo.populateNeighbourList(g);; } } } } /** * returns a geo object based on its point (coordinates in the grid) * @param p * @return */ private Geo getGeoByCoordinates(Point p) { for(Geo geo : geoList) { if(geo.getCoordinates().equals(p)) { return geo; } } return null; } /** * Removes all geos from the geo objects list who have coordinates of 0,0 unless * it has position 0 (i.e. the first geoBlock). * This is needed because if the csv has more data than space on the GeoBlock, * the extra geos are assigned 0,0 by default */ private void removeExtraGeos() { List<Geo> found = new ArrayList<Geo>(); for (Geo geo : geoList) { if(geo.getId() != 0 && geo.getCoordinates().equals(extraPoint)) { found.add(geo); } } geoList.removeAll(found); } /** * Prints all the neighbours of a Geo */ private void printNeighbours() { for (Geo geo : geoList) { System.out.println("Geo " + geo.getId() + " has the following neighbours: "); for(Geo g : geo.getNeighbours()) { System.out.println(g.getId()); } }
} }