(function(){

  function SearchCursor(cm, query, pos, caseFold) {

    this.atOccurrence = false; this.cm = cm;

    if (caseFold == null && typeof query == "string") caseFold = false;



    pos = pos ? cm.clipPos(pos) : {line: 0, ch: 0};

    this.pos = {from: pos, to: pos};



    // The matches method is filled in based on the type of query.

    // It takes a position and a direction, and returns an object

    // describing the next occurrence of the query, or null if no

    // more matches were found.

    if (typeof query != "string") { // Regexp match

      if (!query.global) query = new RegExp(query.source, query.ignoreCase ? "ig" : "g");

      this.matches = function(reverse, pos) {

        if (reverse) {

          query.lastIndex = 0;

          var line = cm.getLine(pos.line).slice(0, pos.ch), match = query.exec(line), start = 0;

          while (match) {

            start += match.index + 1;

	    line = line.slice(start);

            query.lastIndex = 0;

            var newmatch = query.exec(line);

            if (newmatch) match = newmatch;

            else break;

          }

          start--;

        } else {

          query.lastIndex = pos.ch;

          var line = cm.getLine(pos.line), match = query.exec(line),

          start = match && match.index;

        }

        if (match)

          return {from: {line: pos.line, ch: start},

                  to: {line: pos.line, ch: start + match[0].length},

                  match: match};

      };

    } else { // String query

      if (caseFold) query = query.toLowerCase();

      var fold = caseFold ? function(str){return str.toLowerCase();} : function(str){return str;};

      var target = query.split("\n");

      // Different methods for single-line and multi-line queries

      if (target.length == 1)

        this.matches = function(reverse, pos) {

          var line = fold(cm.getLine(pos.line)), len = query.length, match;

          if (reverse ? (pos.ch >= len && (match = line.lastIndexOf(query, pos.ch - len)) != -1)

              : (match = line.indexOf(query, pos.ch)) != -1)

            return {from: {line: pos.line, ch: match},

                    to: {line: pos.line, ch: match + len}};

        };

      else

        this.matches = function(reverse, pos) {

          var ln = pos.line, idx = (reverse ? target.length - 1 : 0), match = target[idx], line = fold(cm.getLine(ln));

          var offsetA = (reverse ? line.indexOf(match) + match.length : line.lastIndexOf(match));

          if (reverse ? offsetA >= pos.ch || offsetA != match.length

              : offsetA <= pos.ch || offsetA != line.length - match.length)

            return;

          for (;;) {

            if (reverse ? !ln : ln == cm.lineCount() - 1) return;

            line = fold(cm.getLine(ln += reverse ? -1 : 1));

            match = target[reverse ? --idx : ++idx];

            if (idx > 0 && idx < target.length - 1) {

              if (line != match) return;

              else continue;

            }

            var offsetB = (reverse ? line.lastIndexOf(match) : line.indexOf(match) + match.length);

            if (reverse ? offsetB != line.length - match.length : offsetB != match.length)

              return;

            var start = {line: pos.line, ch: offsetA}, end = {line: ln, ch: offsetB};

            return {from: reverse ? end : start, to: reverse ? start : end};

          }

        };

    }

  }



  SearchCursor.prototype = {

    findNext: function() {return this.find(false);},

    findPrevious: function() {return this.find(true);},



    find: function(reverse) {

      var self = this, pos = this.cm.clipPos(reverse ? this.pos.from : this.pos.to);

      function savePosAndFail(line) {

        var pos = {line: line, ch: 0};

        self.pos = {from: pos, to: pos};

        self.atOccurrence = false;

        return false;

      }



      for (;;) {

        if (this.pos = this.matches(reverse, pos)) {

          this.atOccurrence = true;

          return this.pos.match || true;

        }

        if (reverse) {

          if (!pos.line) return savePosAndFail(0);

          pos = {line: pos.line-1, ch: this.cm.getLine(pos.line-1).length};

        }

        else {

          var maxLine = this.cm.lineCount();

          if (pos.line == maxLine - 1) return savePosAndFail(maxLine);

          pos = {line: pos.line+1, ch: 0};

        }

      }

    },



    from: function() {if (this.atOccurrence) return this.pos.from;},

    to: function() {if (this.atOccurrence) return this.pos.to;},



    replace: function(newText) {

      var self = this;

      if (this.atOccurrence)

        self.pos.to = this.cm.replaceRange(newText, self.pos.from, self.pos.to);

    }

  };



  CodeMirror.defineExtension("getSearchCursor", function(query, pos, caseFold) {

    return new SearchCursor(this, query, pos, caseFold);

  });

})();

