SQL alternative for Set::IntSpan::Partition

set-intspan-partition.sql

WITH
args AS (
  SELECT
    '
      [
        [[1,3]],
        [[3,5],[7,8]],
        [[8,8]],
        [[0,100]]
      ]
    ' AS data
),
data AS (
  SELECT
    sets.key AS key,
    json_extract(spans.value, '$[0]') AS lower,
    json_extract(spans.value, '$[1]') AS upper
  FROM
    args
    INNER JOIN json_each(args.data) sets
    INNER JOIN json_each(sets.value) spans
  ORDER BY
    lower,
    upper
),
cuts AS (
  SELECT 'lower' AS type, lower AS value FROM data
  UNION
  SELECT 'upper' AS type, lower-1 AS value FROM data
  UNION
  SELECT 'upper' AS type, upper AS value FROM data
  UNION
  SELECT 'lower' AS type, upper+1 AS value FROM data
),
bounds AS (
  SELECT
    CASE
    WHEN type = 'lower' THEN value
    END AS lower,
    lead(value) OVER (ORDER BY value) AS upper
  FROM
    cuts
),
mapped AS (
  SELECT DISTINCT
    data.key AS key,
    bounds.lower AS lower,
    bounds.upper AS upper
  FROM
    data INNER JOIN bounds ON (
      bounds.lower BETWEEN data.lower AND data.upper
      AND
      bounds.upper BETWEEN data.lower AND data.upper
    )
  ORDER BY
    1, 2, 3
),
final AS (
  SELECT
    lower,
    upper, 
    -- FIXME: SQLite does not guarantee ordering here
    JSON_GROUP_ARRAY(key)
  FROM
    mapped
  GROUP BY 
    lower,
    upper
)
SELECT
  *
FROM
  final