from typing import List
from typing import Tuple
import re


def _tokenize_url(url: str) -> List[Tuple[str, int, int]]:
  """Tokenizes a URL and returns list of triples specifying the token string and its start and end position."""
  if not url:
    return []
  separator_regex = "[^a-zA-Z0-9]"
  separator_matches = list(re.finditer(separator_regex, url))
  if not separator_matches:
    # If no separator is found, use the entire string.
    return [(url, 0, len(url))]

  tokens = []  # a list of tuples of token, start index, end index.
  start_idx = 0  # start index for next token
  for i in range(len(separator_matches)):
    sep = separator_matches[i]
    sep_start_idx = sep.start()
    if sep_start_idx > start_idx:
      tokens.append((url[start_idx:sep_start_idx], start_idx, sep_start_idx))
    start_idx = sep.end()

  if start_idx < len(url):
    tokens.append((url[start_idx:], start_idx, len(url)))
  return tokens