note

	description: "Bit sequences of length `count', with binary operations"
	legal: "See notice at end of class."
	status: "See notice at end of class."
	date: "$Date$"
	revision: "$Revision$"

--| Caution:
--| For implementation reasons, additional operations on BIT types can
--| only be introduced by ISE

class BIT_REF inherit

	ANY
		redefine
			out,
			is_equal,
			default_create
		end

create
	default_create

create {BIT_REF}
	make, make_initialized

feature {NONE} -- Initialization

	default_create
			-- Default initialization, with 32 bits.
		do
			make (32)
		end

	make (n: INTEGER)
			-- Initialize space for `n' bits.
		require
			positive_n: n > 0
		local
			tmp_values: ARRAY [INTEGER]
		do
			create tmp_values.make (0, n |>> 5)
			values := tmp_values.area
			count := n
		end

	make_initialized (l_area: SPECIAL [INTEGER]; l_count: INTEGER)
			-- Initialize `Current' with a count of `l_count' and values of `l_area'.
		require
			valid_args: l_area /= Void and l_count > 0 and then l_area.count >= (l_count |>> 5)
		do
			values := l_area
			count := l_count
		end

feature -- Access

	item alias "[]", infix "@" (i: INTEGER): BOOLEAN assign put
			-- `i'-th bit
		require
			index_large_enough: i >= 1
			index_small_enough: i <= count
		do
			Result := (values.item (i |>> 5)).bit_test (i & 31)
		end

	is_equal (other: like Current): BOOLEAN
			-- Is other similar to `Current'?
		local
			i, n, tmp: INTEGER
		do
			n := count |>> 5
			Result := count = other.count
			from
				
			until
				i = n or not Result
			loop
				Result := (values @ i) = (other.values @ i)
				i := i + 1
			end
			if Result then
				i := count & 31
				if i = 0 then
					i := 32
				end
				i := (31 |<< i).bit_not
				tmp := other.values @ n
				tmp := tmp & i
				Result := tmp = ((values @ i) & i)
			end
		end

feature -- Measurement

	count: INTEGER
			-- Size of the current bit object

feature -- Element change

	put (value: BOOLEAN; i: INTEGER)
			-- Set the `i'-th bit to 1 if `value' is True, 0 if False
		require
			index_large_enough: i >= 1
			index_small_enough: i <= count
		local
			index: INTEGER
		do
			index := i |>> 5
			if value then
				values.put ((values.item (i)) | (1 |<< (i & 31)), index)
			else
				values.put ((values.item (i)) & ((1 |<< (i & 31)).bit_not ), index)
			end
		ensure
			value_inserted: item (i) = value
		end

feature -- Basic operations

	infix "^" (s: INTEGER): like Current
			-- Result of shifting bit sequence by `s' positions
			-- (Positive `s' shifts right, negative `s' shifts left;
			-- bits falling off the sequence's bounds are lost.)
		local
			tmp_values: like values
			int_shift: INTEGER
			f_shift: INTEGER
			n, i, tmp, left: INTEGER
		do
			n := count |>> 5
			left := 31 - (count & 31)
			tmp_values := (create {ARRAY [INTEGER]}.make (0, n)).area
			if s > 0 then
					--| Make sure there are 0's in the undefined bits at the end.
				tmp := count & 31
				if tmp = 0 then
					tmp := 32
				end
				values.put ((values @ n) & (31 |<< tmp).bit_not, n)
				
				f_shift := s & 31
				int_shift := s |<< 5
				if f_shift = 0 then
						--| Slight optimization: we move integers instead of bits.
					from
						i := int_shift
					until
						i > n
					loop
						tmp_values.put (values @ i, i - int_shift)
						i := i + 1
					end
					from
						i := n - int_shift
					until
						i > n
					loop
						tmp_values.put (0, i)
						i := i + 1
					end
				else
						--| We have to move bits.
					tmp := (values @ int_shift) |>> f_shift
					tmp := tmp | ((values @ (int_shift + 1)) |<< (32 - f_shift))
					tmp_values.put (tmp, 0)
					from
						i := int_shift + 1
					until
						i = n
					loop
						tmp := (values @ i) |>> f_shift
						tmp := tmp | ((values @ (i + 1)) |<< (32 - f_shift))
						tmp_values.put (tmp, i - int_shift)
						i := i + 1
					end
					tmp := (values @ i) |>> f_shift
					tmp_values.put (tmp, n - int_shift)
					from
						i := n - int_shift + 1
					until
						i > n
					loop
						tmp_values.put (0, i)
						i := i + 1
					end
				end
			elseif s < 0 then
				f_shift := (-s) & 31
				int_shift := (-s) |<< 5
				if f_shift = 0 then
						--| Slight optimization: we move integers instead of bits.
					from
					until
						i = int_shift
					loop
						tmp_values.put (0, i)
						i := i + 1
					end
					from
					until
						i > n
					loop
						tmp_values.put (values @ (i - int_shift), i)
						i := i + 1
					end
				else
						--| We have to move bits.
					from
					until
						i = int_shift
					loop
						tmp_values.put (0, i)
						i := i + 1
					end
					tmp := (values @ 0) |<< f_shift
					tmp_values.put (tmp, int_shift)
					from
						i := int_shift + 1
					until
						i > n
					loop
						tmp := (values @ (i - int_shift)) |<< f_shift
						tmp := tmp | ((values @ (i - int_shift - 1)) |>> (32 - f_shift))
						tmp_values.put (tmp, i)
						i := i + 1
					end
				end
			end
			create Result.make_initialized (tmp_values, count)
		end

	infix "#" (s: INTEGER): like Current
			-- Result of rotating bit sequence by `s' positions
			-- (Positive `s' rotates right, negative `s' rotates left.)
		local
			tmp_values: like values
			int_shift: INTEGER
			f_shift: INTEGER
			n, i, tmp, xb: INTEGER
		do
			n := count |>> 5
			tmp_values := (create {ARRAY [INTEGER]}.make (0, n)).area
			if s > 0 then
				f_shift := s & 31
				int_shift := s |<< 5
				from
					i := int_shift
				until
					i = n - 1
				loop
					tmp := (values @ i) |>> f_shift
					tmp := tmp | ((values @ (i + 1)) |<< (32 - f_shift))
					tmp_values.put (tmp, i - int_shift)
					i := i + 1
				end
				xb := count & 31
				if xb = 0 then
					xb := 32
				end
					--| Make sure there are 0's in the undefined bits at the end.
				values.put ((values @ n) & (31 |<< xb).bit_not, n)

				if xb < f_shift then
						--| i = n - 1.
					tmp := (values @ i) |>> f_shift
					tmp := tmp | ((values @ (i + 1)) |<< (32 - f_shift))
					f_shift := f_shift - xb
					tmp := tmp | ((values @ 0) |<< (32 - f_shift))
					tmp_values.put (tmp, i - int_shift)
				else
					tmp := (values @ i) |>> f_shift
					tmp := tmp | ((values @ (i + 1)) |<< (32 - f_shift))
					tmp_values.put (tmp, i - int_shift)
					i := i + 1
						--| i = n.
					tmp := (values @ i) |>> f_shift
					f_shift := f_shift + 32 - xb
					tmp := tmp | ((values @ 0) |<< (32 - f_shift))
					tmp_values.put (tmp, 0)
				end
					
				from
					i := 0
				until
					i = int_shift
				loop
					tmp := (values @ i) |>> f_shift
					tmp := tmp | ((values @ (i + 1)) |<< (32 - f_shift))
					tmp_values.put (tmp, n - int_shift + i)
					i := i + 1
				end
				create Result.make_initialized (tmp_values, count)
			else
				Result := Current # (count - s)
			end
		end

	infix "and" (other: BIT_REF): BIT_REF
			-- Bit-by-bit boolean conjunction with `other'
		require
			other_exists: other /= Void
			conformance: other.count <= count
		local
			i, n, m, c, oc: INTEGER
			tmp_values: SPECIAL [INTEGER]
		do
			c := count |>> 5
			oc := other.count |>> 5
				--| n is the max, m is the min.
			if c > oc then
				n := c
				m := oc
			else
				n := oc
				m := c
			end
			tmp_values := (create {ARRAY [INTEGER]}.make (0, n)).area
			from
				
			until
				i > m 
			loop
				tmp_values.put ((values @ i) & (other.values @ i), i)
				i := i + 1
			end
			create Result.make_initialized (tmp_values, n)
		end

	infix "implies" (other: BIT_REF): BIT_REF
			-- Bit-by-bit boolean implication of `other'
		require
			other_exists: other /= Void
			conformance: other.count <= count
		local
			i, n, m, c, oc: INTEGER
			tmp_values: SPECIAL [INTEGER]
		do
			c := count |>> 5
			oc := other.count |>> 5
				--| n is the max, m is the min.
			if c > oc then
				n := c
				m := oc
				tmp_values := values.twin
			else
				n := oc
				m := c
				tmp_values := (create {ARRAY [INTEGER]}.make (0, n)).area
			end
			from
				
			until
				i > m 
			loop
				tmp_values.put ((values @ i).bit_not | (other.values @ i), i)
				i := i + 1
			end
			from
				
			until
				i > n
			loop
				tmp_values.put ((tmp_values @ i).bit_not, i)
				i := i + 1
			end
			create Result.make_initialized (tmp_values, n)
		end

	infix "or", infix "|" (other: BIT_REF): BIT_REF
			-- Bit-by-bit boolean disjunction with `other'
		require
			other_exists: other /= Void
			conformance: other.count <= count
		local
			i, n, m, c, oc: INTEGER
			tmp_values: SPECIAL [INTEGER]
		do
			c := count |>> 5
			oc := other.count |>> 5
				--| n is the max, m is the min.
			if c > oc then
				n := c
				m := oc
				tmp_values := values.twin
			else
				n := oc
				m := c
				tmp_values := other.values.twin
			end
			from
				
			until
				i > m 
			loop
				tmp_values.put ((values @ i) | (other.values @ i), i)
				i := i + 1
			end
			create Result.make_initialized (tmp_values, n)
		end

	infix "xor" (other: BIT_REF): BIT_REF
			-- Bit-by-bit exclusive or with `other'
		require
			other_exists: other /= Void
			conformance: other.count <= count
		local
			i, n, m, c, oc: INTEGER
			tmp_values: SPECIAL [INTEGER]
		do
			c := count |>> 5
			oc := other.count |>> 5
				--| n is the max, m is the min.
			if c > oc then
				n := c
				m := oc
				tmp_values := values.twin
			else
				n := oc
				m := c
				tmp_values := other.values.twin
			end
			from
				
			until
				i > m 
			loop
				tmp_values.put ((values @ i).bit_xor (other.values @ i), i)
				i := i + 1
			end
			create Result.make_initialized (tmp_values, n)
		end

	prefix "not": like Current
			-- Bit-by-bit negation
		local
			i, n: INTEGER
			tmp_values: SPECIAL [INTEGER]
		do
			n := count |>> 5
			tmp_values := (create {ARRAY [INTEGER]}.make (0, n)).area
			from
				
			until
				i > n 
			loop
				tmp_values.put ((values @ i).bit_not, i)
				i := i + 1
			end
			create Result.make_initialized (tmp_values, n)
		end

feature -- Output

	out: STRING
			-- Tagged printable representation.
		local
			i, n, ci, j: INTEGER
		do
			n := count |>> 5
			create Result.make (count)
			from
				
			until
				i = n
			loop
				from
					ci := values @ i
					j := 1
				until
					j > 32
				loop
					if (ci & 1) = 0 then
						Result.append_character ('0')
					else
						Result.append_character ('1')
					end
					ci := ci |>> 1
					j := j + 1
				end
			end
			from
				ci := values @ i
				j := 1
			until
				j > count & 31
			loop
				if (ci & 1) = 0 then
					Result.append_character ('0')
				else
					Result.append_character ('1')
				end
				ci := ci |>> 1
				j := j + 1
			end
		end

feature -- Conversion

	to_reference: BIT_REF
			-- Associated reference of Current.
		do
			create Result.make_initialized (values.twin, count)
		end
	
feature {BIT_REF} -- Implementation

	values: SPECIAL [INTEGER]
			-- Array where integers store `Current' in a compact way.

invariant
	valid_count: count > 0
	
note
	library:	"EiffelBase: Library of reusable components for Eiffel."
	copyright:	"Copyright (c) 1984-2006, Eiffel Software and others"
	license:	"Eiffel Forum License v2 (see http://www.eiffel.com/licensing/forum.txt)"
	source: "[
			 Eiffel Software
			 356 Storke Road, Goleta, CA 93117 USA
			 Telephone 805-685-1006, Fax 805-685-6869
			 Website http://www.eiffel.com
			 Customer support http://support.eiffel.com
		]"



end -- class BIT_REF