record UTF8Decoder[Iterator] (
    iter: Iterator
);

[T] overload iterator(u: UTF8Decoder[T]) = u;

alias REPLACEMENT_CHAR = UniChar(0xFFFDu);
alias MAX_CODE_POINT = UniChar(0x10FFFFu);

private validSequenceChar?(d) = bitand(UInt32(d), 0xC0u) == 0x80u;

private minUniChar(minCode, code) {
    if (code < minCode)
        return REPLACEMENT_CHAR;
    else
        return UniChar(code);
}

private rangeUniChar(minCode, maxCode, code) {
    if (code < minCode or code > maxCode)
        return REPLACEMENT_CHAR;
    else
        return UniChar(code);
}

decodeTwo(c, d) {
    if (validSequenceChar?(d)) {
        return minUniChar(0x80u, bitor(
            bitshl(bitand(UInt32(c), 0x1Fu), 6),
            bitand(UInt32(d), 0x3Fu)
        ));
    } else {
        return REPLACEMENT_CHAR;
    }
}
decodeThree(c, d, e) {
    if (validSequenceChar?(d) and validSequenceChar?(e)) {
        return minUniChar(0x800u, bitor(
            bitshl(bitand(UInt32(c), 0x0Fu), 12),
            bitshl(bitand(UInt32(d), 0x3Fu),  6),
            bitand(UInt32(e), 0x3Fu)
        ));
    } else {
        return REPLACEMENT_CHAR;
    }
}
decodeFour(c, d, e, f) {
    if (validSequenceChar?(d) and validSequenceChar?(e) and validSequenceChar?(f)) {
        return rangeUniChar(0x10000u, UInt32(MAX_CODE_POINT), bitor(
            bitshl(bitand(UInt32(c), 0x07u), 18),
            bitshl(bitand(UInt32(d), 0x3Fu), 12),
            bitshl(bitand(UInt32(e), 0x3Fu),  6),
            bitand(UInt32(f), 0x3Fu)
        ));
    } else {
        return REPLACEMENT_CHAR;
    }
}

[T] overload hasNext?(decoder: UTF8Decoder[T]) = hasNext?(decoder.iter);

[T] overload next(decoder: UTF8Decoder[T]) {
    var c = UInt8(next(decoder.iter));
    if (c < 0x80u) {
        return UniChar(c);
    } else if (c < 0xC0u) {
        return REPLACEMENT_CHAR;
    } else {
        if (c < 0xE0u) {
            if (not hasNext?(decoder.iter)) goto eof;
            return decodeTwo(c, next(decoder.iter));
        } else if (c < 0xF0u) {
            if (not hasNext?(decoder.iter)) goto eof;
            var d = next(decoder.iter);
            if (not hasNext?(decoder.iter)) goto eof;
            return decodeThree(c, d, next(decoder.iter));
        } else if (c < 0xF8u) {
            if (not hasNext?(decoder.iter)) goto eof;
            var d = next(decoder.iter);
            if (not hasNext?(decoder.iter)) goto eof;
            var e = next(decoder.iter);
            if (not hasNext?(decoder.iter)) goto eof;
            return decodeFour(c, d, e, next(decoder.iter));
        }
    }

eof:
    return REPLACEMENT_CHAR;
}

record UTF8[Sequence] (
    encoded: Sequence
);

[T] overload iterator(u: UTF8[T]) = UTF8Decoder(iterator(u.encoded));

private encodeTwo(code)
    = bitor(0xC0, bitshr(bitand(code, 0x7C0), 6)),
      bitor(0x80, bitand(code, 0x3F));

private encodeThree(code)
    = bitor(0xE0, bitshr(bitand(code, 0xF000), 12)),
      bitor(0x80, bitshr(bitand(code, 0x0FC0),  6)),
      bitor(0x80, bitand(code, 0x3F));

private encodeFour(code)
    = bitor(0xF0, bitshr(bitand(code, 0x1C0000), 18)),
      bitor(0x80, bitshr(bitand(code, 0x03F000), 12)),
      bitor(0x80, bitshr(bitand(code, 0x000FC0),  6)),
      bitor(0x80, bitand(code, 0x3F));

[T] overload push(u: UTF8[T], c) {
    var code = UInt32(c);
    if (code > UInt32(MAX_CODE_POINT))
        code = UInt32(REPLACEMENT_CHAR);

    if (code < 0x80u) {
        push(u.encoded, Char(c));
    } else if (code < 0x800u) {
        var x, y = ..encodeTwo(code);
        push(u.encoded, Char(x));
        push(u.encoded, Char(y));
    } else if (code < 0x10000u) {
        var x, y, z = ..encodeThree(code);
        push(u.encoded, Char(x));
        push(u.encoded, Char(y));
        push(u.encoded, Char(z));
    } else {
        var x, y, z, w = ..encodeFour(code);
        push(u.encoded, Char(x));
        push(u.encoded, Char(y));
        push(u.encoded, Char(z));
        push(u.encoded, Char(w));
    }
}
