diff options
| -rw-r--r-- | Source/SPGotoDatabaseController.m | 70 | ||||
| -rw-r--r-- | Source/SPStringAdditions.h | 4 | ||||
| -rw-r--r-- | Source/SPStringAdditions.m | 34 | ||||
| -rw-r--r-- | UnitTests/SPStringAdditionsTests.m | 55 |
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]; +} |