1 /* 2 * Copyright (C) 2009 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.contacts.common; 18 19 import java.util.Iterator; 20 import java.util.List; 21 22 /** 23 * Class used for collapsing data items into groups of similar items. The data items that should be 24 * collapsible should implement the Collapsible interface. The class also contains a utility 25 * function that takes an ArrayList of items and returns a list of the same items collapsed into 26 * groups. 27 */ 28 public final class Collapser { 29 30 /* 31 * This utility class cannot be instantiated. 32 */ 33 private Collapser() {} 34 35 /* 36 * The Collapser uses an n^2 algorithm so we don't want it to run on 37 * lists beyond a certain size. This specifies the maximum size to collapse. 38 */ 39 private static final int MAX_LISTSIZE_TO_COLLAPSE = 20; 40 41 /* 42 * Interface implemented by data types that can be collapsed into groups of similar data. This 43 * can be used for example to collapse similar contact data items into a single item. 44 */ 45 public interface Collapsible<T> { 46 public void collapseWith(T t); 47 public boolean shouldCollapseWith(T t); 48 } 49 50 /** 51 * Collapses a list of Collapsible items into a list of collapsed items. Items are collapsed 52 * if {@link Collapsible#shouldCollapseWith(Object)} returns true, and are collapsed 53 * through the {@Link Collapsible#collapseWith(Object)} function implemented by the data item. 54 * 55 * @param list List of Objects of type <T extends Collapsible<T>> to be collapsed. 56 */ 57 public static <T extends Collapsible<T>> void collapseList(List<T> list) { 58 59 int listSize = list.size(); 60 // The algorithm below is n^2 so don't run on long lists 61 if (listSize > MAX_LISTSIZE_TO_COLLAPSE) { 62 return; 63 } 64 65 for (int i = 0; i < listSize; i++) { 66 T iItem = list.get(i); 67 if (iItem != null) { 68 for (int j = i + 1; j < listSize; j++) { 69 T jItem = list.get(j); 70 if (jItem != null) { 71 if (iItem.shouldCollapseWith(jItem)) { 72 iItem.collapseWith(jItem); 73 list.set(j, null); 74 } else if (jItem.shouldCollapseWith(iItem)) { 75 jItem.collapseWith(iItem); 76 list.set(i, null); 77 break; 78 } 79 } 80 } 81 } 82 } 83 84 // Remove the null items 85 Iterator<T> itr = list.iterator(); 86 while (itr.hasNext()) { 87 if (itr.next() == null) { 88 itr.remove(); 89 } 90 } 91 92 } 93 } 94