Improve the search method in "Go To Database" to sort results in a more relevant order

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];
+}