OLD | NEW |
1 // Copyright 2015 The Chromium Authors. All rights reserved. | 1 // Copyright 2015 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #import "ios/chrome/browser/ui/tab_switcher/tab_switcher_utils.h" | 5 #import "ios/chrome/browser/ui/tab_switcher/tab_switcher_utils.h" |
6 | 6 |
7 #import <UIKit/UIKit.h> | 7 #import <UIKit/UIKit.h> |
8 | 8 |
9 #include "base/logging.h" | 9 #include "base/logging.h" |
10 #include "base/mac/scoped_nsobject.h" | 10 #include "base/mac/scoped_nsobject.h" |
11 #include "components/browser_sync/profile_sync_service.h" | 11 #include "components/browser_sync/profile_sync_service.h" |
12 #include "components/sync/driver/sync_service.h" | 12 #include "components/sync/driver/sync_service.h" |
13 #include "components/sync_sessions/open_tabs_ui_delegate.h" | 13 #include "components/sync_sessions/open_tabs_ui_delegate.h" |
14 #include "ios/chrome/browser/browser_state/chrome_browser_state.h" | 14 #include "ios/chrome/browser/browser_state/chrome_browser_state.h" |
15 #import "ios/chrome/browser/favicon/favicon_loader.h" | 15 #import "ios/chrome/browser/favicon/favicon_loader.h" |
16 #include "ios/chrome/browser/favicon/ios_chrome_favicon_loader_factory.h" | 16 #include "ios/chrome/browser/favicon/ios_chrome_favicon_loader_factory.h" |
17 #include "ios/chrome/browser/sync/ios_chrome_profile_sync_service_factory.h" | 17 #include "ios/chrome/browser/sync/ios_chrome_profile_sync_service_factory.h" |
18 #import "ios/chrome/browser/ui/uikit_ui_util.h" | 18 #import "ios/chrome/browser/ui/uikit_ui_util.h" |
19 #include "ios/chrome/grit/ios_theme_resources.h" | 19 #include "ios/chrome/grit/ios_theme_resources.h" |
20 | 20 |
21 namespace { | 21 namespace { |
22 | 22 |
23 UIImage* DefaultFaviconImage() { | 23 UIImage* DefaultFaviconImage() { |
24 return NativeImage(IDR_IOS_OMNIBOX_HTTP); | 24 return NativeImage(IDR_IOS_OMNIBOX_HTTP); |
25 } | 25 } |
26 | 26 |
27 enum BacktrackOperation { NOTHING, SUBSTITUTION, DELETION, INSERTION }; | 27 enum BacktrackOperation { NOTHING, SUBSTITUTION, DELETION, INSERTION }; |
28 | 28 |
29 BacktrackOperation BacktrackOperationInCostMatrix( | 29 BacktrackOperation BacktrackOperationInCostMatrix( |
30 std::vector<std::vector<int>> const& costMatrix, | 30 std::vector<std::vector<int>> const& cost_matrix, |
31 size_t finalIndex, | 31 size_t final_index, |
32 size_t initialIndex) { | 32 size_t initial_index) { |
33 DCHECK(finalIndex || initialIndex); | 33 DCHECK(final_index || initial_index); |
34 DCHECK(initialIndex < costMatrix.size()); | 34 DCHECK(initial_index < cost_matrix.size()); |
35 DCHECK(finalIndex < costMatrix[initialIndex].size()); | 35 DCHECK(final_index < cost_matrix[initial_index].size()); |
36 | 36 |
37 if (finalIndex == 0) | 37 if (final_index == 0) |
38 return DELETION; | 38 return DELETION; |
39 if (initialIndex == 0) | 39 if (initial_index == 0) |
40 return INSERTION; | 40 return INSERTION; |
41 | 41 |
42 int currentCost = costMatrix[initialIndex][finalIndex]; | 42 int currentCost = cost_matrix[initial_index][final_index]; |
43 | 43 |
44 int costBeforeInsertion = costMatrix[initialIndex][finalIndex - 1]; | 44 int costBeforeInsertion = cost_matrix[initial_index][final_index - 1]; |
45 if (costBeforeInsertion + 1 == currentCost) | 45 if (costBeforeInsertion + 1 == currentCost) |
46 return INSERTION; | 46 return INSERTION; |
47 | 47 |
48 int costBeforeDeletion = costMatrix[initialIndex - 1][finalIndex]; | 48 int costBeforeDeletion = cost_matrix[initial_index - 1][final_index]; |
49 if (costBeforeDeletion + 1 == currentCost) | 49 if (costBeforeDeletion + 1 == currentCost) |
50 return DELETION; | 50 return DELETION; |
51 | 51 |
52 int costBeforeSubstitution = costMatrix[initialIndex - 1][finalIndex - 1]; | 52 int costBeforeSubstitution = cost_matrix[initial_index - 1][final_index - 1]; |
53 if (costBeforeSubstitution == currentCost) | 53 if (costBeforeSubstitution == currentCost) |
54 return NOTHING; | 54 return NOTHING; |
55 | 55 |
56 return SUBSTITUTION; | 56 return SUBSTITUTION; |
57 } | 57 } |
58 | 58 |
59 } // namespace | 59 } // namespace |
60 | 60 |
61 void TabSwitcherGetFavicon(GURL const& url, | 61 void TabSwitcherGetFavicon(GURL const& url, |
62 ios::ChromeBrowserState* browser_state, | 62 ios::ChromeBrowserState* browser_state, |
63 TabSwitcherFaviconGetterCompletionBlock block) { | 63 TabSwitcherFaviconGetterCompletionBlock block) { |
64 DCHECK(browser_state); | 64 DCHECK(browser_state); |
65 syncer::SyncService* sync_service = | 65 syncer::SyncService* sync_service = |
66 IOSChromeProfileSyncServiceFactory::GetForBrowserState(browser_state); | 66 IOSChromeProfileSyncServiceFactory::GetForBrowserState(browser_state); |
67 sync_sessions::OpenTabsUIDelegate* open_tabs = | 67 sync_sessions::OpenTabsUIDelegate* open_tabs = |
68 sync_service ? sync_service->GetOpenTabsUIDelegate() : NULL; | 68 sync_service ? sync_service->GetOpenTabsUIDelegate() : NULL; |
69 scoped_refptr<base::RefCountedMemory> favicon; | 69 scoped_refptr<base::RefCountedMemory> favicon; |
70 if (open_tabs && | 70 if (open_tabs && |
71 open_tabs->GetSyncedFaviconForPageURL(url.spec(), &favicon)) { | 71 open_tabs->GetSyncedFaviconForPageURL(url.spec(), &favicon)) { |
72 dispatch_queue_t queue = | 72 dispatch_queue_t queue = |
73 dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0); | 73 dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0); |
74 dispatch_async(queue, ^{ | 74 dispatch_async(queue, ^{ |
75 NSData* pngData = | 75 NSData* png_data = |
76 [NSData dataWithBytes:favicon->front() length:favicon->size()]; | 76 [NSData dataWithBytes:favicon->front() length:favicon->size()]; |
77 base::scoped_nsobject<UIImage> image( | 77 base::scoped_nsobject<UIImage> image( |
78 [[UIImage alloc] initWithData:pngData]); | 78 [[UIImage alloc] initWithData:png_data]); |
79 dispatch_async(dispatch_get_main_queue(), ^{ | 79 dispatch_async(dispatch_get_main_queue(), ^{ |
80 // |UIImage initWithData:| may return nil. | 80 // |UIImage initWithData:| may return nil. |
81 if (image) { | 81 if (image) { |
82 block(image); | 82 block(image); |
83 } else { | 83 } else { |
84 block(DefaultFaviconImage()); | 84 block(DefaultFaviconImage()); |
85 } | 85 } |
86 }); | 86 }); |
87 }); | 87 }); |
88 block(DefaultFaviconImage()); | 88 block(DefaultFaviconImage()); |
(...skipping 24 matching lines...) Expand all Loading... |
113 DCHECK(deletions); | 113 DCHECK(deletions); |
114 DCHECK(insertions); | 114 DCHECK(insertions); |
115 DCHECK_EQ(substitutions->size(), 0UL); | 115 DCHECK_EQ(substitutions->size(), 0UL); |
116 DCHECK_EQ(deletions->size(), 0UL); | 116 DCHECK_EQ(deletions->size(), 0UL); |
117 DCHECK_EQ(insertions->size(), 0UL); | 117 DCHECK_EQ(insertions->size(), 0UL); |
118 | 118 |
119 // The substitutions/deletions/insertions are computed using the Levenshtein | 119 // The substitutions/deletions/insertions are computed using the Levenshtein |
120 // algorithm. | 120 // algorithm. |
121 // https://en.wikipedia.org/wiki/Levenshtein_distance | 121 // https://en.wikipedia.org/wiki/Levenshtein_distance |
122 | 122 |
123 const size_t initialSize = initial.size() + 1; | 123 const size_t initial_size = initial.size() + 1; |
124 const size_t finalSize = final.size() + 1; | 124 const size_t final_size = final.size() + 1; |
125 | 125 |
126 std::vector<std::vector<int>> costMatrix(initialSize, | 126 std::vector<std::vector<int>> cost_matrix(initial_size, |
127 std::vector<int>(finalSize)); | 127 std::vector<int>(final_size)); |
128 | 128 |
129 for (size_t i = 1; i < initialSize; i++) | 129 for (size_t i = 1; i < initial_size; i++) |
130 costMatrix[i][0] = i; | 130 cost_matrix[i][0] = i; |
131 for (size_t i = 1; i < finalSize; i++) | 131 for (size_t i = 1; i < final_size; i++) |
132 costMatrix[0][i] = i; | 132 cost_matrix[0][i] = i; |
133 | 133 |
134 // Step 1: Generate cost matrix. | 134 // Step 1: Generate cost matrix. |
135 for (size_t initialIndex = 1; initialIndex < initialSize; initialIndex++) { | 135 for (size_t initial_index = 1; initial_index < initial_size; |
136 for (size_t finalIndex = 1; finalIndex < finalSize; finalIndex++) { | 136 initial_index++) { |
137 if (initial[initialIndex - 1] == final[finalIndex - 1]) { | 137 for (size_t final_index = 1; final_index < final_size; final_index++) { |
138 costMatrix[initialIndex][finalIndex] = | 138 if (initial[initial_index - 1] == final[final_index - 1]) { |
139 costMatrix[initialIndex - 1][finalIndex - 1]; | 139 cost_matrix[initial_index][final_index] = |
| 140 cost_matrix[initial_index - 1][final_index - 1]; |
140 } else { | 141 } else { |
141 int costAfterSubstitution = | 142 int cost_after_substitution = |
142 costMatrix[initialIndex - 1][finalIndex - 1] + 1; | 143 cost_matrix[initial_index - 1][final_index - 1] + 1; |
143 int costAfterInsertion = costMatrix[initialIndex][finalIndex - 1] + 1; | 144 int cost_after_insertion = |
144 int costAfterDeletion = costMatrix[initialIndex - 1][finalIndex] + 1; | 145 cost_matrix[initial_index][final_index - 1] + 1; |
145 costMatrix[initialIndex][finalIndex] = | 146 int cost_after_deletion = |
146 std::min(std::min(costAfterDeletion, costAfterInsertion), | 147 cost_matrix[initial_index - 1][final_index] + 1; |
147 costAfterSubstitution); | 148 cost_matrix[initial_index][final_index] = |
| 149 std::min(std::min(cost_after_deletion, cost_after_insertion), |
| 150 cost_after_substitution); |
148 } | 151 } |
149 } | 152 } |
150 } | 153 } |
151 | 154 |
152 // Step 2: Backtrack to find the operations (deletion, insertion, | 155 // Step 2: Backtrack to find the operations (deletion, insertion, |
153 // substitution). | 156 // substitution). |
154 size_t initialIndex = initialSize - 1; | 157 size_t initial_index = initial_size - 1; |
155 size_t finalIndex = finalSize - 1; | 158 size_t final_index = final_size - 1; |
156 while (initialIndex != 0 || finalIndex != 0) { | 159 while (initial_index != 0 || final_index != 0) { |
157 BacktrackOperation op = | 160 BacktrackOperation op = |
158 BacktrackOperationInCostMatrix(costMatrix, finalIndex, initialIndex); | 161 BacktrackOperationInCostMatrix(cost_matrix, final_index, initial_index); |
159 switch (op) { | 162 switch (op) { |
160 case SUBSTITUTION: | 163 case SUBSTITUTION: |
161 finalIndex--; | 164 final_index--; |
162 initialIndex--; | 165 initial_index--; |
163 // The substitution is relative to |initial|. | 166 // The substitution is relative to |initial|. |
164 substitutions->push_back(initialIndex); | 167 substitutions->push_back(initial_index); |
165 break; | 168 break; |
166 case DELETION: | 169 case DELETION: |
167 initialIndex--; | 170 initial_index--; |
168 // The deletion is relative to |initial|. | 171 // The deletion is relative to |initial|. |
169 deletions->push_back(initialIndex); | 172 deletions->push_back(initial_index); |
170 break; | 173 break; |
171 case INSERTION: | 174 case INSERTION: |
172 finalIndex--; | 175 final_index--; |
173 // The insertion is relative to |final|. | 176 // The insertion is relative to |final|. |
174 insertions->push_back(finalIndex); | 177 insertions->push_back(final_index); |
175 break; | 178 break; |
176 case NOTHING: | 179 case NOTHING: |
177 finalIndex--; | 180 final_index--; |
178 initialIndex--; | 181 initial_index--; |
179 break; | 182 break; |
180 } | 183 } |
181 } | 184 } |
182 | 185 |
183 // The backtracking results in the indexes of the operations being stored in | 186 // The backtracking results in the indexes of the operations being stored in |
184 // decreasing order. | 187 // decreasing order. |
185 // For readability, order them in ascending value. | 188 // For readability, order them in ascending value. |
186 std::reverse(std::begin(*substitutions), std::end(*substitutions)); | 189 std::reverse(std::begin(*substitutions), std::end(*substitutions)); |
187 std::reverse(std::begin(*deletions), std::end(*deletions)); | 190 std::reverse(std::begin(*deletions), std::end(*deletions)); |
188 std::reverse(std::begin(*insertions), std::end(*insertions)); | 191 std::reverse(std::begin(*insertions), std::end(*insertions)); |
189 } | 192 } |
OLD | NEW |