import gleam/bool
import gleam/dict
import gleam/float
import gleam/int
import gleam/list
import gleam/result
import gleam/set.{type Set}
import gleam/string

/// An alphabet that can be used to encode and decode Sqids.
/// The alphabet used to encode numbers determines which characters can be used
/// in their string representation.
/// You can build one using the [`alphabet`](#alphabet) function.
///
/// ## Examples
///
/// If you want Sqids that only contains lowercase letters you can define an
/// alphabet like this:
///
/// ```gleam
/// let assert Ok(alphabet) =
///   sqid.alphabet("abcdefghijklmnopqrstuvwxyz")
/// ```
///
pub opaque type Alphabet {
  Alphabet(
    /// This goes from index to character. If the alphabet were `"abc"`, then
    /// this would be `dict.from_list([#(0, "a"), #(1, "b"), #(2, "c")])`.
    letters: dict.Dict(Int, String),
  )
}

/// The options used to encode and decode a Sqid.
/// You can create one from a valid `Alphabet` with the [`new`](#new) function.
///
pub opaque type Options {
  Options(
    /// The alphabet determining which characters can appear in the generated
    /// Sqid.
    alphabet: Alphabet,
    /// The minimum length that a Sqid must have.
    /// This value must be between 0 and 255, any value lower or higher is
    /// considered either 0 or 255.
    minimum_length: Int,
    /// A list of words that must not appear in the generated Sqid.
    blocklist: List(String),
  )
}

/// Creates a new alphabet from the letters making up the given string.
/// An alphabet is what defines what characters can end up in a generated Sqid.
///
/// This function will fail if:
/// - The alphabet has less than 3 characters
/// - The alphabet contains repeated characters
/// - The alphabet has multi-byte characters
///
/// ## Examples
///
/// If you want Sqids that only contains lowercase letters you can define an
/// alphabet like this:
///
/// ```gleam
/// let assert Ok(alphabet) =
///   sqid.alphabet("abcdefghijklmnopqrstuvwxyz")
/// ```
///
/// ```gleam
/// assert Error(Nil) == sqid.alphabet("wibble")
///   as "wrong alphabet: it contains duplicates"
///
/// assert Error(Nil) == sqid.alphabet("dziękuję")
///   as "wrong alphabet: it contains non ascii characters"
///
/// assert Error(Nil) == sqid.alphabet("01")
///   as "wrong alphabet: it contains less than 3 characters"
/// ```
///
pub fn alphabet(string: String) -> Result(Alphabet, Nil) {
  let letters = string.to_graphemes(string)
  use <- bool.guard(when: has_duplicates(letters), return: Error(Nil))
  use <- bool.guard(when: list.any(letters, is_multi_byte), return: Error(Nil))

  case letters {
    [] | [_] | [_, _] -> Error(Nil)
    _ -> {
      let letters =
        list.index_fold(letters, dict.new(), fn(acc, letter, index) {
          dict.insert(acc, index, letter)
        })
      Ok(shuffle_alphabet(Alphabet(letters:)))
    }
  }
}

fn is_multi_byte(string: String) -> Bool {
  string.byte_size(string) > 1
}

fn has_duplicates(list: List(a)) -> Bool {
  has_duplicates_loop(list, set.new())
}

fn has_duplicates_loop(list: List(a), seen_so_far: Set(a)) -> Bool {
  case list {
    [] -> False
    [first, ..rest] ->
      case set.contains(seen_so_far, first) {
        True -> True
        False -> has_duplicates_loop(rest, set.insert(seen_so_far, first))
      }
  }
}

/// Creates an `Options` object from a valid alphabet.
/// `Options` determine how Sqids are encoded and decoded.
///
/// If you want to change the generated Sqids you can also use:
/// - [`set_minimum_length`](#set_minimum_length): to pick a minimum length for
///   the generated Sqids.
/// - [`set_blocklist`](#set_blocklist): to specify a blocklist of words that
///   will not end up in any of the generated Sqids.
///
pub fn new(alphabet: Alphabet) -> Options {
  Options(alphabet:, minimum_length: 0, blocklist: [])
}

/// Sets the minimum length of the generated Sqids.
/// The value must be between 0 and 255. Any value lower than 0 is considered
/// as 0, while any value higher than 255 is considered as 255.
///
pub fn set_minimum_length(options: Options, minimum_length: Int) -> Options {
  Options(
    ..options,
    minimum_length: int.clamp(minimum_length, min: 0, max: 255),
  )
}

/// Sets the list of blocked words that cannot appear inside any of the
/// generated Sqids.
/// This is useful if you want to make sure a generated Sqid cannot contain
/// profanities.
///
/// There's a couple of things to note:
/// - The blocklist is case insensitive. If `"gleam"` is a blocked word,
///   generated Sqids will not contain any of `"gLeaM"`, `"GLEAM"`, `"GLeam"`,
///   ... and so on.
/// - All words in the blocklist must be more than three characters long, any
///   word shorter than that will be ignored.
///
pub fn set_blocklist(options: Options, blocklist: List(String)) -> Options {
  let alphabet_string = alphabet_to_string(options.alphabet)
  let blocklist =
    list.fold(blocklist, [], fn(blocklist, word) {
      // The block list is case insensitive, all words are turned to lowercase.
      let word = string.lowercase(word)
      case string.to_graphemes(word) {
        // Words that are less than three characters are ignored.
        [] | [_] | [_, _] -> blocklist
        // Otherwise they can be added. But, we can preemptively remove all the
        // strings that contain letters that are not in the alphabet.
        // Since we only generate
        letters ->
          case list.all(letters, string.contains(alphabet_string, _)) {
            True -> [word, ..blocklist]
            False -> blocklist
          }
      }
    })

  Options(..options, blocklist:)
}

/// Encodes a list of numbers into a readable string using the given options.
/// This function might fail if it's not possible to generate a string that is
/// not excluded by the options' blocklist.
///
pub fn encode(options: Options, numbers: List(Int)) -> Result(String, Nil) {
  case numbers {
    [] -> Ok("")
    _ -> do_encode(options, numbers, 0)
  }
}

fn do_encode(
  options: Options,
  numbers: List(Int),
  attempts: Int,
) -> Result(String, Nil) {
  case attempts >= dict.size(options.alphabet.letters) {
    // We've reached the maximum number of attempts to generate an id and
    // couldn't generate one!
    True -> Error(Nil)
    False -> {
      // Otherwise the algorithm works as follow: we start by shifting the
      // alphabet, and get the first separator from this shifted one.
      let alphabet_size = dict.size(options.alphabet.letters)
      use offset <- result.try(semi_random_offset(options.alphabet, numbers))
      let offset = offset % alphabet_size
      let offset = { offset + attempts } % alphabet_size
      let alphabet = shift_alphabet(options.alphabet, offset)
      let id = alphabet_separator(alphabet)

      // We then have to reverse the alphabet and iterate over all the numbers
      // encoding each one into a single id.
      let alphabet = reverse_alphabet(alphabet)
      let #(id, alphabet) = encode_numbers(numbers, alphabet, id)

      // Then we keep adding pad characters to reach the minimum character
      // limit.
      let id = pad_to_length(id, options.minimum_length, alphabet)

      // Finally we check if the id contains any word that is in the block list.
      // If it does it is discarded and we try generating a new one!
      case is_blocked_id(id, options) {
        True -> do_encode(options, numbers, attempts + 1)
        False -> Ok(id)
      }
    }
  }
}

/// Returns true if the id contains any of the words that are in the options'
/// block list.
/// Checking is case insensitive: if `"gleam"` is not allowed then `"GLeaM"`
/// would be rejected as well.
///
fn is_blocked_id(id: String, options: Options) -> Bool {
  let id = string.lowercase(id)
  let id_size = string.byte_size(id)
  list.any(options.blocklist, satisfying: fn(blocked_word) {
    let blocked_word_size = string.byte_size(blocked_word)
    case blocked_word_size > id_size {
      // If the word is longer than the id, then it's impossible for the id to
      // contain it, we keep going.
      True -> False
      // Otherwise we have to check if the blocked word is inside the id.
      // For short ids/words, we only check if they are exactly the same,
      // otherwise we would be excluding way too many ids.
      False if id_size <= 3 || blocked_word_size <= 3 -> id == blocked_word
      // Otherwise we just check as regular if the id contains the word.
      False -> string.contains(id, blocked_word)
    }
  })
}

fn encode_numbers(
  numbers: List(Int),
  alphabet: Alphabet,
  id: String,
) -> #(String, Alphabet) {
  case numbers {
    [] -> #(id, alphabet)
    [last] -> #(id <> number_to_id(last, alphabet), alphabet)
    // If the number is not the last one, we need to turn it into a string id,
    // and then add a separator character before the next one.
    [first, ..rest] -> {
      let id = id <> number_to_id(first, alphabet)
      let id = id <> alphabet_separator(alphabet)
      // Before dealing with each number we need to shuffle the alphabet.
      let alphabet = shuffle_alphabet(alphabet)
      encode_numbers(rest, alphabet, id)
    }
  }
}

fn number_to_id(number: Int, alphabet: Alphabet) -> String {
  number_to_id_loop(number, alphabet, [])
}

fn number_to_id_loop(
  number: Int,
  alphabet: Alphabet,
  acc: List(String),
) -> String {
  // The number is used as an index to pick a letter from the alphabet.
  // The only thing we need to be careful with is that the first character in
  // the alphabet (the one at index 0), is used as the separator.
  // So we can only pick letters with indices `[1, alphabet_size - 1]`.
  let alphabet_size = dict.size(alphabet.letters) - 1
  let assert Ok(letter) =
    dict.get(alphabet.letters, { number % alphabet_size } + 1)

  // We then divide the number by the alphabet size and keep going picking
  // letters until we get to 0.
  // Why do we do that? Ask the Sqid folks, that's just how this works!
  let acc = [letter, ..acc]
  let number =
    float.floor(int.to_float(number) /. int.to_float(alphabet_size))
    |> float.round

  case number > 0 {
    True -> number_to_id_loop(number, alphabet, acc)
    False -> string.join(acc, "")
  }
}

fn pad_to_length(id: String, length: Int, alphabet: Alphabet) -> String {
  let id_length = string.byte_size(id)
  case id_length < length {
    False -> id
    True -> {
      let id = id <> alphabet_separator(alphabet)
      let missing = length - id_length - 1
      pad_to_length_loop(id, missing, alphabet)
    }
  }
}

fn pad_to_length_loop(id: String, missing: Int, alphabet: Alphabet) -> String {
  case missing > 0 {
    False -> id
    True -> {
      let alphabet = shuffle_alphabet(alphabet)
      let alphabet_size = dict.size(alphabet.letters)
      let slice_size = int.min(missing, alphabet_size)
      let slice = string.slice(alphabet_to_string(alphabet), 0, slice_size)
      let id = id <> slice
      let missing = missing - slice_size
      pad_to_length_loop(id, missing, alphabet)
    }
  }
}

/// Returns the separator of the alphabet, the separator changes based on how
/// the
fn alphabet_separator(alphabet: Alphabet) -> String {
  let assert Ok(separator) = dict.get(alphabet.letters, 0) as "empty alphabet"
  separator
}

/// Shifts the alphabet by the given offset.
/// For example if alphabet is `"abcde"` and I end up shifting it by 2 to the
/// left it ends up being `"cdeab"`.
///
fn shift_alphabet(alphabet: Alphabet, offset: Int) {
  // All values after the offset need to be moved to the start of the alphabet:
  //
  //   index    0 1 2 3 4
  //   letter   a b c d e
  //                  ^ imagine offset is 3
  //
  // We need to move `d` and `e` so that they start from 0 onward, we can do
  // that by subtracting the offset from their index:
  //
  // - `d` goes to `3 - 3` -> `0`
  // - `e` goes to `4 - 3` -> `1`
  //
  // All good! With numbers that come before the offset they'll have to start
  // after all the number that we've moved. How many numbers are we moving?
  // All the numbers that go from `offset` to the end of the alphabet; in this
  // example if would be just two (`d` and `e`). In general that's given by
  // `alphabet_size - offset`.
  //
  // - We can check this works for our example: we're moving
  //   `alphabet_size - offset` -> `5 - 3` -> `2` characters
  // - `a` goes to `0 + 2` -> `2`
  // - `b` goes to `1 + 2` -> `3`
  // - `c` goes to `2 + 2` -> `4`
  let alphabet_size = dict.size(alphabet.letters)
  let letters =
    dict.fold(alphabet.letters, dict.new(), fn(letters, index, letter) {
      let new_index = case index < offset {
        True -> alphabet_size - offset + index
        False -> index - offset
      }
      dict.insert(letters, new_index, letter)
    })
  Alphabet(letters:)
}

/// This computes an offset from a list of numbers, the Sqid spec calls this
/// "semi random": it's random looking but it's actually deterministically
/// decided by the numbers and alphabet we pass as arguments.
/// This returns an error if any of the numbers is negative.
fn semi_random_offset(
  alphabet: Alphabet,
  numbers: List(Int),
) -> Result(Int, Nil) {
  let alphabet_size = dict.size(alphabet.letters)
  list.try_fold(numbers, #(list.length(numbers), 0), fn(pair, number) {
    let #(acc, index) = pair
    case number < 0 {
      True -> Error(Nil)
      False -> {
        let assert Ok(letter_value) =
          letter_value(alphabet.letters, number % alphabet_size)
          as "index outside of dictionary"

        Ok(#(letter_value + index + acc, index + 1))
      }
    }
  })
  |> result.map(fn(pair) { pair.0 })
}

/// Given a dictionary of letters this returns the codepoint value of the letter
/// at the given index.
/// This would fail if:
/// - the index is not included in the dictionary
/// - the dictionary value is an empty string
///
/// We only ever use this internally after validating an alphabet and making
/// sure that all the entries are single letters, so under this assumption it
/// should never fail.
fn letter_value(
  letters: dict.Dict(Int, String),
  index: Int,
) -> Result(Int, Nil) {
  dict.get(letters, index)
  |> result.map(string.to_utf_codepoints)
  |> result.try(list.first)
  |> result.map(string.utf_codepoint_to_int)
}

/// Shuffles an alphabet.
/// Don't be fooled by the name: the shuffle might look random, but it's
/// actually deterministic. Given an alphabet its shuffled version is always
/// going to be the same.
///
fn shuffle_alphabet(alphabet: Alphabet) -> Alphabet {
  let letters =
    shuffle_alphabet_loop(alphabet.letters, 0, dict.size(alphabet.letters) - 1)
  Alphabet(letters:)
}

fn shuffle_alphabet_loop(
  letters: dict.Dict(Int, String),
  i: Int,
  j: Int,
) -> dict.Dict(Int, String) {
  case j <= 0 {
    True -> letters
    False -> {
      let assert Ok(i_value) = letter_value(letters, i) as "i always in range"
      let assert Ok(j_value) = letter_value(letters, j) as "j always in range"
      let r = { i * j + i_value + j_value } % dict.size(letters)

      let assert Ok(old_i) = dict.get(letters, i) as "i always in range"
      let assert Ok(old_r) = dict.get(letters, r) as "r always in range"
      let letters = dict.insert(letters, i, old_r) |> dict.insert(r, old_i)
      shuffle_alphabet_loop(letters, i + 1, j - 1)
    }
  }
}

/// This reverses an alphabet: if the initial alphabet is "abcd", the reversed
/// alphabet is going to be "dcba".
fn reverse_alphabet(alphabet: Alphabet) -> Alphabet {
  let size = dict.size(alphabet.letters)
  let letters =
    dict.fold(alphabet.letters, dict.new(), fn(letters, index, letter) {
      dict.insert(letters, size - 1 - index, letter)
    })

  Alphabet(letters:)
}

fn alphabet_to_string(alphabet: Alphabet) -> String {
  dict.to_list(alphabet.letters)
  |> list.sort(fn(one, other) { int.compare(one.0, other.0) })
  |> list.map(fn(pair) { pair.1 })
  |> string.join(with: "")
}

// --- DECODING ----------------------------------------------------------------

/// Decodes a Sqid into the list of integers that was used to generate it.
/// To decode a Sqid, always use the same options that were used to encode it,
/// otherwise you will get nonsense results!
///
/// This function will fail if the Sqid has carachters that are not allowed by
/// these options, meaning that the Sqid was encoded with a different alphabet.
///
pub fn decode(options: Options, sqid: String) -> Result(List(Int), Nil) {
  case string.pop_grapheme(sqid) {
    // The string is empty, so it was encoded from the empty list
    Error(_) -> Ok([])
    // Otherwise we use the prefix to get back to the original offset we used to
    // shift the alphabet, so we can shift it back into its original form.
    Ok(#(separator, sqid)) ->
      case index(alphabet_to_string(options.alphabet), of: separator) {
        // The Sqid's character is not in the alphabet. This means it was
        // encoded using a different alphabet.
        Error(_) -> Error(Nil)
        Ok(offset) ->
          shift_alphabet(options.alphabet, offset)
          |> reverse_alphabet
          |> decode_loop(sqid, [])
      }
  }
}

fn decode_loop(
  alphabet: Alphabet,
  sqid: String,
  numbers: List(Int),
) -> Result(List(Int), Nil) {
  let separator = alphabet_separator(alphabet)
  case string.split(sqid, separator) {
    // If the string is empty, or the first chunk is empty we're done (the rest
    // are junk padding characters).
    [] | ["", ..] -> Ok(list.reverse(numbers))
    // If the chunk is empty we're done, the rest are junk padding characters.
    [id, ..rest] ->
      case id_to_number(id, alphabet) {
        Error(_) -> Error(Nil)
        Ok(number) -> {
          let numbers = [number, ..numbers]
          let alphabet = shuffle_alphabet(alphabet)
          let sqid = string.join(rest, with: separator)
          decode_loop(alphabet, sqid, numbers)
        }
      }
  }
}

fn id_to_number(id: String, alphabet: Alphabet) -> Result(Int, Nil) {
  let alphabet_size = dict.size(alphabet.letters) - 1
  let alphabet_string = alphabet_to_string(alphabet)

  list.try_fold(string.to_graphemes(id), 0, fn(acc, letter) {
    use index <- result.try(index(alphabet_string, of: letter))
    Ok(acc * alphabet_size + index - 1)
  })
}

fn index(string: String, of separator: String) -> Result(Int, Nil) {
  use #(before, _) <- result.try(string.split_once(string, on: separator))
  Ok(string.byte_size(before))
}