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() {
    // returns a string describing what the sentence will do if executed
    return this._verb.getDescription( this._DO, this._modifiers );
  }

 recursiveParse: function( unusedWords, filledMods, unfilledMods ) {
    var x;
    var suggestions = [];
    var completions = [];
    var directObject = "";
    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 ( matchIndices.length == 0 ) {
	// no match for this preposition.
	// Leave it blank and try to parse the rest:
	filledMods[preposition] = "";
	var directObject = unusedWords.join( " " );
	return [ new ParsedSentence( this, directObject, filledMods ) ];
	//return this.recursiveParse( unusedWords, filledMods, newUnfilledMods );
      } else {
	// this is placeholder, destroy it.
	for ( x in matchIndices ) {
	  var noun = unusedWords[ matchIndices[x]+1 ];
	  var newUnusedWords = unusedWords.slice();
	  newUnusedWords.splice( matchIndices[x], 2 );
	  var directObject = newUnusedWords.join( " " );

	  suggestions = nounType.suggest( noun );
	  for ( var y in suggestions ) {
	    var newFilledMods = dictDeepCopy( filledMods );
	    newFilledMods[ preposition ] = suggestions[y];
	    var 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 } );
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 = []; // 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 ) ];
  },

 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 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
3. prepositional phrases past the first don't get matched?
4. sentences need to have descriptions
*/