1/*
2 * Copyright (C) 2012 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16package android.bordeaux.services;
17import android.location.Location;
18import android.text.format.Time;
19import android.util.Log;
20
21import java.lang.Math;
22import java.util.ArrayList;
23import java.util.HashMap;
24import java.util.Map;
25
26public class BaseCluster {
27
28    public static String TAG = "BaseCluster";
29
30    public double[] mCenter;
31  // protected double[] mCenter;
32
33    protected static final int VECTOR_LENGTH = 3;
34
35    private static final long FORGETTING_ENUMERATOR = 95;
36    private static final long FORGETTING_DENOMINATOR = 100;
37
38    // Histogram illustrates the pattern of visit during time of day,
39    protected HashMap<String, Long> mHistogram = new HashMap<String, Long>();
40
41    protected long mDuration;
42
43    protected String mSemanticId;
44
45    protected static final double EARTH_RADIUS = 6378100f;
46
47    public BaseCluster(Location location) {
48        mCenter = getLocationVector(location);
49        mDuration = 0;
50    }
51
52    public BaseCluster(String semanticId, double longitude, double latitude,
53                     long duration) {
54        mSemanticId = semanticId;
55        mCenter = getLocationVector(longitude, latitude);
56        mDuration = duration;
57    }
58
59    public String getSemanticId() {
60        return mSemanticId;
61    }
62
63    public void generateSemanticId(long index) {
64        mSemanticId = "cluser: " + String.valueOf(index);
65    }
66
67    public long getDuration() {
68        return mDuration;
69    }
70
71    public boolean hasSemanticId() {
72        return mSemanticId != null;
73    }
74
75    protected double[] getLocationVector(Location location) {
76        return getLocationVector(location.getLongitude(), location.getLatitude());
77    }
78
79    protected double[] getLocationVector(double longitude, double latitude) {
80        double vector[] = new double[VECTOR_LENGTH];
81        double lambda = Math.toRadians(longitude);
82        double phi = Math.toRadians(latitude);
83
84        vector[0] = Math.cos(lambda) * Math.cos(phi);
85        vector[1] = Math.sin(lambda) * Math.cos(phi);
86        vector[2] = Math.sin(phi);
87        return vector;
88    }
89
90    protected double getCenterLongitude() {
91        // Because latitude ranges from -90 to 90 degrees, cosPhi >= 0.
92        double cosPhi = Math.cos(Math.asin(mCenter[2]));
93        double longitude = Math.toDegrees(Math.asin(mCenter[1] / cosPhi));
94        if (mCenter[0] < 0) {
95            longitude = (longitude > 0) ? 180f - longitude : -180 - longitude;
96        }
97        return longitude;
98    }
99
100    protected double getCenterLatitude() {
101        return Math.toDegrees(Math.asin(mCenter[2]));
102    }
103
104    private double computeDistance(double[] vector1, double[] vector2) {
105        double product = 0f;
106        for (int i = 0; i < VECTOR_LENGTH; ++i) {
107            product += vector1[i] * vector2[i];
108        }
109        double radian = Math.acos(Math.min(product, 1f));
110        return radian * EARTH_RADIUS;
111    }
112
113    /*
114     * This computes the distance from loation to the cluster center in meter.
115     */
116    public float distanceToCenter(Location location) {
117        return (float) computeDistance(mCenter, getLocationVector(location));
118    }
119
120    public float distanceToCluster(BaseCluster cluster) {
121        return (float) computeDistance(mCenter, cluster.mCenter);
122    }
123
124    public void absorbCluster(BaseCluster cluster) {
125        averageCenter(cluster.mCenter, cluster.mDuration);
126        absorbHistogram(cluster);
127    }
128
129    public void setCluster(BaseCluster cluster) {
130        for (int i = 0; i < VECTOR_LENGTH; ++i) {
131            mCenter[i] = cluster.mCenter[i];
132        }
133        mHistogram.clear();
134        mHistogram.putAll(cluster.mHistogram);
135        mDuration = cluster.mDuration;
136    }
137
138    private void absorbHistogram(BaseCluster cluster) {
139        for (Map.Entry<String, Long> entry : cluster.mHistogram.entrySet()) {
140            String timeLabel = entry.getKey();
141            long duration = entry.getValue();
142
143            if (mHistogram.containsKey(timeLabel)) {
144                duration += mHistogram.get(timeLabel);
145            }
146            mHistogram.put(timeLabel, duration);
147        }
148        mDuration += cluster.mDuration;
149    }
150
151    public boolean passThreshold(long durationThreshold) {
152        // TODO: might want to keep semantic cluster
153        return mDuration > durationThreshold;
154    }
155
156    public final HashMap<String, Long> getHistogram() {
157        return mHistogram;
158    }
159
160    public void setHistogram(Map<String, Long> histogram) {
161        mHistogram.clear();
162        mHistogram.putAll(histogram);
163
164        mDuration = 0;
165        if (mHistogram.containsKey(TimeStatsAggregator.WEEKEND)) {
166            mDuration += mHistogram.get(TimeStatsAggregator.WEEKEND);
167        }
168        if (mHistogram.containsKey(TimeStatsAggregator.WEEKDAY)) {
169            mDuration += mHistogram.get(TimeStatsAggregator.WEEKDAY);
170        }
171    }
172
173    public void forgetPastHistory() {
174        mDuration *= FORGETTING_ENUMERATOR;
175        mDuration /= FORGETTING_DENOMINATOR;
176
177        for (Map.Entry<String, Long> entry : mHistogram.entrySet()) {
178            String key = entry.getKey();
179            long value = entry.getValue();
180
181            value *= FORGETTING_ENUMERATOR;
182            value /= FORGETTING_DENOMINATOR;
183
184            mHistogram.put(key, value);
185        }
186    }
187
188    protected void normalizeCenter() {
189        double norm = 0;
190        for (int i = 0; i < VECTOR_LENGTH; ++i) {
191            norm += mCenter[i] * mCenter[i];
192        }
193        norm = Math.sqrt(norm);
194        for (int i = 0; i < VECTOR_LENGTH; ++i) {
195            mCenter[i] /= norm;
196        }
197    }
198
199    protected void averageCenter(double[] newCenter, long newDuration) {
200        double weight = ((double) mDuration) / (mDuration + newDuration);
201        double newWeight = 1f - weight;
202
203        double norm = 0;
204        for (int i = 0; i < VECTOR_LENGTH; ++i) {
205            mCenter[i] = weight * mCenter[i] + newWeight * newCenter[i];
206            norm += mCenter[i] * mCenter[i];
207        }
208        norm = Math.sqrt(norm);
209        for (int i = 0; i < VECTOR_LENGTH; ++i) {
210            mCenter[i] /= norm;
211        }
212    }
213}
214