Basic string search, match and replace.

# Basic string search, match and replace.
module string_search

import abstract_text

# Patterns are abstract string motifs (include `String` and `Char`).
interface Pattern
	# Search `self` into `s` from a certain position.
	# Return the position of the first character of the matching section.
	# Return -1 if not found.
	#
	#     assert 'l'.search_index_in("hello world", 0)  == 2
	#     assert 'l'.search_index_in("hello world", 3)  == 3
	#     assert 'z'.search_index_in("hello world", 0)  == -1
	#
	# This method is usually faster than `search_in` if what is
	# required is only the index.
	# Note: in most implementation, `search_in` is implemented with this method.
	protected fun search_index_in(s: Text, from: Int): Int is abstract

	# Search `self` into `s` from a certain position.
	# Return null if not found.
	#
	#     assert 'l'.search_in("hello world", 0).from  == 2
	#     assert 'l'.search_in("hello world", 3).from  == 3
	#     assert 'z'.search_in("hello world", 0)       == null
	#
	# If only the index of the first character if required, see `search_index_in`.
	#
	# Note: Is used by `String::search`, `String::search_from`, and others.
	protected fun search_in(s: Text, from: Int): nullable Match is abstract

	# Search all `self` occurrences into `s`.
	#
	#     assert 'l'.search_all_in("hello world").length  == 3
	#     assert 'z'.search_all_in("hello world").length  == 0
	#
	# Note: Is used by `String::search_all`.
	protected fun search_all_in(s: Text): Array[Match]
	do
		var res = new Array[Match] # Result
		var match = search_in(s, 0)
		while match != null do
			res.add(match)
			match = search_in(s, match.after)
		end
		return res
	end

	# Split `s` using `self` is separator.
	#
	# Returns an array of matches that are between each occurence of `self`.
	# If self is not present, an array with a single match on `s` is retunred.
	#
	#     assert 'l'.split_in("hello world").join("|")  == "he||o wor|d"
	#     assert 'z'.split_in("hello world").join("|")  == "hello world"
	#
	# Note: is used by `String::split`
	protected fun split_in(s: Text): Array[Match]
	do
		var res = new Array[Match] # Result
		var i = 0 # Cursor
		var match = search_in(s, 0)
		while match != null do
			# Compute the splited part length
			var len = match.from - i
			res.add(new Match(s.to_s, i, len))
			i = match.after
			match = search_in(s, i)
		end
		# Add the last part
		res.add(new Match(s.to_s, i, s.length - i))
		return res
	end

	# Is `self` in `s`?
	protected fun is_in(s: Text): Bool do return search_index_in(s, 0) != -1
end

# BM_Pattern are pre-compiled string motif for the Boyer-Moore algorithm.
# (cf. A Fast String Searching Algorithm, with R.S. Boyer.  Communications
# of the Association for Computing Machinery, 20(10), 1977, pp. 762-772.)
# http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/index.html
#
#     var pat = new BM_Pattern("hello")
#     assert "I say hello to the world!".search(pat).from  == 6
#     assert "I say goodbye to the world!".search(pat)     == null
class BM_Pattern
	super Pattern

	redef fun to_s do return _motif

	# boyer-moore search gives the position of the first occurrence of a pattern starting at position `from`
	redef fun search_index_in(s, from)
	do
		assert from >= 0
		var n = s.length
		var m = _length

		var j = from
		while j < n - m + 1 do
			var i = m - 1 # Cursor in the pattern
			while i >= 0 and _motif[i] == s[i + j] do i -= 1
			if i < 0 then
				return j
			else
				var gs = _gs[i] # Good shift
				var bc = bc(s[i+j]) - m + 1 + i # Bad char
				# Both are true, do move to the best
				if gs > bc then
					j += gs
				else
					j += bc
				end
			end
		end
		return -1 # found nothing
	end

	# boyer-moore search. Return null if not found
	redef fun search_in(s, from)
	do
		var to = search_index_in(s, from)
		if to < 0 then
			return null
		else
			return new Match(s.to_s, to, _length)
		end
	end

	init
	do
		_length = _motif.length
		_gs = new Array[Int].with_capacity(_length)
		compute_gs
		compute_bc
	end

	# searched motif
	private var motif: String

	# length of the motif
	private var length: Int is noinit

	private fun bc(e: Char): Int
	do
		if _bc_table.has_key(e) then
			return _bc_table[e]
		else
			return _length
		end
	end

	# good shifts
	private var gs: Array[Int] is noinit

	# bad characters
	private var bc_table = new ArrayMap[Char, Int]

	private fun compute_bc
	do
		var x = _motif
		var m = _length
		var i = 0
		while i < m - 1 do
			_bc_table[x.chars[i]] = m - i - 1
			i += 1
		end
	end

	private fun suffixes: Array[Int]
	do
		var x = _motif
		var m = _length
		var suff = new Array[Int].filled_with(m, m)

		var f = 0
		var g = m - 1
		var i = m - 2
		while i >= 0 do
			if i > g and suff[i+m-1-f] < i - g then
				suff[i] = suff[i+m-1-f]
			else
				if i < g then g = i
				f = i
				while g >= 0 and x.chars[g] == x.chars[g + m - 1 - f] do g -= 1
				suff[i] = f - g
			end
			i -= 1
		end
		return suff
	end

	private fun compute_gs
	do
		var m = _length
		var suff = suffixes
		var i = 0
		while i < m do
			_gs[i] = m
			i += 1
		end
		var j = 0
		i = m - 1
		while i >= -1 do
			if i == -1 or suff[i] == i + 1 then
				while j < m - 1 - i do
					if _gs[j] == m then _gs[j] = m - 1 - i
					j += 1
				end
			end
			i -= 1
		end
		i = 0
		while i < m - 1 do
			_gs[m - 1 - suff[i]] = m - 1 - i
			i += 1
		end
	end

	redef fun hash do return _motif.hash
	redef fun ==(o) do return o isa BM_Pattern and o._motif == _motif
end

# Matches are a part of a `Text` found by a `Pattern`.
class Match
	# The base string matched
	#
	# ~~~
	# var m = "hello world".search("lo")
	# assert m.string == "hello world"
	# ~~~
	var string: String

	# The starting position in the string
	#
	# ~~~
	# var m = "hello world".search("lo")
	# assert m.from == 3
	# ~~~
	var from: Int

	# The length of the matching part
	#
	# ~~~
	# var m = "hello world".search("lo")
	# assert m.length == 2
	# ~~~
	var length: Int

	# The position of the first character just after the matching part.
	# May be out of the base string
	#
	# ~~~
	# var m = "hello world".search("lo")
	# assert m.after == 5
	# ~~~
	fun after: Int do return from + length

	# The contents of the matching part
	#
	# ~~~
	# var m = "hello world".search("lo")
	# assert m.to_s == "lo"
	# ~~~
	redef fun to_s do return string.substring(from,length)

	# The content of `string` before the match
	#
	# ~~~
	# var m = "hello world".search("lo")
	# assert m.text_before == "hel"
	# ~~~
	fun text_before: String do return string.substring(0, from)

	# The content of `string` after the match
	#
	# ~~~
	# var m = "hello world".search("lo")
	# assert m.text_after == " world"
	# ~~~
	fun text_after: String do return string.substring_from(after)

	init
	do
		assert positive_length: length >= 0
		assert valid_from: from >= 0
		assert valid_after: from + length <= string.length
	end
end

redef class Char
	super Pattern

	redef fun search_index_in(s, from)
	do
		var stop = s.length
		while from < stop do
			if s[from] == self then return from
			from += 1
		end
		return -1
	end

	redef fun search_in(s, from)
	do
		var pos = search_index_in(s, from)
		if pos < 0 then
			return null
		else
			return new Match(s.to_s, pos, 1)
		end
	end
end

redef class Text
	super Pattern

	redef fun search_index_in(s, from)
	do
		assert from >= 0
		var stop = s.length - length + 1
		while from < stop do
			var i = length - 1
			while i >= 0 and self[i] == s[i + from] do i -= 1
			# Test if we found
			if i < 0 then return from
			# Not found so try next one
			from += 1
		end
		return -1
	end

	redef fun search_in(s, from)
	do
		var pos = search_index_in(s, from)
		if pos < 0 then
			return null
		else
			return new Match(s.to_s, pos, length)
		end
	end

	# Search the first occurence of `pattern`.
	# Return null if not found.
	#
	#     assert "I say hello to the world!".search("hello").from  == 6
	#     assert "I say goodbye to the world!".search("hello")     == null
	fun search(pattern: Pattern): nullable Match do return pattern.search_in(self, 0)

	# Search the first occurence of `pattern` after `from`.
	# The search starts at `from`.
	# Return null if not found.
	#
	#     assert "I say hello to the world!".search_from("hello",4).from  == 6
	#     assert "I say hello to the world!".search_from("hello",7)       == null
	fun search_from(pattern: Pattern, from: Int): nullable Match do return pattern.search_in(self, from)

	# Search the last occurence of the text `t`.
	#
	#     assert "bob".search_last("b").from == 2
	#     assert "bob".search_last("bo").from == 0
	#     assert "bob".search_last("ob").from == 1
	#     assert "bobob".search_last("ob").from == 3
	#     assert "bobbob".search_last("bb").from == 2
	#     assert "bobbob".search_last("bob").from == 3
	#     assert "bob".search_last("z") == null
	#     assert "".search_last("b") == null
	fun search_last(t: Text): nullable Match do
		return search_last_up_to(t, length)
	end

	# Search the last occurence of the text `t` before `up_to`.
	#
	#     assert "bobbob".search_last_up_to("b", 3).from == 2
	#     assert "bobbob".search_last_up_to("b", 6).from == 5
	#     assert "bobbob".search_last_up_to("b", 0) == null
	fun search_last_up_to(t: Text, up_to: Int): nullable Match do
		var i = up_to - t.length

		while i >= 0 do
			if substring(i, t.length) == t then
				return new Match(self.to_s, i, t.length)
			end
			i -= 1
		end
		return null
	end

	# Extract a given prefix, if any.
	#
	# ~~~
	# var p = "hello world".prefix("hello")
	# assert p != null
	# assert p.text_after == " world"
	# ~~~
	fun prefix(t: Text): nullable Match do
		var len = t.length
		if substring(0, len) == t then
			return new Match(self.to_s, 0, len)
		end
		return null
	end

	# Extract a given suffix, if any.
	#
	# ~~~
	# var p = "hello world".suffix("world")
	# assert p != null
	# assert p.text_before == "hello "
	# ~~~
	fun suffix(t: Text): nullable Match do
		var len = t.length
		var from = length - len
		if substring(from, len) == t then
			return new Match(self.to_s, from, len)
		end
		return null
	end

	# Search all occurrences of `pattern` into self.
	#
	#     var a = new Array[Int]
	#     for i in "hello world".search_all('o') do
	#         a.add(i.from)
	#     end
	#     assert a         ==  [4, 7]
	fun search_all(pattern: Pattern): Array[Match] do return pattern.search_all_in(self)

	# Split `self` using `pattern` as separator.
	#
	#     assert "hello world".split('o')          ==  ["hell", " w", "rld"]
	fun split(pattern: Pattern): Array[String]
	do
		var matches = pattern.split_in(self)
		var res = new Array[String].with_capacity(matches.length)
		for m in matches do res.add(m.to_s)
		return res
	end

	# @deprecated alias for `split`
	fun split_with(pattern: Pattern): Array[String] do return self.split(pattern)

	# Split `self` on the first occurence of `pattern`
	#
	#     assert "hello".split_once_on('l') == ["he", "lo"]
	#     assert "a, b, c, d, e".split_once_on(", ") == ["a", "b, c, d, e"]
	fun split_once_on(pattern: Pattern): Array[SELFTYPE]
	do
		var m = pattern.search_in(self, 0)
		var res = new Array[SELFTYPE]
		if m == null then
			res.add self
		else
			res.add substring(0, m.from)
			res.add substring_from(m.after)
		end
		return res
	end

	# Replace all occurrences of `pattern` with `string`
	#
	#     assert "hlelo".replace("le", "el") == "hello"
	#     assert "hello".replace('l', "")    == "heo"
	#
	#     var t: Text = "hello"
	#     assert t.replace("hello", new FlatBuffer) == ""
	fun replace(pattern: Pattern, string: Text): String
	do
		return self.split_with(pattern).join(string)
	end

	# Replace the first occurrence of `pattern` with `string`
	#
	#     assert "hlelo".replace_first("le", "el") == "hello"
	#     assert "hello".replace_first('l', "")    == "helo"
	fun replace_first(pattern: Pattern, string: Text): String
	do
		return self.split_once_on(pattern).join(string)
	end

	# Does `self` contains at least one instance of `pattern`?
	#
	#     assert "hello".has('l')
	#     assert "hello".has("ll")
	#     assert not "hello".has("lll")
	fun has(pattern: Pattern): Bool do return pattern.is_in(self)

	# Returns a copy of `self` minus all occurences of `pattern`
	#
	#     assert "__init__".remove_all('_') == "init"
	#     assert "abcd".remove_all("bc") == "ad"
	#     assert "abcd".remove_all("[ad]".to_re) == "bc"
	fun remove_all(pattern: Pattern): String do return split(pattern).join
end

lib/core/text/string_search.nit:13,1--507,3

module string_search

Summary

Basic string search, match and replace.

Introduced classes

BM_Pattern

Match

Pattern

Redefined classes

Char

Text

Basic string search, match and replace.

Introduced classes

class BM_Pattern

class Match

interface Pattern

Redefined classes

redef enum Char

redef abstract class Text

Summary

All class definitions

BM_Pattern

Char

Match

Pattern

Text

All class definitions

class BM_Pattern

redef enum Char

class Match

interface Pattern

redef abstract class Text

Summary

Ancestors

abstract_collection

array

circular_array

collection

fixed_ints

hash_collection

kernel

list

math

native

range

sorter

union_find

Parents

abstract_text

Children

fixed_ints_text

Descendants

a_star

a_star-m

abstract_tree

activities

actors

agent_simulation

ai

all

android

android19

angles

api

app

app

app_base

app_kit

array_debug

assets

assets

assets

assets_and_resources

at_boot

attributes

attributes_impl

audio

audio

audio

audio

aware