code: def _numba_dual_join(
      df: pd.DataFrame, right: pd.DataFrame, gt_lt: list
  ):
      """
      # https://www.scitepress.org/papers/2018/68268/68268.pdf
      An alternative to the _range_indices algorithm
      and more generalised - it covers any pair of non equi joins
      in >, >=, <, <=.
      Returns a tuple of left and right indices.
      """
      # https://www.scitepress.org/papers/2018/68268/68268.pdf
  
      # summary:
      # get regions for first and second conditions in the pair
      # (l_col1, r_col1, op1), (l_col2, r_col2, op2)
      # the idea is that r_col1 should always be ahead of the
      # appropriate value from lcol1; same applies to l_col2 & r_col2.
      # if the operator is in less than join types
      # the l_col should be in ascending order
      # if in greater than join types, l_col should be
      # in descending order
      # Example :
      #     df1:
      #    id  value_1
      # 0   1        2
      # 1   1        5
      # 2   1        7
      # 3   2        1
      # 4   2        3
      # 5   3        4
      #
      #
      #  df2:
      #    id  value_2A  value_2B
      # 0   1         0         1
      # 1   1         3         5
      # 2   1         7         9
      # 3   1        12        15
      # 4   2         0         1
      # 5   2         2         4
      # 6   2         3         6
      # 7   3         1         3
      #
      #
      # ('value_1', 'value_2A','>'), ('value_1', 'value_2B', '<')
      # for the first pair, since op is greater than
      # 'value_1' is sorted in descending order
      #  our pairing should be :
      # value  source      region number
      # 12   value_2A       0
      # 7    value_2A       1
      # 7    value_1        2
      # 5    value_1        2
      # 4    value_1        2
      # 3    value_2A       2
      # 3    value_2A       2
      # 3    value_1        3
      # 2    value_2A       3
      # 2    value_1        4
      # 1    value_2A       4
      # 1    value_1        5
      # 0    value_2A       5
      # 0    value_2A       5
      #
      # note that 7 for value_2A is not matched with 7 of value_1
      # because it is >, not >=, hence the different region numbers
      # looking at the output above, we can safely discard regions 0 and 1
      # since they do not have any matches with value_1
      # for the second pair, since op is <, value_1 is sorted
      # in ascending order, and our pairing should be:
      #   value    source    region number
      #     1    value_2B       0
      #     1    value_2B       1
      #     1    value_1        2
      #     2    value_1        2
      #     3    value_2B       2
      #     3    value_1        3
      #     4    value_2B       3
      #     4    value_1        4
      #     5    value_2B       4
      #     5    value_1        5
      #     6    value_2B       5
      #     7    value_1        6
      #     9    value_2B       6
      #     15   value_2B       6
      #
      # from the above we can safely discard regions 0 and 1, since there are
      # no matches with value_1 ... note that the index for regions 0 and 1
      # coincide with the index for region 5 values in value_2A(0, 0);
      # as such those regions will be discarded.
      # Similarly, the index for regions 0 and 1 of value_2A(12, 7)
      # coincide with the index for regions 6 for value_2B(9, 15);
      # these will be discarded as well.
      # let's create a table of the regions, paired with the index
      #
      #
      #  value_1 :
      ###############################################
      # index-->  2  1  5  4  0  3
      # pair1-->  2  2  2  3  4  5
      # pair2-->  6  5  4  3  2  2
      ###############################################
      #
      #
      # value_2A, value_2B
      ##############################################
      # index --> 1  6  5  7
      # pair1 --> 2  2  3  4
      # pair2 --> 4  5  3  2
      ##############################################
      #
      # To find matching indices, the regions from value_1 must be less than
      # or equal to the regions in value_2A/2B.
      # pair1 <= pair1 and pair2 <= pair2
      # Starting from the highest region in value_1
      # 5 in pair1 is not less than any in value_2A/2B, so we discard
      # 4 in pair1 is matched to 4 in pair1 of value_2A/2B
      # we look at the equivalent value in pair2 for 4, which is 2
      # 2 matches 2 in pair 2, so we have a match -> (0, 7)
      # 3 in pair 1 from value_1 matches 3 and 4 in pair1 for value_2A/2B
      # next we compare the equivalent value from pair2, which is 3
      # 3 matches only 3 in value_2A/2B, so our only match is  -> (4, 5)
      # next is 2 (we have 3 2s in value_1 for pair1)
      # they all match 2, 2, 3, 4 in pair1 of value_2A/2B
      # compare the first equivalent in pair2 -> 4
      # 4 matches only 4, 5 in pair2 of value_2A/2B
      # ->(5, 1), (5, 6)
      # the next equivalent is -> 5
      # 5 matches only 5 in pair2 of value_2A/2B
      # -> (1, 6)
      # the last equivalent is -> 6
      # 6 has no match in pair2 of value_2A/2B, so we discard
      # our final matching indices for the left and right pairs
      #########################################################
      # left_index      right_index
      #     0              7
      #     4              5
      #     5              1
      #     5              6
      #     1              6
      ########################################################
      # and if we index the dataframes, we should get the output below:
      #################################
      #    value_1  value_2A  value_2B
      # 0        2         1         3
      # 1        5         3         6
      # 2        3         2         4
      # 3        4         3         5
      # 4        4         3         6
      ################################
      def _get_regions(
          df: pd.DataFrame,
          right: pd.DataFrame,
          left_on: str,
          right_on: str,
          op: str,
      ) -> tuple:
          """
          Get the regions for df[left_on] and right[right_on].
          Strictly for non-equi joins,
          specifically the  >, >= , <, <= operators.
          """
          mapping = {">=": "<=", ">": "<", "<=": ">=", "<": ">"}
          left_index = df.index._values
          right_index = right.index._values
          left_c = df[left_on]
          right_c = right[right_on]
          outcome = _generic_func_cond_join(
              left=right_c,
              right=left_c,
              op=mapping[op],
              multiple_conditions=True,
              keep="all",
          )
          if not outcome:
              return None
          right_index, left_index, search_indices = outcome
  
          if op in greater_than_join_types:
              left_index = left_index[::-1]
              search_indices = left_index.size - search_indices
          # logic for computing regions
          # relies on binary search
          # subtract 1 from search indices
          # to align it with the lowest value for left region
          # say we had 2, 3, 5, 8, for the left region
          # and 6 for the right region
          # and is a < operation
          # a binary search returns 3
          # subtracting 1, yields 2,
          # which pairs it correctly with 5
          # since 2, 3, 5 are less than 6
          # if it was a > operation
          # first a subtraction from len(left) -> 4 - 3
          # which yields 1
          # flipping the left region in descending order
          # -> 8, 3, 5 ,2
          # subtract 1 from the search index yields 0
          # which correctly pairs with 8,
          # since 8 is the first closest number greater than 6
          # from here on we can compute the regions
          search_indices -= 1
          left_region = np.zeros(left_index.size, np.intp)
          left_region[search_indices] = 1
          max_position = np.max(search_indices) + 1
          # exclude values from left that are not ahead
          # of values from the right
          # e.g left -> [7,5, 3], right -> 4
          # 3 is not greater than 4, so we exclude it
          # left becomes -> [7,5]
          # if left -> [3,5,7], right -> 6
          # we exclude 7 since it is not less than 6
          # left becomes -> [3,5]
          if max_position < left_index.size:
              left_index = left_index[:max_position]
              left_region = left_region[:max_position]
          # compute regions from the end
          left_region[-1] = left_region.sum() - left_region[-1]
          left_region = np.subtract.accumulate(left_region[::-1])[::-1]
          right_region = left_region[search_indices]
          return left_index, left_region, right_index, right_region
  
      def _realign(indices_and_regions):
          """
          Realign the indices and regions
          obtained from _get_regions.
          """
          (index1, region1), *rest = indices_and_regions
          index1 = pd.Index(index1)
          outcome = []
          for index2, region2 in rest:
              indexer = index1.get_indexer(index2)
  
              mask = indexer == -1
              if mask.all():
                  return None
              if mask.any():
                  region2 = region2[~mask]
                  indexer = indexer[~mask]
              reindexer = np.empty(index1.size, dtype=np.intp)
              reindexer[indexer] = np.arange(indexer.size)
              booleans = np.zeros(index1.size, dtype=np.bool_)
              booleans[indexer] = True
              if not booleans.all():
                  index1 = index1[booleans]
                  region1 = region1[booleans]
                  reindexer = reindexer[booleans]
                  if outcome:
                      outcome = [entry[booleans] for entry in outcome]
              region2 = region2[reindexer]
              outcome.append(region1)
              region1 = region2
          outcome.extend((region1, index1._values))
          return outcome
  
      left_indices_and_regions = []
      right_indices_and_regions = []
      for condition in gt_lt:
          result = _get_regions(df, right, *condition)
          if result is None:
              return None
          left_indices_and_regions.append(result[:2])
          right_indices_and_regions.append(result[2:])
  
      left_indices_and_regions = _realign(left_indices_and_regions)
      if not left_indices_and_regions:
          return None
      right_indices_and_regions = _realign(right_indices_and_regions)
      if not right_indices_and_regions:
          return None
  
      # left_indices_and_regions[0] is sorted ascending
      # use this to get the base line positions for right_indices_and_regions
      # it marks the highest possible point, beyond which there are no matches
      # for the right regions
      # with this, we can then search downwards for any matches
      # where left region is less than or equal to right region
      region_left, *left_region, left_index = left_indices_and_regions
      (
          region_right,
          *right_region,
          right_index,
      ) = right_indices_and_regions
      search_indices = region_left.searchsorted(
          region_right, side="right"
      )
      booleans = search_indices == 0
      if booleans.all():
          return None
      if booleans.any():
          search_indices = search_indices[~booleans]
          right_region = [array[~booleans] for array in right_region]
          right_index = right_index[~booleans]
  
      if len(left_region) == 1:
          left_region = left_region[0]
          right_region = right_region[0]
          # shortcut
          if pd.Series(left_region).is_monotonic_decreasing:
              return _get_indices_dual_monotonic_decreasing(
                  left_region=left_region,
                  right_region=right_region,
                  left_index=left_index,
                  right_index=right_index,
                  search_indices=search_indices,
              )
  
          cummin_arr = np.minimum.accumulate(left_region)
          # no point searching if right_region is not greater
          # than the minimum at that point
          booleans = right_region >= cummin_arr[search_indices - 1]
          if not booleans.any():
              return None
          if not booleans.all():
              right_region = right_region[booleans]
              search_indices = search_indices[booleans]
              right_index = right_index[booleans]
          return _get_indices_dual(
              left_region=left_region,
              right_region=right_region,
              left_index=left_index,
              right_index=right_index,
              search_indices=search_indices,
              cummin_arr=cummin_arr,
          )
  
      left_region = np.column_stack(left_region)
      right_region = np.column_stack(right_region)
      cummin_arr = np.minimum.accumulate(left_region)
      # no point searching if right_region is not greater
      # than the minimum at that point
      booleans = right_region >= cummin_arr[search_indices - 1]
      if not booleans.all():
          booleans = booleans.all(axis=1)
          if not booleans.any():
              return None
          right_region = right_region[booleans]
          search_indices = search_indices[booleans]
          right_index = right_index[booleans]
      return _get_indices_multiple(
          left_region=left_region,
          right_region=right_region,
          left_index=left_index,
          right_index=right_index,
          search_indices=search_indices,
          cummin_arr=cummin_arr,
      )
  
file_path: pyjanitor/janitor/functions/_numba.py
imports: import numpy
  import pandas
  from numba import njit, prange
  from pandas.api.types import is_datetime64_dtype, is_extension_array_dtype
  from janitor.functions.utils import _generic_func_cond_join, _null_checks_cond_join, greater_than_join_types, less_than_join_types
label_desc: Use image node_id 6 for calling a global function with example usage: _numba_dual_join(df, right, gt_lt) and returns: _get_indices_multiple, left_index,  left_region,  right_index,  right_region, outcome, None, None, None, _get_indices_dual, None, None, _get_indices_dual_monotonic_decreasing, None, None, None