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