/*

 * typeahead.js

 * https://github.com/twitter/typeahead.js

 * Copyright 2013-2014 Twitter, Inc. and other contributors; Licensed MIT

 */



var SearchIndex = window.SearchIndex = (function() {

  'use strict';



  var CHILDREN = 'c', IDS = 'i';



  // constructor

  // -----------



  function SearchIndex(o) {

    o = o || {};



    if (!o.datumTokenizer || !o.queryTokenizer) {

      $.error('datumTokenizer and queryTokenizer are both required');

    }



    this.identify = o.identify || _.stringify;

    this.datumTokenizer = o.datumTokenizer;

    this.queryTokenizer = o.queryTokenizer;



    this.reset();

  }



  // instance methods

  // ----------------



  _.mixin(SearchIndex.prototype, {



    // ### public



    bootstrap: function bootstrap(o) {

      this.datums = o.datums;

      this.trie = o.trie;

    },



    add: function(data) {

      var that = this;



      data = _.isArray(data) ? data : [data];



      _.each(data, function(datum) {

        var id, tokens;



        that.datums[id = that.identify(datum)] = datum;

        tokens = normalizeTokens(that.datumTokenizer(datum));



        _.each(tokens, function(token) {

          var node, chars, ch;



          node = that.trie;

          chars = token.split('');



          while (ch = chars.shift()) {

            node = node[CHILDREN][ch] || (node[CHILDREN][ch] = newNode());

            node[IDS].push(id);

          }

        });

      });

    },



    get: function get(ids) {

      var that = this;



      return _.map(ids, function(id) { return that.datums[id]; });

    },



    search: function search(query) {

      var that = this, tokens, matches;



      tokens = normalizeTokens(this.queryTokenizer(query));



      _.each(tokens, function(token) {

        var node, chars, ch, ids;



        // previous tokens didn't share any matches

        if (matches && matches.length === 0) {

          return false;

        }



        node = that.trie;

        chars = token.split('');



        while (node && (ch = chars.shift())) {

          node = node[CHILDREN][ch];

        }



        if (node && chars.length === 0) {

          ids = node[IDS].slice(0);

          matches = matches ? getIntersection(matches, ids) : ids;

        }



        // break early if we find out there are no possible matches

        else {

          matches = [];

          return false;

        }

      });



      return matches ?

        _.map(unique(matches), function(id) { return that.datums[id]; }) : [];

    },



    all: function all() {

      var values = [];



      for (var key in this.datums) {

        values.push(this.datums[key]);

      }



      return values;

    },



    reset: function reset() {

      this.datums = {};

      this.trie = newNode();

    },



    serialize: function serialize() {

      return { datums: this.datums, trie: this.trie };

    }

  });



  return SearchIndex;



  // helper functions

  // ----------------



  function normalizeTokens(tokens) {

   // filter out falsy tokens

    tokens = _.filter(tokens, function(token) { return !!token; });



    // normalize tokens

    tokens = _.map(tokens, function(token) { return token.toLowerCase(); });



    return tokens;

  }



  function newNode() {

    var node = {};



    node[IDS] = [];

    node[CHILDREN] = {};



    return node;

  }



  function unique(array) {

    var seen = {}, uniques = [];



    for (var i = 0, len = array.length; i < len; i++) {

      if (!seen[array[i]]) {

        seen[array[i]] = true;

        uniques.push(array[i]);

      }

    }



    return uniques;

  }



  function getIntersection(arrayA, arrayB) {

    var ai = 0, bi = 0, intersection = [];



    arrayA = arrayA.sort();

    arrayB = arrayB.sort();



    var lenArrayA = arrayA.length, lenArrayB = arrayB.length;



    while (ai < lenArrayA && bi < lenArrayB) {

      if (arrayA[ai] < arrayB[bi]) {

        ai++;

      }



      else if (arrayA[ai] > arrayB[bi]) {

        bi++;

      }



      else {

        intersection.push(arrayA[ai]);

        ai++;

        bi++;

      }

    }



    return intersection;

  }

})();

