Home :: Blogs :: gsolano's blog

Iterating Complex Map Structures

Submitted by gsolano on 10 December, 2009 - 16:24

Have you ever encountered yourself with nested data structures mixed with generics syntax? Even worse, have you or have you been creating this confuse statements in your code?

Let me show you an example of what I mean and what I had found in some interactions with colleague's programming code.

In our example application we need to store and show the enrollment data for a university quatrimester. The data is structured in a hierarchical fashion where we have as first node the year, then the quatrimesters, the courses and at the bottom the students enlisted in those courses.

Year
++ Quatrimester
+++ Course
++++ Student

Seems like we could sit down with some paper and a pencil to start drawing some nice class diagrams, well let me show you what can happen when someone wants to skip some designing time:

  1. //
  2. Map<Integer, Map<Integer, Map<String, List<Student>>>> studentsByQuarter = new HashMap<Integer, Map<Integer, Map<String, List<Student>>>>();
  3. //

Why bother our application adding more files to represent new classes when you can have it all in one line? That is the implicit approach when someone decides to create this level of complexity, that for him could be understandable but poor of the guy that needs to maintain that later.

I'm going to develop more the code taking this approach to show the increasing complexity we get by not isolating the distinct components of the problem we want to solve.

The Student class is pretty much simple with just the fullName attribute:

  1. public class Student {
  2. 	private String fullName;
  3.  
  4. 	public Student(String fullName) {
  5. 		this.fullName = fullName;
  6. 	}
  7.  
  8. 	public String getFullName() {
  9. 		return fullName;
  10. 	}
  11.  
  12. 	public void setFullName(String fullName) {
  13. 		this.fullName = fullName;
  14. 	}
  15. }

Now we add an "EnrollmentProcessVr1" class with the already presented scary variable and two methods:

+ public static void startEnrollment(int year, int quarter){...} // To fill our enrollment data.
+ public static void showEnrollment() {...} // Show the data contained in the data structure.

Let's see the complex of the code to add/show data from this structure:

  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.Iterator;
  4. import java.util.List;
  5. import java.util.Map;
  6.  
  7. public class EnrollmentProcessVr1 {
  8. 	private static Map<Integer, Map<Integer, Map<String, List<Student>>>> studentsByQuarter =
  9. 		new HashMap<Integer, Map<Integer, Map<String, List<Student>>>>();
  10.  
  11. 	public static void startEnrollment(int year, int quarter) {
  12. 		// Create a Year.
  13. 		Integer currentYear = new Integer(year);
  14.  
  15. 		// Create a quatrimester.
  16. 		Integer quatrimester = new Integer(quarter);
  17.  
  18. 		// Create courses.
  19. 		String course1 = "Discrete Maths";
  20. 		String course2 = "Programming I";
  21.  
  22. 		// Create List of Students.
  23. 		List<Student> students = new ArrayList<Student>();
  24. 		students.add(new Student("Cristobal Colón"));
  25. 		students.add(new Student("Juan SantaMaría"));
  26.  
  27. 		// Create a Map of Courses/Students.
  28. 		Map <String, List<Student>> studentsByCourses = new HashMap<String, List<Student>>();
  29.  
  30. 		// Add Students to courses.
  31. 		studentsByCourses.put(course1, students);
  32. 		studentsByCourses.put(course2, students);
  33.  
  34. 		// Create a Map of Quarter/Courses.
  35. 		Map<Integer, Map <String, List<Student>>> coursesQuarterMap =
  36. 			new HashMap<Integer, Map<String,List<Student>>>();
  37.  
  38. 		coursesQuarterMap.put(quatrimester, studentsByCourses);
  39.  
  40. 		// Add quarter to year.
  41. 		studentsByQuarter.put(currentYear, coursesQuarterMap);
  42. 	}
  43.  
  44. 	public static void showEnrollment() {
  45. 		Iterator studentsByQuarterIterator = studentsByQuarter.entrySet().iterator();
  46. 		while (studentsByQuarterIterator.hasNext()) {
  47. 			Map.Entry studentsByQuarterPairs = (Map.Entry)studentsByQuarterIterator.next();
  48. 			System.out.println("Year: " + String.valueOf(studentsByQuarterPairs.getKey()));
  49.  
  50. 			Map<Integer, Map<String, List<Student>>> quarterCoursesMap =
  51. 					(Map<Integer, Map<String, List<Student>>>) studentsByQuarterPairs.getValue();
  52.  
  53. 			Iterator quarterCoursesIterator = quarterCoursesMap.entrySet().iterator();
  54.  
  55. 			while (quarterCoursesIterator.hasNext()) {
  56. 				Map.Entry coursesByQuarterPairs = (Map.Entry)quarterCoursesIterator.next();
  57. 				System.out.println("\tQuarter: " + String.valueOf(coursesByQuarterPairs.getKey()));
  58.  
  59. 				Map<String, List<Student>> coursesStudentsMap =
  60. 					(Map<String, List<Student>>) coursesByQuarterPairs.getValue();
  61.  
  62. 				Iterator coursesStudentsIterator = coursesStudentsMap.entrySet().iterator();
  63.  
  64. 				while (coursesStudentsIterator.hasNext()) {
  65. 					Map.Entry coursesStudentsPairs = (Map.Entry)coursesStudentsIterator.next();
  66. 					System.out.println("\t\tCourse: " + String.valueOf(coursesStudentsPairs.getKey()));
  67.  
  68. 					List<Student> studentsByCourse = (List<Student>) coursesStudentsPairs.getValue();
  69.  
  70. 					for(Student student : studentsByCourse) {
  71. 						System.out.println("\t\t\tStudent: "  + student.getFullName());
  72. 					}
  73. 				}
  74. 			}
  75. 		}
  76. 	}
  77.  
  78. 	public static void main(String[] args) {
  79. 		EnrollmentProcessVr1.startEnrollment(2009, 3);
  80. 		EnrollmentProcessVr1.showEnrollment();
  81. 	}
  82. }

Output from main method:

My focus in this post will be how to solve the intrinsic complexity of iterating map structures, not necessary the refactoring of bad designed data structures, but this will help to demonstrate that even well designed classes can have some problems it they have internal map structures. Having said that let's create some classes:

EnrollmentTrackVr1:

  1. import java.util.LinkedHashMap;
  2. import java.util.Map;
  3.  
  4. public class EnrollmentTrackVr1 {
  5. 	private  Map<Integer, QuatrimestersVr1> quatrimesters;
  6.  
  7. 	public EnrollmentTrackVr1() {
  8. 		quatrimesters = new LinkedHashMap<Integer, QuatrimestersVr1>();
  9. 	}
  10.  
  11. 	public Map<Integer, QuatrimestersVr1> getQuatrimesters() {
  12. 		return quatrimesters;
  13. 	}
  14.  
  15.  
  16. 	public void addStudent(Student student, int year, int quatrimesterNumber, String courseName) {
  17. 		if (!quatrimesters.containsKey(year)) {
  18. 			quatrimesters.put(year, new QuatrimestersVr1());
  19. 		}
  20. 		quatrimesters.get(year).addCourse(quatrimesterNumber, courseName, student);
  21. 	}
  22. }

QuatrimestersVr1:

  1. import java.util.HashMap;
  2. import java.util.Map;
  3.  
  4. public class QuatrimestersVr1 {
  5.  
  6. 	private Map<Integer, CoursesVr1> courses;
  7.  
  8. 	public QuatrimestersVr1() {
  9. 		courses = new HashMap<Integer, CoursesVr1>();
  10. 	}
  11.  
  12. 	public void addCourse(int quatrimesterNumber, String courseName, Student student) {
  13. 		if (!courses.containsKey(quatrimesterNumber)) {
  14. 			courses.put(quatrimesterNumber, new CoursesVr1());
  15. 		}
  16. 		courses.get(quatrimesterNumber).addStudent(courseName, student);
  17. 	}
  18.  
  19. 	public Map<Integer, CoursesVr1> getCourses() {
  20. 		return courses;
  21. 	}
  22. }

CoursesVr1:

  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.List;
  4. import java.util.Map;
  5.  
  6.  
  7. public class CoursesVr1 {
  8. 	private Map<String, List<Student>> students;
  9.  
  10. 	public CoursesVr1() {
  11. 		students = new HashMap<String, List<Student>>();
  12. 	}
  13.  
  14. 	public void addStudent(String courseName, Student student) {
  15. 		if (!students.containsKey(courseName)) {
  16. 			students.put(courseName, new ArrayList<Student>());
  17. 		}
  18. 		students.get(courseName).add(student);
  19. 	}
  20.  
  21. 	public Map<String, List<Student>> getStudents() {
  22. 		return students;
  23. 	}
  24.  
  25. }

The new classes simplify the code to add data but as we can see the iteration logic still remains a pain, we still have to use the iterator of the internal map structures of every single class:

  1. import java.util.Iterator;
  2. import java.util.List;
  3. import java.util.Map;
  4.  
  5.  
  6. public class EnrollmentProcessVr2 {
  7. 	private static EnrollmentTrackVr1 enrollmentTrackVr1;
  8.  
  9. 	public static void startEnrollment(int year, int quarter) {
  10.  
  11. 		String course1 = "Discrete Maths";
  12. 		String course2 = "Programming I";
  13. 		Student student1 =  new Student("Cristobal Colón");
  14. 		Student student2 =  new Student("Juan Santamaría");
  15.  
  16. 		enrollmentTrackVr1 = new EnrollmentTrackVr1();
  17. 		enrollmentTrackVr1.addStudent(student1, year, quarter, course1);
  18. 		enrollmentTrackVr1.addStudent(student2, year, quarter, course1);
  19. 		enrollmentTrackVr1.addStudent(student1, year, quarter, course2);
  20. 		enrollmentTrackVr1.addStudent(student2, year, quarter, course2);
  21.  
  22. 	}
  23.  
  24. 	public static void showEnrollment() {
  25. 		Iterator enrollmentIterator =
  26. 			enrollmentTrackVr1.getQuatrimesters().entrySet().iterator();
  27.  
  28. 		while (enrollmentIterator.hasNext()) {
  29. 			Map.Entry enrollmentPairs = (Map.Entry)enrollmentIterator.next();
  30. 			System.out.println("Year: " + String.valueOf(enrollmentPairs.getKey()));
  31.  
  32. 			QuatrimestersVr1 quatrimesters  =
  33. 					(QuatrimestersVr1) enrollmentPairs.getValue();
  34.  
  35. 			Iterator quatrimestersIterator =
  36. 				quatrimesters.getCourses().entrySet().iterator();
  37.  
  38. 			while (quatrimestersIterator.hasNext()) {
  39. 				Map.Entry quatrimestersPairs = (Map.Entry)quatrimestersIterator.next();
  40. 				System.out.println("\tQuarter: " + String.valueOf(quatrimestersPairs.getKey()));
  41.  
  42. 				CoursesVr1 courses = (CoursesVr1) quatrimestersPairs.getValue();
  43.  
  44. 				Iterator coursesIterator =
  45. 						courses.getStudents().entrySet().iterator();
  46.  
  47. 				while (coursesIterator.hasNext()) {
  48. 					Map.Entry coursesPairs = (Map.Entry)coursesIterator.next();
  49. 					System.out.println("\t\tCourse: " + String.valueOf(coursesPairs.getKey()));
  50.  
  51. 					List<Student> studentsByCourse = (List<Student>) coursesPairs.getValue();
  52.  
  53. 					for(Student student : studentsByCourse) {
  54. 						System.out.println("\t\t\tStudent: "  + student.getFullName());
  55. 					}
  56. 				}
  57. 			}
  58. 		}
  59. 	}
  60.  
  61. 	public static void main(String[] args) {
  62. 		EnrollmentProcessVr2.startEnrollment(2009, 3);
  63. 		EnrollmentProcessVr2.showEnrollment();
  64. 	}
  65. }

Wouldn't be nice if we could iterate our classes in the same way we do with any list from java collections?

  1. List<String> fooList = new ArrayList<String>();
  2. ...
  3. for (String fooObject : fooList) {
  4. 	System.out.println(fooObject);
  5. }

It is possible to do that if we learn how to use the Iterable & Iterator interfaces. In the following design I use my own interface which extends from these two and additional, a new method that will be helpful to return the key of the object that is being iterated in the loop (I will explain it more).

This is how the new design looks:

My custom interface receives a new generic element "K" that will be the type/class of the map's key.

  1. import java.util.Iterator;
  2.  
  3. public abstract interface MapIterable<K, V> extends Iterable<V>, Iterator<V>{
  4. 	public K currentKey();
  5. }

Let's implement the new interface and explain further which methods we need to implement for our classes to be iterable:

+ public boolean hasNext() : this method indicates if the class can advance more in the structure. In my implementation I added a private variable (currentKeyYearIndex)
to keep record of the current array's index. This variable is incremented with the next() method.

+ public V next(): returns the next object of the iteration. In my implementation I get the keyset from the internal map and then I convert it to an array to get the element
from the current index location.

+ public void remove(): removes the current object. Here I didn't want to bother too much and I just throw an UnsupportedOperationException;

+ public Iterator iterator(): gets the iterator. Simply return the class.

+ public K currentKey(): my added method to get the current key of the iteration.

EnrollmentTrackVr2:

  1. import java.util.Iterator;
  2. import java.util.LinkedHashMap;
  3. import java.util.Map;
  4.  
  5. public class EnrollmentTrackVr2	implements MapIterable<Integer, QuatrimestersVr2> {
  6.  
  7. 	private  Map<Integer, QuatrimestersVr2> quatrimesters;
  8. 	private int currentKeyYearIndex;
  9.  
  10. 	public EnrollmentTrackVr2() {
  11. 		quatrimesters = new LinkedHashMap<Integer, QuatrimestersVr2>();
  12. 		currentKeyYearIndex = 0;
  13. 	}
  14.  
  15. 	public Map<Integer, QuatrimestersVr2> getQuatrimesters() {
  16. 		return quatrimesters;
  17. 	}
  18.  
  19.  
  20. 	public void addStudent(Student student, int year, int quatrimesterNumber, String courseName) {
  21. 		if (!quatrimesters.containsKey(year)) {
  22. 			quatrimesters.put(year, new QuatrimestersVr2());
  23. 		}
  24. 		quatrimesters.get(year).addCourse(quatrimesterNumber, courseName, student);
  25. 	}
  26.  
  27. 	public boolean hasNext() {
  28. 		if (quatrimesters.keySet().toArray().length > currentKeyYearIndex) {
  29. 			return true;
  30. 		}
  31. 		return false;
  32. 	}
  33.  
  34. 	public QuatrimestersVr2 next() {
  35. 		int currentKeyYear = (Integer)
  36. 			quatrimesters.keySet().toArray()[currentKeyYearIndex++];
  37. 		return quatrimesters.get(currentKeyYear);
  38. 	}
  39.  
  40. 	public void remove() {
  42. 	}
  43.  
  44. 	public Iterator<QuatrimestersVr2> iterator() {
  45. 		return this;
  46. 	}
  47. 	public Integer currentKey() {
  48. 		return (Integer)
  49. 			quatrimesters.keySet().toArray()[currentKeyYearIndex-1];
  50. 	}
  51. }

QuatrimestersVr2:

  1. import java.util.HashMap;
  2. import java.util.Iterator;
  3. import java.util.Map;
  4.  
  5. public class QuatrimestersVr2 implements MapIterable<Integer, CoursesVr2> {
  6.  
  7. 	private Map<Integer, CoursesVr2> courses;
  8. 	private int currentQuatriIndex;
  9. 	private int year;
  10.  
  11. 	public QuatrimestersVr2() {
  12. 		courses = new HashMap<Integer, CoursesVr2>();
  13. 		currentQuatriIndex = 0;
  14. 	}
  15.  
  16. 	public QuatrimestersVr2(int year) {
  17. 		this();
  18. 		this.year = year;
  19. 	}
  20.  
  21. 	public void addCourse(int quatrimesterNumber, String courseName, Student student) {
  22. 		if (!courses.containsKey(quatrimesterNumber)) {
  23. 			courses.put(quatrimesterNumber, new CoursesVr2());
  24. 		}
  25. 		courses.get(quatrimesterNumber).addStudent(courseName, student);
  26. 	}
  27.  
  28. 	public Map<Integer, CoursesVr2> getCourses() {
  29. 		return courses;
  30. 	}
  31.  
  32. 	public boolean hasNext() {
  33. 		if (courses.keySet().toArray().length > currentQuatriIndex) {
  34. 			return true;
  35. 		}
  36. 		return false;
  37. 	}
  38.  
  39. 	public CoursesVr2 next() {
  40. 		int currentQuatri = (Integer)
  41. 			courses.keySet().toArray()[currentQuatriIndex++];
  42. 		return courses.get(currentQuatri);
  43. 	}
  44.  
  45. 	public void remove() {
  47. 	}
  48.  
  49. 	public Iterator<CoursesVr2> iterator() {
  50. 		return this;
  51. 	}
  52.  
  53. 	public int getYear() {
  54. 		return year;
  55. 	}
  56.  
  57. 	public void setYear(int year) {
  58. 		this.year = year;
  59. 	}
  60.  
  61. 	public Integer currentKey() {
  62. 		return (Integer)
  63. 			courses.keySet().toArray()[currentQuatriIndex-1];
  64. 	}
  65. }

CoursesVr2:

  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.Iterator;
  4. import java.util.List;
  5. import java.util.Map;
  6.  
  7. public class CoursesVr2 implements MapIterable<String, List<Student>> {
  8.  
  9. 	private Map<String, List<Student>> students;
  10. 	private int currentCourseIndex;
  11. 	private int quatrimester;
  12.  
  13. 	public CoursesVr2() {
  14. 		students = new HashMap<String, List<Student>>();
  15. 		currentCourseIndex = 0;
  16. 	}
  17.  
  18. 	public CoursesVr2(int quatrimester) {
  19. 		this();
  20. 		this.quatrimester = quatrimester;
  21. 	}
  22.  
  23. 	public void addStudent(String courseName, Student student) {
  24. 		if (!students.containsKey(courseName)) {
  25. 			students.put(courseName, new ArrayList<Student>());
  26. 		}
  27. 		students.get(courseName).add(student);
  28. 	}
  29.  
  30. 	public Map<String, List<Student>> getStudents() {
  31. 		return students;
  32. 	}
  33.  
  34. 	public boolean hasNext() {
  35. 		if (students.keySet().toArray().length > currentCourseIndex) {
  36. 			return true;
  37. 		}
  38. 		return false;
  39. 	}
  40.  
  41. 	public List<Student> next() {
  42. 		String currentCourse =
  43. 			students.keySet().toArray()[currentCourseIndex++].toString();
  44. 		return students.get(currentCourse);
  45. 	}
  46.  
  47. 	public void remove() {
  49. 	}
  50.  
  51. 	public Iterator<List<Student>> iterator() {
  52. 		return this;
  53. 	}
  54.  
  55. 	public int getQuatrimester() {
  56. 		return quatrimester;
  57. 	}
  58.  
  59. 	public void setQuatrimester(int quatrimester) {
  60. 		this.quatrimester = quatrimester;
  61. 	}
  62.  
  63. 	public String currentKey() {
  64. 		return students.
  65. 				keySet().toArray()[currentCourseIndex-1].toString();
  66. 	}
  67. }

Finally let's see how it ends up the iteration process:

EnrollmentProcessVr3:

  1. import java.util.List;
  2.  
  3. public class EnrollmentProcessVr3 {
  4. 	private static EnrollmentTrackVr2 enrollmentTrackVr2;
  5.  
  6. 	public static void startEnrollment(int year, int quarter) {
  7.  
  8. 		String course1 = "Discrete Maths";
  9. 		String course2 = "Programming I";
  10. 		Student student1 =  new Student("Cristobal Colón");
  11. 		Student student2 =  new Student("Juan Santamaría");
  12.  
  13. 		enrollmentTrackVr2 = new EnrollmentTrackVr2();
  14.  
  15. 		enrollmentTrackVr2.addStudent(student1, year, quarter, course1);
  16. 		enrollmentTrackVr2.addStudent(student2, year, quarter, course1);
  17.  
  18. 		enrollmentTrackVr2.addStudent(student1, year, quarter, course2);
  19. 		enrollmentTrackVr2.addStudent(student2, year, quarter, course2);
  20.  
  21. 	}
  22.  
  23. 	public static void showEnrollment() {
  24. 		for(QuatrimestersVr2 quatrimesters : enrollmentTrackVr2) {
  25. 			System.out.println("Year: " + enrollmentTrackVr2.currentKey());
  26. 			for (CoursesVr2 courses : quatrimesters) {
  27. 				System.out.println("\tQuatrimester: " + quatrimesters.currentKey());
  28. 				for (List<Student> students : courses) {
  29. 					System.out.println("\t\tCourses: " + courses.currentKey());
  30. 					for (Student student : students) {
  31. 						System.out.println("\t\t\tStudent: " + student.getFullName());
  32. 					}
  33. 				}
  34. 			}
  35. 		}
  36. 	}
  37.  
  38. 	public static void main(String[] args) {
  39. 		EnrollmentProcessVr3.startEnrollment(2009, 3);
  40. 		EnrollmentProcessVr3.showEnrollment();
  41. 	}
  42. }

The code may have some bugs, I think I forgot to reset the current key at some point, but this was done only to demostrate the power of using the Iterable interface.
I may be reinventing the wheel or doing more complex than it is so you are invited to give me any suggestions you have. Thanks!

- Gabriel Solano