1 /* 2 * Copyright (C) 2009 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 */ 16 17 package com.cooliris.media; 18 19 import java.util.ArrayList; 20 21 import android.text.format.DateFormat; 22 import android.text.format.DateUtils; 23 import android.content.Context; 24 25 import android.content.res.Resources; 26 27 import com.cooliris.app.App; 28 import com.cooliris.app.Res; 29 30 /** 31 * Implementation of an agglomerative based clustering where all items within a 32 * certain time cutoff are grouped into the same cluster. Small adjacent 33 * clusters are merged and large individual clusters are considered for 34 * splitting. 35 * 36 * TODO: Limitation: Can deal with items not being added incrementally to the 37 * end of the current date range but effectively assumes this is the case for 38 * efficient performance. 39 */ 40 41 public final class MediaClustering { 42 // If 2 items are greater than 25 miles apart, they will be in different 43 // clusters. 44 private static final int GEOGRAPHIC_DISTANCE_CUTOFF_IN_MILES = 20; 45 46 // Do not want to split based on anything under 1 min. 47 private static final long MIN_CLUSTER_SPLIT_TIME_IN_MS = 60000L; 48 49 // Disregard a cluster split time of anything over 2 hours. 50 private static final long MAX_CLUSTER_SPLIT_TIME_IN_MS = 7200000L; 51 52 // Try and get around 9 clusters (best-effort for the common case). 53 private static final int NUM_CLUSTERS_TARGETED = 9; 54 55 // Try and merge 2 clusters if they are both smaller than min cluster size. 56 // The min cluster size can range from 8 to 15. 57 private static final int MIN_MIN_CLUSTER_SIZE = 8; 58 private static final int MAX_MIN_CLUSTER_SIZE = 15; 59 60 // Try and split a cluster if it is bigger than max cluster size. 61 // The max cluster size can range from 20 to 50. 62 private static final int MIN_MAX_CLUSTER_SIZE = 20; 63 private static final int MAX_MAX_CLUSTER_SIZE = 50; 64 65 // Initially put 2 items in the same cluster as long as they are within 66 // 3 cluster frequencies of each other. 67 private static int CLUSTER_SPLIT_MULTIPLIER = 3; 68 69 // The minimum change factor in the time between items to consider a 70 // partition. 71 // Example: (Item 3 - Item 2) / (Item 2 - Item 1). 72 private static final int MIN_PARTITION_CHANGE_FACTOR = 2; 73 74 // Make the cluster split time of a large cluster half that of a regular 75 // cluster. 76 private static final int PARTITION_CLUSTER_SPLIT_TIME_FACTOR = 2; 77 78 private ArrayList<Cluster> mClusters; 79 private Cluster mCurrCluster; 80 private boolean mIsPicassaAlbum = false; 81 private long mClusterSplitTime = (MIN_CLUSTER_SPLIT_TIME_IN_MS + MAX_CLUSTER_SPLIT_TIME_IN_MS) / 2; 82 private long mLargeClusterSplitTime = mClusterSplitTime / PARTITION_CLUSTER_SPLIT_TIME_FACTOR; 83 private int mMinClusterSize = (MIN_MIN_CLUSTER_SIZE + MAX_MIN_CLUSTER_SIZE) / 2; 84 private int mMaxClusterSize = (MIN_MAX_CLUSTER_SIZE + MAX_MAX_CLUSTER_SIZE) / 2; 85 86 MediaClustering(boolean isPicassaAlbum) { 87 mClusters = new ArrayList<Cluster>(); 88 mIsPicassaAlbum = isPicassaAlbum; 89 mCurrCluster = new Cluster(mIsPicassaAlbum); 90 } 91 92 public void clear() { 93 int numClusters = mClusters.size(); 94 for (int i = 0; i < numClusters; i++) { 95 Cluster cluster = mClusters.get(i); 96 cluster.clear(); 97 } 98 if (mCurrCluster != null) { 99 mCurrCluster.clear(); 100 } 101 } 102 103 public void setTimeRange(long timeRange, int numItems) { 104 if (numItems != 0) { 105 int meanItemsPerCluster = numItems / NUM_CLUSTERS_TARGETED; 106 // Heuristic to get min and max cluster size - half and double the 107 // desired items per cluster. 108 mMinClusterSize = meanItemsPerCluster / 2; 109 mMaxClusterSize = meanItemsPerCluster * 2; 110 mClusterSplitTime = timeRange / numItems * CLUSTER_SPLIT_MULTIPLIER; 111 } 112 mClusterSplitTime = Shared.clamp(mClusterSplitTime, MIN_CLUSTER_SPLIT_TIME_IN_MS, MAX_CLUSTER_SPLIT_TIME_IN_MS); 113 mLargeClusterSplitTime = mClusterSplitTime / PARTITION_CLUSTER_SPLIT_TIME_FACTOR; 114 mMinClusterSize = Shared.clamp(mMinClusterSize, MIN_MIN_CLUSTER_SIZE, MAX_MIN_CLUSTER_SIZE); 115 mMaxClusterSize = Shared.clamp(mMaxClusterSize, MIN_MAX_CLUSTER_SIZE, MAX_MAX_CLUSTER_SIZE); 116 } 117 118 public void addItemForClustering(MediaItem mediaItem) { 119 compute(mediaItem, false); 120 } 121 122 public void removeItemFromClustering(MediaItem mediaItem) { 123 // Find the cluster that contains this item. 124 if (mCurrCluster.removeItem(mediaItem)) { 125 return; 126 } 127 int numClusters = mClusters.size(); 128 for (int i = 0; i < numClusters; i++) { 129 Cluster cluster = mClusters.get(i); 130 if (cluster.removeItem(mediaItem)) { 131 if (cluster.mNumItemsLoaded == 0) { 132 mClusters.remove(cluster); 133 } 134 return; 135 } 136 } 137 } 138 139 public void compute(MediaItem currentItem, boolean processAllItems) { 140 if (currentItem != null) { 141 int numClusters = mClusters.size(); 142 int numCurrClusterItems = mCurrCluster.mNumItemsLoaded; 143 boolean geographicallySeparateItem = false; 144 boolean itemAddedToCurrentCluster = false; 145 146 // Determine if this item should go in the current cluster or be the 147 // start of a new cluster. 148 if (numCurrClusterItems == 0) { 149 mCurrCluster.addItem(currentItem); 150 } else { 151 MediaItem prevItem = mCurrCluster.getLastItem(); 152 if (isGeographicallySeparated(prevItem, currentItem)) { 153 mClusters.add(mCurrCluster); 154 geographicallySeparateItem = true; 155 } else if (numCurrClusterItems > mMaxClusterSize) { 156 splitAndAddCurrentCluster(); 157 } else if (timeDistance(prevItem, currentItem) < mClusterSplitTime) { 158 mCurrCluster.addItem(currentItem); 159 itemAddedToCurrentCluster = true; 160 } else if (numClusters > 0 && numCurrClusterItems < mMinClusterSize 161 && !mCurrCluster.mGeographicallySeparatedFromPrevCluster) { 162 mergeAndAddCurrentCluster(); 163 } else { 164 mClusters.add(mCurrCluster); 165 } 166 167 // Creating a new cluster and adding the current item to it. 168 if (!itemAddedToCurrentCluster) { 169 mCurrCluster = new Cluster(mIsPicassaAlbum); 170 if (geographicallySeparateItem) { 171 mCurrCluster.mGeographicallySeparatedFromPrevCluster = true; 172 } 173 mCurrCluster.addItem(currentItem); 174 } 175 } 176 } 177 178 if (processAllItems && mCurrCluster.mNumItemsLoaded > 0) { 179 int numClusters = mClusters.size(); 180 int numCurrClusterItems = mCurrCluster.mNumItemsLoaded; 181 182 // The last cluster may potentially be too big or too small. 183 if (numCurrClusterItems > mMaxClusterSize) { 184 splitAndAddCurrentCluster(); 185 } else if (numClusters > 0 && numCurrClusterItems < mMinClusterSize 186 && !mCurrCluster.mGeographicallySeparatedFromPrevCluster) { 187 mergeAndAddCurrentCluster(); 188 } else { 189 mClusters.add(mCurrCluster); 190 } 191 mCurrCluster = new Cluster(mIsPicassaAlbum); 192 } 193 } 194 195 private void splitAndAddCurrentCluster() { 196 ArrayList<MediaItem> currClusterItems = mCurrCluster.getItems(); 197 int numCurrClusterItems = mCurrCluster.mNumItemsLoaded; 198 int secondPartitionStartIndex = getPartitionIndexForCurrentCluster(); 199 if (secondPartitionStartIndex != -1) { 200 Cluster partitionedCluster = new Cluster(mIsPicassaAlbum); 201 for (int j = 0; j < secondPartitionStartIndex; j++) { 202 partitionedCluster.addItem(currClusterItems.get(j)); 203 } 204 mClusters.add(partitionedCluster); 205 partitionedCluster = new Cluster(mIsPicassaAlbum); 206 for (int j = secondPartitionStartIndex; j < numCurrClusterItems; j++) { 207 partitionedCluster.addItem(currClusterItems.get(j)); 208 } 209 mClusters.add(partitionedCluster); 210 } else { 211 mClusters.add(mCurrCluster); 212 } 213 } 214 215 private int getPartitionIndexForCurrentCluster() { 216 int partitionIndex = -1; 217 float largestChange = MIN_PARTITION_CHANGE_FACTOR; 218 ArrayList<MediaItem> currClusterItems = mCurrCluster.getItems(); 219 int numCurrClusterItems = mCurrCluster.mNumItemsLoaded; 220 int minClusterSize = mMinClusterSize; 221 222 // Could be slightly more efficient here but this code seems cleaner. 223 if (numCurrClusterItems > minClusterSize + 1) { 224 for (int i = minClusterSize; i < numCurrClusterItems - minClusterSize; i++) { 225 MediaItem prevItem = currClusterItems.get(i - 1); 226 MediaItem currItem = currClusterItems.get(i); 227 MediaItem nextItem = currClusterItems.get(i + 1); 228 229 if (prevItem.isDateTakenValid() && currItem.isDateModifiedValid() && nextItem.isDateModifiedValid()) { 230 long diff1 = Math.abs(nextItem.mDateTakenInMs - currItem.mDateTakenInMs); 231 long diff2 = Math.abs(currItem.mDateTakenInMs - prevItem.mDateTakenInMs); 232 float change = Math.max(diff1 / (diff2 + 0.01f), diff2 / (diff1 + 0.01f)); 233 if (change > largestChange) { 234 if (timeDistance(currItem, prevItem) > mLargeClusterSplitTime) { 235 partitionIndex = i; 236 largestChange = change; 237 } else if (timeDistance(nextItem, currItem) > mLargeClusterSplitTime) { 238 partitionIndex = i + 1; 239 largestChange = change; 240 } 241 } 242 } 243 } 244 } 245 return partitionIndex; 246 } 247 248 private void mergeAndAddCurrentCluster() { 249 int numClusters = mClusters.size(); 250 Cluster prevCluster = mClusters.get(numClusters - 1); 251 ArrayList<MediaItem> currClusterItems = mCurrCluster.getItems(); 252 int numCurrClusterItems = mCurrCluster.mNumItemsLoaded; 253 if (prevCluster.mNumItemsLoaded < mMinClusterSize) { 254 for (int i = 0; i < numCurrClusterItems; i++) { 255 prevCluster.addItem(currClusterItems.get(i)); 256 } 257 mClusters.set(numClusters - 1, prevCluster); 258 } else { 259 mClusters.add(mCurrCluster); 260 } 261 } 262 263 public synchronized ArrayList<Cluster> getClusters() { 264 int numCurrClusterItems = mCurrCluster.mNumItemsLoaded; 265 if (numCurrClusterItems == 0) { 266 return mClusters; 267 } 268 ArrayList<Cluster> mergedClusters = new ArrayList<Cluster>(); 269 mergedClusters.addAll(mClusters); 270 if (numCurrClusterItems > 0) { 271 mergedClusters.add(mCurrCluster); 272 } 273 return mergedClusters; 274 } 275 276 public ArrayList<Cluster> getClustersForDisplay() { 277 return mClusters; 278 } 279 280 public static final class Cluster extends MediaSet { 281 private boolean mGeographicallySeparatedFromPrevCluster = false; 282 private boolean mClusterChanged = false; 283 private boolean mIsPicassaAlbum = false; 284 private static final String MMDDYY_FORMAT = "MMddyy"; 285 286 public Cluster(boolean isPicassaAlbum) { 287 mIsPicassaAlbum = isPicassaAlbum; 288 } 289 290 public void generateCaption(Context context) { 291 if (mClusterChanged) { 292 Resources resources = context.getResources(); 293 294 long minTimestamp = -1L; 295 long maxTimestamp = -1L; 296 if (areTimestampsAvailable()) { 297 minTimestamp = mMinTimestamp; 298 maxTimestamp = mMaxTimestamp; 299 } else if (areAddedTimestampsAvailable()) { 300 minTimestamp = mMinAddedTimestamp; 301 maxTimestamp = mMaxAddedTimestamp; 302 } 303 304 if (minTimestamp != -1L) { 305 if (mIsPicassaAlbum) { 306 minTimestamp -= App.CURRENT_TIME_ZONE.getOffset(minTimestamp); 307 maxTimestamp -= App.CURRENT_TIME_ZONE.getOffset(maxTimestamp); 308 } 309 String minDay = DateFormat.format(MMDDYY_FORMAT, minTimestamp).toString(); 310 String maxDay = DateFormat.format(MMDDYY_FORMAT, maxTimestamp).toString(); 311 312 if (minDay.substring(4).equals(maxDay.substring(4))) { 313 // The items are from the same year - show at least as 314 // much granularity as abbrev_all allows. 315 mName = DateUtils.formatDateRange(context, minTimestamp, maxTimestamp, DateUtils.FORMAT_ABBREV_ALL); 316 317 // Get a more granular date range string if the min and 318 // max timestamp are on the same day and from the 319 // current year. 320 if (minDay.equals(maxDay)) { 321 int flags = DateUtils.FORMAT_ABBREV_MONTH | DateUtils.FORMAT_SHOW_DATE; 322 // Contains the year only if the date does not 323 // correspond to the current year. 324 String dateRangeWithOptionalYear = DateUtils.formatDateTime(context, minTimestamp, flags); 325 String dateRangeWithYear = DateUtils.formatDateTime(context, minTimestamp, flags 326 | DateUtils.FORMAT_SHOW_YEAR); 327 if (!dateRangeWithOptionalYear.equals(dateRangeWithYear)) { 328 // This means both dates are from the same year 329 // - show the time. 330 // Not enough room to display the time range. 331 // Pick the mid-point. 332 long midTimestamp = (minTimestamp + maxTimestamp) / 2; 333 mName = DateUtils.formatDateRange(context, midTimestamp, midTimestamp, DateUtils.FORMAT_SHOW_TIME 334 | flags); 335 } 336 } 337 } else { 338 // The items are not from the same year - only show 339 // month and year. 340 int flags = DateUtils.FORMAT_NO_MONTH_DAY | DateUtils.FORMAT_ABBREV_MONTH | DateUtils.FORMAT_SHOW_DATE; 341 mName = DateUtils.formatDateRange(context, minTimestamp, maxTimestamp, flags); 342 } 343 } else { 344 mName = resources.getString(Res.string.date_unknown); 345 } 346 updateNumExpectedItems(); 347 generateTitle(false); 348 mClusterChanged = false; 349 } 350 } 351 352 public void addItem(MediaItem item) { 353 super.addItem(item); 354 mClusterChanged = true; 355 } 356 357 public boolean removeItem(MediaItem item) { 358 if (super.removeItem(item)) { 359 mClusterChanged = true; 360 return true; 361 } 362 return false; 363 } 364 365 public MediaItem getLastItem() { 366 final ArrayList<MediaItem> items = super.getItems(); 367 if (items == null || mNumItemsLoaded == 0) { 368 return null; 369 } else { 370 return items.get(mNumItemsLoaded - 1); 371 } 372 } 373 } 374 375 // Returns the time interval between the two items in milliseconds. 376 public static long timeDistance(MediaItem a, MediaItem b) { 377 if (a == null || b == null) { 378 return 0; 379 } 380 return Math.abs(a.mDateTakenInMs - b.mDateTakenInMs); 381 } 382 383 // Returns true if a, b are sufficiently geographically separated. 384 private static boolean isGeographicallySeparated(MediaItem a, MediaItem b) { 385 // If a or b are null, a or b have the default latitude, longitude 386 // values or are close enough, return false. 387 if (a != null && b != null && a.isLatLongValid() && b.isLatLongValid()) { 388 int distance = (int) (LocationMediaFilter.toMile(LocationMediaFilter.distanceBetween(a.mLatitude, a.mLongitude, 389 b.mLatitude, b.mLongitude)) + 0.5); 390 if (distance > GEOGRAPHIC_DISTANCE_CUTOFF_IN_MILES) { 391 return true; 392 } 393 } 394 return false; 395 } 396 } 397