src/com/android/gallery3d/data/TimeClustering.java - platform/packages/apps/Gallery2 - Git at Google

 /*
  * 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 {
     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;
     }
 }
	/*
	* 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 {
	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;
	}
	}