[m-dev.] For review: improvements to string.m

[Ralph Becket]

Estimated hours taken: 

Fixed some inefficiencies in the string module.

library/string.m:
	The following previously made use of string__first_char/3
	which is heinously inefficient in most cases:
		string__base_string_to_int/3
		string__is_alpha/1
		string__is_alpha_or_underscore/1
		string__is_alnum_or_underscore/1
		string__duplicate_char/3
	I have recoded them to use string__foldl/5 or a new predicate,
	string__all_match/2, or string__from_char_list/2, which should
	be far more economical.

	I have also added the following functions:
		string__det_string_to_int/1
		string__det_base_string_to_int/2
	the former using 10 as the base.

Index: string.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/string.m,v
retrieving revision 1.130
diff -u -r1.130 string.m
--- string.m	2000/09/14 15:24:44	1.130
+++ string.m	2000/09/18 13:53:20
@@ -452,34 +452,34 @@
 string__to_int(String, Int) :-
 	string__base_string_to_int(10, String, Int).
 
+
+
+:- type int_acc
+	--->	nil			% Haven't accumulated anything yet
+	;	acc(int, int).		% Sign, NumSoFar
+
 string__base_string_to_int(Base, String, Int) :-
-	( string__first_char(String, Char, String1) ->
-		( Char = ('-') ->
-			string__base_string_to_int_2(Base, String1, 0,
Int1),
-			Int is 0 - Int1
-		; Char = ('+') ->
-			string__base_string_to_int_2(Base, String1, 0, Int)
-		;
-			string__base_string_to_int_2(Base, String, 0, Int)
-		)
-	;
-		Int = 0
-	).
+	string__foldl(base_string_to_int_2(Base), String, nil, acc(Sign,
Int0)),
+	Int = Sign * Int0.
 
-:- pred string__base_string_to_int_2(int, string, int, int).
-:- mode string__base_string_to_int_2(in, in, in, out) is semidet.
+:- pred base_string_to_int_2(int, char, int_acc, int_acc).
+:- mode base_string_to_int_2(in, in, in, out) is semidet.
 
-string__base_string_to_int_2(Base, String, Int0, Int) :-
-	( string__first_char(String, DigitChar, String1) ->
-		char__digit_to_int(DigitChar, DigitValue),
-		DigitValue < Base,
-		Int1 is Base * Int0,
-		Int2 is Int1 + DigitValue,
-		string__base_string_to_int_2(Base, String1, Int2, Int) 
-	;
-		Int = Int0
+base_string_to_int_2(Base, Char, nil, acc(Sign, N)) :-
+	(      if Char = ('-') then
+		Sign = -1, N = 0
+	  else if Char = ('+') then
+		Sign =  1, N = 0
+	  else
+	  	Sign =  1, char__digit_to_int(Char, N), N < Base
 	).
 
+base_string_to_int_2(Base, Char, acc(Sign, N), acc(Sign, (Base * N) + M))
:-
+	char__digit_to_int(Char, M),
+	M < Base.
+
+
+
 string__index_det(String, Int, Char) :-
 	( string__index(String, Int, Char0) ->
 		Char = Char0
@@ -749,30 +749,38 @@
 		S = S0
 	).
 
-string__is_alpha(S) :-
-	( string__first_char(S, C, S1) ->
-		char__is_alpha(C),
-		string__is_alpha(S1)
-	;
-		true
+
+
+:- pred string__all_match(pred(char), string).
+:- mode string__all_match(pred(in) is semidet, in) is semidet.
+
+string__all_match(P, String) :-
+	all_match_2(string__length(String) - 1, P, String).
+
+:- pred all_match_2(int, pred(char), string).
+:- mode all_match_2(in, pred(in) is semidet, in) is semidet.
+
+string__all_match_2(I, P, String) :-
+	( if I >= 0 then
+		P(string__unsafe_index(String, I)),
+		string__all_match_2(I - 1, P, String)
+	  else
+	  	true
 	).
 
+
+
+string__is_alpha(S) :-
+	string__all_match(char__is_alpha, S).
+
 string__is_alpha_or_underscore(S) :-
-	( string__first_char(S, C, S1) ->
-		char__is_alpha_or_underscore(C),
-		string__is_alpha_or_underscore(S1)
-	;
-		true
-	).
+	string__all_match(char__is_alpha_or_underscore, S).
 
 string__is_alnum_or_underscore(S) :-
-	( string__first_char(S, C, S1) ->
-		char__is_alnum_or_underscore(C),
-		string__is_alnum_or_underscore(S1)
-	;
-		true
-	).
+	string__all_match(char__is_alnum_or_underscore, S).
+
 
+
 string__pad_left(String0, PadChar, Width, String) :-
 	string__length(String0, Length),
 	( Length < Width ->
@@ -794,13 +802,7 @@
 	).
 
 string__duplicate_char(Char, Count, String) :-
-	( Count =< 0 ->
-		String = ""
-	;
-		Count1 is Count - 1,
-		string__first_char(String, Char, String1),
-		string__duplicate_char(Char, Count1, String1)
-	).
+	String = string__from_char_list(list__duplicate(Count, Char)).
 
 
%---------------------------------------------------------------------------
--%
 
@@ -1765,6 +1767,12 @@
 
 :- func string__format(string, list(string__poly_type)) = string.
 
+	% Convert a base 10 string to an int.
+	%
+:- func string__det_string_to_int(string) = int.
+
+:- func string__det_base_string_to_int(int, string) = int.
+
 %
----------------------------------------------------------------------------
%
 %
----------------------------------------------------------------------------
%
 
@@ -1896,6 +1904,18 @@
 S1 ++ S2 = string__append(S1, S2).
 
 %
----------------------------------------------------------------------------
%
+
+string__det_string_to_int(S) = string__det_base_string_to_int(10, S).
+
+%
----------------------------------------------------------------------------
%
+
+string__det_base_string_to_int(Base, S) = N :-
+	( if string__base_string_to_int(Base, S, N0) then
+		N = N0
+	  else
+	  	error("string__det_base_string_to_int/2: conversion failed")
+	).
+
 %
----------------------------------------------------------------------------
%
 
 :- end_module string.

--
Ralph Becket      |      MSR Cambridge      |      rbeck at microsoft.com 
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------