Home | History | Annotate | Download | only in data 
      1 /*
      2  * Copyright (C) 2010 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.android.gallery3d.data;
     18 
     19 import com.android.gallery3d.common.Utils;
     20 import com.android.gallery3d.util.GalleryUtils;
     21 
     22 import android.content.Context;
     23 import android.text.format.DateFormat;
     24 import android.text.format.DateUtils;
     25 
     26 import java.util.ArrayList;
     27 import java.util.Collections;
     28 import java.util.Comparator;
     29 
     30 public class TimeClustering extends Clustering {
     31     private static final String TAG = "TimeClustering";
     32 
     33     // If 2 items are greater than 25 miles apart, they will be in different
     34     // clusters.
     35     private static final int GEOGRAPHIC_DISTANCE_CUTOFF_IN_MILES = 20;
     36 
     37     // Do not want to split based on anything under 1 min.
     38     private static final long MIN_CLUSTER_SPLIT_TIME_IN_MS = 60000L;
     39 
     40     // Disregard a cluster split time of anything over 2 hours.
     41     private static final long MAX_CLUSTER_SPLIT_TIME_IN_MS = 7200000L;
     42 
     43     // Try and get around 9 clusters (best-effort for the common case).
     44     private static final int NUM_CLUSTERS_TARGETED = 9;
     45 
     46     // Try and merge 2 clusters if they are both smaller than min cluster size.
     47     // The min cluster size can range from 8 to 15.
     48     private static final int MIN_MIN_CLUSTER_SIZE = 8;
     49     private static final int MAX_MIN_CLUSTER_SIZE = 15;
     50 
     51     // Try and split a cluster if it is bigger than max cluster size.
     52     // The max cluster size can range from 20 to 50.
     53     private static final int MIN_MAX_CLUSTER_SIZE = 20;
     54     private static final int MAX_MAX_CLUSTER_SIZE = 50;
     55 
     56     // Initially put 2 items in the same cluster as long as they are within
     57     // 3 cluster frequencies of each other.
     58     private static int CLUSTER_SPLIT_MULTIPLIER = 3;
     59 
     60     // The minimum change factor in the time between items to consider a
     61     // partition.
     62     // Example: (Item 3 - Item 2) / (Item 2 - Item 1).
     63     private static final int MIN_PARTITION_CHANGE_FACTOR = 2;
     64 
     65     // Make the cluster split time of a large cluster half that of a regular
     66     // cluster.
     67     private static final int PARTITION_CLUSTER_SPLIT_TIME_FACTOR = 2;
     68 
     69     private Context mContext;
     70     private ArrayList<Cluster> mClusters;
     71     private String[] mNames;
     72     private Cluster mCurrCluster;
     73 
     74     private long mClusterSplitTime =
     75             (MIN_CLUSTER_SPLIT_TIME_IN_MS + MAX_CLUSTER_SPLIT_TIME_IN_MS) / 2;
     76     private long mLargeClusterSplitTime =
     77             mClusterSplitTime / PARTITION_CLUSTER_SPLIT_TIME_FACTOR;
     78     private int mMinClusterSize = (MIN_MIN_CLUSTER_SIZE + MAX_MIN_CLUSTER_SIZE) / 2;
     79     private int mMaxClusterSize = (MIN_MAX_CLUSTER_SIZE + MAX_MAX_CLUSTER_SIZE) / 2;
     80 
     81 
     82     private static final Comparator<SmallItem> sDateComparator =
     83             new DateComparator();
     84 
     85     private static class DateComparator implements Comparator<SmallItem> {
     86         public int compare(SmallItem item1, SmallItem item2) {
     87             return -Utils.compare(item1.dateInMs, item2.dateInMs);
     88         }
     89     }
     90 
     91     public TimeClustering(Context context) {
     92         mContext = context;
     93         mClusters = new ArrayList<Cluster>();
     94         mCurrCluster = new Cluster();
     95     }
     96 
     97     @Override
     98     public void run(MediaSet baseSet) {
     99         final int total = baseSet.getTotalMediaItemCount();
    100         final SmallItem[] buf = new SmallItem[total];
    101         final double[] latLng = new double[2];
    102 
    103         baseSet.enumerateTotalMediaItems(new MediaSet.ItemConsumer() {
    104             public void consume(int index, MediaItem item) {
    105                 if (index < 0 || index >= total) return;
    106                 SmallItem s = new SmallItem();
    107                 s.path = item.getPath();
    108                 s.dateInMs = item.getDateInMs();
    109                 item.getLatLong(latLng);
    110                 s.lat = latLng[0];
    111                 s.lng = latLng[1];
    112                 buf[index] = s;
    113             }
    114         });
    115 
    116         ArrayList<SmallItem> items = new ArrayList<SmallItem>(total);
    117         for (int i = 0; i < total; i++) {
    118             if (buf[i] != null) {
    119                 items.add(buf[i]);
    120             }
    121         }
    122 
    123         Collections.sort(items, sDateComparator);
    124 
    125         int n = items.size();
    126         long minTime = 0;
    127         long maxTime = 0;
    128         for (int i = 0; i < n; i++) {
    129             long t = items.get(i).dateInMs;
    130             if (t == 0) continue;
    131             if (minTime == 0) {
    132                 minTime = maxTime = t;
    133             } else {
    134                 minTime = Math.min(minTime, t);
    135                 maxTime = Math.max(maxTime, t);
    136             }
    137         }
    138 
    139         setTimeRange(maxTime - minTime, n);
    140 
    141         for (int i = 0; i < n; i++) {
    142             compute(items.get(i));
    143         }
    144 
    145         compute(null);
    146 
    147         int m = mClusters.size();
    148         mNames = new String[m];
    149         for (int i = 0; i < m; i++) {
    150             mNames[i] = mClusters.get(i).generateCaption(mContext);
    151         }
    152     }
    153 
    154     @Override
    155     public int getNumberOfClusters() {
    156         return mClusters.size();
    157     }
    158 
    159     @Override
    160     public ArrayList<Path> getCluster(int index) {
    161         ArrayList<SmallItem> items = mClusters.get(index).getItems();
    162         ArrayList<Path> result = new ArrayList<Path>(items.size());
    163         for (int i = 0, n = items.size(); i < n; i++) {
    164             result.add(items.get(i).path);
    165         }
    166         return result;
    167     }
    168 
    169     @Override
    170     public String getClusterName(int index) {
    171         return mNames[index];
    172     }
    173 
    174     private void setTimeRange(long timeRange, int numItems) {
    175         if (numItems != 0) {
    176             int meanItemsPerCluster = numItems / NUM_CLUSTERS_TARGETED;
    177             // Heuristic to get min and max cluster size - half and double the
    178             // desired items per cluster.
    179             mMinClusterSize = meanItemsPerCluster / 2;
    180             mMaxClusterSize = meanItemsPerCluster * 2;
    181             mClusterSplitTime = timeRange / numItems * CLUSTER_SPLIT_MULTIPLIER;
    182         }
    183         mClusterSplitTime = Utils.clamp(mClusterSplitTime, MIN_CLUSTER_SPLIT_TIME_IN_MS, MAX_CLUSTER_SPLIT_TIME_IN_MS);
    184         mLargeClusterSplitTime = mClusterSplitTime / PARTITION_CLUSTER_SPLIT_TIME_FACTOR;
    185         mMinClusterSize = Utils.clamp(mMinClusterSize, MIN_MIN_CLUSTER_SIZE, MAX_MIN_CLUSTER_SIZE);
    186         mMaxClusterSize = Utils.clamp(mMaxClusterSize, MIN_MAX_CLUSTER_SIZE, MAX_MAX_CLUSTER_SIZE);
    187     }
    188 
    189     private void compute(SmallItem currentItem) {
    190         if (currentItem != null) {
    191             int numClusters = mClusters.size();
    192             int numCurrClusterItems = mCurrCluster.size();
    193             boolean geographicallySeparateItem = false;
    194             boolean itemAddedToCurrentCluster = false;
    195 
    196             // Determine if this item should go in the current cluster or be the
    197             // start of a new cluster.
    198             if (numCurrClusterItems == 0) {
    199                 mCurrCluster.addItem(currentItem);
    200             } else {
    201                 SmallItem prevItem = mCurrCluster.getLastItem();
    202                 if (isGeographicallySeparated(prevItem, currentItem)) {
    203                     mClusters.add(mCurrCluster);
    204                     geographicallySeparateItem = true;
    205                 } else if (numCurrClusterItems > mMaxClusterSize) {
    206                     splitAndAddCurrentCluster();
    207                 } else if (timeDistance(prevItem, currentItem) < mClusterSplitTime) {
    208                     mCurrCluster.addItem(currentItem);
    209                     itemAddedToCurrentCluster = true;
    210                 } else if (numClusters > 0 && numCurrClusterItems < mMinClusterSize
    211                         && !mCurrCluster.mGeographicallySeparatedFromPrevCluster) {
    212                     mergeAndAddCurrentCluster();
    213                 } else {
    214                     mClusters.add(mCurrCluster);
    215                 }
    216 
    217                 // Creating a new cluster and adding the current item to it.
    218                 if (!itemAddedToCurrentCluster) {
    219                     mCurrCluster = new Cluster();
    220                     if (geographicallySeparateItem) {
    221                         mCurrCluster.mGeographicallySeparatedFromPrevCluster = true;
    222                     }
    223                     mCurrCluster.addItem(currentItem);
    224                 }
    225             }
    226         } else {
    227             if (mCurrCluster.size() > 0) {
    228                 int numClusters = mClusters.size();
    229                 int numCurrClusterItems = mCurrCluster.size();
    230 
    231                 // The last cluster may potentially be too big or too small.
    232                 if (numCurrClusterItems > mMaxClusterSize) {
    233                     splitAndAddCurrentCluster();
    234                 } else if (numClusters > 0 && numCurrClusterItems < mMinClusterSize
    235                         && !mCurrCluster.mGeographicallySeparatedFromPrevCluster) {
    236                     mergeAndAddCurrentCluster();
    237                 } else {
    238                     mClusters.add(mCurrCluster);
    239                 }
    240                 mCurrCluster = new Cluster();
    241             }
    242         }
    243     }
    244 
    245     private void splitAndAddCurrentCluster() {
    246         ArrayList<SmallItem> currClusterItems = mCurrCluster.getItems();
    247         int numCurrClusterItems = mCurrCluster.size();
    248         int secondPartitionStartIndex = getPartitionIndexForCurrentCluster();
    249         if (secondPartitionStartIndex != -1) {
    250             Cluster partitionedCluster = new Cluster();
    251             for (int j = 0; j < secondPartitionStartIndex; j++) {
    252                 partitionedCluster.addItem(currClusterItems.get(j));
    253             }
    254             mClusters.add(partitionedCluster);
    255             partitionedCluster = new Cluster();
    256             for (int j = secondPartitionStartIndex; j < numCurrClusterItems; j++) {
    257                 partitionedCluster.addItem(currClusterItems.get(j));
    258             }
    259             mClusters.add(partitionedCluster);
    260         } else {
    261             mClusters.add(mCurrCluster);
    262         }
    263     }
    264 
    265     private int getPartitionIndexForCurrentCluster() {
    266         int partitionIndex = -1;
    267         float largestChange = MIN_PARTITION_CHANGE_FACTOR;
    268         ArrayList<SmallItem> currClusterItems = mCurrCluster.getItems();
    269         int numCurrClusterItems = mCurrCluster.size();
    270         int minClusterSize = mMinClusterSize;
    271 
    272         // Could be slightly more efficient here but this code seems cleaner.
    273         if (numCurrClusterItems > minClusterSize + 1) {
    274             for (int i = minClusterSize; i < numCurrClusterItems - minClusterSize; i++) {
    275                 SmallItem prevItem = currClusterItems.get(i - 1);
    276                 SmallItem currItem = currClusterItems.get(i);
    277                 SmallItem nextItem = currClusterItems.get(i + 1);
    278 
    279                 long timeNext = nextItem.dateInMs;
    280                 long timeCurr = currItem.dateInMs;
    281                 long timePrev = prevItem.dateInMs;
    282 
    283                 if (timeNext == 0 || timeCurr == 0 || timePrev == 0) continue;
    284 
    285                 long diff1 = Math.abs(timeNext - timeCurr);
    286                 long diff2 = Math.abs(timeCurr - timePrev);
    287 
    288                 float change = Math.max(diff1 / (diff2 + 0.01f), diff2 / (diff1 + 0.01f));
    289                 if (change > largestChange) {
    290                     if (timeDistance(currItem, prevItem) > mLargeClusterSplitTime) {
    291                         partitionIndex = i;
    292                         largestChange = change;
    293                     } else if (timeDistance(nextItem, currItem) > mLargeClusterSplitTime) {
    294                         partitionIndex = i + 1;
    295                         largestChange = change;
    296                     }
    297                 }
    298             }
    299         }
    300         return partitionIndex;
    301     }
    302 
    303     private void mergeAndAddCurrentCluster() {
    304         int numClusters = mClusters.size();
    305         Cluster prevCluster = mClusters.get(numClusters - 1);
    306         ArrayList<SmallItem> currClusterItems = mCurrCluster.getItems();
    307         int numCurrClusterItems = mCurrCluster.size();
    308         if (prevCluster.size() < mMinClusterSize) {
    309             for (int i = 0; i < numCurrClusterItems; i++) {
    310                 prevCluster.addItem(currClusterItems.get(i));
    311             }
    312             mClusters.set(numClusters - 1, prevCluster);
    313         } else {
    314             mClusters.add(mCurrCluster);
    315         }
    316     }
    317 
    318     // Returns true if a, b are sufficiently geographically separated.
    319     private static boolean isGeographicallySeparated(SmallItem itemA, SmallItem itemB) {
    320         if (!GalleryUtils.isValidLocation(itemA.lat, itemA.lng)
    321                 || !GalleryUtils.isValidLocation(itemB.lat, itemB.lng)) {
    322             return false;
    323         }
    324 
    325         double distance = GalleryUtils.fastDistanceMeters(
    326             Math.toRadians(itemA.lat),
    327             Math.toRadians(itemA.lng),
    328             Math.toRadians(itemB.lat),
    329             Math.toRadians(itemB.lng));
    330         return (GalleryUtils.toMile(distance) > GEOGRAPHIC_DISTANCE_CUTOFF_IN_MILES);
    331     }
    332 
    333     // Returns the time interval between the two items in milliseconds.
    334     private static long timeDistance(SmallItem a, SmallItem b) {
    335         return Math.abs(a.dateInMs - b.dateInMs);
    336     }
    337 }
    338 
    339 class SmallItem {
    340     Path path;
    341     long dateInMs;
    342     double lat, lng;
    343 }
    344 
    345 class Cluster {
    346     @SuppressWarnings("unused")
    347     private static final String TAG = "Cluster";
    348     private static final String MMDDYY_FORMAT = "MMddyy";
    349 
    350     // This is for TimeClustering only.
    351     public boolean mGeographicallySeparatedFromPrevCluster = false;
    352 
    353     private ArrayList<SmallItem> mItems = new ArrayList<SmallItem>();
    354 
    355     public Cluster() {
    356     }
    357 
    358     public void addItem(SmallItem item) {
    359         mItems.add(item);
    360     }
    361 
    362     public int size() {
    363         return mItems.size();
    364     }
    365 
    366     public SmallItem getLastItem() {
    367         int n = mItems.size();
    368         return (n == 0) ? null : mItems.get(n - 1);
    369     }
    370 
    371     public ArrayList<SmallItem> getItems() {
    372         return mItems;
    373     }
    374 
    375     public String generateCaption(Context context) {
    376         int n = mItems.size();
    377         long minTimestamp = 0;
    378         long maxTimestamp = 0;
    379 
    380         for (int i = 0; i < n; i++) {
    381             long t = mItems.get(i).dateInMs;
    382             if (t == 0) continue;
    383             if (minTimestamp == 0) {
    384                 minTimestamp = maxTimestamp = t;
    385             } else {
    386                 minTimestamp = Math.min(minTimestamp, t);
    387                 maxTimestamp = Math.max(maxTimestamp, t);
    388             }
    389         }
    390         if (minTimestamp == 0) return "";
    391 
    392         String caption;
    393         String minDay = DateFormat.format(MMDDYY_FORMAT, minTimestamp)
    394                 .toString();
    395         String maxDay = DateFormat.format(MMDDYY_FORMAT, maxTimestamp)
    396                 .toString();
    397 
    398         if (minDay.substring(4).equals(maxDay.substring(4))) {
    399             // The items are from the same year - show at least as
    400             // much granularity as abbrev_all allows.
    401             caption = DateUtils.formatDateRange(context, minTimestamp,
    402                     maxTimestamp, DateUtils.FORMAT_ABBREV_ALL);
    403 
    404             // Get a more granular date range string if the min and
    405             // max timestamp are on the same day and from the
    406             // current year.
    407             if (minDay.equals(maxDay)) {
    408                 int flags = DateUtils.FORMAT_ABBREV_MONTH | DateUtils.FORMAT_SHOW_DATE;
    409                 // Contains the year only if the date does not
    410                 // correspond to the current year.
    411                 String dateRangeWithOptionalYear = DateUtils.formatDateTime(
    412                         context, minTimestamp, flags);
    413                 String dateRangeWithYear = DateUtils.formatDateTime(
    414                         context, minTimestamp, flags | DateUtils.FORMAT_SHOW_YEAR);
    415                 if (!dateRangeWithOptionalYear.equals(dateRangeWithYear)) {
    416                     // This means both dates are from the same year
    417                     // - show the time.
    418                     // Not enough room to display the time range.
    419                     // Pick the mid-point.
    420                     long midTimestamp = (minTimestamp + maxTimestamp) / 2;
    421                     caption = DateUtils.formatDateRange(context, midTimestamp,
    422                             midTimestamp, DateUtils.FORMAT_SHOW_TIME | flags);
    423                 }
    424             }
    425         } else {
    426             // The items are not from the same year - only show
    427             // month and year.
    428             int flags = DateUtils.FORMAT_NO_MONTH_DAY
    429                     | DateUtils.FORMAT_ABBREV_MONTH | DateUtils.FORMAT_SHOW_DATE;
    430             caption = DateUtils.formatDateRange(context, minTimestamp,
    431                     maxTimestamp, flags);
    432         }
    433 
    434         return caption;
    435     }
    436 }
    437