content: /*
   * Copyright (C) 2015 The Android Open Source Project
   *
   * Licensed 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.
   */
  
  package com.android.server.wifi.scanner;
  
  import android.annotation.NonNull;
  import android.annotation.Nullable;
  import android.net.wifi.ScanResult;
  import android.net.wifi.WifiScanner;
  import android.net.wifi.WifiScanner.ScanData;
  import android.net.wifi.WifiScanner.ScanSettings;
  import android.util.ArraySet;
  import android.util.Pair;
  import android.util.Rational;
  import android.util.Slog;
  
  import com.android.server.wifi.WifiNative;
  import com.android.server.wifi.scanner.ChannelHelper.ChannelCollection;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collection;
  import java.util.Collections;
  import java.util.Comparator;
  import java.util.HashMap;
  import java.util.Iterator;
  import java.util.List;
  import java.util.ListIterator;
  import java.util.Map;
  import java.util.Set;
  
  /**
   * <p>This class takes a series of scan requests and formulates the best hardware level scanning
   * schedule it can to try and satisfy requests. The hardware level accepts a series of buckets,
   * where each bucket represents a set of channels and an interval to scan at. This
   * scheduler operates as follows:</p>
   *
   * <p>Each new request is placed in the best predefined bucket. Once all requests have been added
   * the last buckets (lower priority) are placed in the next best bucket until the number of buckets
   * is less than the number supported by the hardware.
   *
   * <p>Finally, the scheduler creates a WifiNative.ScanSettings from the list of buckets which may be
   * passed through the Wifi HAL.</p>
   *
   * <p>This class is not thread safe.</p>
   */
  public class BackgroundScanScheduler {
  
      private static final String TAG = "BackgroundScanScheduler";
      private static final boolean DBG = false;
  
      public static final int DEFAULT_MAX_BUCKETS = 8;
      // Max channels that can be specified per bucket
      public static final int DEFAULT_MAX_CHANNELS_PER_BUCKET = 16;
      // anecdotally, some chipsets will fail without explanation with a higher batch size, and
      // there is apparently no way to retrieve the maximum batch size
      public static final int DEFAULT_MAX_SCANS_TO_BATCH = 10;
      public static final int DEFAULT_MAX_AP_PER_SCAN = 32;
  
      /**
       * Value that all scan periods must be an integer multiple of
       */
      private static final int PERIOD_MIN_GCD_MS = 10000;
      /**
       * Default period to use if no buckets are being scheduled
       */
      private static final int DEFAULT_PERIOD_MS = 30000;
      /**
       * Scan report threshold percentage to assign to the schedule by default
       * @see com.android.server.wifi.WifiNative.ScanSettings#report_threshold_percent
       */
      private static final int DEFAULT_REPORT_THRESHOLD_PERCENTAGE = 100;
  
      /**
       * List of predefined periods (in ms) that buckets can be scheduled at. Ordered by preference
       * if there are not enough buckets for all periods. All periods MUST be an integer multiple of
       * the next smallest bucket with the smallest bucket having a period of PERIOD_MIN_GCD_MS.
       * This requirement allows scans to be scheduled more efficiently because scan requests with
       * intersecting channels will result in those channels being scanned exactly once at the smaller
       * period and no unnecessary scan being scheduled. If this was not the case and two requests
       * had channel 5 with periods of 15 seconds and 25 seconds then channel 5 would be scanned
       * 296  (3600/15 + 3600/25 - 3500/75) times an hour instead of 240 times an hour (3600/15) if
       * the 25s scan is rescheduled at 30s. This is less important with higher periods as it has
       * significantly less impact. Ranking could be done by favoring shorter or longer; however,
       * this would result in straying further from the requested period and possibly power
       * implications if the scan is scheduled at a significantly lower period.
       *
       * For example if the hardware only supports 2 buckets and scans are requested with periods of
       * 40s, 20s and 10s then the two buckets scheduled will have periods 40s and 20s and the 10s
       * scan will be placed in the 20s bucket.
       *
       * If there are special scan requests such as exponential back off, we always dedicate a bucket
       * for each type. Regular scan requests will be packed into the remaining buckets.
       */
      private static final int[] PREDEFINED_BUCKET_PERIODS = {
          3 * PERIOD_MIN_GCD_MS,   // 30s
          12 * PERIOD_MIN_GCD_MS,  // 120s
          48 * PERIOD_MIN_GCD_MS,  // 480s
          1 * PERIOD_MIN_GCD_MS,   // 10s
          6 * PERIOD_MIN_GCD_MS,   // 60s
          192 * PERIOD_MIN_GCD_MS, // 1920s
          24 * PERIOD_MIN_GCD_MS,  // 240s
          96 * PERIOD_MIN_GCD_MS,  // 960s
          384 * PERIOD_MIN_GCD_MS, // 3840s
          -1,                      // place holder for exponential back off scan
      };
  
      private static final int EXPONENTIAL_BACK_OFF_BUCKET_IDX =
              (PREDEFINED_BUCKET_PERIODS.length - 1);
      private static final int NUM_OF_REGULAR_BUCKETS =
              (PREDEFINED_BUCKET_PERIODS.length - 1);
  
      /**
       * This class is an intermediate representation for scheduling. This maintins the channel
       * collection to be scanned by the bucket as settings are added to it.
       */
      private class Bucket {
          public int period;
          public int bucketId;
          private final List<ScanSettings> mScanSettingsList = new ArrayList<>();
          private final ChannelCollection mChannelCollection;
  
          Bucket(int period) {
              this.period = period;
              this.bucketId = 0;
              mScanSettingsList.clear();
              mChannelCollection = mChannelHelper.createChannelCollection();
          }
  
          /**
           * Copy constructor which populates the settings list from the original bucket object.
           */
          Bucket(Bucket originalBucket) {
              this(originalBucket.period);
              for (ScanSettings settings : originalBucket.getSettingsList()) {
                  mScanSettingsList.add(settings);
              }
          }
  
          /**
           * convert ChannelSpec to native representation
           */
          private WifiNative.ChannelSettings createChannelSettings(int frequency) {
              WifiNative.ChannelSettings channelSettings = new WifiNative.ChannelSettings();
              channelSettings.frequency = frequency;
              return channelSettings;
          }
  
          public boolean addSettings(ScanSettings scanSettings) {
              mChannelCollection.addChannels(scanSettings);
              return mScanSettingsList.add(scanSettings);
          }
  
          public boolean removeSettings(ScanSettings scanSettings) {
              if (mScanSettingsList.remove(scanSettings)) {
                  // It's difficult to handle settings removal from buckets in terms of
                  // maintaining the correct channel collection, so recreate the channel
                  // collection from the remaining elements.
                  updateChannelCollection();
                  return true;
              }
              return false;
          }
  
          public List<ScanSettings> getSettingsList() {
              return mScanSettingsList;
          }
  
          public void updateChannelCollection() {
              mChannelCollection.clear();
              for (ScanSettings settings : mScanSettingsList) {
                  mChannelCollection.addChannels(settings);
              }
          }
  
          public ChannelCollection getChannelCollection() {
              return mChannelCollection;
          }
  
          /**
           * convert the setting for this bucket to HAL representation
           */
          public WifiNative.BucketSettings createBucketSettings(int bucketId, int maxChannels) {
              this.bucketId = bucketId;
              int reportEvents = WifiScanner.REPORT_EVENT_NO_BATCH;
              int maxPeriodInMs = 0;
              int stepCount = 0;
              int bucketIndex = 0;
  
              for (int i = 0; i < mScanSettingsList.size(); ++i) {
                  WifiScanner.ScanSettings setting = mScanSettingsList.get(i);
                  int requestedReportEvents = setting.reportEvents;
                  if ((requestedReportEvents & WifiScanner.REPORT_EVENT_NO_BATCH) == 0) {
                      reportEvents &= ~WifiScanner.REPORT_EVENT_NO_BATCH;
                  }
                  if ((requestedReportEvents & WifiScanner.REPORT_EVENT_AFTER_EACH_SCAN) != 0) {
                      reportEvents |= WifiScanner.REPORT_EVENT_AFTER_EACH_SCAN;
                  }
                  if ((requestedReportEvents & WifiScanner.REPORT_EVENT_FULL_SCAN_RESULT) != 0) {
                      reportEvents |= WifiScanner.REPORT_EVENT_FULL_SCAN_RESULT;
                  }
                  // For the bucket allocated to exponential back off scan, the values of
                  // the exponential back off scan related parameters from the very first
                  // setting in the settings list will be used to configure this bucket.
                  //
                  if (i == 0 && setting.maxPeriodInMs != 0
                          && setting.maxPeriodInMs != setting.periodInMs) {
                      // Align the starting period with one of the pre-defined regular
                      // scan periods. This will optimize the scan schedule when it has
                      // both exponential back off scan and regular scan(s).
                      bucketIndex = findBestRegularBucketIndex(setting.periodInMs,
                                                       NUM_OF_REGULAR_BUCKETS);
                      period = PREDEFINED_BUCKET_PERIODS[bucketIndex];
                      maxPeriodInMs = (setting.maxPeriodInMs < period)
                                      ? period
                                      : setting.maxPeriodInMs;
                      stepCount = setting.stepCount;
                  }
              }
  
              WifiNative.BucketSettings bucketSettings = new WifiNative.BucketSettings();
              bucketSettings.bucket = bucketId;
              bucketSettings.report_events = reportEvents;
              bucketSettings.period_ms = period;
              bucketSettings.max_period_ms = maxPeriodInMs;
              bucketSettings.step_count = stepCount;
              mChannelCollection.fillBucketSettings(bucketSettings, maxChannels);
              return bucketSettings;
          }
      }
  
      /**
       * Maintains a list of buckets and the number that are active (non-null)
       */
      private class BucketList {
          // Comparator to sort the buckets in order of increasing time periods
          private final Comparator<Bucket> mTimePeriodSortComparator =
                  new Comparator<Bucket>() {
                      public int compare(Bucket b1, Bucket b2) {
                          return b1.period - b2.period;
                      }
                  };
          private final Bucket[] mBuckets;
          private int mActiveBucketCount = 0;
  
          BucketList() {
              mBuckets = new Bucket[PREDEFINED_BUCKET_PERIODS.length];
          }
  
          public void clearAll() {
              Arrays.fill(mBuckets, null);
              mActiveBucketCount = 0;
          }
  
          public void clear(int index) {
              if (mBuckets[index] != null) {
                  --mActiveBucketCount;
                  mBuckets[index] = null;
              }
          }
  
          public Bucket getOrCreate(int index) {
              Bucket bucket = mBuckets[index];
              if (bucket == null) {
                  ++mActiveBucketCount;
                  bucket = mBuckets[index] = new Bucket(PREDEFINED_BUCKET_PERIODS[index]);
              }
              return bucket;
          }
  
          public boolean isActive(int index) {
              return mBuckets[index] != null;
          }
  
          public Bucket get(int index) {
              return mBuckets[index];
          }
  
          public int size() {
              return mBuckets.length;
          }
  
          public int getActiveCount() {
              return mActiveBucketCount;
          }
  
          public int getActiveRegularBucketCount() {
              if (isActive(EXPONENTIAL_BACK_OFF_BUCKET_IDX)) {
                  return mActiveBucketCount - 1;
              } else {
                  return mActiveBucketCount;
              }
          }
  
          /**
           * Returns the active regular buckets sorted by their increasing time periods.
           */
          public List<Bucket> getSortedActiveRegularBucketList() {
              ArrayList<Bucket> activeBuckets = new ArrayList<>();
              for (int i = 0; i < mBuckets.length; i++) {
                  if (mBuckets[i] != null && i != EXPONENTIAL_BACK_OFF_BUCKET_IDX) {
                      activeBuckets.add(mBuckets[i]);
                  }
              }
              Collections.sort(activeBuckets, mTimePeriodSortComparator);
              return activeBuckets;
          }
      }
  
      private int mMaxBuckets = DEFAULT_MAX_BUCKETS;
      private int mMaxChannelsPerBucket = DEFAULT_MAX_CHANNELS_PER_BUCKET;
      private int mMaxBatch = DEFAULT_MAX_SCANS_TO_BATCH;
      private int mMaxApPerScan = DEFAULT_MAX_AP_PER_SCAN;
  
      public int getMaxBuckets() {
          return mMaxBuckets;
      }
  
      public void setMaxBuckets(int maxBuckets) {
          mMaxBuckets = maxBuckets;
      }
  
      public int getMaxChannelsPerBucket() {
          return mMaxChannelsPerBucket;
      }
  
      // TODO: find a way to get max channels
      public void setMaxChannelsPerBucket(int maxChannels) {
          mMaxChannelsPerBucket = maxChannels;
      }
  
      public int getMaxBatch() {
          return mMaxBatch;
      }
  
      // TODO: find a way to get max batch size
      public void setMaxBatch(int maxBatch) {
          mMaxBatch = maxBatch;
      }
  
      public int getMaxApPerScan() {
          return mMaxApPerScan;
      }
  
      public void setMaxApPerScan(int maxApPerScan) {
          mMaxApPerScan = maxApPerScan;
      }
  
      private final BucketList mBuckets = new BucketList();
      private final ChannelHelper mChannelHelper;
      private WifiNative.ScanSettings mSchedule;
      // This keeps track of the settings to the max time period bucket to which it was scheduled.
      private final Map<ScanSettings, Bucket> mSettingsToScheduledBucket = new HashMap<>();
  
      public BackgroundScanScheduler(ChannelHelper channelHelper) {
          mChannelHelper = channelHelper;
          createSchedule(new ArrayList<Bucket>(), getMaxChannelsPerBucket());
      }
  
      /**
       * Updates the schedule from the given set of requests.
       */
      public void updateSchedule(@NonNull Collection<ScanSettings> requests) {
          // create initial schedule
          mBuckets.clearAll();
          for (ScanSettings request : requests) {
              addScanToBuckets(request);
          }
  
          compactBuckets(getMaxBuckets());
  
          List<Bucket> bucketList = optimizeBuckets();
  
          List<Bucket> fixedBucketList =
                  fixBuckets(bucketList, getMaxBuckets(), getMaxChannelsPerBucket());
  
          createSchedule(fixedBucketList, getMaxChannelsPerBucket());
      }
  
      /**
       * Retrieves the current scanning schedule.
       */
      public @NonNull WifiNative.ScanSettings getSchedule() {
          return mSchedule;
      }
  
      /**
       * Returns true if the given scan result should be reported to a listener with the given
       * settings.
       */
      public boolean shouldReportFullScanResultForSettings(@NonNull ScanResult result,
              int bucketsScanned, @NonNull ScanSettings settings) {
          return ScanScheduleUtil.shouldReportFullScanResultForSettings(mChannelHelper,
                  result, bucketsScanned, settings, getScheduledBucket(settings));
      }
  
      /**
       * Returns a filtered version of the scan results from the chip that represents only the data
       * requested in the settings. Will return null if the result should not be reported.
       */
      public @Nullable ScanData[] filterResultsForSettings(@NonNull ScanData[] scanDatas,
              @NonNull ScanSettings settings) {
          return ScanScheduleUtil.filterResultsForSettings(mChannelHelper, scanDatas, settings,
                  getScheduledBucket(settings));
      }
  
      /**
       * Retrieves the max time period bucket idx at which this setting was scheduled
       */
      public int getScheduledBucket(ScanSettings settings) {
          Bucket maxScheduledBucket = mSettingsToScheduledBucket.get(settings);
          if (maxScheduledBucket != null) {
              return maxScheduledBucket.bucketId;
          } else {
              Slog.wtf(TAG, "No bucket found for settings");
              return -1;
          }
      }
  
      /**
       * creates a schedule for the current buckets
       */
      private void createSchedule(List<Bucket> bucketList, int maxChannelsPerBucket) {
          WifiNative.ScanSettings schedule = new WifiNative.ScanSettings();
          schedule.num_buckets = bucketList.size();
          schedule.buckets = new WifiNative.BucketSettings[bucketList.size()];
  
          schedule.max_ap_per_scan = 0;
          schedule.report_threshold_num_scans = getMaxBatch();
  
          // set all buckets in schedule
          int bucketId = 0;
          for (Bucket bucket : bucketList) {
              schedule.buckets[bucketId] =
                      bucket.createBucketSettings(bucketId, maxChannelsPerBucket);
              for (ScanSettings settings : bucket.getSettingsList()) {
                  // set APs per scan
                  if (settings.numBssidsPerScan > schedule.max_ap_per_scan) {
                      schedule.max_ap_per_scan = settings.numBssidsPerScan;
                  }
                  // set batching
                  if (settings.maxScansToCache != 0
                          && settings.maxScansToCache < schedule.report_threshold_num_scans) {
                      schedule.report_threshold_num_scans = settings.maxScansToCache;
                  }
              }
              bucketId++;
          }
  
          schedule.report_threshold_percent = DEFAULT_REPORT_THRESHOLD_PERCENTAGE;
  
          if (schedule.max_ap_per_scan == 0 || schedule.max_ap_per_scan > getMaxApPerScan()) {
              schedule.max_ap_per_scan = getMaxApPerScan();
          }
  
          // update base period as gcd of periods
          if (schedule.num_buckets > 0) {
              int gcd = schedule.buckets[0].period_ms;
              for (int b = 1; b < schedule.num_buckets; b++) {
                  gcd = Rational.gcd(schedule.buckets[b].period_ms, gcd);
              }
  
              if (gcd < PERIOD_MIN_GCD_MS) {
                  Slog.wtf(TAG, "found gcd less than min gcd");
                  gcd = PERIOD_MIN_GCD_MS;
              }
  
              schedule.base_period_ms = gcd;
          } else {
              schedule.base_period_ms = DEFAULT_PERIOD_MS;
          }
  
          mSchedule = schedule;
      }
  
      /**
       * Add a scan to the most appropriate bucket, creating the bucket if necessary.
       */
      private void addScanToBuckets(ScanSettings settings) {
          int bucketIndex;
  
          if (settings.maxPeriodInMs != 0 && settings.maxPeriodInMs != settings.periodInMs) {
              // exponential back off scan has a dedicated bucket
              bucketIndex = EXPONENTIAL_BACK_OFF_BUCKET_IDX;
          } else {
              bucketIndex = findBestRegularBucketIndex(settings.periodInMs, NUM_OF_REGULAR_BUCKETS);
          }
  
          mBuckets.getOrCreate(bucketIndex).addSettings(settings);
      }
  
      /**
       * find closest bucket period to the requested period in all predefined buckets
       */
      private static int findBestRegularBucketIndex(int requestedPeriod, int maxNumBuckets) {
          maxNumBuckets = Math.min(maxNumBuckets, NUM_OF_REGULAR_BUCKETS);
          int index = -1;
          int minDiff = Integer.MAX_VALUE;
          for (int i = 0; i < maxNumBuckets; ++i) {
              int diff = Math.abs(PREDEFINED_BUCKET_PERIODS[i] - requestedPeriod);
              if (diff < minDiff) {
                  minDiff = diff;
                  index = i;
              }
          }
          if (index == -1) {
              Slog.wtf(TAG, "Could not find best bucket for period " + requestedPeriod + " in "
                       + maxNumBuckets + " buckets");
          }
          return index;
      }
  
      /**
       * Reduce the number of required buckets by reassigning lower priority buckets to the next
       * closest period bucket.
       */
      private void compactBuckets(int maxBuckets) {
          int maxRegularBuckets = maxBuckets;
  
          // reserve one bucket for exponential back off scan if there is
          // such request(s)
          if (mBuckets.isActive(EXPONENTIAL_BACK_OFF_BUCKET_IDX)) {
              maxRegularBuckets--;
          }
          for (int i = NUM_OF_REGULAR_BUCKETS - 1;
                  i >= 0 && mBuckets.getActiveRegularBucketCount() > maxRegularBuckets; --i) {
              if (mBuckets.isActive(i)) {
                  for (ScanSettings scanRequest : mBuckets.get(i).getSettingsList()) {
                      int newBucketIndex = findBestRegularBucketIndex(scanRequest.periodInMs, i);
                      mBuckets.getOrCreate(newBucketIndex).addSettings(scanRequest);
                  }
                  mBuckets.clear(i);
              }
          }
      }
  
      /**
       * Clone the provided scan settings fields to a new ScanSettings object.
       */
      private ScanSettings cloneScanSettings(ScanSettings originalSettings) {
          ScanSettings settings = new ScanSettings();
          settings.band = originalSettings.band;
          settings.channels = originalSettings.channels;
          settings.periodInMs = originalSettings.periodInMs;
          settings.reportEvents = originalSettings.reportEvents;
          settings.numBssidsPerScan = originalSettings.numBssidsPerScan;
          settings.maxScansToCache = originalSettings.maxScansToCache;
          settings.maxPeriodInMs = originalSettings.maxPeriodInMs;
          settings.stepCount = originalSettings.stepCount;
          settings.isPnoScan = originalSettings.isPnoScan;
          return settings;
      }
  
      /**
       * Creates a split scan setting that needs to be added back to the current bucket.
       */
      private ScanSettings createCurrentBucketSplitSettings(ScanSettings originalSettings,
              Set<Integer> currentBucketChannels) {
          ScanSettings currentBucketSettings = cloneScanSettings(originalSettings);
          // Let's create a new settings for the current bucket with the same flags, but the missing
          // channels from the other bucket
          currentBucketSettings.band = WifiScanner.WIFI_BAND_UNSPECIFIED;
          currentBucketSettings.channels = new WifiScanner.ChannelSpec[currentBucketChannels.size()];
          int chanIdx = 0;
          for (Integer channel : currentBucketChannels) {
              currentBucketSettings.channels[chanIdx++] = new WifiScanner.ChannelSpec(channel);
          }
          return currentBucketSettings;
      }
  
      /**
       * Creates a split scan setting that needs to be added to the target lower time period bucket.
       * The reportEvents field is modified to remove REPORT_EVENT_AFTER_EACH_SCAN because we
       * need this flag only in the higher time period bucket.
       */
      private ScanSettings createTargetBucketSplitSettings(ScanSettings originalSettings,
              Set<Integer> targetBucketChannels) {
          ScanSettings targetBucketSettings = cloneScanSettings(originalSettings);
          // The new settings for the other bucket will have the channels that already in the that
          // bucket. We'll need to do some migration of the |reportEvents| flags.
          targetBucketSettings.band = WifiScanner.WIFI_BAND_UNSPECIFIED;
          targetBucketSettings.channels = new WifiScanner.ChannelSpec[targetBucketChannels.size()];
          int chanIdx = 0;
          for (Integer channel : targetBucketChannels) {
              targetBucketSettings.channels[chanIdx++] = new WifiScanner.ChannelSpec(channel);
          }
          targetBucketSettings.reportEvents =
                  originalSettings.reportEvents
                          & (WifiScanner.REPORT_EVENT_NO_BATCH
                                  | WifiScanner.REPORT_EVENT_FULL_SCAN_RESULT);
          return targetBucketSettings;
      }
  
      /**
       * Split the scan settings into 2 so that they can be put into 2 separate buckets.
       * @return The first scan setting needs to be added back to the current bucket
       *         The second scan setting needs to be added to the other bucket
       */
      private Pair<ScanSettings, ScanSettings> createSplitSettings(ScanSettings originalSettings,
              ChannelCollection targetBucketChannelCol) {
          Set<Integer> currentBucketChannels =
                  targetBucketChannelCol.getMissingChannelsFromSettings(originalSettings);
          Set<Integer> targetBucketChannels =
                  targetBucketChannelCol.getContainingChannelsFromSettings(originalSettings);
          // Two Copy of the original settings
          ScanSettings currentBucketSettings =
                  createCurrentBucketSplitSettings(originalSettings, currentBucketChannels);
          ScanSettings targetBucketSettings =
                  createTargetBucketSplitSettings(originalSettings, targetBucketChannels);
          return Pair.create(currentBucketSettings, targetBucketSettings);
      }
  
      /**
       * Try to merge the settings to lower buckets.
       * Check if the channels in this settings is already covered by a lower time period
       * bucket. If it's partially covered, the settings is split else the entire settings
       * is moved to the lower time period bucket.
       * This method updates the |mSettingsToScheduledBucket| mapping.
       * @return Pair<wasMerged, remainingSplitSettings>
       *         wasMerged -  boolean indicating whether the original setting was merged to lower time
       *                      period buckets.
       *         remainingSplitSettings - Partial Scan Settings that need to be added back to the
       *                                  current bucket.
       */
      private Pair<Boolean, ScanSettings> mergeSettingsToLowerBuckets(ScanSettings originalSettings,
              Bucket currentBucket, ListIterator<Bucket> iterTargetBuckets) {
          ScanSettings remainingSplitSettings = null;
          boolean wasMerged = false;
          Bucket maxScheduledBucket = currentBucket;
  
          while (iterTargetBuckets.hasPrevious()) {
              Bucket targetBucket = iterTargetBuckets.previous();
              ChannelCollection targetBucketChannelCol = targetBucket.getChannelCollection();
              if (targetBucketChannelCol.containsSettings(originalSettings)) {
                  targetBucket.addSettings(originalSettings);
                  // Update the max scheduled bucket for this setting
                  maxScheduledBucket = targetBucket;
                  wasMerged = true;
              } else if (targetBucketChannelCol.partiallyContainsSettings(originalSettings)) {
                  Pair<ScanSettings, ScanSettings> splitSettings;
                  if (remainingSplitSettings == null) {
                      splitSettings = createSplitSettings(originalSettings, targetBucketChannelCol);
                  } else {
                      splitSettings =
                              createSplitSettings(remainingSplitSettings, targetBucketChannelCol);
                  }
                  targetBucket.addSettings(splitSettings.second);
                  // Update the |remainingSplitSettings| to keep track of the remaining scan settings.
                  // The original settings could be split across multiple buckets.
                  remainingSplitSettings = splitSettings.first;
                  wasMerged = true;
              }
          }
          // Update the settings to scheduled bucket mapping. This is needed for event
          // reporting lookup
          mSettingsToScheduledBucket.put(originalSettings, maxScheduledBucket);
  
          return Pair.create(wasMerged, remainingSplitSettings);
      }
  
      /**
       * Optimize all the active buckets by removing duplicate channels in the buckets.
       * This method tries to go through the settings in all the buckets and checks if the same
       * channels for the setting is already being scanned by another bucked with lower time period.
       * If yes, move the setting to the lower time period bucket. If all the settings from a higher
       * period has been moved out, that bucket can be removed.
       *
       * We're trying to avoid cases where we have the same channels being scanned in different
       * buckets. This is to workaround the fact that the HAL implementations have a max number of
       * cumulative channel across buckets (b/28022609).
       */
      private List<Bucket> optimizeBuckets() {
          mSettingsToScheduledBucket.clear();
          List<Bucket> sortedBuckets = mBuckets.getSortedActiveRegularBucketList();
          ListIterator<Bucket> iterBuckets = sortedBuckets.listIterator();
          // This is needed to keep track of split settings that need to be added back to the same
          // bucket at the end of iterating thru all the settings. This has to be a separate temp list
          // to prevent concurrent modification exceptions during iterations.
          List<ScanSettings> currentBucketSplitSettingsList = new ArrayList<>();
  
          // We need to go thru each setting starting from the lowest time period bucket and check
          // if they're already contained in a lower time period bucket. If yes, delete the setting
          // from the current bucket and move it to the other bucket. If the settings are only
          // partially contained, split the settings into two and move the partial bucket back
          // to the same bucket. Finally, if all the settings have been moved out, remove the current
          // bucket altogether.
          while (iterBuckets.hasNext()) {
              Bucket currentBucket = iterBuckets.next();
              Iterator<ScanSettings> iterSettings = currentBucket.getSettingsList().iterator();
  
              currentBucketSplitSettingsList.clear();
  
              while (iterSettings.hasNext()) {
                  ScanSettings currentSettings = iterSettings.next();
                  ListIterator<Bucket> iterTargetBuckets =
                          sortedBuckets.listIterator(iterBuckets.previousIndex());
  
                  Pair<Boolean, ScanSettings> mergeResult =
                          mergeSettingsToLowerBuckets(
                                  currentSettings, currentBucket, iterTargetBuckets);
  
                  boolean wasMerged = mergeResult.first.booleanValue();
                  if (wasMerged) {
                      // Remove the original settings from the current bucket.
                      iterSettings.remove();
                      ScanSettings remainingSplitSettings = mergeResult.second;
                      if (remainingSplitSettings != null) {
                          // Add back the remaining split settings to the current bucket.
                          currentBucketSplitSettingsList.add(remainingSplitSettings);
                      }
                  }
              }
  
              for (ScanSettings splitSettings: currentBucketSplitSettingsList) {
                  currentBucket.addSettings(splitSettings);
              }
              if (currentBucket.getSettingsList().isEmpty()) {
                  iterBuckets.remove();
              } else {
                  // Update the channel collection to account for the removed settings
                  currentBucket.updateChannelCollection();
              }
          }
  
          // Update the settings to scheduled bucket map for all exponential scans.
          if (mBuckets.isActive(EXPONENTIAL_BACK_OFF_BUCKET_IDX)) {
              Bucket exponentialBucket = mBuckets.get(EXPONENTIAL_BACK_OFF_BUCKET_IDX);
              for (ScanSettings settings : exponentialBucket.getSettingsList()) {
                  mSettingsToScheduledBucket.put(settings, exponentialBucket);
              }
              sortedBuckets.add(exponentialBucket);
          }
  
          return sortedBuckets;
      }
  
      /**
       * Partition the channel set into 2 or more based on the max channels that can be specified for
       * each bucket.
       */
      private List<Set<Integer>> partitionChannelSet(Set<Integer> originalChannelSet,
              int maxChannelsPerBucket) {
          ArrayList<Set<Integer>> channelSetList = new ArrayList();
          ArraySet<Integer> channelSet = new ArraySet<>();
          Iterator<Integer> iterChannels = originalChannelSet.iterator();
  
          while (iterChannels.hasNext()) {
              channelSet.add(iterChannels.next());
              if (channelSet.size() == maxChannelsPerBucket) {
                  channelSetList.add(channelSet);
                  channelSet = new ArraySet<>();
              }
          }
          // Add the last partial set if any
          if (!channelSet.isEmpty()) {
              channelSetList.add(channelSet);
          }
          return channelSetList;
      }
  
      /**
       * Creates a list of split buckets with the channel collection corrected to fit the
       * max channel list size that can be specified. The original channel collection will be split
       * into multiple buckets with the same scan settings.
       * Note: This does not update the mSettingsToScheduledBucket map because this bucket is
       * essentially a copy of the original bucket, so it should not affect the event reporting.
       * This bucket results will come back the same time the original bucket results come back.
       */
      private List<Bucket> createSplitBuckets(Bucket originalBucket, List<Set<Integer>> channelSets) {
          List<Bucket> splitBucketList = new ArrayList<>();
          int channelSetIdx = 0;
  
          for (Set<Integer> channelSet : channelSets) {
              Bucket splitBucket;
              if (channelSetIdx == 0) {
                  // Need to keep the original bucket to keep track of the settings to scheduled
                  // bucket mapping.
                  splitBucket = originalBucket;
              } else {
                  splitBucket = new Bucket(originalBucket);
              }
              ChannelCollection splitBucketChannelCollection = splitBucket.getChannelCollection();
              splitBucketChannelCollection.clear();
              for (Integer channel : channelSet) {
                  splitBucketChannelCollection.addChannel(channel);
              }
              channelSetIdx++;
              splitBucketList.add(splitBucket);
          }
          return splitBucketList;
      }
  
      /**
       * Check if any of the buckets don't fit into the bucket specification and fix it. This
       * creates duplicate buckets to fit all the channels. So, the channels to be scanned
       * will be split across 2 (or more) buckets.
       * TODO: If we reach the max number of buckets, then this fix will be skipped!
       */
      private List<Bucket> fixBuckets(List<Bucket> originalBucketList, int maxBuckets,
              int maxChannelsPerBucket) {
          List<Bucket> fixedBucketList = new ArrayList<>();
          int totalNumBuckets = originalBucketList.size();
  
          for (Bucket originalBucket : originalBucketList) {
              ChannelCollection channelCollection = originalBucket.getChannelCollection();
              Set<Integer> channelSet = channelCollection.getChannelSet();
              if (channelSet.size() > maxChannelsPerBucket) {
                  List<Set<Integer>> channelSetList =
                          partitionChannelSet(channelSet, maxChannelsPerBucket);
                  int newTotalNumBuckets = totalNumBuckets + channelSetList.size() - 1;
                  if (newTotalNumBuckets <= maxBuckets) {
                      List<Bucket> splitBuckets = createSplitBuckets(originalBucket, channelSetList);
                      for (Bucket bucket : splitBuckets) {
                          fixedBucketList.add(bucket);
                      }
                      totalNumBuckets = newTotalNumBuckets;
                  } else {
                      fixedBucketList.add(originalBucket);
                  }
              } else {
                  fixedBucketList.add(originalBucket);
              }
          }
          return fixedBucketList;
      }
  }
  