docstr: Performs predictions using silverkite model.
  It determines if the prediction should be simulation-based or not and then
  predicts using that setting.
  The function determines if it should use simulation-based predictions or
  that is not necessary.
  Here is the logic for determining if simulations are needed:
  
  - If the model is not autoregressive, then clearly no simulations are needed
  - If the model is autoregressive, however the minimum lag appearing in the model
    is larger than the forecast horizon, then simulations are not needed.
    This is because the lags can be calculated fully without predicting the future.
  
  User can overwrite the above behavior and force no simulations using
  ``force_no_sim`` argument, in which case some lags will be imputed.
  This option should not be used by most users.
  Some scenarios where advanced user might want to use
  this is (a) when ``min_lag_order >= forecast_horizon`` does not hold strictly
  but close to hold. (b) user want to predict fast, the autoregression
  lags are normalized. In that case the predictions returned could correspond
  to an approximation of a model without autoregression.
  
  
  Parameters
  ----------
  fut_df : `pandas.DataFrame`
      The data frame which includes the timestamps for prediction
      and possibly regressors.
  trained_model : `dict`
      A fitted silverkite model which is the output of ``self.forecast``
  freq : `str`, optional, default None
      Timeseries frequency, DateOffset alias.
      See https://pandas.pydata.org/pandas-docs/stable/user_guide/timeseries.html#offset-aliases
      for the allowed strings.
      If None, it is extracted from ``trained_model`` input.
  past_df : `pandas.DataFrame` or None, default None
      A data frame with past values if autoregressive methods are called
      via autoreg_dict parameter of ``greykite.algo.forecast.silverkite.SilverkiteForecast.py``.
      Note that this ``past_df`` can be anytime before the training end timestamp, but can not
      exceed it.
  new_external_regressor_df: `pandas.DataFrame` or None, default None
      Contains the regressors not already included in ``fut_df``.
  include_err : `bool`, optional, default None
      Boolean to determine if errors are to be incorporated in the simulations.
      If None, it will be set to True if uncertainty is passed to the model and
      otherwise will be set to False
  force_no_sim : `bool`, default False
      If True, prediction with no simulations is forced.
      This can be useful when speed is of concern or for validation purposes.
      In this case, the potential non-available lags will be imputed.
      Most users should not set this to True as the consequences could be
      hard to quantify.
  simulation_num : `int` or None, default None
      The number of simulations for when simulations are used for generating
      forecasts and prediction intervals. If None, it will be inferred from
      the model (``trained_model``).
  fast_simulation: `bool` or None, default None
      Deterimes if fast simulations are to be used. This only impacts models
      which include auto-regression. This method will only generate one simulation
      without any error being added and then add the error using the volatility
      model. The advantage is a major boost in speed during inference and the
      disadvantage is potentially less accurate prediction intervals.
      If None, it will be inferred from the model (``trained_model``).
  na_fill_func : callable (`pd.DataFrame` -> `pd.DataFrame`)
      default::
  
          lambda df: df.interpolate().bfill().ffill()
  
      A function which interpolates missing values in a dataframe.
      The main usage is invoked when there is a gap between the timestamps in ``fut_df``.
      The main use case is when the user wants to predict a period which is not an immediate period
      after training.
      In that case to fill in the gaps, the regressors need to be interpolated/filled.
      The default works by first interpolating the continuous variables.
      Then it uses back-filling and then forward-filling for categorical variables.
  
  
  Returns
  -------
  result: `dict`
      A dictionary with following items
  
      - "fut_df": `pandas.DataFrame`
          The same as input dataframe with an added column for the response.
          If value_col already appears in ``fut_df``, it will be over-written.
          If ``uncertainty_dict`` is provided as input,
          it will also contain a ``QUANTILE_SUMMARY_COL`` column.
          Here are the expected columns:
  
          (1) A time column with the column name being ``trained_model["time_col"]``
          (2) The predicted response in ``value_col`` column.
          (3) Quantile summary response in ``QUANTILE_SUMMARY_COL`` column.
              This column only appears if the model includes uncertainty.
          (4) Error std in `ERR_STD_COL` column.
              This column only appears if the model includes uncertainty.
  
      - "x_mat": `pandas.DataFrame`
          Design matrix of the predictive machine-learning model
code: def predict(
      self,
      fut_df,
      trained_model,
      freq=None,
      past_df=None,
      new_external_regressor_df=None,
      include_err=None,
      force_no_sim=False,
      simulation_num=None,
      fast_simulation=None,
      na_fill_func=lambda s: s.interpolate().bfill().ffill(),
  ):
      """Performs predictions using silverkite model.
      It determines if the prediction should be simulation-based or not and then
      predicts using that setting.
      The function determines if it should use simulation-based predictions or
      that is not necessary.
      Here is the logic for determining if simulations are needed:
  
      - If the model is not autoregressive, then clearly no simulations are needed
      - If the model is autoregressive, however the minimum lag appearing in the model
        is larger than the forecast horizon, then simulations are not needed.
        This is because the lags can be calculated fully without predicting the future.
  
      User can overwrite the above behavior and force no simulations using
      ``force_no_sim`` argument, in which case some lags will be imputed.
      This option should not be used by most users.
      Some scenarios where advanced user might want to use
      this is (a) when ``min_lag_order >= forecast_horizon`` does not hold strictly
      but close to hold. (b) user want to predict fast, the autoregression
      lags are normalized. In that case the predictions returned could correspond
      to an approximation of a model without autoregression.
  
  
      Parameters
      ----------
      fut_df : `pandas.DataFrame`
          The data frame which includes the timestamps for prediction
          and possibly regressors.
      trained_model : `dict`
          A fitted silverkite model which is the output of ``self.forecast``
      freq : `str`, optional, default None
          Timeseries frequency, DateOffset alias.
          See https://pandas.pydata.org/pandas-docs/stable/user_guide/timeseries.html#offset-aliases
          for the allowed strings.
          If None, it is extracted from ``trained_model`` input.
      past_df : `pandas.DataFrame` or None, default None
          A data frame with past values if autoregressive methods are called
          via autoreg_dict parameter of ``greykite.algo.forecast.silverkite.SilverkiteForecast.py``.
          Note that this ``past_df`` can be anytime before the training end timestamp, but can not
          exceed it.
      new_external_regressor_df: `pandas.DataFrame` or None, default None
          Contains the regressors not already included in ``fut_df``.
      include_err : `bool`, optional, default None
          Boolean to determine if errors are to be incorporated in the simulations.
          If None, it will be set to True if uncertainty is passed to the model and
          otherwise will be set to False
      force_no_sim : `bool`, default False
          If True, prediction with no simulations is forced.
          This can be useful when speed is of concern or for validation purposes.
          In this case, the potential non-available lags will be imputed.
          Most users should not set this to True as the consequences could be
          hard to quantify.
      simulation_num : `int` or None, default None
          The number of simulations for when simulations are used for generating
          forecasts and prediction intervals. If None, it will be inferred from
          the model (``trained_model``).
      fast_simulation: `bool` or None, default None
          Deterimes if fast simulations are to be used. This only impacts models
          which include auto-regression. This method will only generate one simulation
          without any error being added and then add the error using the volatility
          model. The advantage is a major boost in speed during inference and the
          disadvantage is potentially less accurate prediction intervals.
          If None, it will be inferred from the model (``trained_model``).
      na_fill_func : callable (`pd.DataFrame` -> `pd.DataFrame`)
          default::
  
              lambda df: df.interpolate().bfill().ffill()
  
          A function which interpolates missing values in a dataframe.
          The main usage is invoked when there is a gap between the timestamps in ``fut_df``.
          The main use case is when the user wants to predict a period which is not an immediate period
          after training.
          In that case to fill in the gaps, the regressors need to be interpolated/filled.
          The default works by first interpolating the continuous variables.
          Then it uses back-filling and then forward-filling for categorical variables.
  
  
      Returns
      -------
      result: `dict`
          A dictionary with following items
  
          - "fut_df": `pandas.DataFrame`
              The same as input dataframe with an added column for the response.
              If value_col already appears in ``fut_df``, it will be over-written.
              If ``uncertainty_dict`` is provided as input,
              it will also contain a ``QUANTILE_SUMMARY_COL`` column.
              Here are the expected columns:
  
              (1) A time column with the column name being ``trained_model["time_col"]``
              (2) The predicted response in ``value_col`` column.
              (3) Quantile summary response in ``QUANTILE_SUMMARY_COL`` column.
                  This column only appears if the model includes uncertainty.
              (4) Error std in `ERR_STD_COL` column.
                  This column only appears if the model includes uncertainty.
  
          - "x_mat": `pandas.DataFrame`
              Design matrix of the predictive machine-learning model
  
      """
      fut_df = fut_df.copy()
      time_col = trained_model["time_col"]
      value_col = trained_model["value_col"]
      min_lag_order = trained_model["min_lag_order"]
      max_lag_order = trained_model["max_lag_order"]
  
      if simulation_num is None:
          simulation_num = trained_model["simulation_num"]
  
      if fast_simulation is None:
          fast_simulation = trained_model["fast_simulation"]
  
      if freq is None:
          freq = trained_model["freq"]
  
      if fut_df.shape[0] <= 0:
          raise ValueError(
              "``fut_df`` must be a dataframe of non-zero size."
          )
  
      if time_col not in fut_df.columns:
          raise ValueError(
              f"``fut_df`` must include {time_col} as time column, "
              "which is what ``trained_model`` considers to be the time column."
          )
      fut_df[time_col] = pd.to_datetime(fut_df[time_col])
  
      # Handles ``past_df``.
      training_past_df = trained_model["train_df"].copy()
      if past_df is None or len(past_df) == 0:
          # In the case that we use ``train_df`` from the ``forecast`` method,
          # we don't check the quality since it's constructed by the method.
          log_message(
              message="``past_df`` not provided during prediction, use the ``train_df`` from training results.",
              level=LoggingLevelEnum.DEBUG,
          )
          # The ``past_df`` has been manipulated in the training method to immediately precede the future periods.
          past_df = training_past_df
      else:
          # In the case that ``past_df`` is passed, we combine it with the known dfs.
          past_df[time_col] = pd.to_datetime(past_df[time_col])
          if past_df[time_col].max() > training_past_df[time_col].max():
              raise ValueError(
                  "``past_df`` can not have timestamps later than the training end timestamp."
              )
          # Combines ``past_df`` with ``training_past_df`` to get all available values.
          past_df = (
              past_df.append(training_past_df)
              .dropna(subset=[value_col])
              # When there are duplicates, the value passed from ``past_df`` is kept.
              .drop_duplicates(subset=time_col)
              .reset_index(drop=True)
          )
      # Fills any missing timestamps in ``past_df``. These values will be imputed.
      past_df = fill_missing_dates(
          df=past_df, time_col=time_col, freq=freq
      )[
          0
      ]  # `fill_missing_dates` returns a tuple where the first one is the df.
  
      # If ``value_col`` appears in user provided ``fut_df``,
      # we remove it to avoid issues in merging
      # also note that such column is unnecessary
      if value_col in fut_df.columns:
          del fut_df[value_col]
  
      if include_err is None:
          include_err = trained_model["uncertainty_dict"] is not None
  
      if trained_model["uncertainty_dict"] is None and include_err:
          raise ValueError(
              "`include_err=True` was passed. "
              "However model does not support uncertainty. "
              "To support uncertainty pass `uncertainty_dict` to the model."
          )
  
      # If the minimal lag order for lagged regressors is less than the size of fut_df,
      # raise a warning of potential imputation of lagged regressor columns.
      # Note that all lagged regressor columns must be included in ``fut_df`` or ``new_external_regressor_df``
      min_lagged_regressor_order = trained_model[
          "min_lagged_regressor_order"
      ]
      lagged_regressor_dict = trained_model["lagged_regressor_dict"]
      if (
          min_lagged_regressor_order is not None
          and min_lagged_regressor_order < fut_df.shape[0]
      ):
          warnings.warn(
              f"Trained model's `min_lagged_regressor_order` ({int(min_lagged_regressor_order)}) "
              f"is less than the size of `fut_df` ({fut_df.shape[0]}), "
              f"NaN values (if there are any) in lagged regressor columns have been imputed. "
              f"More info: {lagged_regressor_dict}.",
              UserWarning,
          )
  
      has_autoreg_structure = trained_model["has_autoreg_structure"]
  
      # In absence of autoregression, we can return quickly.
      # Also note ``fut_df`` can overlap with training times without any issues,
      # ``past_df`` is not needed for autoregression, but may be needed for lagged regression
      # and we do not need to track the overlap.
      if not has_autoreg_structure:
          pred_res = self.predict_no_sim(
              fut_df=fut_df,
              trained_model=trained_model,
              past_df=past_df,
              new_external_regressor_df=new_external_regressor_df,
              time_features_ready=False,
              regressors_ready=False,
          )
          fut_df = pred_res["fut_df"]
          x_mat = pred_res["x_mat"]
  
          return {
              "fut_df": fut_df,
              "x_mat": x_mat,
              "simulations_not_used": None,
              "fut_df_info": None,
              "min_lag_order": None,
          }
  
      # From here we assume model has autoregression,
      # because otherwise we would have returned above.
  
      # Checks if imputation is needed.
      # Writes to log message if imputation is needed for debugging purposes.
      # This happens when
      # (1) ``past_df`` is too short and does not cover the earliest lag needed.
      # (2) ``past_df`` has missing values.
      past_df_sufficient = True
      # The check happens when ``freq`` is not None.
      # We made sure ``freq`` is not None before but wanna add a safeguard.
      if freq is not None:
          pred_min_ts = fut_df[
              time_col
          ].min()  # the prediction period's minimum timestamp
          past_df_min_ts = past_df[
              time_col
          ].min()  # the past df's minimum timestamp
          lag_min_ts_needed = (
              pred_min_ts - to_offset(freq) * max_lag_order
          )  # the minimum timestamp needed (max lag)
          # Checks (1) if ``past_df`` covers the period after ``lag_min_ts_needed``.
          past_df_sufficient = past_df_sufficient and (
              past_df_min_ts <= lag_min_ts_needed
          )
          if past_df_sufficient:
              # Checks (2) if ``past_df`` has any missing value after ``lag_min_ts_needed``
              past_df_after_min_ts = past_df[
                  past_df[time_col] >= lag_min_ts_needed
              ]
              past_df_sufficient = past_df_sufficient and (
                  past_df_after_min_ts[value_col].isna().sum() == 0
              )
      if not past_df_sufficient:
          log_message(
              message="``past_df`` is not sufficient, imputation is performed when creating autoregression terms.",
              level=LoggingLevelEnum.DEBUG,
          )
  
      if new_external_regressor_df is not None:
          fut_df = pd.concat(
              [fut_df, new_external_regressor_df],
              axis=1,
              ignore_index=False,
              sort=False,
          )
  
      fut_df_info = self.partition_fut_df(
          fut_df=fut_df,
          trained_model=trained_model,
          na_fill_func=na_fill_func,
          freq=freq,
      )
  
      fut_df_before_training = fut_df_info["fut_df_before_training"]
      fut_df_within_training = fut_df_info["fut_df_within_training"]
      fut_df_after_training_expanded = fut_df_info[
          "fut_df_after_training_expanded"
      ]
      index_after_training_original = fut_df_info[
          "index_after_training_original"
      ]
  
      inferred_forecast_horizon = fut_df_info[
          "inferred_forecast_horizon"
      ]
  
      fut_df_list = []
      x_mat_list = []
  
      # We allow calculating extended fitted values on a longer backward
      # history with imputation if ``past_df`` is not sufficient.
      if fut_df_before_training.shape[0] > 0:
          min_timestamp = fut_df_before_training[time_col].min()
          past_df_before_min_timestamp = past_df[
              past_df[time_col] < min_timestamp
          ]
          # Since ``fut_df_before_training`` does not have ``value_col`` (dropped above),
          # but we need the actual values for ``fut_df_before_training`` in case the lags
          # are not enough and we don't have simulation, we try to find the values from
          # ``past_df``. If some values are still missing, those values will be imputed.
          fut_df_before_training = fut_df_before_training.merge(
              past_df[[time_col, value_col]], on=time_col, how="left"
          )
          # Imputation will be done during ``self.predict_no_sim`` if ``past_df_before_min_timestamp``
          # does not have sufficient AR terms.
          pred_res = self.predict_no_sim(
              fut_df=fut_df_before_training,
              trained_model=trained_model,
              past_df=past_df_before_min_timestamp,
              new_external_regressor_df=None,
              time_features_ready=False,
              regressors_ready=True,
          )
          fut_df0 = pred_res["fut_df"]
          x_mat0 = pred_res["x_mat"]
          fut_df_list.append(fut_df0.reset_index(drop=True))
          x_mat_list.append(x_mat0)
  
      fitted_df = trained_model["fitted_df"]
      fitted_x_mat = trained_model["x_mat"]
      potential_forecast_cols = [
          time_col,
          value_col,
          QUANTILE_SUMMARY_COL,
          ERR_STD_COL,
      ]
      existing_forecast_cols = [
          col
          for col in potential_forecast_cols
          if col in fitted_df.columns
      ]
      fitted_df = fitted_df[existing_forecast_cols]
  
      # For within training times, we simply use the fitted data
      if fut_df_within_training.shape[0] > 0:
          # Creates a dummy index to get the consistent index on ``fitted_x_mat``
          fut_df0 = pd.merge(
              fut_df_within_training.reset_index(drop=True),
              fitted_df.reset_index(drop=True),
              on=[time_col],
          )
  
          # Finds out where ``fut_df_within_training`` intersects with ``fitted_df``
          # This is for edge cases where ```fut_df_within_training``` does not have all the
          # times appearing in ``fitted_df``
          fut_df_within_training["dummy_bool_index"] = True
          fut_df_index = pd.merge(
              fut_df_within_training.reset_index(drop=True)[
                  [time_col, "dummy_bool_index"]
              ],
              fitted_df.reset_index(drop=True)[[time_col]],
              on=[time_col],
              how="right",
          )
          ind = fut_df_index["dummy_bool_index"].fillna(False)
          del fut_df_index
          fitted_x_mat = fitted_x_mat.reset_index(drop=True).loc[ind]
          del fut_df_within_training["dummy_bool_index"]
  
          assert fut_df0.shape[0] == fut_df_within_training.shape[0]
  
          fut_df_list.append(fut_df0.reset_index(drop=True))
          x_mat_list.append(fitted_x_mat)
  
      # The future timestamps need to be predicted
      # There are two cases: either simulations are needed or not
      # This is decided as follows:
      simulations_not_used = (
          (not has_autoreg_structure)
          or force_no_sim
          or (inferred_forecast_horizon <= min_lag_order)
      )
  
      # ``new_external_regressor_df`` will be passed as None
      # since it is already included in ``fut_df``.
      # ``past_df`` doesn't need to change because either (1) it is passed from
      # this ``predict`` method directly, in which case it should be immediately preceding the
      # ``fut_df_after_training_expanded``;
      # or (2) it is from the training model, where the last term is the last training timestamp,
      # which should also immediately precedes the ``fut_df_after_training_expanded``.
      if (
          fut_df_after_training_expanded is not None
          and fut_df_after_training_expanded.shape[0] > 0
      ):
          if simulations_not_used:
              pred_res = self.predict_no_sim(
                  fut_df=fut_df_after_training_expanded,
                  trained_model=trained_model,
                  past_df=past_df,
                  new_external_regressor_df=None,
                  time_features_ready=False,
                  regressors_ready=True,
              )
              fut_df0 = pred_res["fut_df"]
              x_mat0 = pred_res["x_mat"]
          elif fast_simulation:
              pred_res = self.predict_via_sim_fast(
                  fut_df=fut_df_after_training_expanded,
                  trained_model=trained_model,
                  past_df=past_df,
                  new_external_regressor_df=None,
              )
              fut_df0 = pred_res["fut_df"]
              x_mat0 = pred_res["x_mat"]
          else:
              pred_res = self.predict_via_sim(
                  fut_df=fut_df_after_training_expanded,
                  trained_model=trained_model,
                  past_df=past_df,
                  new_external_regressor_df=None,
                  simulation_num=simulation_num,
                  include_err=include_err,
              )
              fut_df0 = pred_res["fut_df"]
              x_mat0 = pred_res["x_mat"]
          fut_df0 = fut_df0[index_after_training_original]
          x_mat0 = x_mat0[index_after_training_original]
          fut_df_list.append(fut_df0.reset_index(drop=True))
          x_mat_list.append(x_mat0)
  
      fut_df_final = pd.concat(
          fut_df_list, axis=0, ignore_index=True, sort=False
      )
  
      x_mat_final = pd.concat(
          x_mat_list, axis=0, ignore_index=True, sort=False
      )
  
      # Makes sure to return only necessary columns
      potential_forecast_cols = [
          time_col,
          value_col,
          QUANTILE_SUMMARY_COL,
          ERR_STD_COL,
      ]
      existing_forecast_cols = [
          col
          for col in potential_forecast_cols
          if col in fut_df_final.columns
      ]
      fut_df_final = fut_df_final[existing_forecast_cols]
  
      # Expects the created data has same size as the passed ``fut_df``
      assert len(fut_df_final) == len(
          fut_df
      ), "The generated data at predict phase must have same length as input ``fut_df``"
      assert len(x_mat_final) == len(
          fut_df
      ), "The generated data at predict phase must have same length as input ``fut_df``"
  
      return {
          "fut_df": fut_df_final,
          "x_mat": x_mat_final,
          "simulations_not_used": simulations_not_used,
          "fut_df_info": fut_df_info,
          "min_lag_order": min_lag_order,
      }
  
imports: import re
  import warnings
  from typing import Type
  import numpy
  import pandas
  from pandas.plotting import register_matplotlib_converters
  from pandas.tseries.frequencies import to_offset
  from greykite.algo.changepoint.adalasso.changepoint_detector import get_changepoints_dict
  from greykite.algo.changepoint.adalasso.changepoint_detector import get_seasonality_changepoints
  from greykite.algo.changepoint.adalasso.changepoints_utils import build_seasonality_feature_df_from_detection_result
  from greykite.algo.changepoint.adalasso.changepoints_utils import get_seasonality_changepoint_df_cols
  from greykite.algo.common.ml_models import fit_ml_model_with_evaluation
  from greykite.algo.common.ml_models import predict_ml
  from greykite.algo.common.ml_models import predict_ml_with_uncertainty
  from greykite.algo.forecast.silverkite.constants.silverkite_constant import default_silverkite_constant
  from greykite.algo.forecast.silverkite.constants.silverkite_seasonality import SilverkiteSeasonalityEnum
  from greykite.algo.forecast.silverkite.constants.silverkite_seasonality import SilverkiteSeasonalityEnumMixin
  from greykite.algo.forecast.silverkite.forecast_silverkite_helper import get_fourier_feature_col_names
  from greykite.algo.forecast.silverkite.forecast_silverkite_helper import get_similar_lag
  from greykite.common.constants import CHANGEPOINT_COL_PREFIX
  from greykite.common.constants import ERR_STD_COL
  from greykite.common.constants import QUANTILE_SUMMARY_COL
  from greykite.common.constants import SEASONALITY_REGEX
  from greykite.common.constants import TimeFeaturesEnum
  from greykite.common.enums import TimeEnum
  from greykite.common.features.timeseries_features import add_daily_events
  from greykite.common.features.timeseries_features import add_time_features_df
  from greykite.common.features.timeseries_features import fourier_series_multi_fcn
  from greykite.common.features.timeseries_features import get_changepoint_dates_from_changepoints_dict
  from greykite.common.features.timeseries_features import get_changepoint_features
  from greykite.common.features.timeseries_features import get_changepoint_features_and_values_from_config
  from greykite.common.features.timeseries_features import get_default_origin_for_time_vars
  from greykite.common.features.timeseries_lags import build_autoreg_df
  from greykite.common.features.timeseries_lags import build_autoreg_df_multi
  from greykite.common.logging import LoggingLevelEnum
  from greykite.common.logging import log_message
  from greykite.common.python_utils import get_pattern_cols
  from greykite.common.python_utils import unique_elements_in_list
  from greykite.common.time_properties import describe_timeseries
  from greykite.common.time_properties import fill_missing_dates
  from greykite.common.time_properties import min_gap_in_seconds
  from greykite.common.time_properties_forecast import get_default_horizon_from_period
label_desc: Use image node_id 10 for calling the SilverkiteForecast obj's underlying member method code with example usage: obj.predict(fut_df, trained_model, freq, past_df, new_external_regressor_df, include_err, force_no_sim, simulation_num, fast_simulation, na_fill_func) and returns: dict, dict