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