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.
 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() {
    // returns completed and canonicalized sentence
    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 ) {
      if ( this._modifiers[ x ] ) {
	sentence = sentence + " " + x + " " + this._modifiers[x];
      } else {
	sentence = sentence + " <span class=\"needarg\">(" + this._verb._modifiers[x]._name + ")</span>";
      }
    }
    return sentence;
  },

 getDescription: function() {
    // returns a string describing what the sentence will do if executed
  }

};


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 }
  },

 recursiveParse: function( unusedWords, filledMods, unfilledMods ) {
    var x;
    var suggestions = [];
    var completions = [];
    var directObject = "";
    if ( [key for (key in 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 = [key for (key in unfilledMods)][0];
      var newUnfilledMods = unfilledMods.splice();
      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 ] ) == 0 ) {
	    // Match for the preposition at index x followed by
	    // an appropriate noun at index x+1
	    matchIndices.push( x );
	  }
	}
      }
      if ( matchIndices.length == 0 ) {
	// no match for this preposition.
	// Leave it blank and try to parse the rest:
	filledMods[preposition] = "";
	return recursiveParse( unusedWords, filledMods, newUnfilledMods );
      } else {
	for ( x in matchIndices ) {
	  // remove the words that matched the preposition and following
	  // noun:
	  var noun = unusedWords[ matchIndices[x]+1 ];
	  var newUnusedWords = unusedWords.slice();
	  newUnusedWords.splice( possibilities[x], 2 );
	  // add every noun completion from every possibility...
	  suggestions = nounType.suggest( noun );
	  for ( var y in suggestions ) {
	    var newFilledMods = filledMods.slice();
	    newFilledMods[ preposition ] = suggestions[y];
	    var newCompletions = recursiveParse( newUnusedWords,
						 newFilledMods,
						 newUnfilledMods );
	    completions = completions.concat( newCompletions );
	  }
	}
	return completions;
      }
    }
    }, */

 parse: 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 );
  },

 getCompletions: function( words ) {
    var sentences = this.parse( words );
    return [ sentences[x].getCompletionText() for ( x in sentences ) ];
  },

 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 } );
var define = new Verb( "define", "word", anyWord, {} );
var google = new Verb( "google", "word", anyWord, {} );
var go = new Verb( "go", "tab", tab, {} );
var close = new Verb( "close", null, null, {} );
var translate = new Verb( "translate", "text", anyWord, { "from": language, "to": language } );
var nuke = new Verb( "nuke", "city", city, {} );
var open = new Verb( "open", "url", anyWord, {} );
var email = new Verb( "email", "text", anyWord, { "to": person, "subject": anyWord } );
var encrypt = new Verb( "encrypt", "text", anyWord, { "for": person } );
var wiki = new Verb( "wikipedia", "word", anyWord, { "language": language } );

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 = [];
  },
 
 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;
  },

 getSuggestions : function() {
    return this._suggestionList;
  },

 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 ] + " ";
    } 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.getSuggestions();
   var hilitedSuggestion = gQs.getHilitedSuggestion();
   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() {
    $("#search-box").focus();
    $("#search-box").keyup( searchBoxQuery );
    $("#autocomplete-popup").css(
        "width",
        $("#search-box").css("width")
    );
});

/* Minor problems:
1. verbs with indirect objects are returning empty completion lists
2. multiple word direct objects are truncated to single word
*/