90 version_bitmap

     %--------------------------------------------------%
     % Copyright (C) 2004-2007, 2010-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.
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     %
     % File: version_bitmap.m.
     % Author: Ralph Becket <rafe@cs.mu.oz.au>.
     % Stability: low.
     %
     % (See the header comments in version_array.m for an explanation of version
     % types.)
     %
     % Version bitmaps: an implementation of bitmaps using version arrays.
     %
     % The advantage of version bitmaps is that in the common, singly threaded,
     % case, they are almost as fast as unique bitmaps, but can be treated as
     % ordinary ground values rather than unique values.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%
     
     :- module version_bitmap.
     :- interface.
     
     :- import_module bool.
     
     %--------------------------------------------------%
     
     :- type version_bitmap.
     
         % init(N, B) creates a version_bitmap of size N (indexed 0 .. N-1)
         % setting each bit if B = yes and clearing each bit if B = no.
         % An exception is thrown if N is negative.
         %
     :- func init(int, bool) = version_bitmap.
     
         % Returns the number of bits in a version_bitmap.
         %
     :- func num_bits(version_bitmap) = int.
     
         % set(BM, I), clear(BM, I) and flip(BM, I) set, clear and flip
         % bit I in BM respectively.  An exception is thrown if I is out
         % of range.  Predicate versions are also provided.
         %
     :- func set(version_bitmap, int) = version_bitmap.
     :- pred set(int::in, version_bitmap::in, version_bitmap::out) is det.
     
     :- func clear(version_bitmap, int) = version_bitmap.
     :- pred clear(int::in, version_bitmap::in, version_bitmap::out) is det.
     
     :- func flip(version_bitmap, int) = version_bitmap.
     :- pred flip(int::in, version_bitmap::in, version_bitmap::out) is det.
     
         % is_set(BM, I) and is_clear(BM, I) succeed iff bit I in BM
         % is set or clear respectively.
         %
     :- pred is_set(version_bitmap::in, int::in) is semidet.
     :- pred is_clear(version_bitmap::in, int::in) is semidet.
     
         % Get the given bit.
         %
     :- func version_bitmap ^ bit(int) = bool.
     
         % Set the given bit.
         %
     :- func (version_bitmap ^ bit(int) := bool) = version_bitmap.
     
         % Create a new copy of a version_bitmap.
         %
     :- func copy(version_bitmap) = version_bitmap.
     
         % Set operations; the second argument is altered in all cases.
         %
     :- func complement(version_bitmap) = version_bitmap.
     
     :- func union(version_bitmap, version_bitmap) = version_bitmap.
     
     :- func intersect(version_bitmap, version_bitmap) = version_bitmap.
     
     :- func difference(version_bitmap, version_bitmap) = version_bitmap.
     
     :- func xor(version_bitmap, version_bitmap) = version_bitmap.
     
         % resize(BM, N, B) resizes version_bitmap BM to have N bits; if N is
         % smaller than the current number of bits in BM then the excess
         % are discarded.  If N is larger than the current number of bits
         % in BM then the new bits are set if B = yes and cleared if
         % B = no.
         %
     :- func resize(version_bitmap, int, bool) = version_bitmap.
     
         % Version of the above suitable for use with state variables.
         %
     :- pred resize(int::in, bool::in, version_bitmap::in, version_bitmap::out)
                 is det.
     
         % unsafe_rewind(B) produces a version of B for which all accesses are
         % O(1).  Invoking this predicate renders B and all later versions undefined
         % that were derived by performing individual updates.  Only use this when
         % you are absolutely certain there are no live references to B or later
         % versions of B.
         %
     :- func unsafe_rewind(version_bitmap) = version_bitmap.
     
         % A version of the above suitable for use with state variables.
         %
     :- pred unsafe_rewind(version_bitmap::in, version_bitmap::out) is det.
     
     %--------------------------------------------------%
     %--------------------------------------------------%