summaryrefslogblamecommitdiffstats
path: root/helper/ListGPS.java
blob: 79b383aab922f1578cf9ce722cf0835f2923d3ca (plain) (tree)






























































































































































































                                                                                                           
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<GPScoordinate> intersect(
			LinkedList<GPScoordinate> list1, LinkedList<GPScoordinate> list2,
			int threshold) {
		LinkedList<GPScoordinate> result = new LinkedList<GPScoordinate>();
		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<GPScoordinate>();
			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<GPScoordinate> getSimilarValues(
			LinkedList<GPScoordinate> list, GPScoordinate point, int threshold) {
		if (list == null || list.isEmpty() || point == null)
			return new LinkedList<GPScoordinate>();
		LinkedList<GPScoordinate> result = new LinkedList<GPScoordinate>();
		for (GPScoordinate element : list) {
			if (Distance.calc(point, element) * 1000 < threshold
					&& !contains(result, element)) {
				result.add(element);

			}
		}

		return null;

	}

	public static LinkedList<GPScoordinate> intersect(
			LinkedList<LinkedList<GPScoordinate>> nestedlist) {
		LinkedList<GPScoordinate> result = new LinkedList<GPScoordinate>();
		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<GPScoordinate> list) {
		// get clone. Not just reference/pointer
		if (list == null || list.isEmpty())
			return null;
		ArrayList<GPScoordinate> list2 = new ArrayList<GPScoordinate>(list);
		// int count = 0;
		LinkedList<GPScoordinate> output = new LinkedList<GPScoordinate>();
		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<GPScoordinate> 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<GPScoordinate> removeNullElements(
			LinkedList<GPScoordinate> list) {
		if (list == null)
			return null;
		LinkedList<GPScoordinate> list2 = new LinkedList<GPScoordinate>();
		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<LinkedList<GPScoordinate>> removeAllNullElements(
			LinkedList<LinkedList<GPScoordinate>> nestedlist) {
		LinkedList<LinkedList<GPScoordinate>> result = new LinkedList<LinkedList<GPScoordinate>>();
		java.util.Iterator<LinkedList<GPScoordinate>> itr = result.iterator();
		while (itr.hasNext()) {
			LinkedList<GPScoordinate> intermediate = itr.next();
			intermediate = removeNullElements(intermediate);
			if (intermediate != null && !intermediate.isEmpty())
				result.add(intermediate);
		}
		return result;
	}

}