package net.abhinavsarkar.former;

import java.util.ArrayList;
import java.util.List;
import java.util.Optional;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * https://techdevguide.withgoogle.com/resources/compress-decompression/
 */
public class StringDecompression {
  public static void main(String[] args) {
    System.out.println(decompress("10[a]"));
    System.out.println(decompress("3[abc]4[ab]c"));
    System.out.println(decompress("2[3[a]b]"));
    System.out.println(decompress("2[]b"));
    System.out.println(decompress("0[abc]v"));
    System.out.println(decompress("szs"));
  }

  static String decompress(String s) {
    return parse(s).toString();
  }

  private static CompressedString parse(String s) {
    Optional<Tuple<String, CompressedString>> parsed = CompressedString.PARSER.parse(s);
    if (!parsed.isPresent()) {
      throw new IllegalArgumentException("Unable to decompress");
    }
    return parsed.get().second;
  }
}

class Tuple<A, B> {
  A first;
  B second;

  Tuple(A first, B second) {
    this.first = first;
    this.second = second;
  }

  <C> Tuple<A, C> map(Function<B, C> f) {
    return new Tuple<>(first, f.apply(second));
  }
}

@FunctionalInterface
interface Parser<I, O> {
  Optional<Tuple<I, O>> parse(I input);

  default <P> Parser<I, P> map(Function<O, P> mapper) {
    return input -> this.parse(input).map(tup -> tup.map(mapper));
  }

  default <P> Parser<I, P> seqApply(Parser<I, Function<O, P>> parser) {
    return input -> parser.parse(input)
            .flatMap(ftup -> this.parse(ftup.first).map(tup -> tup.map(ftup.second)));
  }

  default <P> Parser<I, P> leftSeqApply(Parser<I, P> parser) {
    return this.apply((x, y) -> y, parser);
  }

  default <P> Parser<I, O> rightSeqApply(Parser<I, P> parser) {
    return this.apply((x, y) -> x, parser);
  }

  default <P, Q> Parser<I, Q> apply(BiFunction<O, P, Q> function, Parser<I, P> parser) {
    return parser.seqApply(this.map(o -> p -> function.apply(o, p)));
  }

  default Parser<I, O> or(Parser<I, O> parser) {
    return input -> this.parse(input).or(() -> parser.parse(input));
  }

  default Parser<I, List<O>> many() {
    return input -> {
      I rest = input;
      List<O> output = new ArrayList<>();

      Optional<Tuple<I, O>> parsed = this.parse(rest);
      while (parsed.isPresent()) {
        Tuple<I, O> tup = parsed.get();
        rest = tup.first;
        output.add(tup.second);
        parsed = this.parse(rest);
      }
      return Optional.of(new Tuple<>(rest, output));
    };
  }

  default Parser<I, List<O>> some() {
    return input -> {
      Tuple<I, List<O>> output = many().parse(input).get();
      if (output.second.isEmpty()) {
        return Optional.empty();
      } else {
        return Optional.of(output);
      }
    };
  }

}

class CharPredicateParser implements Parser<String, Character> {
  private Predicate<Character> predicate;

  CharPredicateParser(Predicate<Character> predicate) {
    this.predicate = predicate;
  }

  @Override
  public Optional<Tuple<String, Character>> parse(String input) {
    if (input.isEmpty()) {
      return Optional.empty();
    }

    Character i = input.charAt(0);
    if (predicate.test(i)) {
      return Optional.of(new Tuple<>(input.substring(1), i));
    }

    return Optional.empty();
  }
}

class Parsers {
  public static final Parser<String, Character> DIGIT_PARSER =
          new CharPredicateParser(Character::isDigit);

  public static final Parser<String, Integer> NUMBER_PARSER =
          DIGIT_PARSER
                  .some()
                  .map(Parsers::digitsToInt);

  public static final Parser<String, Character> ENGLISH_LOWER_CASE_CHAR_PARSER =
          new CharPredicateParser(c -> c >= 97 && c <= 122);

  public static Parser<String, Character> charParser(Character c) {
    return new CharPredicateParser(c::equals);
  }

  private static Integer digitsToInt(List<Character> digits) {
    int i = 0;
    for (char c : digits) {
      i = i * 10 + (c - 48);
    }
    return i;
  }
}

class CompressedString {
  private List<Part> parts;

  CompressedString(List<Part> parts) {
    this.parts = parts;
  }

  interface Part {
    String toString();
  }

  @Override
  public String toString() {
    return parts.stream()
            .map(Object::toString)
            .collect(Collectors.joining());
  }

  public static final Parser<String, CompressedString> PARSER =
          CompressedPart.PARSER
                  .or(StringPart.PARSER)
                  .many()
                  .map(CompressedString::new);
}


class StringPart implements CompressedString.Part {
  private String string;

  StringPart(String string) {
    this.string = string;
  }

  @Override
  public String toString() {
    return this.string;
  }

  public static final Parser<String, CompressedString.Part> PARSER =
          Parsers.ENGLISH_LOWER_CASE_CHAR_PARSER
                  .some()
                  .map(chars -> new StringPart(charListToString(chars)));

  private static String charListToString(List<Character> chars) {
    return chars.stream()
            .map(String::valueOf)
            .collect(Collectors.joining());
  }
}

class CompressedPart implements CompressedString.Part {
  private int repetition;
  private CompressedString string;

  CompressedPart(int repetition, CompressedString string) {
    this.repetition = repetition;
    this.string = string;
  }

  @Override
  public String toString() {
    String s = string.toString();
    return Stream.generate(() -> s)
            .limit(repetition)
            .collect(Collectors.joining());
  }

  private static final Parser<String, CompressedString> BRACKETED_STRING_PARSER =
          Parsers.charParser('[')
                  .leftSeqApply(input -> CompressedString.PARSER
                          .rightSeqApply(Parsers.charParser(']'))
                          .parse(input));

  public static final Parser<String, CompressedString.Part> PARSER =
          Parsers.NUMBER_PARSER.apply(CompressedPart::new, BRACKETED_STRING_PARSER);
}