/* Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#define C_LUCY_PROXIMITYMATCHER
#define C_LUCY_POSTING
#define C_LUCY_SCOREPOSTING
#include "Lucy/Util/ToolSet.h"

#include "LucyX/Search/ProximityMatcher.h"
#include "Lucy/Index/Posting/ScorePosting.h"
#include "Lucy/Index/PostingList.h"
#include "Lucy/Index/Similarity.h"
#include "Lucy/Search/Compiler.h"


ProximityMatcher*
ProximityMatcher_new(Similarity *sim, VArray *plists, Compiler *compiler,
                     uint32_t within) {
    ProximityMatcher *self =
        (ProximityMatcher*)VTable_Make_Obj(PROXIMITYMATCHER);
    return ProximityMatcher_init(self, sim, plists, compiler, within);

}

ProximityMatcher*
ProximityMatcher_init(ProximityMatcher *self, Similarity *similarity,
                      VArray *plists, Compiler *compiler, uint32_t within) {
    Matcher_init((Matcher*)self);

    // Init.
    self->anchor_set       = BB_new(0);
    self->proximity_freq   = 0.0;
    self->proximity_boost  = 0.0;
    self->first_time       = true;
    self->more             = true;
    self->within           = within;

    // Extract PostingLists out of VArray into local C array for quick access.
    self->num_elements = VA_Get_Size(plists);
    self->plists = (PostingList**)MALLOCATE(
                       self->num_elements * sizeof(PostingList*));
    for (size_t i = 0; i < self->num_elements; i++) {
        PostingList *const plist
            = (PostingList*)CERTIFY(VA_Fetch(plists, i), POSTINGLIST);
        if (plist == NULL) {
            THROW(ERR, "Missing element %u32", i);
        }
        self->plists[i] = (PostingList*)INCREF(plist);
    }

    // Assign.
    self->sim       = (Similarity*)INCREF(similarity);
    self->compiler  = (Compiler*)INCREF(compiler);
    self->weight    = Compiler_Get_Weight(compiler);

    return self;
}

void
ProximityMatcher_destroy(ProximityMatcher *self) {
    if (self->plists) {
        for (size_t i = 0; i < self->num_elements; i++) {
            DECREF(self->plists[i]);
        }
        FREEMEM(self->plists);
    }
    DECREF(self->sim);
    DECREF(self->anchor_set);
    DECREF(self->compiler);
    SUPER_DESTROY(self, PROXIMITYMATCHER);
}

int32_t
ProximityMatcher_next(ProximityMatcher *self) {
    if (self->first_time) {
        return ProximityMatcher_Advance(self, 1);
    }
    else if (self->more) {
        const int32_t target = PList_Get_Doc_ID(self->plists[0]) + 1;
        return ProximityMatcher_Advance(self, target);
    }
    else {
        return 0;
    }
}

int32_t
ProximityMatcher_advance(ProximityMatcher *self, int32_t target) {
    PostingList **const plists       = self->plists;
    const uint32_t      num_elements = self->num_elements;
    int32_t             highest      = 0;

    // Reset match variables to indicate no match.  New values will be
    // assigned if a match succeeds.
    self->proximity_freq = 0.0;
    self->doc_id         = 0;

    // Find the lowest possible matching doc ID greater than the current doc
    // ID.  If any one of the PostingLists is exhausted, we're done.
    if (self->first_time) {
        self->first_time = false;

        // On the first call to Advance(), advance all PostingLists.
        for (size_t i = 0, max = self->num_elements; i < max; i++) {
            int32_t candidate = PList_Advance(plists[i], target);
            if (!candidate) {
                self->more = false;
                return 0;
            }
            else if (candidate > highest) {
                // Remember the highest doc ID so far.
                highest = candidate;
            }
        }
    }
    else {
        // On subsequent iters, advance only one PostingList.  Its new doc ID
        // becomes the minimum target which all the others must move up to.
        highest = PList_Advance(plists[0], target);
        if (highest == 0) {
            self->more = false;
            return 0;
        }
    }

    // Find a doc which contains all the terms.
    while (1) {
        bool_t agreement = true;

        // Scoot all posting lists up to at least the current minimum.
        for (uint32_t i = 0; i < num_elements; i++) {
            PostingList *const plist = plists[i];
            int32_t candidate = PList_Get_Doc_ID(plist);

            // Is this PostingList already beyond the minimum?  Then raise the
            // bar for everyone else.
            if (highest < candidate) { highest = candidate; }
            if (target < highest)    { target = highest; }

            // Scoot this posting list up.
            if (candidate < target) {
                candidate = PList_Advance(plist, target);

                // If this PostingList is exhausted, we're done.
                if (candidate == 0) {
                    self->more = false;
                    return 0;
                }

                // After calling PList_Advance(), we are guaranteed to be
                // either at or beyond the minimum, so we can assign without
                // checking and the minumum will either go up or stay the
                // same.
                highest = candidate;
            }
        }

        // See whether all the PostingLists have managed to converge on a
        // single doc ID.
        for (uint32_t i = 0; i < num_elements; i++) {
            const int32_t candidate = PList_Get_Doc_ID(plists[i]);
            if (candidate != highest) { agreement = false; }
        }

        // If we've found a doc with all terms in it, see if they form a
        // phrase.
        if (agreement && highest >= target) {
            self->proximity_freq = ProximityMatcher_Calc_Proximity_Freq(self);
            if (self->proximity_freq == 0.0) {
                // No phrase.  Move on to another doc.
                target += 1;
            }
            else {
                // Success!
                self->doc_id = highest;
                return highest;
            }
        }
    }
}


static INLINE uint32_t
SI_winnow_anchors(uint32_t *anchors_start, const uint32_t *const anchors_end,
                  const uint32_t *candidates, const uint32_t *const candidates_end,
                  uint32_t offset, uint32_t within) {
    uint32_t *anchors = anchors_start;
    uint32_t *anchors_found = anchors_start;
    uint32_t target_anchor;
    uint32_t target_candidate;

    // Safety check, so there's no chance of a bad dereference.
    if (anchors_start == anchors_end || candidates == candidates_end) {
        return 0;
    }

    /* This function is a loop that finds terms that can continue a phrase.
     * It overwrites the anchors in place, and returns the number remaining.
     * The basic algorithm is to alternately increment the candidates' pointer
     * until it is at or beyond its target position, and then increment the
     * anchors' pointer until it is at or beyond its target.  The non-standard
     * form is to avoid unnecessary comparisons.  This loop has not been
     * tested for speed, but glancing at the object code produced (objdump -S)
     * it appears to be significantly faster than the nested loop alternative.
     * But given the vagaries of modern processors, it merits actual
     * testing.*/

SPIN_CANDIDATES:
    target_candidate = *anchors + offset;
    while (*candidates < target_candidate) {
        if (++candidates == candidates_end) { goto DONE; }
    }
    if ((*candidates - target_candidate) < within) { goto MATCH; }
    goto SPIN_ANCHORS;

SPIN_ANCHORS:
    target_anchor = *candidates - offset;
    while (*anchors < target_anchor) {
        if (++anchors == anchors_end) { goto DONE; }
    };
    if (*anchors == target_anchor) { goto MATCH; }
    goto SPIN_CANDIDATES;

MATCH:
    *anchors_found++ = *anchors;
    if (++anchors == anchors_end) { goto DONE; }
    goto SPIN_CANDIDATES;

DONE:
    // Return number of anchors remaining.
    return anchors_found - anchors_start;
}

float
ProximityMatcher_calc_proximity_freq(ProximityMatcher *self) {
    PostingList **const plists   = self->plists;

    /* Create a overwriteable "anchor set" from the first posting.
     *
     * Each "anchor" is a position, measured in tokens, corresponding to a a
     * term which might start a phrase.  We start off with an "anchor set"
     * comprised of all positions at which the first term in the phrase occurs
     * in the field.
     *
     * There can never be more proximity matches than instances of this first
     * term.  There may be fewer however, which we will determine by seeing
     * whether all the other terms line up at subsequent position slots.
     *
     * Every time we eliminate an anchor from the anchor set, we splice it out
     * of the array.  So if we begin with an anchor set of (15, 51, 72) and we
     * discover that matches occur at the first and last instances of the
     * first term but not the middle one, the final array will be (15, 72).
     *
     * The number of elements in the anchor set when we are finished winnowing
     * is our proximity freq.
     */
    ScorePosting *posting = (ScorePosting*)PList_Get_Posting(plists[0]);
    uint32_t anchors_remaining = posting->freq;
    if (!anchors_remaining) { return 0.0f; }

    size_t    amount        = anchors_remaining * sizeof(uint32_t);
    uint32_t *anchors_start = (uint32_t*)BB_Grow(self->anchor_set, amount);
    uint32_t *anchors_end   = anchors_start + anchors_remaining;
    memcpy(anchors_start, posting->prox, amount);

    // Match the positions of other terms against the anchor set.
    for (uint32_t i = 1, max = self->num_elements; i < max; i++) {
        // Get the array of positions for the next term.  Unlike the anchor
        // set (which is a copy), these won't be overwritten.
        ScorePosting *posting = (ScorePosting*)PList_Get_Posting(plists[i]);
        uint32_t *candidates_start = posting->prox;
        uint32_t *candidates_end   = candidates_start + posting->freq;

        // Splice out anchors that don't match the next term.  Bail out if
        // we've eliminated all possible anchors.
        if (self->within == 1) { // exact phrase match
            anchors_remaining = SI_winnow_anchors(anchors_start, anchors_end,
                                                  candidates_start,
                                                  candidates_end, i, 1);
        }
        else {  // fuzzy-phrase match
            anchors_remaining = SI_winnow_anchors(anchors_start, anchors_end,
                                                  candidates_start,
                                                  candidates_end, i,
                                                  self->within);
        }
        if (!anchors_remaining) { return 0.0f; }

        // Adjust end for number of anchors that remain.
        anchors_end = anchors_start + anchors_remaining;
    }

    // The number of anchors left is the proximity freq.
    return (float)anchors_remaining;
}

int32_t
ProximityMatcher_get_doc_id(ProximityMatcher *self) {
    return self->doc_id;
}

float
ProximityMatcher_score(ProximityMatcher *self) {
    ScorePosting *posting = (ScorePosting*)PList_Get_Posting(self->plists[0]);
    float score = Sim_TF(self->sim, self->proximity_freq)
                  * self->weight
                  * posting->weight;
    return score;
}