Repository: prebid/prebid-server
Pull request #2805 (2023-05-26 01:10:51)

Find bid duration in linear time
We currently sort the `targeting.DurationRange` array in order to pick a duration that better resembles the `bid.BidVideo.Duration`. This results in O(nlogn) time and O(n) space because we copy the `targeting.DurationRange` slice before sorting. This pull requests modifies to get the same result in O(n) time and O(1) space.


Patch:
diff --git a/.gitignore b/.gitignore
index 514e217b..4e298f2a 100644
--- a/.gitignore
+++ b/.gitignore
@@ -51,3 +51,8 @@ analytics/filesystem/testFiles/
 # autogenerated mac file
 
 .DS_Store
+
+# Autogenerated Vim swap files
+*~
+*.swp
+*.swo
diff --git a/exchange/exchange.go b/exchange/exchange.go
index 4251c3e2..e7ba2839 100644
--- a/exchange/exchange.go
+++ b/exchange/exchange.go
@@ -1006,24 +1006,11 @@ func applyCategoryMapping(ctx context.Context, targeting openrtb_ext.ExtRequestT
 
 			priceBucket = GetPriceBucket(*bid.Bid, *targData)
 
-			newDur := duration
-			if len(targeting.DurationRangeSec) > 0 {
-				durationRange := make([]int, len(targeting.DurationRangeSec))
-				copy(durationRange, targeting.DurationRangeSec)
-				sort.Ints(durationRange)
-
-				//if the bid is above the range of the listed durations (and outside the buffer), reject the bid
-				if duration > durationRange[len(durationRange)-1] {
-					bidsToRemove = append(bidsToRemove, bidInd)
-					rejections = updateRejections(rejections, bidID, "Bid duration exceeds maximum allowed")
-					continue
-				}
-				for _, dur := range durationRange {
-					if duration <= dur {
-						newDur = dur
-						break
-					}
-				}
+			newDur, err := findDurationRange(duration, targeting.DurationRangeSec)
+			if err != nil {
+				bidsToRemove = append(bidsToRemove, bidInd)
+				rejections = updateRejections(rejections, bidID, err.Error())
+				continue
 			}
 
 			var categoryDuration string
@@ -1113,6 +1100,33 @@ func applyCategoryMapping(ctx context.Context, targeting openrtb_ext.ExtRequestT
 	return res, seatBids, rejections, nil
 }
 
+// findDurationRange returns the element in the array 'durationRanges' that is both greater than 'dur' and closest
+// in value to 'dur' unless a value equal to 'dur' is found. Returns an error if all elements in 'durationRanges'
+// are less than 'dur'.
+func findDurationRange(dur int, durationRanges []int) (int, error) {
+	newDur := dur
+	madeSelection := false
+	var err error
+
+	for i := range durationRanges {
+		if dur > durationRanges[i] {
+			continue
+		}
+		if dur == durationRanges[i] {
+			return durationRanges[i], nil
+		}
+		// dur < durationRanges[i]
+		if durationRanges[i] < newDur || !madeSelection {
+			newDur = durationRanges[i]
+			madeSelection = true
+		}
+	}
+	if !madeSelection && len(durationRanges) > 0 {
+		err = errors.New("bid duration exceeds maximum allowed")
+	}
+	return newDur, err
+}
+
 func removeBidById(seatBid *entities.PbsOrtbSeatBid, bidID string) {
 	//Find index of bid to remove
 	dupeBidIndex := -1
diff --git a/static/bidder-info/lunamedia.yaml b/static/bidder-info/lunamedia.yaml
index 79e19a43..ef34143e 100644
--- a/static/bidder-info/lunamedia.yaml
+++ b/static/bidder-info/lunamedia.yaml
@@ -1,4 +1,4 @@
-endpoint: "http://api.lunamedia.io/xp/get?pubid={{.PublisherID}}"
+endpoint: "http://rtb.lunamedia.live/?pid={{.PublisherID}}"
 maintainer:
   email: "josh@lunamedia.io"
 capabilities:
@@ -6,13 +6,11 @@ capabilities:
     mediaTypes:
     - banner
     - video
-    
   app:
     mediaTypes:
     - banner
     - video
 userSync:
   iframe:
-    url: "https://api.lunamedia.io/xp/user-sync?redirect={{.RedirectURL}}"
-    userMacro: "$UID"
-
+    url: "https://sync.lunamedia.live/psync?t=s&e=0&cb={{.RedirectURL}}"
+    userMacro: "%USER_ID%"


Test patch:
diff --git a/adapters/lunamedia/lunamedia_test.go b/adapters/lunamedia/lunamedia_test.go
index ef109d92..961cd545 100644
--- a/adapters/lunamedia/lunamedia_test.go
+++ b/adapters/lunamedia/lunamedia_test.go
@@ -11,7 +11,7 @@ import (
 
 func TestJsonSamples(t *testing.T) {
 	bidder, buildErr := Builder(openrtb_ext.BidderLunaMedia, config.Adapter{
-		Endpoint: "http://api.lunamedia.io/xp/get?pubid={{.PublisherID}}"}, config.Server{ExternalUrl: "http://hosturl.com", GvlID: 1, DataCenter: "2"})
+		Endpoint: "http://rtb.lunamedia.live/?pid={{.PublisherID}}"}, config.Server{ExternalUrl: "http://hosturl.com", GvlID: 1, DataCenter: "2"})
 
 	if buildErr != nil {
 		t.Fatalf("Builder returned unexpected error %v", buildErr)
diff --git a/adapters/lunamedia/lunamediatest/exemplary/banner.json b/adapters/lunamedia/lunamediatest/exemplary/banner.json
index 3b5c417f..fa92565b 100644
--- a/adapters/lunamedia/lunamediatest/exemplary/banner.json
+++ b/adapters/lunamedia/lunamediatest/exemplary/banner.json
@@ -31,7 +31,7 @@
   "httpCalls": [
     {
       "expectedRequest": {
-        "uri": "http://api.lunamedia.io/xp/get?pubid=19f1b372c7548ec1fe734d2c9f8dc688",
+        "uri": "http://rtb.lunamedia.live/?pid=19f1b372c7548ec1fe734d2c9f8dc688",
         "body":{
           "id": "testid",
           "imp": [{
diff --git a/adapters/lunamedia/lunamediatest/exemplary/video.json b/adapters/lunamedia/lunamediatest/exemplary/video.json
index 82217373..834963ff 100644
--- a/adapters/lunamedia/lunamediatest/exemplary/video.json
+++ b/adapters/lunamedia/lunamediatest/exemplary/video.json
@@ -24,7 +24,7 @@
   "httpCalls": [
     {
       "expectedRequest": {
-        "uri": "http://api.lunamedia.io/xp/get?pubid=19f1b372c7548ec1fe734d2c9f8dc688",
+        "uri": "http://rtb.lunamedia.live/?pid=19f1b372c7548ec1fe734d2c9f8dc688",
         "body":{
           "id": "testid",
           "imp": [{
diff --git a/adapters/lunamedia/lunamediatest/supplemental/compat.json b/adapters/lunamedia/lunamediatest/supplemental/compat.json
index 5b84d3a5..7fc713e0 100644
--- a/adapters/lunamedia/lunamediatest/supplemental/compat.json
+++ b/adapters/lunamedia/lunamediatest/supplemental/compat.json
@@ -23,7 +23,7 @@
   "httpCalls": [
     {
       "expectedRequest": {
-        "uri": "http://api.lunamedia.io/xp/get?pubid=19f1b372c7548ec1fe734d2c9f8dc688",
+        "uri": "http://rtb.lunamedia.live/?pid=19f1b372c7548ec1fe734d2c9f8dc688",
         "body":{
           "id": "testid",
           "imp": [{
diff --git a/adapters/lunamedia/lunamediatest/supplemental/responseCode.json b/adapters/lunamedia/lunamediatest/supplemental/responseCode.json
index 739af044..075d121a 100644
--- a/adapters/lunamedia/lunamediatest/supplemental/responseCode.json
+++ b/adapters/lunamedia/lunamediatest/supplemental/responseCode.json
@@ -33,7 +33,7 @@
   "httpCalls": [
       {
           "expectedRequest": {
-              "uri": "http://api.lunamedia.io/xp/get?pubid=yu",
+              "uri": "http://rtb.lunamedia.live/?pid=yu",
               "body": {
                   "id": "testid",
                   "imp": [
diff --git a/adapters/lunamedia/lunamediatest/supplemental/responsebid.json b/adapters/lunamedia/lunamediatest/supplemental/responsebid.json
index e9d8c3c5..f8c5b67a 100644
--- a/adapters/lunamedia/lunamediatest/supplemental/responsebid.json
+++ b/adapters/lunamedia/lunamediatest/supplemental/responsebid.json
@@ -33,7 +33,7 @@
   "httpCalls": [
       {
           "expectedRequest": {
-              "uri": "http://api.lunamedia.io/xp/get?pubid=yu",
+              "uri": "http://rtb.lunamedia.live/?pid=yu",
               "body": {
                   "id": "testid",
                   "imp": [
diff --git a/adapters/lunamedia/lunamediatest/supplemental/site.json b/adapters/lunamedia/lunamediatest/supplemental/site.json
index 81d71554..b2610cec 100644
--- a/adapters/lunamedia/lunamediatest/supplemental/site.json
+++ b/adapters/lunamedia/lunamediatest/supplemental/site.json
@@ -33,7 +33,7 @@
   "httpCalls": [
       {
           "expectedRequest": {
-              "uri": "http://api.lunamedia.io/xp/get?pubid=19f1b372c7548ec1fe734d2c9f8dc688",
+              "uri": "http://rtb.lunamedia.live/?pid=19f1b372c7548ec1fe734d2c9f8dc688",
               "body": {
                   "id": "testid",
                   "imp": [
diff --git a/exchange/exchange_test.go b/exchange/exchange_test.go
index 962b1dd9..511fd84b 100644
--- a/exchange/exchange_test.go
+++ b/exchange/exchange_test.go
@@ -7,6 +7,7 @@ import (
 	"errors"
 	"fmt"
 	"io"
+	"math"
 	"net/http"
 	"net/http/httptest"
 	"os"
@@ -3188,7 +3189,7 @@ func TestCategoryMappingBidderNameNoCategories(t *testing.T) {
 		includeWinners:   true,
 	}
 
-	requestExt.Prebid.Targeting.DurationRangeSec = []int{15, 30}
+	requestExt.Prebid.Targeting.DurationRangeSec = []int{30, 10, 25, 5, 20, 50}
 
 	adapterBids := make(map[openrtb_ext.BidderName]*entities.PbsOrtbSeatBid)
 
@@ -3197,8 +3198,8 @@ func TestCategoryMappingBidderNameNoCategories(t *testing.T) {
 	bid1 := openrtb2.Bid{ID: "bid_id1", ImpID: "imp_id1", Price: 10.0000, Cat: cats1, W: 1, H: 1}
 	bid2 := openrtb2.Bid{ID: "bid_id2", ImpID: "imp_id2", Price: 12.0000, Cat: cats2, W: 1, H: 1}
 
-	bid1_1 := entities.PbsOrtbBid{&bid1, nil, "video", nil, &openrtb_ext.ExtBidPrebidVideo{Duration: 30}, nil, nil, 0, false, "", 10.0000, "USD", ""}
-	bid1_2 := entities.PbsOrtbBid{&bid2, nil, "video", nil, &openrtb_ext.ExtBidPrebidVideo{Duration: 30}, nil, nil, 0, false, "", 12.0000, "USD", ""}
+	bid1_1 := entities.PbsOrtbBid{&bid1, nil, "video", nil, &openrtb_ext.ExtBidPrebidVideo{Duration: 17}, nil, nil, 0, false, "", 10.0000, "USD", ""}
+	bid1_2 := entities.PbsOrtbBid{&bid2, nil, "video", nil, &openrtb_ext.ExtBidPrebidVideo{Duration: 8}, nil, nil, 0, false, "", 12.0000, "USD", ""}
 
 	innerBids1 := []*entities.PbsOrtbBid{
 		&bid1_1,
@@ -3220,8 +3221,8 @@ func TestCategoryMappingBidderNameNoCategories(t *testing.T) {
 
 	assert.NoError(t, err, "Category mapping error should be empty")
 	assert.Empty(t, rejections, "There should be 0 bid rejection messages")
-	assert.Equal(t, "10.00_30s_bidder1", bidCategory["bid_id1"], "Category mapping doesn't match")
-	assert.Equal(t, "12.00_30s_bidder2", bidCategory["bid_id2"], "Category mapping doesn't match")
+	assert.Equal(t, "10.00_20s_bidder1", bidCategory["bid_id1"], "Category mapping doesn't match")
+	assert.Equal(t, "12.00_10s_bidder2", bidCategory["bid_id2"], "Category mapping doesn't match")
 	assert.Len(t, adapterBids[bidderName1].Bids, 1, "Bidders number doesn't match")
 	assert.Len(t, adapterBids[bidderName2].Bids, 1, "Bidders number doesn't match")
 	assert.Len(t, bidCategory, 2, "Bidders category mapping doesn't match")
@@ -3287,7 +3288,7 @@ func TestBidRejectionErrors(t *testing.T) {
 			},
 			duration: 70,
 			expectedRejections: []string{
-				"bid rejected [bid ID: bid_id1] reason: Bid duration exceeds maximum allowed",
+				"bid rejected [bid ID: bid_id1] reason: bid duration exceeds maximum allowed",
 			},
 		},
 		{
@@ -5641,6 +5642,77 @@ func TestNilAuctionRequest(t *testing.T) {
 	assert.Nil(t, err)
 }
 
+func TestSelectNewDuration(t *testing.T) {
+	type testInput struct {
+		dur       int
+		durRanges []int
+	}
+	type testOutput struct {
+		dur int
+		err error
+	}
+	testCases := []struct {
+		desc     string
+		in       testInput
+		expected testOutput
+	}{
+		{
+			desc: "nil duration range array, don't expect error",
+			in: testInput{
+				dur:       1,
+				durRanges: nil,
+			},
+			expected: testOutput{1, nil},
+		},
+		{
+			desc: "empty duration range array, don't expect error",
+			in: testInput{
+				dur:       1,
+				durRanges: []int{},
+			},
+			expected: testOutput{1, nil},
+		},
+		{
+			desc: "all duration range array elements less than duration, expect error",
+			in: testInput{
+				dur:       5,
+				durRanges: []int{-1, 0, 1, 2, 3},
+			},
+			expected: testOutput{5, errors.New("bid duration exceeds maximum allowed")},
+		},
+		{
+			desc: "all duration range array elements greater than duration, expect smallest element in durRanges and nil error",
+			in: testInput{
+				dur:       5,
+				durRanges: []int{9, math.MaxInt32, 8},
+			},
+			expected: testOutput{8, nil},
+		},
+		{
+			desc: "some array elements greater than duration, expect the value greater than dur that is closest in value.",
+			in: testInput{
+				dur:       5,
+				durRanges: []int{math.MaxInt32, -3, 7, 2},
+			},
+			expected: testOutput{7, nil},
+		},
+		{
+			desc: "an entry in the duration range array is equal to duration, expect its value in return.",
+			in: testInput{
+				dur:       5,
+				durRanges: []int{-3, math.MaxInt32, 5, 7},
+			},
+			expected: testOutput{5, nil},
+		},
+	}
+	for _, tc := range testCases {
+		newDur, err := findDurationRange(tc.in.dur, tc.in.durRanges)
+
+		assert.Equal(t, tc.expected.dur, newDur, tc.desc)
+		assert.Equal(t, tc.expected.err, err, tc.desc)
+	}
+}
+
 func TestSetSeatNonBid(t *testing.T) {
 	type args struct {
 		bidResponseExt *openrtb_ext.ExtBidResponse