function dictDeepCopy( dict ) {
  var newDict = {};
  for (var i in dict ) {
    newDict[i] = dict[i];
  }
  return newDict;
};

function dictKeys( dict ) {
  return [ key for ( key in dict ) ];
}

function NounType( name, expectedWords ) {
    this._init( name, expectedWords );
  }
NounType.prototype = {
 _init: function( name, expectedWords ) {
    this._name = name;
    this._expectedWords = expectedWords; // an array
  },

 match: function( fragment ) {
    var suggs = this.suggest( fragment );
    // klugy!
    if ( suggs.length > 0 ) {
      return true;
    }
    return false;
  },
 
 suggest: function( fragment ) {
    // returns (ordered) array of suggestions
    var suggestions = [];
    for ( var x in this._expectedWords ) {
      word = this._expectedWords[x];
      if ( word.indexOf( fragment ) > -1 ) {
	suggestions.push( word );
	// TODO sort these in order of goodness
	// todo if fragment is multiple words, search for each of them
	// separately within the expected word.
      }
    }
    return suggestions;
  }
};

// for example....
var city = new NounType( "city", [ "new york", "los angeles", "mexico city", "sao paulo", "rio de janeiro", "buenos aires", "london", "paris", "moscow", "cairo", "lagos", "tehran", "karachi", "mumbai", "delhi", "kolkata", "jakarta", "manila", "bejing", "singapore", "shanghai", "hong kong", "seoul", "tokyo", "osaka" ] );

var language = new NounType( "language", [ "english", "chinese", "hindi", "japanese", "klingon", "esperanto", "sanskrit", "pig latin", "tagalog", "portugese" ] );

var tab = new NounType( "tab", [ "gmail", "mozilla developer connection", "xulplanet", "evilbrainjono.net", "google calendar", "humanized enso forum" ] );

var person = new NounType( "person", ["atul@mozilla.com", "aza@mozilla.com", "thunder@mozilla.com", "chris@mozilla.com", "myk@mozilla.com" ] );

var anyWord = {
  // a singleton object which can be used in place of a NounType.
 _name: "text",
 match: function( fragment ) {
    return true;
  },
 suggest: function( fragment ) {
    return [ fragment ];
  }
};

function ParsedSentence( verb, DO, modifiers ) {
  this._init( verb, DO, modifiers );
}
ParsedSentence.prototype = {
 _init: function( verb, DO, modifiers ) {
    /* modifiers is dictionary of preposition: noun */
    this._verb = verb;
    this._DO = DO;
    this._modifiers = modifiers;
  },

 getCompletionText: function() {
    // return plain text that we should set the input box to if user hits
    // space bar on this sentence.
    var sentence = this._verb._name;
    if ( this._DO ) {
      sentence = sentence + " " + this._DO;
    }
    for ( var x in this._modifiers ) {
      sentence = sentence + " " + x + " " + this._modifiers[x];
    }
    return sentence;
  },

 getDisplayText: function() {
    // returns html formatted sentence for display in suggestion list
    var sentence = this._verb._name;
    if ( this._verb._DOType ) {
      if ( this._DO ) {
	sentence = sentence + " " + this._DO;
      } else {
	sentence = sentence + " <span class=\"needarg\">(" + this._verb._DOLabel + ")</span>";
      }
    }

    for ( var x in this._verb._modifiers ) {  // was this._verb._modifiers
      if ( this._modifiers[ x ] ) {
	sentence = sentence + " <b>" +  x + " " + this._modifiers[x] + "</b>";
      } else {
	sentence = sentence + " <span class=\"needarg\">(" + x + " " + this._verb._modifiers[x]._name + ")</span>";
      }
    }
    return sentence;
  },

 getDescription: function() {
    // returns a string describing what the sentence will do if executed
    return this._verb.getDescription( this._DO, this._modifiers );
  }

};


function Verb( name, DOLabel, DOType, modifiers ) {
  this._init( name, DOLabel, DOType, modifiers );
}
Verb.prototype = {
 _init: function( name, DOLabel, DOType, modifiers ) {
    this._name = name;
    this._DOLabel = DOLabel;
    this._DOType = DOType; // must be a NounType.
    this._modifiers = modifiers;
    // modifiers should be a dictionary
    // keys are prepositions
    // values are NounTypes.
    // example:  { "from" : City, "to" : City, "on" : Day }
  },

 getDescription: function( directObject, prepositionPhrases ) {
    // returns a string describing what the sentence will do if executed
    var desc = "Hit enter to do " + this._name + " with direct object " + directObject;
    for ( var x in prepositionPhrases ) {
      desc = desc + ", " + x + " " + prepositionPhrases[x];
    }
    return desc;
  },

 recursiveParse: function( unusedWords, filledMods, unfilledMods ) {
    var x;
    var suggestions = [];
    var completions = [];
    var newFilledMods = {};
    var directObject = "";
    var newCompletions = [];
    if ( dictKeys( unfilledMods ).length == 0 ) {
      // Done with modifiers, try to parse direct object.
      if ( unusedWords.length == 0 ) {
	// No words left, no direct object.  Try parsing sentence
	// without them.
	return [ new ParsedSentence( this, "", filledMods ) ];
      }

      if ( this._DOType == null ) {
	// intransitive verb; no direct object, only modifiers.
	// We can't use the extra words, so fail.
	  return [];
      } else {
	// Transitive verb, can have direct object.  Try to use the
	// remaining words in that slot.
	directObject = unusedWords.join( " " );
	if ( this._DOType.match( directObject ) ) {
	  // it's a valid direct object.  Make a sentence for each
	  // possible noun completion based on it; return them all.
	  suggestions = this._DOType.suggest( unusedWords[0] );
	  for ( var x in suggestions ) {
	    completions.push( new ParsedSentence( this, suggestions[x],
						  filledMods ) );
	  }
	  return completions;
	} else {
	  // word is invalid direct object.  Fail!
	  return [];
	}
      }
    } else {
      // "pop" a preposition off of the properties of unfilledMods
      var preposition = dictKeys( unfilledMods )[0];
      // newUnfilledMods is the same as unfilledMods without preposition
      var newUnfilledMods = dictDeepCopy( unfilledMods );
      delete newUnfilledMods[preposition];

      // Look for a match for this preposition
      var nounType = unfilledMods[ preposition ];
      var matchIndices = [];
      for ( var x = 0; x < unusedWords.length - 1; x++ ) {
	if ( preposition.indexOf( unusedWords[x] ) == 0 ) {
	  if ( nounType.match( unusedWords[ x + 1 ] ) ) {
	    // Match for the preposition at index x followed by
	    // an appropriate noun at index x+1
	    matchIndices.push( x );
	  }
	}
      }

      // If no match was found, all we'll return is one sentence formed by
      // leaving that preposition blank. But even if a match was found, we
      // still want to include this sentence as a possibility.
      newFilledMods = dictDeepCopy( filledMods );
      newFilledMods[preposition] = "";
      directObject = unusedWords.join( " " );
      newCompletions = this.recursiveParse( unusedWords, 
					    newFilledMods, 
					    newUnfilledMods );
      completions = completions.concat( newCompletions );

      if ( matchIndices.length > 0 ) {
	// Sentences that can be formed by using the match(es) for this
	// preposition.
	for ( x in matchIndices ) {
	  var noun = unusedWords[ matchIndices[x]+1 ];
	  var newUnusedWords = unusedWords.slice();
	  newUnusedWords.splice( matchIndices[x], 2 );
	  directObject = newUnusedWords.join( " " );

	  suggestions = nounType.suggest( noun );
	  for ( var y in suggestions ) {
	    newFilledMods = dictDeepCopy( filledMods );
	    newFilledMods[ preposition ] = suggestions[y];
	    newCompletions = this.recursiveParse( newUnusedWords,
						  newFilledMods,
						  newUnfilledMods );
	    completions = completions.concat( newCompletions );
	  }
	}
      }
      return completions;
    }
  },

 getCompletions: function( words ) {
    /* returns a list of ParsedSentences. */
    /* words is an array of words that were space-separated.
       The first word, which matched this verb, has already been removed.
       Everything after that is either:
       1. my direct object
       2. a preposition
       3. a noun following a preposition. 
    */
    return this.recursiveParse( words, {}, this._modifiers );
  },

 match: function( sentence ) {
    // returns a float from 0 to 1 telling how good of a match the input
    // is to this verb.
    if ( this._name.indexOf( sentence ) == 0 ) {
      // verb starts with the sentence, i.e. you may be typing this
      // verb but haven't typed the full thing yet.
      return sentence.length / this._name.length;
    } else {
      return 0.0;
    }
  }
};

var fly = new Verb( "fly", null, null, { "from": city, "to": city } );
fly.getDescription = function( directObject, mods ) {
  var fromCity = mods[ "from" ];
  var toCity = mods["to"];
  if ( !fromCity ) {
    fromCity = "from somewhere";
  }
  if ( !toCity ) {
    toCity = "to somewhere else";
  }
  return "Buy airplane tickets from " + fromCity + " to " + toCity;
};
var define = new Verb( "define", "word", anyWord, {} );
define.getDescription = function( directObject, mods ) {
  if (directObject ) {
    return "Search for definition of the word &quot;" + directObject + "&quot;";
  } else {
    return "Search for the definition of a word.";
  }
};
var google = new Verb( "google", "word", anyWord, {} );
google.getDescription = function( directObject, mods ) {
  if (directObject ) {
    return "Search Google for &quot;" + directObject + "&quot;";
  } else {
    return "Search Google for a word or phrase.";
  }
};
var go = new Verb( "go", "tab", tab, {} );
go.getDescription = function( directObject, mods ) {
  if (directObject ) {
    return "Switch to the Firefox tab &quot;" + directObject + "&quot;";
  } else {
    return "Search to a given Firefox tab.";
  }
};
var close = new Verb( "close", null, null, {} );
close.getDescription = function( directObject, mods ) {
  return "Close the front window or tab.";
};
var translate = new Verb( "translate", "text", anyWord, { "from": language, "to": language } );
translate.getDescription = function( directObject, mods ) {
  if (directObject ) {
    var DO = "the phrase &quot;" + directObject + "&quot;";
  } else {
    var DO = "a given phrase";
  }
  var fromLang = mods["from"];
  if (!fromLang) {
    fromLang = "a given language";
  }
  var toLang = mods["to"];
  if (!fromLang) {
    toLang = "another language.";
  }
  return "Translate " + DO + " from " + fromLang + " to " + toLang;
};
var nuke = new Verb( "nuke", "city", city, {} );
nuke.getDescription = function( directObject, mods ) {
  if (!directObject) {
    directObject = "a given city";
  }
  return "Launch a nuclear missile at " + directObject;
};
var open = new Verb( "open", "url", anyWord, {} );
open.getDescription = function( directObject, mods ) {
  if (directObject ) {
    return "Open the URL &quot;" + directObject + "&quot;";
  } else {
    return "Open a given URL.";
  }
};

var email = new Verb( "email", "text", anyWord, { "to": person, "subject": anyWord } );
email.getDescription = function( directObject, mods ) {
  if (directObject ) {
    var DO = "the message &quot;" + directObject + "&quot; as an email";
  } else {
    var DO = "an email";
  }
  var target = mods["to"];
  if ( !target ) {
    target = "someone from your address book";
  }
  if ( mods["subject"] ) {
    var subject = ", with the subject " + mods["subject"] + ", ";
  } else { 
    var subject = " ";
  }
  return "Send " + DO + subject + "to " + target;
};

var encrypt = new Verb( "encrypt", "text", anyWord, { "for": person } );
encrypt.getDescription = function( directObject, mods ) {
  if (directObject ) {
    var DO = "the message &quot;" + directObject + "&quot;";
  } else {
    var DO = "a secret message";
  }
  var target = mods["for"];
  if ( !target ) {
    target = "one particular person";
  }
  return "Encrypt " + DO + " so it can only be read by " + target;
};

var wiki = new Verb( "wikipedia", "word", anyWord, { "language": language } );
wiki.getDescription = function( directObject, mods ) {
  var desc = "Search ";
  if ( mods["language"] ) {
    desc = desc + "the " + mods["language"] + " language version of ";
  }
  desc = desc + "Wikipedia for &quot;" + directObject + "&quot;";
  return desc;
};

var verbs = [ fly, define, google, go, close, open, translate, email, nuke, encrypt, wiki ];

/* Initial state: no verb determined.
   After each keypress, update verb suggestion list.
   After first spacebar: lock in top verb from suggestion list.  Create
   parsedSentence object based on verb.  change state to sentence completion.
   Non-keystroke spaces after that: 
   spacebar sends the lock-in-last-word message to lockedInSentence.

   todo: add responder for arrow keys to hilight suggestions
   and escape to clear text.
*/


function QuerySource() {
    this._init( );
  }
QuerySource.prototype = {
 _init: function( ) {
    this._lockedInSentence = null;
    this._hilitedSuggestion = 0;
    this._suggestionList = []; // a list of ParsedSentences.
  },
 
 updateSuggestionList: function( query ) {
    this._suggestionList = [];
    var completions = [];
    var words = query.split( " " );
    for ( var x in verbs ) {
      var verb = verbs[x];
      if ( verb.match( words[0] ) ) {
	completions = verb.getCompletions( words.slice(1) );
	this._suggestionList = this._suggestionList.concat( completions );
      }
    }
    // TODO sort in order of match quality
    this._hilitedSuggestion = 0;
  },

 getSuggestionsAsHtml : function() {
    return [ this._suggestionList[x].getDisplayText() for ( x in this._suggestionList ) ];
  },

 getDescriptionText: function() {
    if ( this._suggestionList.length == 0 ) {
      return "Type some commands!";
    }
    var h = this._hilitedSuggestion;
    if ( h == 0 ) {
      h = 0;
    } else {
      h = h - 1;
    }
    var sentence = this._suggestionList[h];
    return sentence.getDescription();
  },

 indicationDown: function( ) {
    this._hilitedSuggestion ++;
    if ( this._hilitedSuggestion > this._suggestionList.length ) {
      this._hilitedSuggestion = 0;
      }
  },

 indicationUp: function() {
    this._hilitedSuggestion --;
    if ( this._hilitedSuggestion < 0 ) {
      this._hilitedSuggestion = this._suggestionList.length;
      }
  },

 getHilitedSuggestion: function() {
    return this._hilitedSuggestion - 1; // because 0 means no hilite
    // and the suggestion list starts at 1... fencepost!
  },

 autocomplete: function( query ) {
    var hilited = this.getHilitedSuggestion();
    if ( hilited > -1 ) {
      var newText = this._suggestionList[ hilited ].getCompletionText() + " ";
    } else {
      newText = query;
    }
    return newText;
  },

 clear: function() {
    this._suggestionList = [];
    this._hilitedSuggestion = 0;
    lockedInSentence = null;
  }
};

var gQs = new QuerySource();

function makeSuggestionHtml( tagName, list, hilitedNumber ) {
  var result = "";
  var openingTag = "";
  var closingTag = "</" + tagName + ">";

  for (var i = 0; i < list.length; i++) {
    if ( i == hilitedNumber ) {
      openingTag = "<" + tagName + " class=\"hilited\">";
    } else {
      openingTag = "<" + tagName + ">";
    }
    result += (openingTag + list[i] + closingTag );
  }
  return result;
}

function updateDisplay( ) {
   var suggestions = gQs.getSuggestionsAsHtml();
   var hilitedSuggestion = gQs.getHilitedSuggestion();
   var description = gQs.getDescriptionText();
   $("#status-line").html( description );
   var ac = $("#autocomplete-popup");
   ac.html( makeSuggestionHtml( "div", suggestions, hilitedSuggestion ) );
   ac.show();
}

function searchBoxQuery( event ) {
  // TODO: if the event is an 'esc' key, clear the input field.
  // If the event is an 'up arrow' or 'down arrow' key, change the
  // indication.
  
  // key is event.which
  // esc is 27
  // up arrow is 38
  // down arrow is 40
  // enter is 13
  // space is 32
  switch( event.which ) {
  case 27: //esc
    event.target.value = "";
    gQs.clear();
    break;
  case 38: // up arrow
    gQs.indicationUp();
    break;
  case 40: // down arrow
    gQs.indicationDown();
    break;
  case 13: // enter
    gQs.execute();
    break;
  case 32: // spacebar
    event.target.value = gQs.autocomplete( event.target.value );
    gQs.updateSuggestionList( event.target.value );
    break;
  default:
    gQs.updateSuggestionList( event.target.value );
    break;
    // todo: delete key "unlocks" if you delete past a space?
  }

  updateDisplay();

}

$(document).ready( function() {
    $("#status-line").html( "Welcome to Ubiquity." );
    $("#search-box").focus();
    $("#search-box").keyup( searchBoxQuery );
    $("#autocomplete-popup").css(
        "width",
        $("#search-box").css("width")
    );
});

/* Minor problems:
2. multiple word direct objects are truncated to single word
*/