1 /* 2 * Copyright (C) 2015 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.providers.contacts.aggregation.util; 18 19 import android.util.ArrayMap; 20 import android.util.ArraySet; 21 22 import com.google.common.annotations.VisibleForTesting; 23 import com.google.common.collect.Iterables; 24 import com.google.common.collect.Multimap; 25 26 import java.util.Map; 27 import java.util.Set; 28 29 /** 30 * Helper class for contacts aggregation. 31 */ 32 public class ContactAggregatorHelper { 33 ContactAggregatorHelper()34 private ContactAggregatorHelper() {} 35 36 /** 37 * If two connected components have disjoint accounts, merge them. 38 * If there is any uncertainty, keep them separate. 39 */ 40 @VisibleForTesting mergeComponentsWithDisjointAccounts(Set<Set<Long>> connectedRawContactSets, Map<Long, Long> rawContactsToAccounts)41 public static void mergeComponentsWithDisjointAccounts(Set<Set<Long>> connectedRawContactSets, 42 Map<Long, Long> rawContactsToAccounts) { 43 // Index to rawContactIds mapping 44 final Map<Integer, Set<Long>> rawContactIds = new ArrayMap<>(); 45 // AccountId to indices mapping 46 final Map<Long, Set<Integer>> accounts = new ArrayMap<>(); 47 48 int index = 0; 49 for (Set<Long> rIds : connectedRawContactSets) { 50 rawContactIds.put(index, rIds); 51 for (Long rId : rIds) { 52 long acctId = rawContactsToAccounts.get(rId); 53 Set<Integer> s = accounts.get(acctId); 54 if (s == null) { 55 s = new ArraySet<Integer>(); 56 } 57 s.add(index); 58 accounts.put(acctId, s); 59 } 60 index++; 61 } 62 63 connectedRawContactSets.clear(); 64 for (Long accountId : accounts.keySet()) { 65 final Set<Integer> s = accounts.get(accountId); 66 if (s.size() > 1) { 67 for (Integer i : s) { 68 final Set<Long> rIdSet = rawContactIds.get(i); 69 if (rIdSet != null && !rIdSet.isEmpty()) { 70 connectedRawContactSets.add(rIdSet); 71 rawContactIds.remove(i); 72 } 73 } 74 } 75 } 76 77 final Set<Long> mergedSet = new ArraySet<>(); 78 for (Long accountId : accounts.keySet()) { 79 final Set<Integer> s = accounts.get(accountId); 80 if (s.size() == 1) { 81 Set<Long> ids = rawContactIds.get(Iterables.getOnlyElement(s)); 82 if (ids != null && !ids.isEmpty()) { 83 mergedSet.addAll(ids); 84 } 85 } 86 } 87 connectedRawContactSets.add(mergedSet); 88 } 89 90 /** 91 * Given a set of raw contact ids {@code rawContactIdSet} and the connection among them 92 * {@code matchingRawIdPairs}, find the connected components. 93 */ 94 @VisibleForTesting findConnectedComponents(Set<Long> rawContactIdSet, Multimap<Long, Long> matchingRawIdPairs)95 public static Set<Set<Long>> findConnectedComponents(Set<Long> rawContactIdSet, Multimap<Long, 96 Long> matchingRawIdPairs) { 97 Set<Set<Long>> connectedRawContactSets = new ArraySet<>(); 98 Set<Long> visited = new ArraySet<>(); 99 for (Long id : rawContactIdSet) { 100 if (!visited.contains(id)) { 101 Set<Long> set = new ArraySet<>(); 102 findConnectedComponentForRawContact(matchingRawIdPairs, visited, id, set); 103 connectedRawContactSets.add(set); 104 } 105 } 106 return connectedRawContactSets; 107 } 108 findConnectedComponentForRawContact(Multimap<Long, Long> connections, Set<Long> visited, Long rawContactId, Set<Long> results)109 private static void findConnectedComponentForRawContact(Multimap<Long, Long> connections, 110 Set<Long> visited, Long rawContactId, Set<Long> results) { 111 visited.add(rawContactId); 112 results.add(rawContactId); 113 for (long match : connections.get(rawContactId)) { 114 if (!visited.contains(match)) { 115 findConnectedComponentForRawContact(connections, visited, match, results); 116 } 117 } 118 } 119 } 120