import java.util.Arrays;

public class Set<Item extends Comparable<Item>> {
    
    // Implementation Requirement: Each set must be internally stored as a linked list of nodes each holding 
    // some "comparable" item where the list is in order from least to greatest, starting at head.

    private class Node {
        Item item;
        Node next;
        
        Node(Item item) {
            this.item = item;
        }
    }
    
    private Node head;
    
    //////////////////
    // CONSTRUCTORS //
    //////////////////
    
    public Set() { // creates an empty set
        // ADD CODE HERE
    }
    
    public Set(Item item) { // creates a set containing only the Item item
        // ADD CODE HERE
    }
    
    // Note, the next useful "helper" constructor given is set as PRIVATE.
    // It is intended to treat the list that starts with node "head" as a Set object, 
    // but ONLY IF at the time it is called, head starts a SORTED list.
    // The fact that it takes a Node parameter justifies why we make this constructor private --
    // doing so hides the implementation details (i.e., we don't want the client to know
    // we are using nodes and lists formed by nodes as the means to describe a set).
    // This constructor should be especially convenient in constructing the Set objects  
    // resulting from the union(), intersection(), and difference() methods below.

    private Set(Node head) { 
        this.head = head;
    }
    
    //////////////////////
    // INSTANCE METHODS //
    //////////////////////
    
    public String toString() {
        // ADD CODE HERE
    }
    
    private boolean less(Item item1, Item item2) {
        return item1.compareTo(item2) < 0;
    }
	
    // Implementation Requirement: the remaining methods to be written below should accomplish their tasks using RECURSION,
    // but in a way that hides the implementation details of the Set class from "the client".
    
    public Set<Item> union(Set<Item> other) { 
        // This method should return a new set of all elements in EITHER "this" set or the "other" set (or both)
        // ADD CODE HERE
    }
    
    public Set<Item> intersect(Set<Item> other) {
        // This method should return a new set of all elements in BOTH "this" set or the "other" set
        // ADD CODE HERE
    }
    
    public Set<Item> difference(Set<Item> other) {
        // This method should return a new set of all elements in "this" set that are not in the "other" set
        // ADD CODE HERE
    }
    
    ////////////////////////////////////////////////////////////
    //  YOU MAY ADD UP TO 3 ADDITIONAL INSTANCE METHODS HERE  //
    ////////////////////////////////////////////////////////////
    
    public static char[] uniqueLettersIn(String s) {  
        final int MAX_ASCII = 128; 
        boolean[] seenSoFar = new boolean[MAX_ASCII];
        int n = s.length();
        int numUnique = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if ((Character.isLetter(c)) && (! seenSoFar[(int) c])) {
                seenSoFar[(int) c] = true;
                numUnique++;
            }
        }
        char[] uniques = new char[numUnique];
        int count = 0;
        for (int i = 0; i < MAX_ASCII; i++) {
            if (seenSoFar[i]) {
                uniques[count] = (char) i;
                count++;
            }
        }
        return uniques;
    }
    
    public static Set<Character> setOfUniqueCharsFromString(String s) { 
        char[] chars = uniqueLettersIn(s);
        Set<Character> set = new Set<Character>();
        for (int i = chars.length - 1; i >= 0; i--) {
            set = set.union(new Set(chars[i]));
        }
        return set;
    }
    
    public static void main(String[] args) {
        Set<Character> set1 = setOfUniqueCharsFromString("the quick brown fox jumps");
        Set<Character> set2 = setOfUniqueCharsFromString("over the lazy dog");
        
        System.out.println("set1: " + set1);
        System.out.println("set2: " + set2);
        System.out.println();
        
        System.out.println("set1 intersect set2:\n" + set1.intersect(set2) + "\n");
        
        System.out.println("set1 union set2:\n" + set1.union(set2) + "\n");

        System.out.println("set1 difference set2:\n" + set1.difference(set2) + "\n");   
    }
}