diff options
Diffstat (limited to 'src/com/android/gallery3d/data/TimeClustering.java')
| -rw-r--r-- | src/com/android/gallery3d/data/TimeClustering.java | 436 |
1 files changed, 436 insertions, 0 deletions
diff --git a/src/com/android/gallery3d/data/TimeClustering.java b/src/com/android/gallery3d/data/TimeClustering.java new file mode 100644 index 000000000..1ccf14c13 --- /dev/null +++ b/src/com/android/gallery3d/data/TimeClustering.java @@ -0,0 +1,436 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.gallery3d.data; + +import com.android.gallery3d.common.Utils; +import com.android.gallery3d.util.GalleryUtils; + +import android.content.Context; +import android.text.format.DateFormat; +import android.text.format.DateUtils; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; + +public class TimeClustering extends Clustering { + private static final String TAG = "TimeClustering"; + + // If 2 items are greater than 25 miles apart, they will be in different + // clusters. + private static final int GEOGRAPHIC_DISTANCE_CUTOFF_IN_MILES = 20; + + // Do not want to split based on anything under 1 min. + private static final long MIN_CLUSTER_SPLIT_TIME_IN_MS = 60000L; + + // Disregard a cluster split time of anything over 2 hours. + private static final long MAX_CLUSTER_SPLIT_TIME_IN_MS = 7200000L; + + // Try and get around 9 clusters (best-effort for the common case). + private static final int NUM_CLUSTERS_TARGETED = 9; + + // Try and merge 2 clusters if they are both smaller than min cluster size. + // The min cluster size can range from 8 to 15. + private static final int MIN_MIN_CLUSTER_SIZE = 8; + private static final int MAX_MIN_CLUSTER_SIZE = 15; + + // Try and split a cluster if it is bigger than max cluster size. + // The max cluster size can range from 20 to 50. + private static final int MIN_MAX_CLUSTER_SIZE = 20; + private static final int MAX_MAX_CLUSTER_SIZE = 50; + + // Initially put 2 items in the same cluster as long as they are within + // 3 cluster frequencies of each other. + private static int CLUSTER_SPLIT_MULTIPLIER = 3; + + // The minimum change factor in the time between items to consider a + // partition. + // Example: (Item 3 - Item 2) / (Item 2 - Item 1). + private static final int MIN_PARTITION_CHANGE_FACTOR = 2; + + // Make the cluster split time of a large cluster half that of a regular + // cluster. + private static final int PARTITION_CLUSTER_SPLIT_TIME_FACTOR = 2; + + private Context mContext; + private ArrayList<Cluster> mClusters; + private String[] mNames; + private Cluster mCurrCluster; + + private long mClusterSplitTime = + (MIN_CLUSTER_SPLIT_TIME_IN_MS + MAX_CLUSTER_SPLIT_TIME_IN_MS) / 2; + private long mLargeClusterSplitTime = + mClusterSplitTime / PARTITION_CLUSTER_SPLIT_TIME_FACTOR; + private int mMinClusterSize = (MIN_MIN_CLUSTER_SIZE + MAX_MIN_CLUSTER_SIZE) / 2; + private int mMaxClusterSize = (MIN_MAX_CLUSTER_SIZE + MAX_MAX_CLUSTER_SIZE) / 2; + + + private static final Comparator<SmallItem> sDateComparator = + new DateComparator(); + + private static class DateComparator implements Comparator<SmallItem> { + public int compare(SmallItem item1, SmallItem item2) { + return -Utils.compare(item1.dateInMs, item2.dateInMs); + } + } + + public TimeClustering(Context context) { + mContext = context; + mClusters = new ArrayList<Cluster>(); + mCurrCluster = new Cluster(); + } + + @Override + public void run(MediaSet baseSet) { + final int total = baseSet.getTotalMediaItemCount(); + final SmallItem[] buf = new SmallItem[total]; + final double[] latLng = new double[2]; + + baseSet.enumerateTotalMediaItems(new MediaSet.ItemConsumer() { + public void consume(int index, MediaItem item) { + if (index < 0 || index >= total) return; + SmallItem s = new SmallItem(); + s.path = item.getPath(); + s.dateInMs = item.getDateInMs(); + item.getLatLong(latLng); + s.lat = latLng[0]; + s.lng = latLng[1]; + buf[index] = s; + } + }); + + ArrayList<SmallItem> items = new ArrayList<SmallItem>(total); + for (int i = 0; i < total; i++) { + if (buf[i] != null) { + items.add(buf[i]); + } + } + + Collections.sort(items, sDateComparator); + + int n = items.size(); + long minTime = 0; + long maxTime = 0; + for (int i = 0; i < n; i++) { + long t = items.get(i).dateInMs; + if (t == 0) continue; + if (minTime == 0) { + minTime = maxTime = t; + } else { + minTime = Math.min(minTime, t); + maxTime = Math.max(maxTime, t); + } + } + + setTimeRange(maxTime - minTime, n); + + for (int i = 0; i < n; i++) { + compute(items.get(i)); + } + + compute(null); + + int m = mClusters.size(); + mNames = new String[m]; + for (int i = 0; i < m; i++) { + mNames[i] = mClusters.get(i).generateCaption(mContext); + } + } + + @Override + public int getNumberOfClusters() { + return mClusters.size(); + } + + @Override + public ArrayList<Path> getCluster(int index) { + ArrayList<SmallItem> items = mClusters.get(index).getItems(); + ArrayList<Path> result = new ArrayList<Path>(items.size()); + for (int i = 0, n = items.size(); i < n; i++) { + result.add(items.get(i).path); + } + return result; + } + + @Override + public String getClusterName(int index) { + return mNames[index]; + } + + private void setTimeRange(long timeRange, int numItems) { + if (numItems != 0) { + int meanItemsPerCluster = numItems / NUM_CLUSTERS_TARGETED; + // Heuristic to get min and max cluster size - half and double the + // desired items per cluster. + mMinClusterSize = meanItemsPerCluster / 2; + mMaxClusterSize = meanItemsPerCluster * 2; + mClusterSplitTime = timeRange / numItems * CLUSTER_SPLIT_MULTIPLIER; + } + mClusterSplitTime = Utils.clamp(mClusterSplitTime, MIN_CLUSTER_SPLIT_TIME_IN_MS, MAX_CLUSTER_SPLIT_TIME_IN_MS); + mLargeClusterSplitTime = mClusterSplitTime / PARTITION_CLUSTER_SPLIT_TIME_FACTOR; + mMinClusterSize = Utils.clamp(mMinClusterSize, MIN_MIN_CLUSTER_SIZE, MAX_MIN_CLUSTER_SIZE); + mMaxClusterSize = Utils.clamp(mMaxClusterSize, MIN_MAX_CLUSTER_SIZE, MAX_MAX_CLUSTER_SIZE); + } + + private void compute(SmallItem currentItem) { + if (currentItem != null) { + int numClusters = mClusters.size(); + int numCurrClusterItems = mCurrCluster.size(); + boolean geographicallySeparateItem = false; + boolean itemAddedToCurrentCluster = false; + + // Determine if this item should go in the current cluster or be the + // start of a new cluster. + if (numCurrClusterItems == 0) { + mCurrCluster.addItem(currentItem); + } else { + SmallItem prevItem = mCurrCluster.getLastItem(); + if (isGeographicallySeparated(prevItem, currentItem)) { + mClusters.add(mCurrCluster); + geographicallySeparateItem = true; + } else if (numCurrClusterItems > mMaxClusterSize) { + splitAndAddCurrentCluster(); + } else if (timeDistance(prevItem, currentItem) < mClusterSplitTime) { + mCurrCluster.addItem(currentItem); + itemAddedToCurrentCluster = true; + } else if (numClusters > 0 && numCurrClusterItems < mMinClusterSize + && !mCurrCluster.mGeographicallySeparatedFromPrevCluster) { + mergeAndAddCurrentCluster(); + } else { + mClusters.add(mCurrCluster); + } + + // Creating a new cluster and adding the current item to it. + if (!itemAddedToCurrentCluster) { + mCurrCluster = new Cluster(); + if (geographicallySeparateItem) { + mCurrCluster.mGeographicallySeparatedFromPrevCluster = true; + } + mCurrCluster.addItem(currentItem); + } + } + } else { + if (mCurrCluster.size() > 0) { + int numClusters = mClusters.size(); + int numCurrClusterItems = mCurrCluster.size(); + + // The last cluster may potentially be too big or too small. + if (numCurrClusterItems > mMaxClusterSize) { + splitAndAddCurrentCluster(); + } else if (numClusters > 0 && numCurrClusterItems < mMinClusterSize + && !mCurrCluster.mGeographicallySeparatedFromPrevCluster) { + mergeAndAddCurrentCluster(); + } else { + mClusters.add(mCurrCluster); + } + mCurrCluster = new Cluster(); + } + } + } + + private void splitAndAddCurrentCluster() { + ArrayList<SmallItem> currClusterItems = mCurrCluster.getItems(); + int numCurrClusterItems = mCurrCluster.size(); + int secondPartitionStartIndex = getPartitionIndexForCurrentCluster(); + if (secondPartitionStartIndex != -1) { + Cluster partitionedCluster = new Cluster(); + for (int j = 0; j < secondPartitionStartIndex; j++) { + partitionedCluster.addItem(currClusterItems.get(j)); + } + mClusters.add(partitionedCluster); + partitionedCluster = new Cluster(); + for (int j = secondPartitionStartIndex; j < numCurrClusterItems; j++) { + partitionedCluster.addItem(currClusterItems.get(j)); + } + mClusters.add(partitionedCluster); + } else { + mClusters.add(mCurrCluster); + } + } + + private int getPartitionIndexForCurrentCluster() { + int partitionIndex = -1; + float largestChange = MIN_PARTITION_CHANGE_FACTOR; + ArrayList<SmallItem> currClusterItems = mCurrCluster.getItems(); + int numCurrClusterItems = mCurrCluster.size(); + int minClusterSize = mMinClusterSize; + + // Could be slightly more efficient here but this code seems cleaner. + if (numCurrClusterItems > minClusterSize + 1) { + for (int i = minClusterSize; i < numCurrClusterItems - minClusterSize; i++) { + SmallItem prevItem = currClusterItems.get(i - 1); + SmallItem currItem = currClusterItems.get(i); + SmallItem nextItem = currClusterItems.get(i + 1); + + long timeNext = nextItem.dateInMs; + long timeCurr = currItem.dateInMs; + long timePrev = prevItem.dateInMs; + + if (timeNext == 0 || timeCurr == 0 || timePrev == 0) continue; + + long diff1 = Math.abs(timeNext - timeCurr); + long diff2 = Math.abs(timeCurr - timePrev); + + float change = Math.max(diff1 / (diff2 + 0.01f), diff2 / (diff1 + 0.01f)); + if (change > largestChange) { + if (timeDistance(currItem, prevItem) > mLargeClusterSplitTime) { + partitionIndex = i; + largestChange = change; + } else if (timeDistance(nextItem, currItem) > mLargeClusterSplitTime) { + partitionIndex = i + 1; + largestChange = change; + } + } + } + } + return partitionIndex; + } + + private void mergeAndAddCurrentCluster() { + int numClusters = mClusters.size(); + Cluster prevCluster = mClusters.get(numClusters - 1); + ArrayList<SmallItem> currClusterItems = mCurrCluster.getItems(); + int numCurrClusterItems = mCurrCluster.size(); + if (prevCluster.size() < mMinClusterSize) { + for (int i = 0; i < numCurrClusterItems; i++) { + prevCluster.addItem(currClusterItems.get(i)); + } + mClusters.set(numClusters - 1, prevCluster); + } else { + mClusters.add(mCurrCluster); + } + } + + // Returns true if a, b are sufficiently geographically separated. + private static boolean isGeographicallySeparated(SmallItem itemA, SmallItem itemB) { + if (!GalleryUtils.isValidLocation(itemA.lat, itemA.lng) + || !GalleryUtils.isValidLocation(itemB.lat, itemB.lng)) { + return false; + } + + double distance = GalleryUtils.fastDistanceMeters( + Math.toRadians(itemA.lat), + Math.toRadians(itemA.lng), + Math.toRadians(itemB.lat), + Math.toRadians(itemB.lng)); + return (GalleryUtils.toMile(distance) > GEOGRAPHIC_DISTANCE_CUTOFF_IN_MILES); + } + + // Returns the time interval between the two items in milliseconds. + private static long timeDistance(SmallItem a, SmallItem b) { + return Math.abs(a.dateInMs - b.dateInMs); + } +} + +class SmallItem { + Path path; + long dateInMs; + double lat, lng; +} + +class Cluster { + @SuppressWarnings("unused") + private static final String TAG = "Cluster"; + private static final String MMDDYY_FORMAT = "MMddyy"; + + // This is for TimeClustering only. + public boolean mGeographicallySeparatedFromPrevCluster = false; + + private ArrayList<SmallItem> mItems = new ArrayList<SmallItem>(); + + public Cluster() { + } + + public void addItem(SmallItem item) { + mItems.add(item); + } + + public int size() { + return mItems.size(); + } + + public SmallItem getLastItem() { + int n = mItems.size(); + return (n == 0) ? null : mItems.get(n - 1); + } + + public ArrayList<SmallItem> getItems() { + return mItems; + } + + public String generateCaption(Context context) { + int n = mItems.size(); + long minTimestamp = 0; + long maxTimestamp = 0; + + for (int i = 0; i < n; i++) { + long t = mItems.get(i).dateInMs; + if (t == 0) continue; + if (minTimestamp == 0) { + minTimestamp = maxTimestamp = t; + } else { + minTimestamp = Math.min(minTimestamp, t); + maxTimestamp = Math.max(maxTimestamp, t); + } + } + if (minTimestamp == 0) return ""; + + String caption; + String minDay = DateFormat.format(MMDDYY_FORMAT, minTimestamp) + .toString(); + String maxDay = DateFormat.format(MMDDYY_FORMAT, maxTimestamp) + .toString(); + + if (minDay.substring(4).equals(maxDay.substring(4))) { + // The items are from the same year - show at least as + // much granularity as abbrev_all allows. + caption = DateUtils.formatDateRange(context, minTimestamp, + maxTimestamp, DateUtils.FORMAT_ABBREV_ALL); + + // Get a more granular date range string if the min and + // max timestamp are on the same day and from the + // current year. + if (minDay.equals(maxDay)) { + int flags = DateUtils.FORMAT_ABBREV_MONTH | DateUtils.FORMAT_SHOW_DATE; + // Contains the year only if the date does not + // correspond to the current year. + String dateRangeWithOptionalYear = DateUtils.formatDateTime( + context, minTimestamp, flags); + String dateRangeWithYear = DateUtils.formatDateTime( + context, minTimestamp, flags | DateUtils.FORMAT_SHOW_YEAR); + if (!dateRangeWithOptionalYear.equals(dateRangeWithYear)) { + // This means both dates are from the same year + // - show the time. + // Not enough room to display the time range. + // Pick the mid-point. + long midTimestamp = (minTimestamp + maxTimestamp) / 2; + caption = DateUtils.formatDateRange(context, midTimestamp, + midTimestamp, DateUtils.FORMAT_SHOW_TIME | flags); + } + } + } else { + // The items are not from the same year - only show + // month and year. + int flags = DateUtils.FORMAT_NO_MONTH_DAY + | DateUtils.FORMAT_ABBREV_MONTH | DateUtils.FORMAT_SHOW_DATE; + caption = DateUtils.formatDateRange(context, minTimestamp, + maxTimestamp, flags); + } + + return caption; + } +} |