package frame;

import java.util.*;

/**
 *
	*/
public class Frame extends LinkedList {
	
	static final int FAIL_FRAME = 0;
	static final int UNDEFINED_FRAME = 1;
	static final int SYMBOL_FRAME = 2;
	static final int NEGATION_FRAME = 3;
	static final int SLOT_FRAME = 4;
	static final int DISJUNCTION_FRAME = 5; //or
	static final int CONJUNCTION_FRAME = 6; //mult
	
	private static int depth = -1;
	
	static final String[] types = {
		"FAIL_FRAME",
		"UNDEFINED_FRAME",
		"SYMBOL_FRAME",
		"NEGATION_FRAME",
		"SLOT_FRAME",
		"DISJUNCTION_FRAME",
		"CONJUNCTION_FRAME"};
		
	private int type = -1;
	private boolean strictPrune = true;
	private boolean unifyRudely = false;
	
///////////////////////////////////////////////////////////////////////////////
//
// Constructors

	/**
	 *
		*
		*/
	public Frame() {
	
		super();
	}
	
	/**
	 *
		*
		*/
	public Frame(Frame that) {
	
		super(that);
		
		setType(that.getType());
		
		switch(getType()) {
		
			//case FAIL_FRAME:
			//case UNDEFINED_FRAME:
	
			case SYMBOL_FRAME:
			
				set(0, new String((String)that.get(0)));
				break;
				
			case NEGATION_FRAME:
			case DISJUNCTION_FRAME:
			case CONJUNCTION_FRAME:
			
			//System.out.println("size() is " + size());
				for (int i = 0; i < size(); i++) {
				
					set(i, new Frame((Frame)that.get(i)));
				}
				break;
				
			case SLOT_FRAME:
			
				for (int i = 0; i < size(); i++) {
				
					set(i, new SlotValuePair((SlotValuePair)that.get(i)));
				}
				break;
		}
	}
	
	/**
	 *
		*
		*/
	public Frame(int type) throws Exception {

		super();
		
		if (type < 0 || type > types.length) {
		
			throw new Exception("cannot create frame of type " + type);
		}

		setType(type);
	}
	
	/**
	 *
		*
		*/
	public Frame(String s) throws Exception {
	
		super();
	
		//System.out.println("building PF from string " + s);
		//if (s.indexOf('(') == -1 && s.indexOf(')') == -1) {//not enclosed by parens
		if (s.charAt(0) != '(' && s.charAt(s.length()-1) != ')') {//not enclosed by parens, assume string, undef or fail
		
			//base casec - building a string frame
			
			if (s.charAt(0) == '*' && s.charAt(s.length()-1) == '*') {
			
				//fail or undefined
				String keyword = s.substring(1, s.length()-1).toLowerCase();
				
				if (keyword.equals("undefined")) {
				
					setType(UNDEFINED_FRAME);
				} else if (keyword.equals("fail")) {
				
					setType(FAIL_FRAME);
				
				} else {
				
					setType(SYMBOL_FRAME);
					add(s);
					//throw new Exception("you cannot create a frame with *" + keyword + "*");
				}
			} else if (s.charAt(0) == '"' && s.charAt(s.length()-1) == '"') {//quoted string... still needs work here
			
				setType(SYMBOL_FRAME);
				add(s);

			} else if (s.indexOf(' ') == -1) {
			
				setType(SYMBOL_FRAME);
				add(s);
				
			} else {
			
				//complain??
				throw new Exception("you cannot create a Patrick Frame with the string \""
					+ s + "\"");
			}
		} else {
		
			String stripped = s.substring(1, s.length()-1);
			
			if (stripped.length() == 0) {
			
				//complain
				throw new Exception("you cannot create a Patrick Frame with no input");
				
			} else if (stripped.charAt(0) == '*') {
				
				if (stripped.indexOf('*', 1) == -1) {
				
					//complain
					throw new Exception("could not create frame: missing second *");
					
				} else {
				
				String keyword = stripped.substring(1, stripped.indexOf('*', 1)).toLowerCase();
				
				if (keyword.equals("or")) {
			
						setType(DISJUNCTION_FRAME);
						String test = stripped.substring(4, stripped.length()).trim();
						Vector children = tokenizeFrameList(stripped.substring(4, stripped.length()).trim());
						
						for (int i = 0; i < children.size(); i++) {
						
							//create new element first, then test if already in the list
							//if not, add it
							Frame newFrame = new Frame((String)children.get(i));
							
							//if (!this.hasChild(newFrame)) {
							
							//	add(newFrame);
							//}
							setAdd(newFrame);
						}
						sort();
						
					} else if (keyword.equals("mult")) {
					
					
						setType(CONJUNCTION_FRAME);
						Vector children = tokenizeFrameList(stripped.substring(7, stripped.length()));
						//System.out.println("size of tokens is " + children.size());
						for (int i = 0; i < children.size(); i++) {
							
							add(new Frame((String)children.get(i)));
						}
					} else if (keyword.equals("not")) {
				
						setType(NEGATION_FRAME);
						String s1 = stripped.substring(6, stripped.length());
						add(new Frame(s1));
					
					} else if (keyword.equals("fail")) {
				
						setType(FAIL_FRAME);
					
					} else if (keyword.equals("undefined")) {
				
						setType(UNDEFINED_FRAME);
					}
				}
			} else if (stripped.trim().substring(0, 1).equals("(")) {//slot frame
				
				setType(SLOT_FRAME);
				Vector children = tokenizeFrameList(stripped);
			
				for (int i = 0; i < children.size(); i++) {
				
					add(new SlotValuePair((String)children.get(i)));
				}
				sort();
				
			} else {
			
				//complain
				throw new Exception("could not create frame");
			}
		}
	}

///////////////////////////////////////////////////////////////////////////////
//
// Getters and Setters


	/**
	 * sets the type of this Frame.
		*
		* @param type the type to set for this Frame
		*/
	public void setType(int type) {
	
		this.type = type;
	}
	
	/**
	 * sets the value of strictPrune
	 *
		* @param value the value to set for this Frame
		*/
	public void setStrictPrune(boolean value) {
	
		strictPrune = value;
	}
	
	/**
	 * sets the value of unifyRudely
	 *
		* @param value the value to set for this Frame
		*/
	public void setUnifyRudely(boolean value) {
	
		unifyRudely = value;
	}

	/**
	 * gets the type of this Frame.
		*
		* @return the type of this Frame
		*/
	public int getType() {
	
		return type;
	}

 /**
	 * gets the value of strictPrune of this Frame.
		*
		* @return the value of strictPrune of this Frame
		*/
	public boolean getStrictPrune() {
	
		return strictPrune;
	}
	
	/**
	 * gets the value of unifyRudely of this Frame.
		*
		* @return the value of unifyRudely of this Frame
		*/
	public boolean getUnifyRudely() {
	
		return unifyRudely;
	}
	
///////////////////////////////////////////////////////////////////////////////
//
// Utilities
//
// private Vector tokenizeFrameList(String)
// private String indent(int)
// private boolean hasChild(Frame)
// private void sort()
// void prune()
// private Frame hasSlot(String)
// private void promoteSingleChild()
// Frame andAdd(Frame)
// Frame andAddFirst(Frame)
// Frame andConcatenate(Frame)
// Frame conjoin(Frame)
// Frame orAdd(Frame)
// Frame orConcatenate(Frame)
// Frame disjoin(Frame)
// Frame distribute(Frame)
// Frame stitch(Frame)
// Frame unifyAnd(Frame)
// Frame unifyAndAnd(Frame)
// Frame unifyNot(Frame)
// Frame unifyNotNot(Frame)
// Frame unifyOr(Frame)
//	Frame unifyOrNot(Frame)
// Frame unifyPlain(Frame)
// Frame unifySlotSlot(Frame)
// private boolean setAdd(Frame)

	/**
	 * breaks up a frame list into sections bounded by the top level parentheses
	 * or by whitespace
		*/
	static Vector tokenizeFrameList(String s) {
	
		Vector result = new Vector();
		
		if (s.indexOf('(') == -1 && s.indexOf(')') == -1) {//dealing with only strings
		
			StringTokenizer st = new StringTokenizer(s);
				
			while (st.hasMoreTokens()) {
				
					result.add(st.nextToken());
			}
		} else {
		
			Stack parens = new Stack();
			int start = 0;
			
			for (int i = 0; i < s.length(); i++) {//walking through the string
			
				String current = s.substring(i, i+1);//looking at each character as a string
				
				if (current.equals("(")) {
					
					if (parens.empty()) {
					
						start = i;
					}
					parens.push(current);
					
				} else if (current.equals(")")) {
				
					if (parens.empty()) {
						//complain
					}
					parens.pop();
					
					if (parens.empty()) {
						
						result.add(new String(s.substring(start, i+1)));//this will recognize a parenthesized string
						start = i + 1;
					}
				} else if (parens.empty() && (current.equals(" ") || current.equals("\n") || current.equals("\t"))) {//if parens not equal, then we don't care about spaces
				
					//System.out.println("current char at " + i + " is \"" + current + "\"");
					//for a space immediately after a close parens
					if (start < i) {
					result.add(new String(s.substring(start, i)));
					}
					start = i + 1;
					
				}
			}
			if (start < s.length()) {//there's stuff left
				result.add(new String(s.substring(start, s.length())));
			}
		}
		
		return result;
	}
	
	/**
	 * used by the toPrettyString method to indent complex frames
		* determines the depth of an indent based on the static variable
	 * depth
		*/
	private String indent(int depth) {
	
		String s = "";

		for (int i = 0; i < depth; i++) {
		
			s += "  ";
		}
		return s;
	}

	/**
	 * checks if this Frame has the specified child
		*/
	private boolean hasChild(Frame child) {
	
		boolean result = false;
		
		for (int i = 0; i < size(); i++) {
		
			if (((Frame)get(i)).isEqualTo(child)) {
			
				result = true;
				break;
			}
		}
		return result;
	}
	
	/**
	 * sorts this Frame currently bubble sort
	 * will change to merge sort soon
		*/
	private void sort() {

		if (getType() == SLOT_FRAME) {

			//bubble sort
			SlotValuePair temp = new SlotValuePair();
			
			for (int pass = 1; pass < size(); pass ++) {
			
				for (int element = 0; element < size() - 1; element++) {
				
					SlotValuePair first = (SlotValuePair)get(element);
					SlotValuePair second = (SlotValuePair)get(pass);
					
					if (((String)first.getSlot().get(0)).compareTo((String)second.getSlot().get(0)) 
								> 0) {//if first is greater than second
						//swap
						temp = first;
						set(element, second);
						set(pass, temp);
					}
				}
			}
		}
		
		if (getType() == DISJUNCTION_FRAME) {//disjunction frame "or"
		
			//bubble sort
			Frame temp = new Frame();
			
			for (int pass = 1; pass < size(); pass ++) {
			
				for (int element = 0; element < size() - 1; element++) {
				
					Frame first = (Frame)get(element);
					Frame second = (Frame)get(pass);
					
					if (first.isGreaterThan(second)) {
						//swap
						temp = first;
						set(element, second);
						set(pass, temp);
					}
				}
			}
		}
	}
	
	
	/**
	 * creates a frame with a correct structure
		*/
	void prune() {

		switch(getType()) {
		
			//case FAIL_FRAME: 
			//case UNDEFINED_FRAME: 
			//case SYMBOL_FRAME:
			//nothing to prune for the cases above

			case NEGATION_FRAME:

				((Frame)get(0)).prune();
				
				if (((Frame)get(0)).getType() == FAIL_FRAME) {
				
					setType(UNDEFINED_FRAME);
					set(0, null);
					
				} else if (((Frame)get(0)).getType() == UNDEFINED_FRAME) {
				
					setType(FAIL_FRAME);
					set(0, null);
				}
				break;
				
			case SLOT_FRAME:

				for (int i = 0; i < size(); i++) {
				
					((SlotValuePair)get(i)).prune();
					
					if(((SlotValuePair)get(i)).getValue().getType() == FAIL_FRAME) {
					
						setType(FAIL_FRAME);
						
						//zero out children
						for (int j = 0; j < size(); j++) {
						
							set(i, null);
						}
						break;//break out of for loop
						
					} else if (((SlotValuePair)get(i)).getValue().getType() == UNDEFINED_FRAME) {
					
						remove(i);
						i--;//what the?? remove() shifts the indexes of the remaining children, 
							//so in order not to skip the next one, we gotta do this
					}
				}
				if (getType() != FAIL_FRAME) {
				
				//what if you remove all of the slots?  what is left, fail or undefined? probably undefined
					if (size() == 0) {
					
						setType(UNDEFINED_FRAME);
					} 
				}
			 break;
				
			case DISJUNCTION_FRAME:

				for (int i = 0; i < size(); i++) {
				
					((Frame)get(i)).prune();
					
					if (((Frame)get(i)).getType() == FAIL_FRAME 
					    || ((Frame)get(i)).getType() == UNDEFINED_FRAME) {
						
						remove(i);	
						i--;
					}
				}
				
				if (size() == 0) {
				
					setType(FAIL_FRAME);
					
				} else if (size() == 1) {
					
					promoteSingleChild();
				}
				break;
				
			case CONJUNCTION_FRAME:
			
			//if (strictPrune) {//strictPrune == true
			
				//if any children fail, the whole thing fails
				//remove undefineds, if one child left, promote it

				for (int i = 0; i < size(); i++) {
				
						((Frame)get(i)).prune();
						
						if (((Frame)get(i)).getType() == FAIL_FRAME) {
						
							if (strictPrune) {
							
								setType(FAIL_FRAME);
								
								//zero out children
								for (int j = 0; j < size(); j++) {
								
									set(i, null);
								}
								break;//break out of for loop
							
							} else {//strictPrune == false
							
								remove(i);
								i--;
							
							}
						} else if (((Frame)get(i)).getType() == UNDEFINED_FRAME) {
						
							remove(i);
							i--;
						}
					}//end of for loop	
					
					if (getType() != FAIL_FRAME) {
					
						if (size() == 0) {
						
							setType(FAIL_FRAME);
							
						} else if (size() == 1) {
	
							promoteSingleChild();
						}
					}
			
			
			//} else {//strictPrune == false
			
			
					
				//}
				break;//break out of switch
		}
	}
	
	/**
	 * returns null if Frame does not have slot, returns slot's value otherwise
	 * this assumes there are no duplicate slot names in a slot frame
		* need to make sure this is the case when creating slot frames
		*/
	private Frame hasSlot(String slot) {

		Frame result = null;
		SlotValuePair child = null;
		
		if (getType() == SLOT_FRAME) {

			for (int i = 0; i < size(); i++) {
			
				child = (SlotValuePair)get(i);
				
				if (((String)child.getSlot().get(0)).equals(slot)) {
				
					result = child.getValue();
					break;
				}
			}
		}
		return result;
	}
	
	/**
	 * takes a single child and promotes it to this
		*/
	private void promoteSingleChild() {
	
		if (size() == 1 && getType() != SLOT_FRAME) {
		
			Frame child = (Frame)get(0);
		
			//System.out.println("child is " + child);
			for (int i = 0; i < child.size(); i++) {
			
				add(child.get(i));
			}
			removeFirst();
			setType(child.getType());
		}
	}

	/**
	 *
		*/
	Frame andAdd(Frame that) {
	
		add(that);
		return this;
	}
	
	/**
	 *
		*/
	Frame andAddFirst(Frame that) {
	
		that.addFirst(this);
		return that;
	}
	
	/**
	 *
		*/
	Frame andConcatenate(Frame that) {
	
		for (int i = 0; i < that.size(); i++) {
		
			add(that.get(i));
		}
		return this;
	}
	
	/**
	 *
		*/
	Frame conjoin(Frame that) {
	
		Frame result = new Frame();
		result.setType(CONJUNCTION_FRAME);
		result.add(this);
		result.add(that);
		return result;
	}
	
	/**
	 *
		*/
	Frame orAdd(Frame that) {
	
		setAdd(that);
		sort();
		return this;
	}
	
	/**
	 *
		*/
	Frame orConcatenate(Frame that) {
	
		for (int i = 0; i < that.size(); i++) {
		
			setAdd((Frame)that.get(i));	
		}
		sort();
		return this;
	}
	
	/**
	 *
		*/
	Frame disjoin(Frame that) {

		Frame result = new Frame();
		result.setType(DISJUNCTION_FRAME);
		result.setAdd(this);
		result.setAdd(that);
		result.sort();
		result.prune();
		return result;
	}
	
	/**
	 *
		*/
	Frame distribute(Frame that) {
		
		for (int i = 0; i < size(); i++) {
		
			Frame newFrame = new Frame(that);
			set(i, ((Frame)get(i)).or(newFrame));

		}
		return this;
	}
	
	/**
	 *
		*/
	Frame stitch(Frame that) {
	
		Frame result = new Frame();
		result.setType(CONJUNCTION_FRAME);
		int thisSize = size();
		int thatSize = that.size();
		int remainder = thisSize - thatSize;
		
		if (remainder != 0) {//not the same size
		
			//which is bigger?
			if (thisSize < thatSize) {//that is bigger
			
				for (int i = 0; i < thisSize; i++) {
				
					result.add(((Frame)get(i)).or((Frame)that.get(i)));
				
				}
				//add the remaining children in that
				for (int j = thatSize + remainder; j < thatSize; j++) {
				
					result.add((Frame)that.get(j));
				}
			} else {//this is bigger //this works
			
				for (int i = 0; i < thatSize; i++) {
				
					result.add(((Frame)get(i)).or((Frame)that.get(i)));
				
				}
				//add the remaining children in this
			 for (int j = thisSize - remainder; j < thisSize; j++) {
				
					result.add((Frame)get(j));
				}
			}
		} else {//same size
		
			for (int i = 0; i < size(); i++) {
			
				result.add(((Frame)get(i)).or((Frame)that.get(i)));
			}
		}
		
		return result;
	}

	/**
	 *
		*/
	Frame unifyAnd(Frame that) {
	
		Frame result = new Frame();
		Frame temp = new Frame();
		result.setType(CONJUNCTION_FRAME);

		if (strictPrune) {
		
			for (int i = 0; i < size(); i++) {

				temp = ((Frame)get(i)).unify(that);
				
				if (temp.getType() == FAIL_FRAME) {
				
					result.setType(FAIL_FRAME);
					break;
					
				} else {
				
					result.setAdd(temp);
				}
			}

			result.prune();
			return result;
			
		} else {//strictPrune == false
		
			//to do
			return result;
		}
	}
	
	/**
	 *
		*/
	Frame unifyAndAnd(Frame that) {
	
		Frame result = new Frame();
		
		if (strictPrune) {

			if (size() != that.size()) {
	
				result.setType(FAIL_FRAME);
				
			} else {
			
				Frame temp = new Frame();
				
				for (int i = 0; i < size(); i++) {
				
					Frame childThis = (Frame)get(i);
					Frame childThat = (Frame)that.get(i);
					temp = childThis.unify(childThat);
					
					if (temp.getType() == FAIL_FRAME) {
					
						result.setType(FAIL_FRAME);
						break;
					} else {
					
						result.add(temp);
					}
					result.setType(CONJUNCTION_FRAME);
				}
			}
		} else {//strictPrune == false 
			
			Frame original = new Frame(this);//copy because we dont want to alter this
			Frame thatOriginal = new Frame(that);
			
			Frame first = null;
			Frame second = null;
			
			if (size() >= that.size()) {
			
				first = original;
				second = thatOriginal;	
				
			} else {
			
				first = thatOriginal;
				second = original;
			}
			
			Frame temp = null;
			Frame childFirst =  null;
			Frame childSecond = null;
			
			for (int i = 0; i < first.size(); i++) {//use larger frame to guarantee that all elements are looked at

				if (i < first.size()) {
				
					childFirst = (Frame)first.get(i);
					
				} else {
				
					break;
				}
				
				if (i < second.size()) {
				
					childSecond = (Frame)second.get(i);
					
				} else {
				
					break;
				}
				temp = childFirst.unify(childSecond);
				
				if (temp.getType() == FAIL_FRAME) {
				
					if (childFirst.isGreaterThan(childSecond)) {
					
						second.remove(i);
						i--;
						
					} else {
					
						first.remove(i);
						i--;
					}
				
				} else {
				
					result.add(temp);
				}
			
			}
		
		}
		if (result.size() >= 2) {
		
			result.setType(CONJUNCTION_FRAME);
			
		} else if (result.size() == 1) {
		
			result.promoteSingleChild();
			
		} else {
		
			result.setType(FAIL_FRAME);
		}
		return result;
	}
	
	/**
	 *
		*/
	Frame unifyNot(Frame that) {
	
		Frame result = new Frame();
		
		if (((Frame)get(0)).unify(that).getType() != FAIL_FRAME) {
		
			result.setType(FAIL_FRAME);
			
		} else {
		
			result = that;
		}
		
		return result;
	}
	
	/**
	 *
		*/
	Frame unifyNotNot(Frame that) {
	
		Frame result = new Frame();
		Frame temp = ((Frame)get(0)).unify((Frame)that.get(0));
		
		if (temp.getType() != FAIL_FRAME) {
		
			result.setType(NEGATION_FRAME);
			result.add(temp);
		
		} else {
		
			result.setType(CONJUNCTION_FRAME);
			result.add(this);
			result.add(that);
		}
		return result;
	}
	
	/**
	 *
		*/
	Frame unifyOr(Frame that) {//??
	
		Frame result = new Frame();
		Frame child = new Frame();
		Frame temp = new Frame();
		
		result.setType(DISJUNCTION_FRAME);
		
		for (int i = 0; i < size(); i++) {
		
			child = (Frame)get(i);
			
			//for (int j = 0; j < that.size(); j++) {
			
				//temp = child.unify((Frame)that.get(j));
			temp = child.unify(that);
				if (temp.getType() != FAIL_FRAME) {
			
					result.or(temp);
				}
			//}
		}
		
		if (result.size() == 0) {
		
			result.setType(FAIL_FRAME);
		}
		result.prune();
		result.sort();
		return result;
	}
	
	/**
	 *
		*/
	Frame unifyOrNot(Frame that) {
	
		Frame result = new Frame();
		Frame child = new Frame();
		Frame temp = new Frame();
		
		result.setType(DISJUNCTION_FRAME);
		
		for (int i = 0; i < size(); i++) {
		
			child = (Frame)get(i);
			temp = child.unify((Frame)that.get(0));
			
			if (temp.getType() == FAIL_FRAME) {

				result.or(child);
			}
		}
		
		if (result.size() == 0) {
		
			result.setType(FAIL_FRAME);
		}
		result.prune();
		result.sort();
		return result;
	}
	
	/**
	 *
		*/
	Frame unifyPlain(Frame that) {
	
		Frame result = new Frame();
		
		if (getType() == that.getType() && this.isEqualTo(that)) {
		
			result = this;
			
		} else {
		
			result.setType(FAIL_FRAME);
		}
		return result;
	}
	
	/**
	 *
		*/
	Frame unifySlotSlot(Frame that) {
	
		Frame result = new Frame();
		
		for (int i = 0; i < size(); i++) {

			SlotValuePair child = (SlotValuePair)get(i);
			String slot = (String)child.getSlot().get(0);
			
			Frame match = that.hasSlot(slot);
			
			if (match != null) {
			
			 //unify matching children
				Frame temp = child.getValue().unify(match);
				result.add(new SlotValuePair(child.getSlot(), temp));
				
			} else {//if child is not in that, add to result
			
				result.add(child);
			}
		}
		//go through that, add to result children that aren't in this
		for (int i = 0; i < that.size(); i++) {
		
			SlotValuePair child = (SlotValuePair)that.get(i);
			String slot = (String)child.getSlot().get(0);
			Frame match = hasSlot(slot);
		
			if (match == null) {

				result.add(child);
			}
		}
		result.setType(SLOT_FRAME);
		result.prune();
		result.sort();
		return result;
	}

 /**
	 * adds a child to a Frame only if that child is not already there
		*/
	private boolean setAdd(Frame that) {
	
		if (!hasChild(that)) {
		
			add(that);
			return true;
		}
		return false;
	}
	
	
///////////////////////////////////////////////////////////////////////////////
//
// Services
//
// public String toString()
// public String toPrettyString()
// public boolean isEqualTo(Frame)
// private boolean isGreaterThan(Frame)
// public Frame not()
// public Frame and()
// public Frame or()
// public Frame unify()

 /**
	 *
		*/
	public String toString() {
	
		return toPrettyString();
	}
	
	/**
	 *
		*/
	public String toPrettyString() {
	
		depth++;
		String s = "";

		switch (getType()) {
		
		case FAIL_FRAME:
			
				s += "(*FAIL*)";
				break;
				
			case UNDEFINED_FRAME:
			
				s += "(*UNDEFINED*)";
				break;
				
			case SYMBOL_FRAME: 
			
				s += get(0);
				break;
				
			case NEGATION_FRAME: 
			
				s += indent(depth) + "(*NOT* ";
				
				if (((Frame)get(0)).getType() != SYMBOL_FRAME) {
				
					s += "\n";
				}
				
				s += ((Frame)get(0)).toPrettyString() + ")";
				break;
				
			case SLOT_FRAME:
			
				s += indent(depth) + "(";
				
				for (int i = 0; i < size(); i++) {
				
					s += ((SlotValuePair)get(i)).toPrettyString();
					
					if (i < size()-1) {
					
						s += "\n" + indent(depth) + " ";
					}
				}
				s += ")";
				break;
				
			case DISJUNCTION_FRAME: 
			
				s += indent(depth) + "(*OR* ";
				
				if (size() > 0) {//allow printing empty disj frames for debugging
				
				if (((Frame)get(0)).getType() != SYMBOL_FRAME) {
				
					s += "\n";
				}

				for (int i = 0; i < size(); i++) {
				
					s += ((Frame)get(i)).toPrettyString();
					
					if (i < size()-1) {
					
						if (i != size()-1 && ((Frame)get(i+1)).getType() != SYMBOL_FRAME) {
				
							s += "\n";
						
						} else { 
					
							s += " ";
						}
					}
				}
				
				}
				s += ")"; 
				break;

			case CONJUNCTION_FRAME: 
			
				s += indent(depth) + "(*MULT* ";
			
				if (((Frame)get(0)).getType() != SYMBOL_FRAME) {
				
					s += "\n";
				}	
				
				for (int i = 0; i < size(); i++) {
				
					s += ((Frame)get(i)).toPrettyString();
					
					if (i < size()-1) {
						if (i != size()-1 && ((Frame)get(i+1)).getType() != SYMBOL_FRAME) {
				
							s += "\n";
						} else { 
							s += " ";
						}
					}
				}
				s += ")"; 
				break;
		}
		depth--;
		return s;
	}
	
	/**
	 *
		*/
	public boolean isEqualTo(Frame that) {
	
		boolean result = false;
		
		switch(getType()) {
		
			case NEGATION_FRAME:
			
				result = that.getType() == NEGATION_FRAME 
					&& ((Frame)get(0)).isEqualTo((Frame)that.get(0));
				break;
			
			case FAIL_FRAME:
			
				result = that.getType() == FAIL_FRAME;
				break;
				
			case UNDEFINED_FRAME:
			
				result = that.getType() == UNDEFINED_FRAME;
				break;
				
			case SYMBOL_FRAME:
			
				result = that.getType() == SYMBOL_FRAME
					&& ((String)get(0)).equals((String)that.get(0));
				break;
				
			case CONJUNCTION_FRAME:
			case DISJUNCTION_FRAME:
			
				if (size() != that.size()) {
				
					break;
				}

				//this works because the elements are ordered
				// as soon as there is a false comparison of any two ordered elements
				//the whole frame is not equal
				//NOTE: conjunction frames are ordered by the sort() method when created 
				//disjunction frames are ordered by the string that creates them
				result = true;

				for (int i = 0; i < size(); i++) {
				
					if (!((Frame)get(i)).isEqualTo((Frame)that.get(i))) {
					
						result = false;
						break;
					}
				}
				break;

			case SLOT_FRAME:
			
				if (size() != that.size()) {
				
					break;
				}
				
				// SlotValuePairs are ordered, so as soon as the comparison returns
				// false, the result becomes false
				result = true;
				
				for (int i = 0; i < size(); i++) {
				
					if (!((SlotValuePair)get(i)).isEqualTo((SlotValuePair)that.get(i))) {

						result = false;
						break;
					}
				}
				break;
		}
		return result;
	}

//criteria:  first check type, if types are same, check through types
	//for symbols use compareTo
	//for negation use recursive call to first child
	//for slot, disjunction and conjunction, use size first
	//then use recursive call on each child
	/**
	 *
		*
		*/
	private boolean isGreaterThan(Frame that) {
	
		boolean result = false;
	
		//first check types
		if (getType() != that.getType()) {
		
			result = getType() > that.getType();
			
		} else {//if types are the same!!!
		
			switch (getType()) {
			
				case SYMBOL_FRAME:
				
					result = ((String)get(0)).compareTo((String)that.get(0)) > 0;
					break;
				
				case NEGATION_FRAME:
				
					result = ((Frame)get(0)).isGreaterThan((Frame)that.get(0));
					break;
				
				case SLOT_FRAME:
				
					if (size() != that.size()) {
					
						result = size() > that.size();
						break;
						
					} else {//as soon as a child is greater than the other return true and break out
					
						for (int i = 0; i < size(); i++) {
						
							if (((SlotValuePair)get(i)).isGreaterThan((SlotValuePair)that.get(i))) {
							
								result = true;
								break;
							}
						}
					}
					break; // if we haven't broken earlier, break here, the result is false
				
				case DISJUNCTION_FRAME:
				case CONJUNCTION_FRAME:
				
					if (size() != that.size()) {
					
						result = size() > that.size();
						break;
						
					} else {//as soon as a child is greater than the other return true and break out
					
						for (int i = 0; i < size(); i++) {
						
							if (((Frame)get(i)).isGreaterThan((Frame)that.get(i))) {
							
								result = true;
								break;
							}
						}
					}
					break; // if we haven't broken earlier, break here, the result is false
			}
		}
		return result;
	}
	
	/**
	 *
		*/
	public Frame not() throws Exception {
	
		Frame pf = null;
		
		switch (getType()) {
		
			case NEGATION_FRAME:
			
				pf = (Frame)get(0);
				break;
			
			case FAIL_FRAME:
			
				setType(UNDEFINED_FRAME);
				pf = this;
				break;
				
			case UNDEFINED_FRAME:
			
				setType(FAIL_FRAME);
				pf = this;
				break;
				
			case CONJUNCTION_FRAME://mult
			
				pf = new Frame();
				pf.setType(DISJUNCTION_FRAME);
				
				for (int i = 0; i < this.size(); i++) {
				
					pf.setAdd(((Frame)get(i)).not());
					//set(i, ((Frame)get(i)).not());
				}
				//pf = this;
				break;
			
			case DISJUNCTION_FRAME://or
			
				//pf = new Frame();
				//pf.setType(CONJUNCTION_FRAME);
				setType(CONJUNCTION_FRAME);
				
				for (int i = 0; i < this.size(); i++) {
				
					set(i, ((Frame)get(i)).not());
					//pf.setAdd(((Frame)get(i)).not());
				}
				pf = this;
				break;
				
			case SLOT_FRAME:

				pf = new Frame(NEGATION_FRAME);
				pf.add(this);
				break;
				
			case SYMBOL_FRAME:

				pf = new Frame(NEGATION_FRAME);
				pf.add(this);
				break;
		}
		return pf;
	}
	
	/**
	 *
		*/
	public Frame and(Frame that) {
	
		Frame result = new Frame();
		
		switch(getType()) {//this
		
			case FAIL_FRAME:
			
				result.setType(FAIL_FRAME);
				break;
			
			case UNDEFINED_FRAME:
				result = that;
				break;
			
			case DISJUNCTION_FRAME:
			
				switch(that.getType()) {//that
				
					case UNDEFINED_FRAME:
					
					result = that.and(this);
					break;
					
					case FAIL_FRAME:
					
					result = that.and(this);
					break;
					
					case DISJUNCTION_FRAME:
					case SLOT_FRAME:
					case SYMBOL_FRAME:
					case NEGATION_FRAME:

					result = conjoin(that);
					break;
				
					case CONJUNCTION_FRAME:
					
					result = andAddFirst(that);
					break;
				}
			break;
			
			case CONJUNCTION_FRAME:
			
				switch(that.getType()) {
				
					case UNDEFINED_FRAME:
					
					result = that.and(this);
					break;
					
					case FAIL_FRAME:

					result = that.and(this);
					break;
					
					case DISJUNCTION_FRAME:
					case SLOT_FRAME:
					case SYMBOL_FRAME:
					case NEGATION_FRAME:
					
					result = andAdd(that);
					break;
				
					case CONJUNCTION_FRAME:
					
					result = andConcatenate(that);
					break;
				}
			break;
			
			case SLOT_FRAME:
			case SYMBOL_FRAME:
			case NEGATION_FRAME:
			
				switch(that.getType()) {
				
					case UNDEFINED_FRAME:

					result = that.and(this);
					break;
					
					case FAIL_FRAME:

					result = that.and(this);
					break;
					
					case DISJUNCTION_FRAME:
					case SLOT_FRAME:
					case SYMBOL_FRAME:
					case NEGATION_FRAME:
					
					result = conjoin(that);
					break;
				
					case CONJUNCTION_FRAME:
					
					result = andAddFirst(that);
					break;
				}
			break;
		}
	
		return result;
	}
	
	/**
	 *
		*/
	public Frame or(Frame that) {
	
		Frame result = new Frame();
		
		switch(getType()) {//this
		
		 case FAIL_FRAME:
			
				result.setType(FAIL_FRAME);
				break;
				
			case UNDEFINED_FRAME:
			
				result = that;
				break;
				
			case DISJUNCTION_FRAME:
				
				switch(that.getType()) {//that
				
					case UNDEFINED_FRAME:
					case FAIL_FRAME:
					case CONJUNCTION_FRAME:

						result = that.or(this);
						break;
						
					case DISJUNCTION_FRAME:
					
						result = orConcatenate(that);
						break;
						
					case SYMBOL_FRAME:
					case SLOT_FRAME:
					case NEGATION_FRAME:
					
						result = orAdd(that);
					 break;
				}
				break;//disjunction_frame this
				
			case CONJUNCTION_FRAME:
			
				switch(that.getType()) {//that
				
					case UNDEFINED_FRAME:
					case FAIL_FRAME:
					
						result = that.or(this);
						break;
						
					case DISJUNCTION_FRAME:
					case SYMBOL_FRAME:
					case SLOT_FRAME:
					case NEGATION_FRAME:
					
						result = distribute(that);
						break;
						
					case CONJUNCTION_FRAME:
					
						result = stitch(that);
						break;
				}
				break;//conjunction_frame this
				
			case SLOT_FRAME:
			case SYMBOL_FRAME:
			case NEGATION_FRAME:
			
				switch (that.getType()) {//that
					
					case UNDEFINED_FRAME:
					case FAIL_FRAME:
					case DISJUNCTION_FRAME:
					case CONJUNCTION_FRAME:
					
						result = that.or(this);
						break;
						
					case SLOT_FRAME:
					case SYMBOL_FRAME:
					case NEGATION_FRAME:
					
						result = disjoin(that);
						break;
				}
				break;//slot, symbol, negation this
		}
		return result;
	}
	
 /**
	 *
		*/
	public Frame unify(Frame that) {
	
		Frame result = new Frame();
		
		switch(getType()) {
		
			case FAIL_FRAME:
			
				result = this;
				break;
				
			case UNDEFINED_FRAME:
			
				result = that;
				break;
		
			case DISJUNCTION_FRAME:
				
				switch(that.getType()) {
				
					case FAIL_FRAME:
					case UNDEFINED_FRAME:
					case CONJUNCTION_FRAME:
					
						result = that.unify(this);
						break;
					
					case DISJUNCTION_FRAME:
					case SYMBOL_FRAME:
					case SLOT_FRAME:
					
						result = unifyOr(that);
						
						break;
						
					case NEGATION_FRAME:
					
						result = unifyOrNot(that);
						break;
				}
				break;//end case this = DISJUNCTION
				
			case CONJUNCTION_FRAME:
			
				switch(that.getType()) {
				
					case FAIL_FRAME:
					case UNDEFINED_FRAME:
					
						result = that.unify(this);
						break;
						
					case DISJUNCTION_FRAME:
					case NEGATION_FRAME:
					case SYMBOL_FRAME:
					case SLOT_FRAME:
					
						result = unifyAnd(that);
						break;
						
					case CONJUNCTION_FRAME:
					
						result = unifyAndAnd(that);
						break;
				}
				break;
				
			case NEGATION_FRAME:
				
				switch(that.getType()) {
				
					case FAIL_FRAME:
					case UNDEFINED_FRAME:
					case DISJUNCTION_FRAME:
					case CONJUNCTION_FRAME:
					
						result = that.unify(this);
						break;
						
					case NEGATION_FRAME:
					
						result = unifyNotNot(that);
						break;
					
					case SYMBOL_FRAME:
					case SLOT_FRAME:
					
						result = unifyNot(that);
						break;
				}
				break;
				
			case SYMBOL_FRAME:
			case SLOT_FRAME:
			
				switch(that.getType()) {
				
					case UNDEFINED_FRAME:
					case FAIL_FRAME:
					case DISJUNCTION_FRAME:
					case CONJUNCTION_FRAME:
					case NEGATION_FRAME:
					
						result = that.unify(this);
						break;
				
					case SYMBOL_FRAME:
					
						result = unifyPlain(that);
						break;
						
					case SLOT_FRAME:
					
						result = unifySlotSlot(that);
						break;
				}
				break; //this=trivial frame
		}//end switch
		return result;
	}

///////////////////////////////////////////////////////////////////////////////
//
// Inner classes
//
// class SlotValuePair

 /**
	 *
		*/
	class SlotValuePair {
	
		Frame slot = null;
		Frame value = null;
		
		/////////////////////////////////////////////////////////////////
		//
		// Constructors
		
		/**
	  *
		 */
		SlotValuePair() {}
		
		/**
	  *
		 */
		SlotValuePair(Frame slot, Frame value) {
		
			if (slot.getType() != SYMBOL_FRAME) {
			
				//complain
			} else {
			
				this.slot = slot;
				this.value = value;
			}
		}
		
		/**
	  *
		 */
		SlotValuePair(SlotValuePair that) {
		
			setSlot(new Frame((Frame)that.getSlot()));
			setValue(new Frame((Frame)that.getValue()));
		}
		
		/**
	  *
		 */
		SlotValuePair(String s) throws Exception {
		
			// need to make complaint if slot is not SYMBOL_FRAME
			//slot-value strings come in with enclosing parens
			slot = new Frame(s.substring(1, s.indexOf(' ')));
			value = new Frame(s.substring(s.indexOf(' ')+1, s.length()-1));
		}
		
		/////////////////////////////////////////////////////////////////
		//
		// Getters and Setters
		
		/**
	  *
		 */
		Frame getSlot() {
		
			return slot;
		}
		
		/**
	  *
		 */
		void setSlot(Frame slot) {
		
			this.slot = slot;
		}
		
		/**
	  *
		 */ 
		Frame getValue() {
		
			return value;
		}
		
		/**
	  *
		 */
		void setValue(Frame value) {
		
			this.value = value;
		}
		
		/////////////////////////////////////////////////////////////////
		//
		// Services and Utilities
		 
		/**
	  *
		 */
		public String toPrettyString() {
		
			String s = "(" + getSlot().toPrettyString();
			
			if (getValue().getType() != SYMBOL_FRAME) {
			
				s += "\n ";
				
				if (getValue().getType() != SLOT_FRAME) {
				
					s += indent(depth+1);
				}
			} else {
			
				s += " ";
			}
			return s + getValue().toPrettyString() + ")";
		}

		public boolean isEqualTo(Frame.SlotValuePair pair) {

			return (getSlot().isEqualTo(pair.getSlot()) 
				&&  getValue().isEqualTo(pair.getValue()));
		}
		
		/**
	  *
		 */
		public boolean isGreaterThan(Frame.SlotValuePair pair) {
		
			return getSlot().isGreaterThan(pair.getSlot()) 
				&& getValue().isGreaterThan(pair.getValue());
		}
		
		/**
	  *
		 */
	 public void prune() {
	
			getValue().prune();
		}
	}	
}