summaryrefslogtreecommitdiffstats
path: root/src/com/android/gallery3d/data/TimeClustering.java
diff options
context:
space:
mode:
Diffstat (limited to 'src/com/android/gallery3d/data/TimeClustering.java')
-rw-r--r--src/com/android/gallery3d/data/TimeClustering.java439
1 files changed, 0 insertions, 439 deletions
diff --git a/src/com/android/gallery3d/data/TimeClustering.java b/src/com/android/gallery3d/data/TimeClustering.java
deleted file mode 100644
index 35cbab1ee..000000000
--- a/src/com/android/gallery3d/data/TimeClustering.java
+++ /dev/null
@@ -1,439 +0,0 @@
-/*
- * 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 android.content.Context;
-import android.text.format.DateFormat;
-import android.text.format.DateUtils;
-
-import com.android.gallery3d.common.Utils;
-import com.android.gallery3d.util.GalleryUtils;
-
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.Comparator;
-
-public class TimeClustering extends Clustering {
- @SuppressWarnings("unused")
- 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> {
- @Override
- 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() {
- @Override
- 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;
- }
-}