import javax.swing.*;
import javax.swing.event.*;
import javax.swing.tree.*;

public class MTree implements MTreeADT {
    private MTreeNode root = new MTreeNode(0,new java.util.ArrayList<Integer>());

    public static void main(String[] args) {
        int n = 4;
        int k = 3;
        MTree tree1 = makeTree("MTree queue");
        tree1.expandQueue(n,k);
        MTree tree2 = makeTree("MTree stack");
        tree2.expandStack(n,k);
        MTree tree3 = makeTree("MTree recursive");
        tree3.expandRecursively(n,k);
    }
    
    private static MTree makeTree(String title) {
        MTree tree = new MTree();
        JScrollPane content = new JScrollPane(new JTree(tree));
        JFrame window = new JFrame(title);
        window.setContentPane(content);
        window.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        window.pack();
        window.setSize(400,400);
        window.setVisible(true);
        return tree;
    }
    
    private void expandRecursively(int n, int k) {
        expandRecursively(this.root, n, k, 0);
    }

    private int expandRecursively(MTreeNode node, int n, int k, int id) {
        java.util.List<Integer> seq = node.getSeq();
        if (seq.size() < k) {
            for (int i = 1; i <= n; i++) {
                if (!seq.contains(i)) {
                    java.util.List<Integer> newSeq = copyAdd(seq, i);
                    MTreeNode child = new MTreeNode(++id, newSeq);
                    node.getChildren().add(child);
                    id = expandRecursively(child, n, k, id);
                }
            }
        }
        return id;
    }

    private void expandQueue(int n, int k) {
        Queue<MTreeNode> queue = new LinkedQueue<MTreeNode>();
        queue.offer(this.root);
        int id = 0;
        while (!queue.isEmpty()) {
            MTreeNode node = queue.poll();
            java.util.List<Integer> seq = node.getSeq();
            if (seq.size() < k) {
                for (int i = 1; i <= n; i++) {
                    if (!seq.contains(i)) {
                        java.util.List<Integer> newSeq = copyAdd(seq, i);
                        MTreeNode child = new MTreeNode(++id, newSeq);
                        node.getChildren().add(child);
                        queue.offer(child);
                    }
                }
            }
        }
    }

    private void expandStack(int n, int k) {
        Stack<MTreeNode> stack = new LinkedStack<MTreeNode>();
        stack.push(this.root);
        int id = 0;
        while (!stack.isEmpty()) {
            MTreeNode node = stack.pop();
            java.util.List<Integer> seq = node.getSeq();
            if (seq.size() < k) {
                for (int i = 1; i <= n; i++) {
                    if (!seq.contains(i)) {
                        java.util.List<Integer> newSeq = copyAdd(seq, i);
                        MTreeNode child = new MTreeNode(++id, newSeq);
                        node.getChildren().add(child);
                        stack.push(child);
                    }
                }
            }
        }
    }

    private java.util.List<Integer> copyAdd(java.util.List<Integer> seq, int i) {
        java.util.List<Integer> copySeq = new java.util.ArrayList<Integer>(seq);
        copySeq.add(i);
        return copySeq;
    }

    @Override
    public void addTreeModelListener(TreeModelListener arg0) {}
    /* (non-Javadoc)
     * @see MTreeADT#getChild(java.lang.Object, int)
     */
    @Override
    public Object getChild(Object obj, int index) {
        MTreeNode node = (MTreeNode) obj;
        return node.getChildren().get(index);
    }
    /* (non-Javadoc)
     * @see MTreeADT#getChildCount(java.lang.Object)
     */
    @Override
    public int getChildCount(Object obj) {
        MTreeNode node = (MTreeNode) obj;
        return node.getChildren().size();
    }
    /* (non-Javadoc)
     * @see MTreeADT#getIndexOfChild(java.lang.Object, java.lang.Object)
     */
    @Override
    public int getIndexOfChild(Object pObj, Object cObj) {
        MTreeNode parent = (MTreeNode) pObj;
        MTreeNode child = (MTreeNode) cObj;
        return parent.getChildren().indexOf(child);
    }
    /* (non-Javadoc)
     * @see MTreeADT#getRoot()
     */
    @Override
    public Object getRoot() {
        return this.root;
    }
    /* (non-Javadoc)
     * @see MTreeADT#isLeaf(java.lang.Object)
     */
    @Override
    public boolean isLeaf(Object obj) {
        return this.getChildCount(obj) == 0;
    }
    @Override
    public void removeTreeModelListener(TreeModelListener arg0) {}
    @Override
    public void valueForPathChanged(TreePath arg0, Object arg1) {}
}