--- a/channel/ad_channel.inc	Thu May 28 14:53:07 2009 +0000
+++ b/channel/ad_channel.inc	Mon Jul 20 13:54:40 2009 +0000
@@ -14,61 +14,73 @@
 function ad_channel_cache_filter($ads) {
   _debug_echo("ad_channel_cache: adserve_cache_filter");
 
+  // get channel array from cache
   $channels = adserve_cache('get_cache', 'channel');
-  $valid = array();
-  $nochannel = array();
-  $nochannel_weight = array();
-  $matched_channel = array();
+  // 0 = only display advertisements not assigned to any channel if no matching
+  // ads in selected channel; 1 = always display advertisements not assigned to
+  // any channel; 2 = never display advertisements not assigned to any channel
+  $nochannel_display = $channels['display'];
+  $valid_ads = array();
+  $nochannel_fallback_ads = array();
+  $nochannel_percent = array();
+  // determine which channels each advertisement is assigned to
   foreach ($ads as $aid) {
     _debug_echo("ad_channel_cache: checking aid($aid)");
     if (is_array($channels['ads']) && isset($channels['ads'][$aid]) &&
         is_array($channels['ads'][$aid])) {
       foreach ($channels['ads'][$aid] as $chid) {
         $channel = $channels['channels'][$chid];
-        $display = $channel->display;
+        $display_by_url = $channel->display;
         $urls = unserialize($channel->urls);
         $frontpage = adserve_variable('site_frontpage') ? adserve_variable('site_frontpage') : 'node';
         $regexp = '/^('. preg_replace(array('/(\r\n?|\n)/', '/\\\\\*/', '/(^|\|)\\\\<front\\\\>($|\|)/'), array('|', '.*', '\1'. preg_quote($frontpage, '/') .'\2'), preg_quote($urls, '/')) .')$/';
         $match = preg_match($regexp, adserve_variable('url'));
-        _debug_echo("ad_channel_cache: checking aid($aid) against channel($chid) path(". adserve_variable('url') .") regexp($regexp) match($match)");
-        if ($display == 0) { // display on all except listed urls
+        _debug_echo("ad_channel_cache: checking aid($aid) against channel($chid) path(". adserve_variable('url') .") regexp($regexp) match($match) display[$display_by_url]");
+        // display ad on all except matching urls
+        if ($display_by_url == 0) {
           if (empty($urls) || !$match) {
             _debug_echo("ad_channel_cache: aid($aid) is valid");
-            $valid[] = $aid;
-            if ($display == 1) {
-              $nochannel_weight[$chid] = $channel->no_channel_weight;
+            $valid_ads[$chid][] = $aid;
+            if ($nochannel_display == 1) {
+              $nochannel_percent[$chid] = $channel->no_channel_percent;
+              _debug_echo("ad_channel_cache: channel($chid) no_channel_percent($nochannel_percent[$chid])");
             }
-            $matched_channel[$aid] = $chid;
-            _debug_echo("ad_channel_cache: channel($channel->chid) no_channel_weight(". $nochannel_weight[$chid] .')');
+            else {
+              _debug_echo("ad_channel_cache: channel($chid)");
+            }
             break;
           }
         }
-        else { // display only on listed urls
+        // display ad on matching urls
+        else {
           if (!empty($urls) && $match) {
             _debug_echo("ad_channel_cache: aid($aid) is valid");
-            $valid[] = $aid;
-            if ($display == 1) {
-              $nochannel_weight[$chid] = $channel->no_channel_weight;
+            $valid_ads[$chid][] = $aid;
+            if ($nochannel_display == 1) {
+              $nochannel_percent[$chid] = $channel->no_channel_percent;
+              _debug_echo("ad_channel_cache: channel($chid) no_channel_percent($nochannel_percent[$chid])");
             }
-            $matched_channel[$aid] = $chid;
+            else {
+              _debug_echo("ad_channel_cache: channel($chid)");
+            }
             break;
           }
         }
+        // no match so we didn't hit a break, ad is not valid
         _debug_echo("ad_channel_cache: aid($aid) is not valid");
       }
     }
     else {
-      // no channel information for ad, it's valid
-      $display = $channels['display'];
-      _debug_echo("ad_channel_cache: aid($aid) has no channel info [$display]");
-      switch ($display) {
+      // no channel information for ad
+      _debug_echo("ad_channel_cache: aid($aid) has no channel info, nochannel_display($nochannel_display)");
+      switch ($nochannel_display) {
         case 0:
-          $nochannel[] = $aid;
-          _debug_echo("ad_channel_cache: aid($aid) is valid if no valid ads found in current channel");
+          $nochannel_fallback_ads[] = $aid;
+          _debug_echo("ad_channel_cache: non-channel aid($aid) is valid if no valid ads are assigned to current channel");
           break;
         case 1:
-          $valid[] = $aid;
-          _debug_echo("ad_channel_cache: aid($aid) is valid");
+          $valid_ads[0][] = $aid;
+          _debug_echo("ad_channel_cache: non-channel aid($aid) is valid");
           break;
         case 2:
           _debug_echo("ad_channel_cache: aid($aid) is not valid");
@@ -77,57 +89,85 @@
     }
   }
 
-  // Apply weights, applicable for advertisements that are not assigned to any
-  // channel.
-  if (!empty($valid) && !empty($nochannel_weight)) {
-    $weights = array();
-    foreach ($valid as $aid) {
-      if (isset($matched_channel[$aid])) {
-        $chid = $matched_channel[$aid];
-        if (isset($nochannel_weight[$chid])) {
-          $weights[$aid] = $nochannel_weight[$chid];
-          _debug_echo("ad_channel_cache: ad $aid in channel $chid with weight ". $nochannel_weight[$chid]);
+  // Apply frequencies, applicable to all channels
+  if (!empty($valid_ads) && !empty($nochannel_percent)) {
+    $frequencies = array();
+    foreach (array_keys($valid_ads) as $chid) {
+      if ($chid) {
+        if (isset($nochannel_percent[$chid]) && $nochannel_percent[$chid]) {
+          $frequencies[$chid] = $nochannel_percent[$chid];
+          _debug_echo("ad_channel_cache: channel $chid has a non-channel ad frequency of ". $nochannel_percent[$chid]."%");
         }
         else {
-          // by default, ads are assigned a weight of 100%
-          $weights[$aid] = 100;
-          _debug_echo("ad_channel_cache: ad $aid in channel $chid with default weight of 100");
+          // by default, channels return 'non-channel ads' with a frequency
+          // of 10%
+          $frequencies[$chid] = 10;
+          _debug_echo("ad_channel_cache: channel $chid assigned a default non-channel ad frequency of 10%");
         }
       }
       else {
-        // by default, ads are assigned a weight of 100%
-        $weights[$aid] = 100;
-        _debug_echo("ad_channel_cache: ad $aid in no channel with default weight of 100");
+        // frequency for non-channel ads is not meaningful
       }
     }
-    if (!empty($weights)) {
-      $gcd = ad_channel_probability_gcd($weights);
-      $display = array();
-      _debug_echo("ad_channel_cache: adjusting channel weights, gcd ($gcd)");
-      foreach ($valid as $aid) {
-        $weight = $weights[$aid] / $gcd;
-        for ($i = 1; $i <= $weight; $i++) {
-          $display[] = $aid;
+    if (!empty($frequencies)) {
+      $balanced_channels = array();
+      $num_channels = sizeof($valid_ads);
+
+      foreach (array_keys($valid_ads) as $chid) {
+        if (isset($frequencies[$chid])) {
+           // for a given channel, ensure the proper ratio to non-channel ads
+          if ($frequencies[$chid] <=  50) { // increase occurrences of $chid
+            $balanced_channels[] = 0;
+            $frequency = round(100 / $frequencies[$chid]) - 1;
+            _debug_echo("ad_channel_cache: adjusting ratio of channel($chid) to $frequency:1 relative non-channel ads");
+            for ($i = 1; $i <= $frequency; $i++) {
+              $balanced_channels[] = $chid;
+            }
+          }
+          else { // add $chid and additional non-channel ads
+            $balanced_channels[] = $chid;
+            $frequency = round(100 / (100 - $frequencies[$chid])) - 1;
+            _debug_echo("ad_channel_cache: adjusting ratio of channel($chid) to 1:$frequency relative non-channel ads");
+            for ($i = 1; $i <= $frequency; $i++) {
+              $balanced_channels[] = 0;
+            }
+          }
         }
       }
-      $valid = $display;
+      _debug_echo('ad_channel_cache: channel 0 contains all non-channel ads');
+      if (adserve_variable('debug') >= 2) {
+        foreach ($balanced_channels as $key => $chid) {
+          _debug_echo("ad_channel_cache: channel $chid => index $key");
+        }
+      }
     }
+    $random_channel = _select_channel_id($balanced_channels);
   }
-  else if (empty($valid) && !empty($nochannel)) {
+  else if (!empty($valid_ads)) {
+    foreach ($valid_ads as $chid => $ads) {
+      $chids[$chid] = $chid;
+    }
+    shuffle($chids);
+    $random_channel = array_pop($chids);
+  }
+  else if (empty($valid_ads) && !empty($nochannel_fallback_ads)) {
     _debug_echo("ad_channel_cache: using ads with no channel info");
-    $valid = $nochannel;
+    $valid_ads[0] = $nochannel_fallback_ads;
+    $random_channel = 0;
   }
 
   $premiere = adserve_cache('get_cache', 'premiere');
-  $premieres = array();
   if (is_array($premiere)) {
-    foreach ($valid as $aid) {
-      if (in_array($aid, $premiere)) {
-        _debug_echo("ad_channel_cache: aid($aid) is premiere advertisement");
-        $premieres[$aid] = $aid;
-      }
-      else {
-        _debug_echo("ad_channel_cache: aid($aid) is not a premiere advertisement");
+    $premieres = array();
+    foreach (array_keys($valid_ads) as $chid) {
+      foreach ($valid_ads[$chid] as $aid) {
+        if (in_array($aid, $premiere)) {
+          _debug_echo("ad_channel_cache: aid($aid) is premiere advertisement");
+          $premieres[$aid] = $aid;
+        }
+        else {
+          _debug_echo("ad_channel_cache: aid($aid) is not a premiere advertisement");
+        }
       }
     }
     if (!empty($premieres)) {
@@ -135,31 +175,65 @@
       return $premieres;
     }
   }
-  _debug_echo("ad_channel_cache: returning non-premiere advertisements");
-  return $valid;
+  _debug_echo("ad_channel_cache: returning non-premiere advertisements from randomly selected channel $random_channel");
+
+  if (isset($valid_ads[$random_channel])) {
+    return ad_channel_enforce_inventory_level($random_channel, $valid_ads[$random_channel]);
+  }
 }
 
 /**
- * Returns the greatest common divisor of an array of integers.
+ * Randomly select a valid channel id from an array channel ids
+ * @param array, valid array.
  */
-function ad_channel_probability_gcd($integers) {
-  $gcd = array_shift($integers);
+function _select_channel_id($choices) {
+  $selected = 0;
+  if (is_array($choices)) {
+    $available = sizeof($choices);
+    _debug_echo("ad_channel_cache: randomly selecting from $available indexes.");
+    $selected = $available > 1 ? $choices[mt_rand(0, $available - 1)] : $choices[0];
+    _debug_echo("ad_channel_cache: randomly selected channel $selected.");
+  }
 
-  while (!empty($integers)) {
-    $gcd = _ad_channel_probability_gcd($gcd, array_shift($integers));
-  }
-  return $gcd;
+  return $selected;
 }
 
-/**
- * Helper function to calculate the greatest common divisor using the Euclidean
- * algorithm (http://en.wikipedia.org/wiki/Euclidean_algorithm).
+/*
+ * Augment the selected channel with 'remnant' ads to ensure that any specified
+ * inventory level is honored
+ * @param int, channel id
+ * @param array, valid array.
  */
-function _ad_channel_probability_gcd($a, $b) {
-  if ($b == 0) {
-    return $a;
+function ad_channel_enforce_inventory_level($chid, $ads) {
+  if ($chid > 0) {
+    $channels = adserve_cache('get_cache', 'channel');
+    $channel = $channels['channels'][$chid];
+    $level = $channel->inventory;
+    $num_ads = count($ads);
+    if ($num_ads < $level) {
+      _debug_echo("ad_channel_enforce_inventory_level: channel($chid) has $num_ads and needs $level");
+      $remnants = array_values(adserve_cache('get_cache', 'remnant'));
+      $available = count($remnants);
+      if ($available > 0) {
+        _debug_echo("ad_channel_enforce_inventory_level: randomly selecting from $available remnants.");
+        while (count($ads) < $level) {
+          shuffle($remnants);
+          $selected = array_pop($remnants);
+          _debug_echo("ad_channel_enforce_inventory_level: selected $selected.");
+          $ads[] = $selected;
+        }
+      }
+      else {
+        _debug_echo("ad_channel_enforce_inventory_level: no remnants to choose from.");
+      }
+    }
+    else {
+      _debug_echo("ad_channel_enforce_inventory_level: channel($chid) no inventory level assigned");
+    }
   }
   else {
-    return _ad_channel_probability_gcd($b, $a % $b);
+    _debug_echo("ad_channel_enforce_inventory_level: not needed for channel($chid)");
   }
+  return $ads;
 }
+