16012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu/* 26012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * Copyright (C) 2015 The Android Open Source Project 36012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * 46012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * Licensed under the Apache License, Version 2.0 (the "License"); 56012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * you may not use this file except in compliance with the License. 66012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * You may obtain a copy of the License at 76012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * 86012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * http://www.apache.org/licenses/LICENSE-2.0 96012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * 106012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * Unless required by applicable law or agreed to in writing, software 116012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * distributed under the License is distributed on an "AS IS" BASIS, 126012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 136012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * See the License for the specific language governing permissions and 146012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * limitations under the License 156012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu */ 166012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu 176012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fupackage com.android.providers.contacts.aggregation.util; 186012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu 19517d590dc73e5efcf7c94e2431faec2473924ca2Makoto Onukiimport android.util.ArrayMap; 20517d590dc73e5efcf7c94e2431faec2473924ca2Makoto Onukiimport android.util.ArraySet; 21517d590dc73e5efcf7c94e2431faec2473924ca2Makoto Onuki 226012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fuimport com.google.common.annotations.VisibleForTesting; 236012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fuimport com.google.common.collect.Iterables; 246012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fuimport com.google.common.collect.Multimap; 256012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu 266012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fuimport java.util.Map; 276012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fuimport java.util.Set; 286012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu 296012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu/** 306012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * Helper class for contacts aggregation. 316012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu */ 326012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fupublic class ContactAggregatorHelper { 336012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu 346012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu private ContactAggregatorHelper() {} 356012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu 366012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu /** 376012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * If two connected components have disjoint accounts, merge them. 386012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * If there is any uncertainty, keep them separate. 396012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu */ 406012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu @VisibleForTesting 416012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu public static void mergeComponentsWithDisjointAccounts(Set<Set<Long>> connectedRawContactSets, 426012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu Map<Long, Long> rawContactsToAccounts) { 436012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu // Index to rawContactIds mapping 44517d590dc73e5efcf7c94e2431faec2473924ca2Makoto Onuki final Map<Integer, Set<Long>> rawContactIds = new ArrayMap<>(); 456012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu // AccountId to indices mapping 46517d590dc73e5efcf7c94e2431faec2473924ca2Makoto Onuki final Map<Long, Set<Integer>> accounts = new ArrayMap<>(); 476012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu 486012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu int index = 0; 496012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu for (Set<Long> rIds : connectedRawContactSets) { 506012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu rawContactIds.put(index, rIds); 516012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu for (Long rId : rIds) { 526012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu long acctId = rawContactsToAccounts.get(rId); 536012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu Set<Integer> s = accounts.get(acctId); 546012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu if (s == null) { 55517d590dc73e5efcf7c94e2431faec2473924ca2Makoto Onuki s = new ArraySet<Integer>(); 566012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu } 576012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu s.add(index); 586012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu accounts.put(acctId, s); 596012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu } 606012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu index++; 616012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu } 62d0d961e19f19704f7967dadf5be61fe6273a1d32Zheng Fu 636012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu connectedRawContactSets.clear(); 646012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu for (Long accountId : accounts.keySet()) { 656012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu final Set<Integer> s = accounts.get(accountId); 666012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu if (s.size() > 1) { 676012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu for (Integer i : s) { 686012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu final Set<Long> rIdSet = rawContactIds.get(i); 69d0d961e19f19704f7967dadf5be61fe6273a1d32Zheng Fu if (rIdSet != null && !rIdSet.isEmpty()) { 70876a6a921e532b6c1ca653e4c52c1819a75ff3beZheng Fu connectedRawContactSets.add(rIdSet); 716012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu rawContactIds.remove(i); 726012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu } 736012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu } 74d0d961e19f19704f7967dadf5be61fe6273a1d32Zheng Fu } 75d0d961e19f19704f7967dadf5be61fe6273a1d32Zheng Fu } 76d0d961e19f19704f7967dadf5be61fe6273a1d32Zheng Fu 77517d590dc73e5efcf7c94e2431faec2473924ca2Makoto Onuki final Set<Long> mergedSet = new ArraySet<>(); 78d0d961e19f19704f7967dadf5be61fe6273a1d32Zheng Fu for (Long accountId : accounts.keySet()) { 79d0d961e19f19704f7967dadf5be61fe6273a1d32Zheng Fu final Set<Integer> s = accounts.get(accountId); 80d0d961e19f19704f7967dadf5be61fe6273a1d32Zheng Fu if (s.size() == 1) { 816012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu Set<Long> ids = rawContactIds.get(Iterables.getOnlyElement(s)); 82d0d961e19f19704f7967dadf5be61fe6273a1d32Zheng Fu if (ids != null && !ids.isEmpty()) { 836012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu mergedSet.addAll(ids); 846012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu } 856012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu } 866012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu } 876012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu connectedRawContactSets.add(mergedSet); 886012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu } 896012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu 906012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu /** 916012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * Given a set of raw contact ids {@code rawContactIdSet} and the connection among them 926012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu * {@code matchingRawIdPairs}, find the connected components. 936012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu */ 946012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu @VisibleForTesting 956012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu public static Set<Set<Long>> findConnectedComponents(Set<Long> rawContactIdSet, Multimap<Long, 966012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu Long> matchingRawIdPairs) { 97517d590dc73e5efcf7c94e2431faec2473924ca2Makoto Onuki Set<Set<Long>> connectedRawContactSets = new ArraySet<>(); 98517d590dc73e5efcf7c94e2431faec2473924ca2Makoto Onuki Set<Long> visited = new ArraySet<>(); 996012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu for (Long id : rawContactIdSet) { 1006012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu if (!visited.contains(id)) { 101517d590dc73e5efcf7c94e2431faec2473924ca2Makoto Onuki Set<Long> set = new ArraySet<>(); 1026012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu findConnectedComponentForRawContact(matchingRawIdPairs, visited, id, set); 1036012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu connectedRawContactSets.add(set); 1046012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu } 1056012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu } 1066012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu return connectedRawContactSets; 1076012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu } 1086012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu 1096012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu private static void findConnectedComponentForRawContact(Multimap<Long, Long> connections, 1106012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu Set<Long> visited, Long rawContactId, Set<Long> results) { 1116012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu visited.add(rawContactId); 1126012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu results.add(rawContactId); 1136012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu for (long match : connections.get(rawContactId)) { 1146012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu if (!visited.contains(match)) { 1156012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu findConnectedComponentForRawContact(connections, visited, match, results); 1166012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu } 1176012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu } 1186012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu } 1196012b85f0eef8ebcfcb73b72216d17893804d4eaZheng Fu} 120