/*
 Flash: Flashcard program
 Copyright (C) 2005, Niko Matsakis (niko@alum.mit.edu)
 
 This program is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 2
 of the License, or (at your option) any later version.
 
 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.
 
 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#import "QuizMatching.h"
#import "QuizAnswer.h"
#import "QuizGuess.h"
#import "OAMacros.h"
#import "Accessors.h"
#import "OADebug.h"
#import "OACategories.h"

static NSString *normalize(NSString *string) 
{
    return [[string stringByPurgingParentheticalText] normalizeWhitespace];
}

static int CorrespondenceNumber(NSString *normalizedAnswer, NSString *normalizedGuess)
{
    int cnt = [normalizedAnswer sharedCaseInsensitivePrefixLength:normalizedGuess];
    cnt += [normalizedAnswer sharedCaseInsensitiveSuffixLength:normalizedGuess];
    return cnt;
}

// Returns number of stars that should be awarded for
// the given answer/guess pair; a number from 0 to 3,
// where 3 means perfect.
NSNumber *StarCount(NSString *answer, NSString *guess) 
{
    int prec;
    answer = normalize(answer);
    guess = normalize(guess);
    if ([answer isEqualToStringIgnoringCase:guess]) 
        prec = 3;
    else {
        int anslen = [answer length];
        int cnum = CorrespondenceNumber(answer, guess);
        double percent = 1-((double)(anslen-cnum))/((double)anslen);
        if (percent > .75) 
            prec = 2;
        else if (percent > .35)
            prec = 1;
        else 
            prec = 0;
    }
    
    return [NSNumber numberWithInt:prec];
}

// Finds any answers and guesses that are exactly the
// same and matches them up.
static void MatchExactGuesses(NSMutableArray *unmatchedanswers, NSMutableArray *unmatchedguesses)
{
    NSMutableArray *purge = [NSMutableArray array];
    FOREACH (NSManagedObject*, answerWord, unmatchedanswers) {
        NSString *answer = [answerWord textValue];
        NSString *normalizedAnswer = normalize(answer);
        FOREACH (QuizGuess *, guessObject, unmatchedguesses) {
            NSString *guess = [guessObject guess];
            NSString *normalizedGuess = normalize(guess);
            
            if ([normalizedGuess isEqualToStringIgnoringCase:normalizedAnswer]) {
                OALog (@"Answer '%@' maps precisely to a guess", answer);
                [guessObject setAnswerWord:answerWord];
                [unmatchedguesses removeObject:guessObject];                
                [purge addObject:answerWord];
                break;
            }
        } ENDFOREACH;
    } ENDFOREACH;
    
    // Remove the answers corresponding to the guesses that we matched up.
    // Do it here to avoid modifying array during iterati on.
    [unmatchedanswers removeObjectsInArray:purge];
}    

// Iterates through the list of unmatch answers and guesses
// and finds the two that look most alike, returning the pair
// through *bestanswer and *bestguess.
static void MatchBestAnswerAndGuess(NSMutableArray *unmatchedanswers, 
                                    NSMutableArray *unmatchedguesses,
                                    NSManagedObject **bestanswer, 
                                    QuizGuess **bestguess)
{   
    int bestcnt = -1;
    
    // find the answer and guess which match up best
    FOREACH (NSManagedObject*, answerWord, unmatchedanswers) {
        NSString *answer = [answerWord textValue];
        NSString *normalizedAnswer = normalize(answer);
        FOREACH (QuizGuess*, guessObj, unmatchedguesses) {
            NSString *normalizedGuess = normalize([guessObj guess]);
            int cnt = CorrespondenceNumber(normalizedAnswer, normalizedGuess);
            if (cnt > bestcnt) {
                *bestanswer = answerWord;
                *bestguess = guessObj;
                bestcnt = cnt;
            }
        } ENDFOREACH;
    } ENDFOREACH;
}

// Matches a list of answers and guests that are not exact matches.  Works
// by repeatedly iterating over them in an O(N^2) fashion, finding the
// answer and guess that match most closely, until none remain.
static void MatchInexactGuesses(NSMutableArray *unmatchedanswers, 
                                NSMutableArray *unmatchedguesses) {
    OALog(@"%d unmatched remain", [unmatchedanswers count]);
    while ([unmatchedanswers count]) {
        NSManagedObject *bestanswer = nil;
        QuizGuess *bestguess = nil;
        MatchBestAnswerAndGuess(unmatchedanswers, unmatchedguesses, &bestanswer, &bestguess);
        assert(bestguess != nil && bestanswer != nil);
        OALog (@"Answer '%@' maps best to guess '%@'", 
               [bestanswer textValue], [bestguess guess]);
        [unmatchedguesses removeObject:bestguess];
        [unmatchedanswers removeObject:bestanswer];
        [bestguess setAnswerWord:bestanswer];
    }
}

/* 
Match up a list of guesses with the answers they most likely represent.
answers is a list of QuizAnswer, and guesses is a list of QuizGuess.

When completed, each QuizGuess's setAnswerWord: method will have been
called with the answerWord of the corresponding QuizAnswer.  

We process the answer/guesses in batches; we find each set of answers that is
testing a particular relationship, and the corresponding guesses that the user
made, and try to match only w/in that relationship.  Even in that limited context,
we must use a multi-pass process:

1. First, we eliminate any exact matches.  Those are easy.
2. We then iterate over the set of answers and the guesses, and find the two
that most closely resemble one another as judged by CorrespondenceNumber().
Currently this is implemented by a prefix/suffix comparison.  We repeat this step
until no more pairs remain.
*/
BOOL MatchGuessesAndAnswers(NSArray *answers, NSArray *guesses) {
    // answers is an array of QuizAnswer
    // guesses is an array of QuizGuess
   
    assert ([answers count] == [guesses count]);
    BOOL exactMatch = YES;
   
    OAINDENTED(@"Matching guesses and answers") {
        int index = 0;
        
        // The set of answers contains answers for different kinds of relationships.
        // We consider each kind of relationship independently.  We know that the
        // current set of answers is sorted by relationship, and the guesses should
        // be in a corresponding order, so we simply do the matching in batches.
        // "index" always stores the start of the next batch.

        // Break the answers/guesses down by relationship
        while (index < [answers count]) {
            
            // Construct an array of unmatched answers and guesses for this batch.
            // The 'unmatchedanswers' array will have Word entities (NSManagedObjects*) in it, not QuizAnswer
            NSMutableArray *unmatchedanswers = [NSMutableArray array];
            NSMutableArray *unmatchedguesses = [NSMutableArray array];

            // Add each answer/guess pair in the current batch to the above arrays.
            QuizAnswer *qa = [answers objectAtIndex:index];
            for (; index < [answers count]; index++) {
                QuizAnswer *qb = [answers objectAtIndex:index];
                if (![qb groupWith:qa]) {
                    break;
                }
                
                [unmatchedanswers addObject:[qb answerWord]];
                [unmatchedguesses addObject:[guesses objectAtIndex:index]];
            }

            // Match up the answers and guesses.
            MatchExactGuesses(unmatchedanswers, unmatchedguesses);
            if ([unmatchedguesses count] != 0)
                exactMatch = NO;
            MatchInexactGuesses(unmatchedanswers, unmatchedguesses);
            assert([unmatchedanswers count] == 0 && [unmatchedguesses count] == 0);
        }
        
        OALog(@"Exact Match? %d", exactMatch);
    } OAUNDENTED;
    
    return exactMatch;
}