aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--Source/SPGotoDatabaseController.m70
-rw-r--r--Source/SPStringAdditions.h4
-rw-r--r--Source/SPStringAdditions.m34
-rw-r--r--UnitTests/SPStringAdditionsTests.m55
4 files changed, 140 insertions, 23 deletions
diff --git a/Source/SPGotoDatabaseController.m b/Source/SPGotoDatabaseController.m
index b48b77b7..330a240a 100644
--- a/Source/SPGotoDatabaseController.m
+++ b/Source/SPGotoDatabaseController.m
@@ -49,10 +49,14 @@
- (IBAction)searchChanged:(id)sender;
- (IBAction)toggleWordSearch:(id)sender;
-- (BOOL)qualifiesForWordSearch:(NSString *)s;
- (BOOL)qualifiesForWordSearch; //takes s from searchField
@end
+static BOOL StringQualifiesForWordSearch(NSString *s);
+static NSUInteger CountSubMatches(NSAttributedString *s);
+
+#pragma mark -
+
@implementation SPGotoDatabaseController
@synthesize allowCustomNames;
@@ -112,11 +116,17 @@
//always add the search string to the end of the list (in case the user
//wants to switch to a DB not in the list) unless there was an exact match
if ([self allowCustomNames] && !exactMatch) {
- NSMutableAttributedString *searchValue = [[NSMutableAttributedString alloc] initWithString:newFilter];
+ // remove quotes if any
+ if(StringQualifiesForWordSearch(newFilter))
+ newFilter = [newFilter substringWithRange:NSMakeRange(1, [newFilter length]-2)];
+
+ if([newFilter length]) {
+ NSMutableAttributedString *searchValue = [[NSMutableAttributedString alloc] initWithString:newFilter];
- [searchValue applyFontTraits:NSItalicFontMask range:NSMakeRange(0, [newFilter length])];
+ [searchValue applyFontTraits:NSItalicFontMask range:NSMakeRange(0, [newFilter length])];
- [filteredList addObject:[searchValue autorelease]];
+ [filteredList addObject:[searchValue autorelease]];
+ }
}
}
@@ -209,8 +219,10 @@
NSStringCompareOptions opts = NSCaseInsensitiveSearch|NSDiacriticInsensitiveSearch|NSWidthInsensitiveSearch;
+ BOOL useWordSearch = StringQualifiesForWordSearch(filter);
+
// interpret a quoted string as 'looking for exact submachtes only'
- if([self qualifiesForWordSearch:filter]) {
+ if(useWordSearch) {
//remove quotes for matching
filter = [filter substringWithRange:NSMakeRange(1, [filter length]-2)];
@@ -261,17 +273,33 @@
}
}
+ //sort the filtered list
+ [filteredList sortUsingComparator:^NSComparisonResult(id obj1, id obj2) {
+ // word search produces only 1 match, skip.
+ if(!useWordSearch) {
+ // All the items are NSAttributedStrings.
+ // First we want to sort by number of match groups.
+ // Less match groups -> better result:
+ // Search string: abc
+ // Matches: schema_abc, tablecloth
+ // => First only has 1 match group, is more likely to be the desired result
+ NSUInteger mgc1 = CountSubMatches(obj1);
+ NSUInteger mgc2 = CountSubMatches(obj2);
+ if(mgc1 < mgc2)
+ return NSOrderedAscending;
+ if(mgc2 > mgc1)
+ return NSOrderedDescending;
+ }
+ // For strings with the same number of match groups we just sort alphabetically
+ return [[(NSAttributedString *)obj1 string] compare:[(NSAttributedString *)obj2 string]];
+ }];
+
[attrs release];
}
-- (BOOL)qualifiesForWordSearch:(NSString *)s
-{
- return (s && ([s length] > 1) && (([s hasPrefix:@"\""] && [s hasSuffix:@"\""]) || ([s hasPrefix:@"'"] && [s hasSuffix:@"'"])));
-}
-
- (BOOL)qualifiesForWordSearch
{
- return [self qualifiesForWordSearch:[searchField stringValue]];
+ return StringQualifiesForWordSearch([searchField stringValue]);
}
#pragma mark -
@@ -350,3 +378,23 @@
}
@end
+
+#pragma mark -
+
+BOOL StringQualifiesForWordSearch(NSString *s)
+{
+ return (s && ([s length] > 1) && (([s hasPrefix:@"\""] && [s hasSuffix:@"\""]) || ([s hasPrefix:@"'"] && [s hasSuffix:@"'"])));
+}
+
+NSUInteger CountSubMatches(NSAttributedString *s)
+{
+ __block NSUInteger matches = 0;
+ [s enumerateAttribute:NSBackgroundColorAttributeName
+ inRange:NSMakeRange(0, [s length])
+ options:0
+ usingBlock:^(id value, NSRange range, BOOL *stop) {
+ if(value)
+ matches++;
+ }];
+ return matches;
+}
diff --git a/Source/SPStringAdditions.h b/Source/SPStringAdditions.h
index 5f1c0e6d..de6d8377 100644
--- a/Source/SPStringAdditions.h
+++ b/Source/SPStringAdditions.h
@@ -88,6 +88,10 @@ static inline id NSMutableAttributedStringAttributeAtIndex(NSMutableAttributedSt
* Namely the following options will be applied when matching:
* NSCaseInsensitiveSearch|NSDiacriticInsensitiveSearch|NSWidthInsensitiveSearch
* Additionaly this method might match even when it should not.
+ * A regular substring test is always included. Therefore looking e.g. for "abc" in
+ * "axbxabc" would match as (axbx,"abc") and NOT as ("a",x,"b",xab,"c").
+ * Partial submatches will likewise be optimized to return as few matches as possible.
+ * E.g. ".123" in "a._1_12_123" will return (a,".",_1_12_,"123") NOT (a,".",_,"1",_1,"2",_12,"3")
*
* @param other String to match against self
* @param submatches Pass the pointer to a variable that will be set to an NSArray *
diff --git a/Source/SPStringAdditions.m b/Source/SPStringAdditions.m
index 26de14d7..f8aeb296 100644
--- a/Source/SPStringAdditions.m
+++ b/Source/SPStringAdditions.m
@@ -535,9 +535,39 @@ static NSInteger _smallestOf(NSInteger a, NSInteger b, NSInteger c);
tmpMatchStore[mergeTarget] = this;
}
}
+ matchCount = mergeTarget+1;
- NSMutableArray *combinedArray = [NSMutableArray arrayWithCapacity:mergeTarget+1];
- for (NSUInteger j = 0; j <= mergeTarget; j++) {
+ //Next we want to merge non-adjacent matches that could be adjacent. Example:
+ // Haystack: "central_private_rabbit_park"
+ // Needle: "centralpark"
+ // Unoptimized: "central_private_rabbit_park"
+ // ^^^^^^^ ^ ^ ^ ^ = 5
+ // Desired: "central_private_rabbit_park"
+ // ^^^^^^^ ^^^^ = 2
+ //
+ // This time we start from the end (object K) and check if object K-1 can
+ // actually be placed directly in front of K and if so, merge them both into
+ // a new K-1 and shift down K+1 to K, K+2 to K+1, ...
+ for (NSUInteger k = matchCount - 1; k > 0; k--) {
+ NSRange my = tmpMatchStore[k];
+ NSRange prev = tmpMatchStore[k-1];
+ NSString *prevMatch = [self substringWithRange:prev];
+ NSRange left = NSMakeRange(my.location - prev.length, prev.length);
+ NSString *myLeftSide = [self substringWithRange:left];
+ if([prevMatch compare:myLeftSide options:opts] == NSOrderedSame) {
+ //yay, let's merge them
+ tmpMatchStore[k-1] = NSMakeRange(left.location, my.length+prev.length);
+ //we now have to shift down k+1 to k, k+2 to k+1, ...
+ for (NSUInteger n = k+1; n < matchCount; n++) {
+ tmpMatchStore[n-1] = tmpMatchStore[n];
+ }
+ //merging means one match less in total
+ matchCount--;
+ }
+ }
+
+ NSMutableArray *combinedArray = [NSMutableArray arrayWithCapacity:matchCount];
+ for (NSUInteger j = 0; j < matchCount; j++) {
[combinedArray addObject:[NSValue valueWithRange:tmpMatchStore[j]]];
}
diff --git a/UnitTests/SPStringAdditionsTests.m b/UnitTests/SPStringAdditionsTests.m
index b0528ec7..23ec82e9 100644
--- a/UnitTests/SPStringAdditionsTests.m
+++ b/UnitTests/SPStringAdditionsTests.m
@@ -42,6 +42,8 @@
@end
+static NSRange RangeFromArray(NSArray *a,NSUInteger idx);
+
@implementation SPStringAdditionsTests
/**
@@ -102,7 +104,7 @@
{
NSArray *matches = nil;
STAssertTrue([@"" nonConsecutivelySearchString:@"" matchingRanges:&matches], @"Equality of empty strings");
- STAssertTrue(([matches count] == 1) && NSEqualRanges(NSMakeRange(0, 0), [(NSValue *)[matches objectAtIndex:0] rangeValue]), @"Returned matches in empty string");
+ STAssertTrue(([matches count] == 1) && NSEqualRanges(NSMakeRange(0, 0), RangeFromArray(matches, 0)), @"Returned matches in empty string");
}
{
@@ -116,13 +118,13 @@
{
NSArray *matches = nil;
STAssertTrue([@"left" nonConsecutivelySearchString:@"le" matchingRanges:&matches], @"Anchored match left");
- STAssertTrue(([matches count] == 1) && NSEqualRanges(NSMakeRange(0, 2), [(NSValue *)[matches objectAtIndex:0] rangeValue]), @"Returned matches in anchored left match");
+ STAssertTrue(([matches count] == 1) && NSEqualRanges(NSMakeRange(0, 2), RangeFromArray(matches, 0)), @"Returned matches in anchored left match");
}
{
NSArray *matches = nil;
STAssertTrue([@"right" nonConsecutivelySearchString:@"ht" matchingRanges:&matches], @"Anchored match right");
- STAssertTrue(([matches count] == 1) && NSEqualRanges(NSMakeRange(3, 2), [(NSValue *)[matches objectAtIndex:0] rangeValue]), @"Returned matches in anchroed right match");
+ STAssertTrue(([matches count] == 1) && NSEqualRanges(NSMakeRange(3, 2), RangeFromArray(matches, 0)), @"Returned matches in anchroed right match");
}
STAssertFalse([@"ht" nonConsecutivelySearchString:@"right" matchingRanges:NULL], @"Left and Right are not commutative");
@@ -132,9 +134,9 @@
NSArray *matches = nil;
STAssertTrue([@"... is not secure anymore!" nonConsecutivelySearchString:@"NSA" matchingRanges:&matches], @"Non-consecutive match, ignoring case");
STAssertTrue(([matches count] == 3) &&
- (NSEqualRanges(NSMakeRange(7, 1), [(NSValue *)[matches objectAtIndex:0] rangeValue])) &&
- (NSEqualRanges(NSMakeRange(11, 1), [(NSValue *)[matches objectAtIndex:1] rangeValue])) &&
- (NSEqualRanges(NSMakeRange(18, 1), [(NSValue *)[matches objectAtIndex:2] rangeValue])), @"Returned matches in non-consecutive string");
+ NSEqualRanges(NSMakeRange( 7, 1), RangeFromArray(matches, 0)) &&
+ NSEqualRanges(NSMakeRange(11, 1), RangeFromArray(matches, 1)) &&
+ NSEqualRanges(NSMakeRange(18, 1), RangeFromArray(matches, 2)), @"Returned matches in non-consecutive string");
}
STAssertFalse([@"Deoxyribonucleic Acid" nonConsecutivelySearchString:@"DNS" matchingRanges:NULL], @"Non-consecutive mismatch");
@@ -142,10 +144,38 @@
{
NSArray *matches = nil;
STAssertTrue([@"Turn left, then right at the corner" nonConsecutivelySearchString:@"left right" matchingRanges:&matches], @"Partly consecutive match");
- STAssertTrue(([matches count] == 3) &&
- (NSEqualRanges(NSMakeRange(5, 4), [(NSValue *)[matches objectAtIndex:0] rangeValue])) &&
- (NSEqualRanges(NSMakeRange(10, 1), [(NSValue *)[matches objectAtIndex:1] rangeValue])) &&
- (NSEqualRanges(NSMakeRange(16, 5), [(NSValue *)[matches objectAtIndex:2] rangeValue])), @"Returned matches in partly-consecutive string");
+ STAssertTrue(([matches count] == 2) &&
+ (NSEqualRanges(NSMakeRange( 5, 4), RangeFromArray(matches, 0))) &&
+ (NSEqualRanges(NSMakeRange(15, 6), RangeFromArray(matches, 1))), @"Returned matches in partly-consecutive string");
+ }
+
+ //optimization tests
+ {
+ NSArray *matches = nil;
+ // Haystack: "central_private_rabbit_park"
+ // Needle: "centralpark"
+ // Unoptimized: "central_private_rabbit_park"
+ // ^^^^^^^ ^ ^ ^ ^ = 5 (after optimizing consecutive atomic matches)
+ // Desired: "central_private_rabbit_park"
+ // ^^^^^^^ ^^^^ = 2
+ STAssertTrue([@"central_private_rabbit_park" nonConsecutivelySearchString:@"centralpark" matchingRanges:&matches], @"Optimization partly consecutive match");
+ STAssertTrue((([matches count] == 2) &&
+ (NSEqualRanges(NSMakeRange( 0, 7), RangeFromArray(matches, 0))) &&
+ (NSEqualRanges(NSMakeRange(23, 4), RangeFromArray(matches, 1)))), @"Returned matches set is minimal");
+ }
+ {
+ // In the previous test it was always the end of the matches array that got optimized.
+ // This time we'll have two different optimizations
+ // Needle: ".abc123"
+ // Haystack: "a.?a?ab?abc?1?12?123?"
+ // Unoptimized: ^ ^ ^ ^ ^ ^ ^ = 7
+ // Desired: ^ ^^^ ^^^ = 3
+ NSArray *matches = nil;
+ STAssertTrue([@"a.?a?ab?abc?1?12?123?" nonConsecutivelySearchString:@".abc123" matchingRanges:&matches], @"Optimization non-consecutive match");
+ STAssertTrue((([matches count] == 3) &&
+ (NSEqualRanges(NSMakeRange( 1, 1), RangeFromArray(matches, 0))) &&
+ (NSEqualRanges(NSMakeRange( 8, 3), RangeFromArray(matches, 1))) &&
+ (NSEqualRanges(NSMakeRange(17, 3), RangeFromArray(matches, 2)))), @"Returned matches set is minimal (2)");
}
//advanced tests
@@ -166,3 +196,8 @@
}
@end
+
+NSRange RangeFromArray(NSArray *a,NSUInteger idx)
+{
+ return [(NSValue *)[a objectAtIndex:idx] rangeValue];
+}