summaryrefslogblamecommitdiffstats
path: root/DataStructure/BayesAll.java
blob: 27ab797c9aff35c707a14e70c7f64789d767e387 (plain) (tree)



























































































































































































































































































































































































                                                                                                        
package DataStructure;

import helper.ListBTS;

import java.util.ArrayList;
import java.util.Arrays;

public class BayesAll {
	GSMMap map;
	// ArrayList<SingleBTS> MR;
	ArrayList<ratioElem>[][] RatioMap;
	boolean[][] hasElement;

	/**
	 * @param args
	 */
	public static void main(String[] args) {

	}

	public BayesAll(Interpolator map) {
		this.map = map;
		hasElement = map.getAllocation();

		// Compute ALL Ratios for GSMmap
		RatioMap = computeMapRatio();

	}

	public BayesAll(GSMMap map) {
		this.map = map;
		hasElement = map.getAllocation();
		RatioMap = computeMapRatio();
	}

	public double[][] locate(ArrayList<SingleBTS> MR, double confidence) {

		SingleBTS[] content = ListBTS.content(MR);
		// check if MR only has one BTS inside!
		if (content == null || content.length <= 1) {
			// only one or zero BTS. mark all tiles where this BTS is received!
			// get BTS

			return markOneBTS(content);
		}

		// Compute ALL Ratios out of mobile phone's MR
		ArrayList<ratioElem> RSSVector = computeAllRatios(MR);

		// Compute scoremap
		double[][] scoremap = computeScoreMap(RSSVector);

		if (confidence >= 1)
			return scoremap;
		else
			return toConfidence(scoremap, confidence);
	}

	/**
	 * This returns the distribution if only one BTS is measured
	 * 
	 * @param singleBTS
	 * @return
	 */
	private double[][] markOneBTS(SingleBTS[] singleBTS) {
		int count = 0;
		double[][] scoremap = new double[map.Xcoords.length][map.Ycoords.length];

		if (singleBTS == null) {
			long numberOfTiles = map.countTilesWMeasures();
			for (int x = 0; x < map.Xcoords.length; x++) {
				for (int y = 0; y < map.Ycoords.length; y++) {
					if (hasElement[x][y]) {
						scoremap[x][y] = 1d / (double) numberOfTiles;
					}
				}
			}
		}

		// count tiles where this bts is measured
		for (int x = 0; x < map.Xcoords.length; x++) {
			for (int y = 0; y < map.Ycoords.length; y++) {
				if (ListBTS.contains(map.map[x][y], singleBTS[0])) {
					count++;
				}
			}
		}

		// give every tile a equal distributed possibility
		for (int x = 0; x < map.Xcoords.length; x++) {
			for (int y = 0; y < map.Ycoords.length; y++) {
				if (ListBTS.contains(map.map[x][y], singleBTS[0])) {
					scoremap[x][y] = 1d / (double) count;
				}
			}
		}

		return scoremap;
	}

	private double[][] computeScoreMap(ArrayList<ratioElem> RSSVector) {
		double[][] score = new double[map.Xcoords.length][map.Ycoords.length];
		// Compute possibility that this RSSVector was measured in RatioMap as
		// TODO: Thread!!!
		computeTotalProbability totalProbRunnable = new computeTotalProbability(
				RSSVector);
		Thread totalProbThread = new Thread(totalProbRunnable);
		totalProbThread.start();
		// double totalProbability = computeTotalProb(RSSVector);
		// now we have P(S) (=totalProb that RSSVector appears in map)
		double numberOfTiles = map.countTilesWMeasures();
		// compute Bayes with RSSVector
		for (int x = 0; x < RatioMap.length; x++) {
			for (int y = 0; y < RatioMap[0].length; y++) {
				if (hasElement[x][y]) {
					score[x][y] = (ProbabilityForRSSVector(RSSVector,
							RatioMap[x][y]) * (1 / numberOfTiles));
					// / totalProbability;
				}
			}
		}

		// division with total Probability
		try {
			totalProbThread.join();
			double totalProbability = totalProbRunnable.totalProbability;
			for (int x = 0; x < RatioMap.length; x++) {
				for (int y = 0; y < RatioMap[0].length; y++) {
					if (hasElement[x][y]) {
						score[x][y] = score[x][y] / totalProbability;
					}
				}

			}

		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		return score;
	}

	/**
	 * Computes Probability that this RSSVector is seen in the Map
	 * 
	 * @param RSSVector
	 * @return
	 */
	@SuppressWarnings("unused")
	private double computeTotalProb(ArrayList<ratioElem> RSSVector) {
		double totalProb = 0;
		// go through all valid Elements in RatioMap. Sum up the possibilities
		// for each tile
		for (int x = 0; x < RatioMap.length; x++) {
			for (int y = 0; y < RatioMap[0].length; y++) {
				if (hasElement[x][y])
					totalProb += ProbabilityForRSSVector(RSSVector,
							RatioMap[x][y]);
			}

			/*
			 * int y = 0; while (y < RatioMap[0].length) { possibilityThread
			 * threadable1 = new possibilityThread( RSSVector, x, y); Thread
			 * thread1 = new Thread(threadable1); if (hasElement[x][y])
			 * thread1.start(); y++; possibilityThread threadable2 = new
			 * possibilityThread( RSSVector, x, y); Thread thread2 = new
			 * Thread(threadable2); if (y < RatioMap[0].length &&
			 * hasElement[x][y]) thread2.start(); y++; try { thread1.join();
			 * thread2.join(); } catch (InterruptedException e) {
			 * e.printStackTrace(); } // Threads fertig.
			 * 
			 * }
			 */
		}

		double numberOfTiles = map.countTilesWMeasures();
		totalProb = totalProb / numberOfTiles;
		return totalProb;
	}

	private double ProbabilityForRSSVector(ArrayList<ratioElem> MRphone,
			ArrayList<ratioElem> MRmap) {

		double probability = 1;
		boolean thereWasAHit = false;
		for (int i = 0; i < MRphone.size(); i++) {
			// when there is no measurement from phone, go to next ratio element
			if (MRphone.get(i) != null) {
				if (MRmap.get(i) == null)
					return 0;
				probability *= MRphone.get(i).probability(MRmap.get(i));
				thereWasAHit = true;
			}

		}

		if (thereWasAHit)
			return probability;
		else
			return 0;
	}

	/**
	 * Creates Ratios out of map (all possible ratios!)
	 * 
	 * @return
	 */
	private ArrayList<ratioElem>[][] computeMapRatio() {
		ArrayList<ratioElem>[][] result = new ArrayList[map.Xcoords.length][map.Ycoords.length];

		// int size = sumOfRatio(map.content().length - 1);
		// result initilisieren und füllen
		for (int x = 0; x < map.Xcoords.length; x++) {
			for (int y = 0; y < map.Ycoords.length; y++) {
				if (hasElement[x][y]) {
					// result[x][y] = new ArrayList<ratioElem>(size);

					result[x][y] = (computeAllRatios(map.map[x][y]));
				}
			}
		}

		return result;
	}

	/**
	 * Returns all possible Ratios that can be built with GSM-Map's content out
	 * of MR. Not available Ratios get stored as null
	 * 
	 * @return
	 */
	private ArrayList<ratioElem> computeAllRatios(ArrayList<SingleBTS> MR) {
		SingleBTS[] content = map.content();
		ArrayList<ratioElem> result = new ArrayList<ratioElem>(
				sumOfRatio(content.length - 1));
		// get ratio between every BTS and the others
		for (int i = 0; i < content.length; i++) {
			for (int j = i + 1; j < content.length; j++) {
				SingleBTS top = ListBTS.getARFCN(MR, content[i]);
				SingleBTS bottom = ListBTS.getARFCN(MR, content[j]);
				if (top == null || bottom == null) {
					result.add(null);
				} else {
					result.add(new ratioElem(top, bottom));
				}
			}
		}

		return result;
	}

	/**
	 * Computes all Ratios that can be built out of MR
	 * 
	 * @param MR
	 * @return
	 */
	@SuppressWarnings("unused")
	private ArrayList<ratioElem> computeRatios(ArrayList<SingleBTS> MR) {
		ArrayList<ratioElem> result = new ArrayList<ratioElem>(
				sumOfRatio(MR.size() - 1));
		for (int i = 0; i < MR.size(); i++) {
			for (int j = i + 1; j < MR.size(); j++) {
				result.add(new ratioElem(MR.get(i), MR.get(j)));
			}
		}
		return result;
	}

	private static int sumOfRatio(int n) {
		return n == 0 ? 1 : n + sumOfRatio(n - 1);
	}

	public double[][] toConfidence(double[][] scoremap, double confidence) {
		if (confidence >= 1) {
			return scoremap;
		}

		// scoremap to possibility objects (faster...)
		PossibilityObject[] possibilities = toPossibility(scoremap);
		double sum_confidence = 0;
		double[][] result = new double[scoremap.length][scoremap[0].length];
		int boundary = possibilities.length - 1;
		while (sum_confidence < confidence) {
			// run from highest element to lowest.
			// as long as confidence is not reached: store current element in
			// result
			sum_confidence += possibilities[boundary].possibility;
			int x = possibilities[boundary].x;
			int y = possibilities[boundary].y;
			result[x][y] = possibilities[boundary].possibility;
			boundary--;
		}
		// result = PossObjToScoremap(possibilities, boundary, result);

		/*
		 * double max = 0; int xmax = 0; int ymax = 0; for (int x = 0; x <
		 * scoremap.length; x++) { for (int y = 0; y < scoremap[0].length; y++)
		 * { if (scoremap[x][y] > max) { max = scoremap[x][y]; xmax = x; ymax =
		 * y; }
		 * 
		 * } } // max found.
		 * 
		 * result[xmax][ymax] = scoremap[xmax][ymax]; sum_confidence +=
		 * scoremap[xmax][ymax]; scoremap[xmax][ymax] = 0; }
		 */
		return result;

	}

	/**
	 * Makes a scoremap to a SORTED one dimensional PossibilityObject Array.
	 * Calculates the entropy on the way and prints to Console
	 * 
	 * @param scoremap
	 * @return
	 */
	public PossibilityObject[] toPossibility(double[][] scoremap) {
		int gsmmapsize = (int) map.countTilesWMeasures();
		// PossibilityObject[] possibilities = new
		// PossibilityObject[gsmmapsize];
		ArrayList<PossibilityObject> result = new ArrayList<PossibilityObject>(
				gsmmapsize);
		double entropy = 0;
		for (int x = 0; x < scoremap.length; x++) {
			for (int y = 0; y < scoremap[0].length; y++) {
				if (hasElement[x][y] && scoremap[x][y] > 0) {
					entropy = entropy + scoremap[x][y]
							* ((Math.log(scoremap[x][y])) / Math.log(2));

					PossibilityObject current = new PossibilityObject();
					current.possibility = scoremap[x][y];
					current.x = x;
					current.y = y;
					result.add(current);
				}
			}

		}

		System.out.println("Entropy dieser Karte: " + (entropy * (-1))
				+ " max. Entropy: " + (Math.log(gsmmapsize) / Math.log(2)));
		PossibilityObject[] possibilities = result
				.toArray(new PossibilityObject[1]);
		Arrays.sort(possibilities);
		return possibilities;
	}

	class computeTotalProbability implements Runnable {
		private ArrayList<ratioElem> RSSVector;
		public double totalProbability;

		public computeTotalProbability(ArrayList<ratioElem> RSSVector) {
			this.RSSVector = RSSVector;
		}

		@Override
		public void run() {
			double totalProb = 0;
			// go through all valid Elements in RatioMap. Sum up the
			// possibilities
			// for each tile
			for (int x = 0; x < RatioMap.length; x++) {
				for (int y = 0; y < RatioMap[0].length; y++) {
					if (hasElement[x][y])
						totalProb += ProbabilityForRSSVector(RSSVector,
								RatioMap[x][y]);
				}

			}

			double numberOfTiles = map.countTilesWMeasures();
			totalProb = totalProb / numberOfTiles;
			totalProbability = totalProb;
		}

	}

}