%--------------------------------------------------% % vim: ft=mercury ts=4 sw=4 et %--------------------------------------------------% % Copyright (C) 1994-2011 The University of Melbourne. % This file may only be copied under the terms of the GNU Library General % Public License - see the file COPYING.LIB in the Mercury distribution. %--------------------------------------------------% % % File: int.m. % Main authors: conway, fjh. % Stability: medium. % % Predicates and functions for dealing with machine-size integer numbers. % % The behaviour of a computation for which overflow occurs is undefined. % (In the current implementation, the predicates and functions in this % module do not check for overflow, and the results you get are those % delivered by the C compiler. However, future implementations % might check for overflow.) % %--------------------------------------------------% %--------------------------------------------------% :- module int. :- interface. :- import_module array. :- import_module enum. :- import_module pretty_printer. %--------------------------------------------------% :- instance enum(int). %--------------------------------------------------% % Less than. % :- pred (int::in) < (int::in) is semidet. % Greater than. % :- pred (int::in) > (int::in) is semidet. % Less than or equal. % :- pred (int::in) =< (int::in) is semidet. % Greater than or equal. % :- pred (int::in) >= (int::in) is semidet. %--------------------------------------------------% % Absolute value. % :- func abs(int) = int. :- pred abs(int::in, int::out) is det. % Maximum. % :- func max(int, int) = int. :- pred max(int::in, int::in, int::out) is det. % Minimum. % :- func min(int, int) = int. :- pred min(int::in, int::in, int::out) is det. %--------------------------------------------------% % Unary plus. % :- func + (int::in) = (int::uo) is det. % Unary minus. % :- func - (int::in) = (int::uo) is det. % Addition. % :- func int + int = int. :- mode in + in = uo is det. :- mode uo + in = in is det. :- mode in + uo = in is det. :- func plus(int, int) = int. % Subtraction. % :- func int - int = int. :- mode in - in = uo is det. :- mode uo - in = in is det. :- mode in - uo = in is det. :- func minus(int, int) = int. % Multiplication. % :- func (int::in) * (int::in) = (int::uo) is det. :- func times(int, int) = int. % Flooring integer division. % Truncates towards minus infinity, e.g. (-10) div 3 = (-4). % % Throws a `math.domain_error' exception if the right operand is zero. % See the comments at the top of math.m to find out how to disable % domain checks. % :- func div(int::in, int::in) = (int::uo) is det. % Truncating integer division. % Truncates towards zero, e.g. (-10) // 3 = (-3). % `div' has nicer mathematical properties for negative operands, % but `//' is typically more efficient. % % Throws a `math.domain_error' exception if the right operand is zero. % See the comments at the top of math.m to find out how to disable % domain checks. % :- func (int::in) // (int::in) = (int::uo) is det. % (/)/2 is a synonym for (//)/2 to bring Mercury into line with % the common convention for naming integer division. % :- func (int::in) / (int::in) = (int::uo) is det. % unchecked_quotient(X, Y) is the same as X // Y, but the behaviour % is undefined if the right operand is zero. % :- func unchecked_quotient(int::in, int::in) = (int::uo) is det. % Modulus. % X mod Y = X - (X div Y) * Y % :- func (int::in) mod (int::in) = (int::uo) is det. % Remainder. % X rem Y = X - (X // Y) * Y % `mod' has nicer mathematical properties for negative X, % but `rem' is typically more efficient. % % Throws a `math.domain_error' exception if the right operand is zero. % See the comments at the top of math.m to find out how to disable % domain checks. % :- func (int::in) rem (int::in) = (int::uo) is det. % unchecked_rem(X, Y) is the same as X rem Y, but the behaviour % is undefined if the right operand is zero. % :- func unchecked_rem(int::in, int::in) = (int::uo) is det. % even(X) is equivalent to (X mod 2 = 0). % :- pred even(int::in) is semidet. % odd(X) is equivalent to (not even(X)), i.e. (X mod 2 = 1). % :- pred odd(int::in) is semidet. % Exponentiation. % pow(X, Y, Z): Z is X raised to the Yth power. % Throws a `math.domain_error' exception if Y is negative. % :- func pow(int, int) = int. :- pred pow(int::in, int::in, int::out) is det. % Base 2 logarithm. % log2(X) = N is the least integer such that 2 to the power N % is greater than or equal to X. % Throws a `math.domain_error' exception if X is not positive. % :- func log2(int) = int. :- pred log2(int::in, int::out) is det. %--------------------------------------------------% % Left shift. % X << Y returns X "left shifted" by Y bits. % To be precise, if Y is negative, the result is % X div (2^(-Y)), otherwise the result is X * (2^Y). % :- func (int::in) << (int::in) = (int::uo) is det. % unchecked_left_shift(X, Y) is the same as X << Y % except that the behaviour is undefined if Y is negative, % or greater than or equal to the result of `bits_per_int/1'. % It will typically be implemented more efficiently than X << Y. % :- func unchecked_left_shift(int::in, int::in) = (int::uo) is det. % Right shift. % X >> Y returns X "arithmetic right shifted" by Y bits. % To be precise, if Y is negative, the result is % X * (2^(-Y)), otherwise the result is X div (2^Y). % :- func (int::in) >> (int::in) = (int::uo) is det. % unchecked_right_shift(X, Y) is the same as X >> Y % except that the behaviour is undefined if Y is negative, % or greater than or equal to the result of `bits_per_int/1'. % It will typically be implemented more efficiently than X >> Y. % :- func unchecked_right_shift(int::in, int::in) = (int::uo) is det. %--------------------------------------------------% % Bitwise complement. % :- func \ (int::in) = (int::uo) is det. % Bitwise and. % :- func (int::in) /\ (int::in) = (int::uo) is det. % Bitwise or. % :- func (int::in) \/ (int::in) = (int::uo) is det. % Bitwise exclusive or (xor). % :- func xor(int, int) = int. :- mode xor(in, in) = uo is det. :- mode xor(in, uo) = in is det. :- mode xor(uo, in) = in is det. %--------------------------------------------------% % is/2, for backwards compatibility with Prolog. % :- pred is(T, T) is det. :- mode is(uo, di) is det. :- mode is(out, in) is det. :- pragma obsolete(is/2). %--------------------------------------------------% % max_int is the maximum value of an int on this machine. % :- func max_int = int. :- pred max_int(int::out) is det. % min_int is the minimum value of an int on this machine. % :- func min_int = int. :- pred min_int(int::out) is det. % bits_per_int is the number of bits in an int on this machine. % :- func bits_per_int = int. :- pred bits_per_int(int::out) is det. %--------------------------------------------------% % fold_up(F, Low, High, Acc) <=> list.foldl(F, Low .. High, Acc) % % NOTE: fold_up/4 is undefined if High = max_int. % :- func fold_up(func(int, T) = T, int, int, T) = T. % fold_up(F, Low, High, !Acc) <=> list.foldl(F, Low .. High, !Acc) % % NOTE: fold_up/5 is undefined if High = max_int. % :- pred fold_up(pred(int, T, T), int, int, T, T). :- mode fold_up(pred(in, in, out) is det, in, in, in, out) is det. :- mode fold_up(pred(in, mdi, muo) is det, in, in, mdi, muo) is det. :- mode fold_up(pred(in, di, uo) is det, in, in, di, uo) is det. :- mode fold_up(pred(in, array_di, array_uo) is det, in, in, array_di, array_uo) is det. :- mode fold_up(pred(in, in, out) is semidet, in, in, in, out) is semidet. :- mode fold_up(pred(in, mdi, muo) is semidet, in, in, mdi, muo) is semidet. :- mode fold_up(pred(in, di, uo) is semidet, in, in, di, uo) is semidet. :- mode fold_up(pred(in, in, out) is nondet, in, in, in, out) is nondet. :- mode fold_up(pred(in, mdi, muo) is nondet, in, in, mdi, muo) is nondet. :- mode fold_up(pred(in, di, uo) is cc_multi, in, in, di, uo) is cc_multi. :- mode fold_up(pred(in, in, out) is cc_multi, in, in, in, out) is cc_multi. % fold_up2(F, Low, High, !Acc1, Acc2) <=> % list.foldl2(F, Low .. High, !Acc1, !Acc2) % % NOTE: fold_up2/7 is undefined if High = max_int. % :- pred fold_up2(pred(int, T, T, U, U), int, int, T, T, U, U). :- mode fold_up2(pred(in, in, out, in, out) is det, in, in, in, out, in, out) is det. :- mode fold_up2(pred(in, in, out, mdi, muo) is det, in, in, in, out, mdi, muo) is det. :- mode fold_up2(pred(in, in, out, di, uo) is det, in, in, in, out, di, uo) is det. :- mode fold_up2(pred(in, di, uo, di, uo) is det, in, in, di, uo, di, uo) is det. :- mode fold_up2(pred(in, in, out, array_di, array_uo) is det, in, in, in, out, array_di, array_uo) is det. :- mode fold_up2(pred(in, in, out, in, out) is semidet, in, in, in, out, in, out) is semidet. :- mode fold_up2(pred(in, in, out, mdi, muo) is semidet, in, in, in, out, mdi, muo) is semidet. :- mode fold_up2(pred(in, in, out, di, uo) is semidet, in, in, in, out, di, uo) is semidet. :- mode fold_up2(pred(in, in, out, in, out) is nondet, in, in, in, out, in, out) is nondet. :- mode fold_up2(pred(in, in, out, mdi, muo) is nondet, in, in, in, out, mdi, muo) is nondet. % fold_up3(F, Low, High, !Acc1, Acc2, !Acc3) <=> % list.foldl3(F, Low .. High, !Acc1, !Acc2, !Acc3) % % NOTE: fold_up3/9 is undefined if High = max_int. % :- pred fold_up3(pred(int, T, T, U, U, V, V), int, int, T, T, U, U, V, V). :- mode fold_up3(pred(in, in, out, in, out, in, out) is det, in, in, in, out, in, out, in, out) is det. :- mode fold_up3(pred(in, in, out, in, out, mdi, muo) is det, in, in, in, out, in, out, mdi, muo) is det. :- mode fold_up3(pred(in, in, out, in, out, di, uo) is det, in, in, in, out, in, out, di, uo) is det. :- mode fold_up3(pred(in, in, out, di, uo, di, uo) is det, in, in, in, out, di, uo, di, uo) is det. :- mode fold_up3(pred(in, in, out, in, out, array_di, array_uo) is det, in, in, in, out, in, out, array_di, array_uo) is det. :- mode fold_up3(pred(in, in, out, in, out, in, out) is semidet, in, in, in, out, in, out, in, out) is semidet. :- mode fold_up3(pred(in, in, out, in, out, mdi, muo) is semidet, in, in, in, out, in, out, mdi, muo) is semidet. :- mode fold_up3(pred(in, in, out, in, out, di, uo) is semidet, in, in, in, out, in, out, di, uo) is semidet. :- mode fold_up3(pred(in, in, out, in, out, in, out) is nondet, in, in, in, out, in, out, in, out) is nondet. :- mode fold_up3(pred(in, in, out, in, out, mdi, muo) is nondet, in, in, in, out, in, out, mdi, muo) is nondet. % fold_down(F, Low, High, Acc) <=> list.foldr(F, Low .. High, Acc) % % NOTE: fold_down/4 is undefined if Low = min_int. % :- func fold_down(func(int, T) = T, int, int, T) = T. % fold_down(F, Low, High, !Acc) <=> list.foldr(F, Low .. High, !Acc) % % NOTE: fold_down/5 is undefined if Low min_int. % :- pred fold_down(pred(int, T, T), int, int, T, T). :- mode fold_down(pred(in, in, out) is det, in, in, in, out) is det. :- mode fold_down(pred(in, mdi, muo) is det, in, in, mdi, muo) is det. :- mode fold_down(pred(in, di, uo) is det, in, in, di, uo) is det. :- mode fold_down(pred(in, array_di, array_uo) is det, in, in, array_di, array_uo) is det. :- mode fold_down(pred(in, in, out) is semidet, in, in, in, out) is semidet. :- mode fold_down(pred(in, mdi, muo) is semidet, in, in, mdi, muo) is semidet. :- mode fold_down(pred(in, di, uo) is semidet, in, in, di, uo) is semidet. :- mode fold_down(pred(in, in, out) is nondet, in, in, in, out) is nondet. :- mode fold_down(pred(in, mdi, muo) is nondet, in, in, mdi, muo) is nondet. :- mode fold_down(pred(in, in, out) is cc_multi, in, in, in, out) is cc_multi. :- mode fold_down(pred(in, di, uo) is cc_multi, in, in, di, uo) is cc_multi. % fold_down2(F, Low, High, !Acc1, !Acc2) <=> % list.foldr2(F, Low .. High, !Acc1, Acc2). % % NOTE: fold_down2/7 is undefined if Low = min_int. % :- pred fold_down2(pred(int, T, T, U, U), int, int, T, T, U, U). :- mode fold_down2(pred(in, in, out, in, out) is det, in, in, in, out, in, out) is det. :- mode fold_down2(pred(in, in, out, mdi, muo) is det, in, in, in, out, mdi, muo) is det. :- mode fold_down2(pred(in, in, out, di, uo) is det, in, in, in, out, di, uo) is det. :- mode fold_down2(pred(in, di, uo, di, uo) is det, in, in, di, uo, di, uo) is det. :- mode fold_down2(pred(in, in, out, array_di, array_uo) is det, in, in, in, out, array_di, array_uo) is det. :- mode fold_down2(pred(in, in, out, in, out) is semidet, in, in, in, out, in, out) is semidet. :- mode fold_down2(pred(in, in, out, di, uo) is semidet, in, in, in, out, di, uo) is semidet. :- mode fold_down2(pred(in, in, out, in, out) is nondet, in, in, in, out, in, out) is nondet. :- mode fold_down2(pred(in, in, out, mdi, muo) is nondet, in, in, in, out, mdi, muo) is nondet. % fold_up3(F, Low, High, !Acc1, Acc2, !Acc3) <=> % list.foldr3(F, Low .. High, !Acc1, !Acc2, !Acc3) % % NOTE: fold_down3/9 is undefined if Low = min_int. % :- pred fold_down3(pred(int, T, T, U, U, V, V), int, int, T, T, U, U, V, V). :- mode fold_down3(pred(in, in, out, in, out, in, out) is det, in, in, in, out, in, out, in, out) is det. :- mode fold_down3(pred(in, in, out, in, out, mdi, muo) is det, in, in, in, out, in, out, mdi, muo) is det. :- mode fold_down3(pred(in, in, out, in, out, di, uo) is det, in, in, in, out, in, out, di, uo) is det. :- mode fold_down3(pred(in, in, out, di, uo, di, uo) is det, in, in, in, out, di, uo, di, uo) is det. :- mode fold_down3(pred(in, in, out, in, out, array_di, array_uo) is det, in, in, in, out, in, out, array_di, array_uo) is det. :- mode fold_down3(pred(in, in, out, in, out, in, out) is semidet, in, in, in, out, in, out, in, out) is semidet. :- mode fold_down3(pred(in, in, out, in, out, mdi, muo) is semidet, in, in, in, out, in, out, mdi, muo) is semidet. :- mode fold_down3(pred(in, in, out, in, out, di, uo) is semidet, in, in, in, out, in, out, di, uo) is semidet. :- mode fold_down3(pred(in, in, out, in, out, in, out) is nondet, in, in, in, out, in, out, in, out) is nondet. :- mode fold_down3(pred(in, in, out, in, out, mdi, muo) is nondet, in, in, in, out, in, out, mdi, muo) is nondet. %--------------------------------------------------% % nondet_int_in_range(Low, High, I): % % On successive successes, set I to every integer from Low to High. % :- pred nondet_int_in_range(int::in, int::in, int::out) is nondet. % all_true_in_range(P, Low, High): % True iff P is true for every integer in Low to High. % % NOTE: all_true_in_range/3 is undefined if High = max_int. % :- pred all_true_in_range(pred(int)::in(pred(in) is semidet), int::in, int::in) is semidet. %--------------------------------------------------% % Convert an int to a pretty_printer.doc for formatting. % :- func int_to_doc(int) = pretty_printer.doc. %--------------------------------------------------% %--------------------------------------------------%