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