arraymatcher.js 6.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212
  1. // Copyright 2006 The Closure Library Authors. All Rights Reserved.
  2. //
  3. // Licensed under the Apache License, Version 2.0 (the "License");
  4. // you may not use this file except in compliance with the License.
  5. // You may obtain a copy of the License at
  6. //
  7. // http://www.apache.org/licenses/LICENSE-2.0
  8. //
  9. // Unless required by applicable law or agreed to in writing, software
  10. // distributed under the License is distributed on an "AS-IS" BASIS,
  11. // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12. // See the License for the specific language governing permissions and
  13. // limitations under the License.
  14. /**
  15. * @fileoverview Basic class for matching words in an array.
  16. *
  17. */
  18. goog.provide('goog.ui.ac.ArrayMatcher');
  19. goog.require('goog.string');
  20. /**
  21. * Basic class for matching words in an array
  22. * @constructor
  23. * @param {Array<?>} rows Dictionary of items to match. Can be objects if they
  24. * have a toString method that returns the value to match against.
  25. * @param {boolean=} opt_noSimilar if true, do not do similarity matches for the
  26. * input token against the dictionary.
  27. */
  28. goog.ui.ac.ArrayMatcher = function(rows, opt_noSimilar) {
  29. this.rows_ = rows || [];
  30. this.useSimilar_ = !opt_noSimilar;
  31. };
  32. /**
  33. * Replaces the rows that this object searches over.
  34. * @param {Array<?>} rows Dictionary of items to match.
  35. */
  36. goog.ui.ac.ArrayMatcher.prototype.setRows = function(rows) {
  37. this.rows_ = rows || [];
  38. };
  39. /**
  40. * Function used to pass matches to the autocomplete
  41. * @param {string} token Token to match.
  42. * @param {number} maxMatches Max number of matches to return.
  43. * @param {Function} matchHandler callback to execute after matching.
  44. * @param {string=} opt_fullString The full string from the input box.
  45. */
  46. goog.ui.ac.ArrayMatcher.prototype.requestMatchingRows = function(
  47. token, maxMatches, matchHandler, opt_fullString) {
  48. var matches = this.useSimilar_ ?
  49. goog.ui.ac.ArrayMatcher.getMatchesForRows(token, maxMatches, this.rows_) :
  50. this.getPrefixMatches(token, maxMatches);
  51. matchHandler(token, matches);
  52. };
  53. /**
  54. * Matches the token against the specified rows, first looking for prefix
  55. * matches and if that fails, then looking for similar matches.
  56. *
  57. * @param {string} token Token to match.
  58. * @param {number} maxMatches Max number of matches to return.
  59. * @param {!Array<?>} rows Rows to search for matches. Can be objects if they
  60. * have a toString method that returns the value to match against.
  61. * @return {!Array<?>} Rows that match.
  62. */
  63. goog.ui.ac.ArrayMatcher.getMatchesForRows = function(token, maxMatches, rows) {
  64. var matches =
  65. goog.ui.ac.ArrayMatcher.getPrefixMatchesForRows(token, maxMatches, rows);
  66. if (matches.length == 0) {
  67. matches = goog.ui.ac.ArrayMatcher.getSimilarMatchesForRows(
  68. token, maxMatches, rows);
  69. }
  70. return matches;
  71. };
  72. /**
  73. * Matches the token against the start of words in the row.
  74. * @param {string} token Token to match.
  75. * @param {number} maxMatches Max number of matches to return.
  76. * @return {!Array<?>} Rows that match.
  77. */
  78. goog.ui.ac.ArrayMatcher.prototype.getPrefixMatches = function(
  79. token, maxMatches) {
  80. return goog.ui.ac.ArrayMatcher.getPrefixMatchesForRows(
  81. token, maxMatches, this.rows_);
  82. };
  83. /**
  84. * Matches the token against the start of words in the row.
  85. * @param {string} token Token to match.
  86. * @param {number} maxMatches Max number of matches to return.
  87. * @param {!Array<?>} rows Rows to search for matches. Can be objects if they
  88. * have
  89. * a toString method that returns the value to match against.
  90. * @return {!Array<?>} Rows that match.
  91. */
  92. goog.ui.ac.ArrayMatcher.getPrefixMatchesForRows = function(
  93. token, maxMatches, rows) {
  94. var matches = [];
  95. if (token != '') {
  96. var escapedToken = goog.string.regExpEscape(token);
  97. var matcher = new RegExp('(^|\\W+)' + escapedToken, 'i');
  98. for (var i = 0; i < rows.length && matches.length < maxMatches; i++) {
  99. var row = rows[i];
  100. if (String(row).match(matcher)) {
  101. matches.push(row);
  102. }
  103. }
  104. }
  105. return matches;
  106. };
  107. /**
  108. * Matches the token against similar rows, by calculating "distance" between the
  109. * terms.
  110. * @param {string} token Token to match.
  111. * @param {number} maxMatches Max number of matches to return.
  112. * @return {!Array<?>} The best maxMatches rows.
  113. */
  114. goog.ui.ac.ArrayMatcher.prototype.getSimilarRows = function(token, maxMatches) {
  115. return goog.ui.ac.ArrayMatcher.getSimilarMatchesForRows(
  116. token, maxMatches, this.rows_);
  117. };
  118. /**
  119. * Matches the token against similar rows, by calculating "distance" between the
  120. * terms.
  121. * @param {string} token Token to match.
  122. * @param {number} maxMatches Max number of matches to return.
  123. * @param {!Array<?>} rows Rows to search for matches. Can be objects
  124. * if they have a toString method that returns the value to
  125. * match against.
  126. * @return {!Array<?>} The best maxMatches rows.
  127. */
  128. goog.ui.ac.ArrayMatcher.getSimilarMatchesForRows = function(
  129. token, maxMatches, rows) {
  130. var results = [];
  131. for (var index = 0; index < rows.length; index++) {
  132. var row = rows[index];
  133. var str = token.toLowerCase();
  134. var txt = String(row).toLowerCase();
  135. var score = 0;
  136. if (txt.indexOf(str) != -1) {
  137. score = parseInt((txt.indexOf(str) / 4).toString(), 10);
  138. } else {
  139. var arr = str.split('');
  140. var lastPos = -1;
  141. var penalty = 10;
  142. for (var i = 0, c; c = arr[i]; i++) {
  143. var pos = txt.indexOf(c);
  144. if (pos > lastPos) {
  145. var diff = pos - lastPos - 1;
  146. if (diff > penalty - 5) {
  147. diff = penalty - 5;
  148. }
  149. score += diff;
  150. lastPos = pos;
  151. } else {
  152. score += penalty;
  153. penalty += 5;
  154. }
  155. }
  156. }
  157. if (score < str.length * 6) {
  158. results.push({str: row, score: score, index: index});
  159. }
  160. }
  161. results.sort(function(a, b) {
  162. var diff = a.score - b.score;
  163. if (diff != 0) {
  164. return diff;
  165. }
  166. return a.index - b.index;
  167. });
  168. var matches = [];
  169. for (var i = 0; i < maxMatches && i < results.length; i++) {
  170. matches.push(results[i].str);
  171. }
  172. return matches;
  173. };