Efficient Searching

ngram_search.js.coffee

# ALL NGRAMS CACHE (cache this client-side)
# ================
ngrams = {} # Assuming ngrams is a pre-populated hash


# ALL RECORDS CACHE (cache this client-side)
# =================
Records = [] # an array of all records
ShadowRecords = [] # an array of all records' ids


# SEARCH RESULTS (calculated when searching)
# ==============
Results = [] # an array of all results
ShadowResults = [] # an array of all results' ids


# Convenience method for adding a record
addResult = (index) ->
  index = _.index ShadowRecords, id # get the index of the record
  Results.push Records[index] # add that record to the results
  ShadowResults.push id # add that records' id to the shadow results

# Convenience method for removing a result at an index
removeResult = (index) ->
    ShadowResults.splice index, 1 # modify shadow results array in place
    Results.splice index, 1 # modify results array in place


updateResults = (newResults) ->
  if _.isEmpty newResults # an empty array is passed
    Results = newResults # set results to an empty array (no one cares for a record without searching for it)
  else if _.isEmpty Results # if the previous state was an empty array (i.e. no search)
    _.each newResults, addResult
  else # if there were previous results (i.e. we're filtering a previous search)
    _.each newResults, (id) ->
      index = _.index ShadowResults, id # get the index of the new result in the current result records
      if index == -1
        addResult id
    _.each ShadowResults, (id) ->
      index = _.index newResults, id # get index of a current result record in the new result records
      if index == -1 # if a current result record doesn't exist in the new result records
        removeResult index # remove it


getResults = (searchQuery) ->
  searchGrams = searchQuery.match(/\w+/g) # Select all tokens in search query (select all words)
  resultsIds = []
  _.each searchGrams, (ngram) -> # For each search token,
    resultIds = ngrams[ngram] # Get the result ids for that token
    resultIds.push(resultIds) if !_.isUndefined resultIds # If the result ids exist, add them to the resultIds
  resultIds = _.intersection.apply(_, resultIds) # Get the intersection of all results
  updateResults(_.uniq resultIds) # Call updateResults