import tester.*;

// Assignment 3
// Pedbereznak, Tom
// TomPed
// Roth, Brian
// rothb

interface ILoString {
    ILoString sort();
    ILoString insert(String s);
    boolean isSorted();
    boolean isSortedHelper(String s);
    ILoString interleave(ILoString that);
    ILoString reverse();
    ILoString reverseHelp(ILoString acc);
    boolean isDoubledList();
    boolean isDoubledListHelp(String s);
    boolean isPalindromeList();
}

class MtLoString implements ILoString {
    MtLoString() {
        // the constructor is empty because MtLoStrings has no fields
    }

    public ILoString sort() {
        return this;
    }

    public ILoString insert(String s) {
        return new ConsLoString(s, this);
    }

    public boolean isSorted() {
        return true;
    }

    public boolean isSortedHelper(String s) {
        return true;
    }

    public ILoString interleave(ILoString that) {
        return that;
    }

    public ILoString reverse() {
        return new MtLoString();
    }

    public ILoString reverseHelp(ILoString acc) {
        return acc;
    }

    public boolean isDoubledList() {
        return true;
    }

    public boolean isDoubledListHelp(String s) {
        return false;
    }

    public boolean isPalindromeList() {
        return true;
    }
}

class ConsLoString implements ILoString {
    String first;
    ILoString rest;

    // the constructor
    ConsLoString(String first, ILoString rest) {
        this.first = first;
        this.rest = rest;
    }

    public ILoString sort() {
        return this.rest.sort().insert(this.first);
    }

    public ILoString insert(String s) {
        if (this.first.toLowerCase().compareTo(s.toLowerCase()) <= 0) {
            return new ConsLoString(this.first, this.rest.insert(s));
        }
        else {
            return new ConsLoString(s, this);
        }
    }

    public boolean isSorted() {
        return this.rest.isSortedHelper(this.first);
    }

    public boolean isSortedHelper(String s) {
        if (this.first.toLowerCase().compareTo(s.toLowerCase()) >= 0) {
            return this.rest.isSorted();
        }
        else {
            return false;
        }
    }

    public ILoString interleave(ILoString that) {
        return new ConsLoString(this.first, that.interleave(this.rest));
    }

    public ILoString reverse() {
        return this.rest.reverseHelp(new ConsLoString(this.first, new MtLoString()));
    }

    public ILoString reverseHelp(ILoString acc) {
        return this.rest.reverseHelp(new ConsLoString(this.first, acc));
    }

    public boolean isDoubledList() {
        return this.rest.isDoubledListHelp(this.first);
    }

    public boolean isDoubledListHelp(String s) {
        if (this.first.toLowerCase().equals(s.toLowerCase())) {
            return this.rest.isDoubledList();
        }
        else {
            return false;
        }
    }

    public boolean isPalindromeList() {
        return this.interleave(this.reverse()).isDoubledList();
    }
}

class ExamplesStrings {
    ILoString listOfString1 = new ConsLoString("zzz",
            new ConsLoString("aaa",
                    new ConsLoString("ccc",
                            new ConsLoString("bbb",
                                    new MtLoString()))));
    ILoString listOfString2 = new ConsLoString("ZZZ",
            new ConsLoString("aaa",
                    new ConsLoString("CCC",
                            new ConsLoString("bBb",
                                    new MtLoString()))));
    ILoString listOfString3 = new ConsLoString("a",
            new ConsLoString("b",
                    new ConsLoString("c",
                            new ConsLoString("d",
                                    new MtLoString()))));
    ILoString listOfString4 = new ConsLoString("a",
            new ConsLoString("a",
                    new ConsLoString("c",
                            new ConsLoString("d",
                                    new MtLoString()))));
    ILoString listOfString5 = new ConsLoString("a",
            new ConsLoString("b",
                    new MtLoString()));
    ILoString listOfString6 = new ConsLoString("zzz",
            new ConsLoString("aaa",
                    new ConsLoString("aaa",
                            new ConsLoString("zzz",
                                    new MtLoString()))));
    ILoString listOfString7 = new ConsLoString("zzz",
            new ConsLoString("aaa",
                    new ConsLoString("zzz",
                            new MtLoString())));
    ILoString listOfString8 = new ConsLoString("zzz",
            new ConsLoString("zzz",
                    new ConsLoString("aaa",
                            new ConsLoString("aaa",
                                    new MtLoString()))));
    ILoString listOfString9 = new ConsLoString("aaa",
            new ConsLoString("zzz",
                    new ConsLoString("zzz",
                            new MtLoString())));


    boolean testSort(Tester t) {
        return t.checkExpect(this.listOfString1.sort(), new ConsLoString("aaa",
                new ConsLoString("bbb",
                        new ConsLoString("ccc",
                                new ConsLoString("zzz",
                                        new MtLoString()))))) &&
                t.checkExpect(this.listOfString2.sort(), new ConsLoString("aaa",
                        new ConsLoString("bBb",
                                new ConsLoString("CCC",
                                        new ConsLoString("ZZZ",
                                                new MtLoString())))));
    }

    boolean testIsSorted(Tester t) {
        return t.checkExpect(this.listOfString1.isSorted(), false) &&
                t.checkExpect(this.listOfString3.isSorted(), true) &&
                t.checkExpect(this.listOfString4.isSorted(), true);
    }

    boolean testInterleave(Tester t) {
        return t.checkExpect(this.listOfString1.interleave(this.listOfString2),
                new ConsLoString("zzz",
                        new ConsLoString("ZZZ",
                                new ConsLoString("aaa",
                                        new ConsLoString("aaa",
                                                new ConsLoString("ccc",
                                                        new ConsLoString("CCC",
                                                                new ConsLoString("bbb",
                                                                new ConsLoString("bBb",
                                                                new MtLoString()))))))))) &&
                t.checkExpect(this.listOfString5.interleave(this.listOfString1),
                        new ConsLoString("a",
                                new ConsLoString("zzz",
                                        new ConsLoString("b",
                                                new ConsLoString("aaa",
                                                        new ConsLoString("ccc",
                                                                new ConsLoString("bbb",
                                                                        new MtLoString()))))))) &&
                t.checkExpect(this.listOfString1.interleave(this.listOfString5),
                        new ConsLoString("zzz",
                                new ConsLoString("a",
                                        new ConsLoString("aaa",
                                                new ConsLoString("b",
                                                        new ConsLoString("ccc",
                                                                new ConsLoString("bbb",
                                                                        new MtLoString())))))));
    }

    boolean testReverse(Tester t) {
        return t.checkExpect(this.listOfString1.reverse(),
                new ConsLoString("bbb",
                        new ConsLoString("ccc",
                                new ConsLoString("aaa",
                                        new ConsLoString("zzz",
                                                new MtLoString())))));
    }

    boolean testIsDouble(Tester t) {
        return t.checkExpect(this.listOfString1.isDoubledList(), false) &&
                t.checkExpect(this.listOfString8.isDoubledList(), true) &&
                t.checkExpect(new ConsLoString("a", new ConsLoString("a", new ConsLoString("a", new MtLoString()))).isDoubledList(), false);
    }

    boolean testIsPalindromeList(Tester t) {
        return t.checkExpect(this.listOfString1.isPalindromeList(), false) &&
                t.checkExpect(this.listOfString6.isPalindromeList(), true) &&
                t.checkExpect(this.listOfString9.isPalindromeList(), false) &&
                t.checkExpect(this.listOfString7.isPalindromeList(), true);
    }

    /*boolean testMerge(Tester t) {
        return t.checkExpect(this.listOfString5.merge(this.listOfString9),
                new ConsLoString("a",
                        new ConsLoString("aaa",
                                new ConsLoString("b",
                                        new ConsLoString("zzz",
                                                new ConsLoString("zzz",
                                                        new MtLoString()))))));
    }*/
}