Code Coverage
 
Classes and Traits
Functions and Methods
Lines
Total
0.00% covered (danger)
0.00%
0 / 1
25.00% covered (danger)
25.00%
1 / 4
CRAP
70.45% covered (warning)
70.45%
31 / 44
TeamDraftInterleaver
0.00% covered (danger)
0.00%
0 / 1
25.00% covered (danger)
25.00%
1 / 4
19.06
70.45% covered (warning)
70.45%
31 / 44
 __construct
0.00% covered (danger)
0.00%
0 / 1
2
0.00% covered (danger)
0.00%
0 / 2
 interleave
0.00% covered (danger)
0.00%
0 / 1
2
0.00% covered (danger)
0.00%
0 / 7
 extractResults
0.00% covered (danger)
0.00%
0 / 1
6
0.00% covered (danger)
0.00%
0 / 4
 interleaveResults
100.00% covered (success)
100.00%
1 / 1
10
100.00% covered (success)
100.00%
31 / 31
<?php
namespace CirrusSearch\Search;
use CirrusSearch\Util;
/**
 * Implementation of algorithm 2, Team-Draft Interleaving, from F. Radlinski, M.
 * Kurup, and T. Joachims. How does clickthrough data reflect retrieval
 * quality? In Proc 17th Intl. Conf. on Information and Knowledge Management.
 * ACM New York, NY, USA, 2008.
 */
class TeamDraftInterleaver {
    /** @var string The query provided by the user. */
    private $searchTerm;
    /**
     * @param string $searchTerm The query provided by the user.
     */
    public function __construct( $searchTerm ) {
        $this->searchTerm = $searchTerm;
    }
    /**
     * @param CirrusSearchResultSet $a Results for team A
     * @param CirrusSearchResultSet $b Results for team B
     * @param int $limit Maximum number of results to return
     * @return CirrusSearchResultSet
     */
    public function interleave( CirrusSearchResultSet $a, CirrusSearchResultSet $b, $limit ): CirrusSearchResultSet {
        // Seed the randomness so an individual user the clicks a result and then
        // comes back to the search page sees the same interleaving. This is not
        // strictly necessary for the test, but provides the user a more consistent
        // experience.
        $seed = hexdec( substr( Util::generateIdentToken( $this->searchTerm ), 0, 8 ) );
        mt_srand( $seed );
        $aResults = $this->extractResults( $a );
        $bResults = $this->extractResults( $b );
        list( $interleaved, $teamA, $teamB, $aOffset ) = $this->interleaveResults(
            $aResults,
            $bResults,
            $limit
        );
        return new InterleavedResultSet( $a, $interleaved, $teamA, $teamB, $aOffset );
    }
    private function extractResults( CirrusSearchResultSet $resultSet ) {
        $extracted = [];
        /** @var $result CirrusSearchResult */
        foreach ( $resultSet as $result ) {
            $extracted[$result->getDocId()] = $result;
        }
        return $extracted;
    }
    /**
     * Interleave two arrays using team draft interleaving. Only public
     * for unit tests. The id's used as keys in $a and $b must represent
     * the same thing, to prevent duplicates in the returned results.
     *
     * @param mixed[] $a Map from id to anything in preferred order for team A
     * @param mixed[] $b Map from id to anything in preferred order for team B
     * @param int $limit Maximum number of results to interleave
     * @return mixed[] Four item array. first item being the values from $a
     *  and $b in the interleaved ordering, second the ids belonging to team
     *  A, third the ids belonging to team B, and finally the offset for the
     *  next page in $a.
     */
    public static function interleaveResults( $a, $b, $limit ) {
        $interleaved = [];
        $teamA = [];
        $teamB = [];
        $aIds = array_combine( array_keys( $a ), array_keys( $a ) );
        $bIds = array_combine( array_keys( $b ), array_keys( $b ) );
        while (
            count( $interleaved ) < $limit
            && ( $aIds || $bIds )
        ) {
            if ( !$aIds ) {
                $id = reset( $bIds );
                $teamB[] = $id;
                $interleaved[] = $b[$id];
            } elseif ( !$bIds ) {
                $id = reset( $aIds );
                $teamA[] = $id;
                $interleaved[] = $a[$id];
            // If team b has already chosen, then a needs to go
            } elseif ( count( $teamA ) < count( $teamB )
                || (
                // If the counts are equal choose randomly which team goes next
                    count( $teamA ) == count( $teamB )
                    && mt_rand( 0, 1 ) === 1
            ) ) {
                $id = reset( $aIds );
                $teamA[] = $id;
                $interleaved[] = $a[$id];
            } else {
                $id = reset( $bIds );
                $teamB[] = $id;
                $interleaved[] = $b[$id];
            }
            unset( $aIds[$id], $bIds[$id] );
        }
        if ( $aIds ) {
            // $offset needs to be set such that results starting at $offset +
            // $limit are new. As such if we have 20 items and 10 of a are
            // used, then offset should be -10. If 15 are used we want -5.
            // This doesn't guarantee we don't show duplicates. Items from B
            // could be in second page of A. The goal here is to ensure
            // everything from A is seen when paginating even if there are
            // dupes.
            $nextA = reset( $aIds );
            $nextAIdx = array_search( $nextA, array_keys( $a ) );
            $offset = -( $limit - $nextAIdx );
        } else {
            $offset = 0;
        }
        return [ $interleaved, $teamA, $teamB, $offset ];
    }
}