/**
 *                _ _   _               _
 * __      ___ __(_) |_| |_ ___ _ __   | |__  _   _
 * \ \ /\ / / '__| | __| __/ _ \ '_ \  | '_ \| | | |
 *  \ V  V /| |  | | |_| ||  __/ | | | | |_) | |_| |
 *   \_/\_/ |_|  |_|\__|\__\___|_| |_| |_.__/ \__, |
 *                                            |___/
 *  ____                  __     __               _
 * / ___|_   _____ _ __   \ \   / /__   __ _  ___| |
 * \___ \ \ / / _ \ '_ \   \ \ / / _ \ / _` |/ _ \ |
 *  ___) \ V /  __/ | | |   \ V / (_) | (_| |  __/ |
 * |____/ \_/ \___|_| |_|    \_/ \___/ \__, |\___|_|
 *                                     |___/
 * Licensed under the GPLv2 License, Version 2.0 (the "License");
 * Copyright (c) Sven Vogel
 */

/// Sort the string chars alphabetically.
/// This function works inplace but assumes the string to be ASCII only.
/// If the supplied string is not exclusively ASCII the function will panic.
/// The reason for this is that UTF-8 encoded string characters may take up more
/// bytes than just one.
fn sort_ascii_str_inplace(str: &mut String) {
    if !str.is_ascii() {
        panic!("String is not ascii")
    }
    unsafe {
        str.as_mut_vec().sort();
    }
}

/// Sort the input string alphabetically
/// Works on any UTF-8 encoded string but requires N-bytes of extra allocated memory.
fn sort_utf8_str_with_extra_mem(string: &mut String) {
    let mut chars = string.chars().collect::<Vec<char>>();
    chars.sort();
    string.clear();
    string.push_str(chars.into_iter().collect::<String>().as_str());
}

/// performs an inplace bubble sort on the supplied string
fn sort_utf8_str_inplace(string: &mut String) {
    let char_count = string.chars().count();

    for x in 0..(char_count - 1) {
        for y in 0..(char_count - x - 1) {
            // we need to recalculate the correct character indices every time we changed sth.
            let mut char_iter = string.char_indices();
            // fetch character at index y and y + 1
            let y0 = char_iter.nth(y).unwrap();
            let y1 = char_iter.next().unwrap();

            if y0.1 > y1.1 {
                // replace character at y with the character from y + 1
                string.remove(y0.0);
                string.insert(y0.0, y1.1);

                // replace character at y + 1 with the character from the original y
                string.remove(y1.0);
                string.insert(y1.0, y0.1);
            }
        }
    }
}

fn main() {
    const SOURCE: &'static str = "9876543210zyxwvutsrqponmlkjihgfedcba";

    let mut to_sort = String::from(SOURCE);
    sort_utf8_str_inplace(&mut to_sort);
    println!("UTF-8 inplace: {to_sort}");

    let mut to_sort = String::from(SOURCE);
    sort_utf8_str_with_extra_mem(&mut to_sort);
    println!("UTF-8 with extra memory: {to_sort}");

    let mut to_sort = String::from(SOURCE);
    sort_ascii_str_inplace(&mut to_sort);
    println!("ASCII inplace + unsafe: {to_sort}");
}