text: /* ***** BEGIN LICENSE BLOCK *****
   * Distributed under the BSD license:
   *
   * Copyright (c) 2010, Ajax.org B.V.
   * All rights reserved.
   * 
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions are met:
   *     * Redistributions of source code must retain the above copyright
   *       notice, this list of conditions and the following disclaimer.
   *     * Redistributions in binary form must reproduce the above copyright
   *       notice, this list of conditions and the following disclaimer in the
   *       documentation and/or other materials provided with the distribution.
   *     * Neither the name of Ajax.org B.V. nor the
   *       names of its contributors may be used to endorse or promote products
   *       derived from this software without specific prior written permission.
   * 
   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
   * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
   * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
   * DISCLAIMED. IN NO EVENT SHALL AJAX.ORG B.V. BE LIABLE FOR ANY
   * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
   * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
   * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
   * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   *
   * ***** END LICENSE BLOCK ***** */
  
  define(function(require, exports, module) {
  "use strict";
  
  var lang = require("./lib/lang");
  var oop = require("./lib/oop");
  var Range = require("./range").Range;
  
  /**
   * class Search
   *
   * A class designed to handle all sorts of text searches within a [[Document `Document`]].
   *
   **/
  
  /**
   * new Search()
   *
   * Creates a new `Search` object. The following search options are avaliable:
   *
   * * `needle`: The string or regular expression you're looking for
   * * `backwards`: Whether to search backwards from where cursor currently is. Defaults to `false`.
   * * `wrap`: Whether to wrap the search back to the beginning when it hits the end. Defaults to `false`.
   * * `caseSensitive`: Whether the search ought to be case-sensitive. Defaults to `false`.
   * * `wholeWord`: Whether the search matches only on whole words. Defaults to `false`.
   * * `range`: The [[Range]] to search within. Set this to `null` for the whole document
   * * `regExp`: Whether the search is a regular expression or not. Defaults to `false`.
   * * `start`: The starting [[Range]] or cursor position to begin the search
   * * `skipCurrent`: Whether or not to include the current line in the search. Default to `false`.
   *
  **/
  
  var Search = function() {
      this.$options = {};
  };
  
  (function() {
      /**
       * Search.set(options) -> Search
       * - options (Object): An object containing all the new search properties
       *
       * Sets the search options via the `options` parameter.
       *
      **/
      this.set = function(options) {
          oop.mixin(this.$options, options);
          return this;
      };
  
      /**
       * Search.getOptions() -> Object
       *
       * [Returns an object containing all the search options.]{: #Search.getOptions}
       *
      **/
      this.getOptions = function() {
          return lang.copyObject(this.$options);
      };
  
      this.setOptions = function(options) {
          this.$options = options;
      };
      /**
       * Search.find(session) -> Range
       * - session (EditSession): The session to search with
       *
       * Searches for `options.needle`. If found, this method returns the [[Range `Range`]] where the text first occurs. If `options.backwards` is `true`, the search goes backwards in the session.
       *
      **/
      this.find = function(session) {
          var iterator = this.$matchIterator(session, this.$options);
  
          if (!iterator)
              return false;
  
          var firstRange = null;
          iterator.forEach(function(range, row, offset) {
              if (!range.start) {
                  var column = range.offset + (offset || 0);
                  firstRange = new Range(row, column, row, column+range.length);
              } else
                  firstRange = range;
              return true;
          });
  
          return firstRange;
      };
  
      /**
       * Search.findAll(session) -> [Range]
       * - session (EditSession): The session to search with
       *
       * Searches for all occurances `options.needle`. If found, this method returns an array of [[Range `Range`s]] where the text first occurs. If `options.backwards` is `true`, the search goes backwards in the session.
       *
      **/
      this.findAll = function(session) {
          var options = this.$options;
          if (!options.needle)
              return [];
          this.$assembleRegExp(options);
  
          var range = options.range;
          var lines = range
              ? session.getLines(range.start.row, range.end.row)
              : session.doc.getAllLines();
  
          var ranges = [];
          var re = options.re;
          if (options.$isMultiLine) {
              var len = re.length;
              var maxRow = lines.length - len;
              for (var row = re.offset || 0; row <= maxRow; row++) {
                  for (var j = 0; j < len; j++)
                      if (lines[row + j].search(re[j]) == -1)
                          break;
                  
                  var startLine = lines[row];
                  var line = lines[row + len - 1];
                  var startIndex = startLine.match(re[0])[0].length;
                  var endIndex = line.match(re[len - 1])[0].length;
  
                  ranges.push(new Range(
                      row, startLine.length - startIndex,
                      row + len - 1, endIndex
                  ));
              }
          } else {
              for (var i = 0; i < lines.length; i++) {
                  var matches = lang.getMatchOffsets(lines[i], re);
                  for (var j = 0; j < matches.length; j++) {
                      var match = matches[j];
                      ranges.push(new Range(i, match.offset, i, match.offset + match.length));
                  }
              }
          }
  
          if (range) {
              var startColumn = range.start.column;
              var endColumn = range.start.column;
              var i = 0, j = ranges.length - 1;
              while (i < j && ranges[i].start.column < startColumn && ranges[i].start.row == range.start.row)
                  i++;
  
              while (i < j && ranges[j].end.column > endColumn && ranges[j].end.row == range.end.row)
                  j--;
              return ranges.slice(i, j + 1);
          }
  
          return ranges;
      };
  
      /**
       * Search.replace(input, replacement) -> String
       * - input (String): The text to search in
       * - replacement (String): The replacing text
       * + (String): If `options.regExp` is `true`, this function returns `input` with the replacement already made. Otherwise, this function just returns `replacement`.<br/>
       * If `options.needle` was not found, this function returns `null`.
       *
       * Searches for `options.needle` in `input`, and, if found, replaces it with `replacement`.
       *
      **/
      this.replace = function(input, replacement) {
          var options = this.$options;
  
          var re = this.$assembleRegExp(options);
          if (options.$isMultiLine)
              return replacement;
  
          if (!re)
              return;
  
          var match = re.exec(input);
          if (!match || match[0].length != input.length)
              return null;
          
          replacement = input.replace(re, replacement);
          if (options.preserveCase) {
              replacement = replacement.split("");
              for (var i = Math.min(input.length, input.length); i--; ) {
                  var ch = input[i];
                  if (ch && ch.toLowerCase() != ch)
                      replacement[i] = replacement[i].toUpperCase();
                  else
                      replacement[i] = replacement[i].toLowerCase();
              }
              replacement = replacement.join("");
          }
          
          return replacement;
      };
  
      /** internal, hide
       * Search.$matchIterator(session) -> String | Boolean
       * - session (EditSession): The session to search with
       *
      **/
      this.$matchIterator = function(session, options) {
          var re = this.$assembleRegExp(options);
          if (!re)
              return false;
  
          var self = this, callback, backwards = options.backwards;
  
          if (options.$isMultiLine) {
              var len = re.length;
              var matchIterator = function(line, row, offset) {
                  var startIndex = line.search(re[0]);
                  if (startIndex == -1)
                      return;
                  for (var i = 1; i < len; i++) {
                      line = session.getLine(row + i);
                      if (line.search(re[i]) == -1)
                          return;
                  }
  
                  var endIndex = line.match(re[len - 1])[0].length;
  
                  var range = new Range(row, startIndex, row + len - 1, endIndex);
                  if (re.offset == 1) {
                      range.start.row--;
                      range.start.column = Number.MAX_VALUE;
                  } else if (offset)
                      range.start.column += offset;
  
                  if (callback(range))
                      return true;
              };
          } else if (backwards) {
              var matchIterator = function(line, row, startIndex) {
                  var matches = lang.getMatchOffsets(line, re);
                  for (var i = matches.length-1; i >= 0; i--)
                      if (callback(matches[i], row, startIndex))
                          return true;
              };
          } else {
              var matchIterator = function(line, row, startIndex) {
                  var matches = lang.getMatchOffsets(line, re);
                  for (var i = 0; i < matches.length; i++)
                      if (callback(matches[i], row, startIndex))
                          return true;
              };
          }
  
          return {
              forEach: function(_callback) {
                  callback = _callback;
                  self.$lineIterator(session, options).forEach(matchIterator);
              }
          };
      };
  
      this.$assembleRegExp = function(options) {
          if (options.needle instanceof RegExp)
              return options.re = options.needle;
  
          var needle = options.needle;
  
          if (!options.needle)
              return options.re = false;
  
          if (!options.regExp)
              needle = lang.escapeRegExp(needle);
  
          if (options.wholeWord)
              needle = "\\b" + needle + "\\b";
  
          var modifier = options.caseSensitive ? "g" : "gi";
  
          options.$isMultiLine = /[\n\r]/.test(needle);
          if (options.$isMultiLine)
              return options.re = this.$assembleMultilineRegExp(needle, modifier);
  
          try {
              var re = new RegExp(needle, modifier);
          } catch(e) {
              re = false;
          }
          return options.re = re;
      };
  
      this.$assembleMultilineRegExp = function(needle, modifier) {
          var parts = needle.replace(/\r\n|\r|\n/g, "$\n^").split("\n");
          var re = [];
          for (var i = 0; i < parts.length; i++) try {
              re.push(new RegExp(parts[i], modifier));
          } catch(e) {
              return false;
          }
          if (parts[0] == "") {
              re.shift();
              re.offset = 1;
          } else {
              re.offset = 0;
          }
          return re;
      };
  
      this.$lineIterator = function(session, options) {
          var backwards = options.backwards == true;
          var skipCurrent = options.skipCurrent != false;
  
          var range = options.range;
          var start = options.start;
          if (!start)
              start = range ? range[backwards ? "end" : "start"] : session.selection.getRange();
           
          if (start.start)
              start = start[skipCurrent != backwards ? "end" : "start"];
  
          var firstRow = range ? range.start.row : 0;
          var lastRow = range ? range.end.row : session.getLength() - 1;
  
          var forEach = backwards ? function(callback) {
                  var row = start.row;
  
                  var line = session.getLine(row).substring(0, start.column);
                  if (callback(line, row))
                      return;
  
                  for (row--; row >= firstRow; row--)
                      if (callback(session.getLine(row), row))
                          return;
  
                  if (options.wrap == false)
                      return;
  
                  for (row = lastRow, firstRow = start.row; row >= firstRow; row--)
                      if (callback(session.getLine(row), row))
                          return;
              } : function(callback) {
                  var row = start.row;
  
                  var line = session.getLine(row).substr(start.column);
                  if (callback(line, row, start.column))
                      return;
  
                  for (row = row+1; row <= lastRow; row++)
                      if (callback(session.getLine(row), row))
                          return;
  
                  if (options.wrap == false)
                      return;
  
                  for (row = firstRow, lastRow = start.row; row <= lastRow; row++)
                      if (callback(session.getLine(row), row))
                          return;
              };
          
          return {forEach: forEach};
      };
  
  }).call(Search.prototype);
  
  exports.Search = Search;
  });
  