package helper; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import DataStructure.GPScoordinate; public class ListGPS { /** * Get the intersection between both lists. That is, if one coordinate is in * both lists. add this coordinate to the returning set. * * @param list1 * @param list2 * @param threshold_dB * when both coordinates are less than threshold_dB meters away, * they count as identical. Threshold may be 0. Then only * identical coordinates get used * @return */ public static LinkedList intersect( LinkedList list1, LinkedList list2, int threshold) { LinkedList result = new LinkedList(); if (list1 == null || list2 == null) return result; if (threshold == 0) { for (GPScoordinate element1 : list1) { if ((contains(list2, element1)) && !contains(result, element1)) { result.add(element1); } } return result; } else { for (GPScoordinate element1 : list1) { result.addAll(getSimilarValues(list2, element1, threshold)); } // remove null elements result = removeNullElements(result); // remove duplicate entries GPScoordinate[] resultarray = content(result); // clear result to reuse it result = new LinkedList(); if (resultarray == null) return null; for (int i = 0; i < resultarray.length; i++) { result.add(resultarray[i]); } return result; } } /** * * @param list * where to search * @param point * get elements near to that point * @param threshold_dB * how far in meters may elements be away from the point * @return LinkedList of elements near point. Every element is only added * once */ public static LinkedList getSimilarValues( LinkedList list, GPScoordinate point, int threshold) { if (list == null || list.isEmpty() || point == null) return new LinkedList(); LinkedList result = new LinkedList(); for (GPScoordinate element : list) { if (Distance.calc(point, element) * 1000 < threshold && !contains(result, element)) { result.add(element); } } return null; } public static LinkedList intersect( LinkedList> nestedlist) { LinkedList result = new LinkedList(); if (nestedlist.isEmpty()) return null; if (nestedlist.size() == 1) return nestedlist.getFirst(); // nestedlist has at least 2 elements. do intersect with both. Store in // list. remove null elements first nestedlist.add(removeNullElements(nestedlist.removeLast())); nestedlist.addFirst(removeNullElements(nestedlist.removeFirst())); result.addAll(intersect(nestedlist.removeFirst(), nestedlist.removeLast(), 0)); // now do intersect with the rest. This could get a speedup by using // pairwise intersection. would be O(log n) then. while (!nestedlist.isEmpty()) { nestedlist.addFirst(removeNullElements(nestedlist.removeFirst())); result = intersect(result, nestedlist.removeFirst(), 0); } return result; } public static GPScoordinate[] content(List list) { // get clone. Not just reference/pointer if (list == null || list.isEmpty()) return null; ArrayList list2 = new ArrayList(list); // int count = 0; LinkedList output = new LinkedList(); while (!list2.isEmpty()) { GPScoordinate gps = list2.get(0); list2.remove(0); output.add(gps); // remove the just added bts from the GPS-list for (int i = 0; i < list2.size(); i++) { if (list2.get(i).equals(gps)) { // remove every element in the list that is the same as the // first list2.remove(i); // WARNING: this is slow! Do it with list // and iterator i--; } } } return output.toArray(new GPScoordinate[1]); } /** * true if list contains element (that is, coord1 and coord2 are identical) * * @param list * @param element * @return */ public static boolean contains(LinkedList list, GPScoordinate element) { if (element == null || list == null || list.isEmpty()) return false; for (GPScoordinate current : list) { if (current.equals(element)) return true; } return false; } /** * Takes a list. Returns a copy of that list without null-elements * * @param list * ListBTS where all elements with null will be filtered out * @return a copy of this list without null-elements. Null if the whole list * is null */ public static LinkedList removeNullElements( LinkedList list) { if (list == null) return null; LinkedList list2 = new LinkedList(); boolean element_present = false; for (GPScoordinate element : list) { if (element != null) { element_present = true; list2.add(element); } } if (element_present) return list2; else return null; } public static LinkedList> removeAllNullElements( LinkedList> nestedlist) { LinkedList> result = new LinkedList>(); java.util.Iterator> itr = result.iterator(); while (itr.hasNext()) { LinkedList intermediate = itr.next(); intermediate = removeNullElements(intermediate); if (intermediate != null && !intermediate.isEmpty()) result.add(intermediate); } return result; } }