src/com/cooliris/media/MediaClustering.java

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