| 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 |