note
	description: "Partially deterministic finite state automata."

class PDFA

inherit
	NDFA
		redefine
			copy, is_equal
		end

	ASCII
		redefine
			copy, is_equal
		end

create

	make

feature {NONE} -- Initialization

	make (n, i: INTEGER)
			-- Make a PDFA with `n' states, and `i' + 1 inputs.
		do
			nb_states := n
			greatest_input := i
			create input_array.make_filled (Void, greatest_input + 1)
			create final_array.make_filled (0, 1, nb_states)
			create keywords_list.make
			create area.make_filled (Void, nb_states)
		end

feature {PDFA} -- Access

	item (i: INTEGER): detachable LINKED_LIST [INTEGER]
			-- Entry at index `i'.
		require
			valid_index: i >= 1 and i <= nb_states
		do
			Result := area.item (i - 1)
		end

	input_array: SPECIAL [detachable FIXED_INTEGER_SET]
			-- For each input, set of the states which have
			-- a transition on this input to the following state.

	final_array: ARRAY [INTEGER]
			-- The `final' value for each state
			-- (regular expression, if any, for which it is final).

	keywords_list: LINKED_LIST [STRING]
			-- Keywords associated with current automaton.

feature -- Access

	has_letters: BOOLEAN
			-- Are there any letters among the active transitions?

feature -- Status setting

	set_letters
			-- Direct the active transitions to include letters.
		do
			has_letters := True
		end

	set_final (s, r: INTEGER)
			-- Make `s' the final state of regular expression `r'.
		do
			final_array.put (r, s)
		end

	set_transition (source, input_doc, target: INTEGER)
			-- Set transition from `source' to `target' on `input_doc'.
		require else
			source_in_automaton: source >= 1 and source <= nb_states
			target_in_automaton: target >= 1 and target <= nb_states
			possible_input_doc: input_doc >= 0 and input_doc <= greatest_input
			good_successor: target = source + 1
		local
			l_set: FIXED_INTEGER_SET
		do
			if attached input_array.item (input_doc) as l_input_array_item then
				l_input_array_item.put (source)
			else
				create l_set.make (nb_states)
				input_array.put (l_set, input_doc)
				l_set.put (source)
			end
		end

	set_e_transition (source, target: INTEGER)
			-- Set epsilon transition from `source' to `target'.
		local
			list: detachable LINKED_LIST [INTEGER]
		do
			list := item (source)
			if list = Void then
				create list.make
				put (list, source)
			end
			list.put_right (target)
			list.forth
		end

feature -- Element change

	put (v: like item; i: INTEGER)
			-- Replace `i'-th entry, if in index interval, by `v'.
		require
			valid_index: i >= 1 and i <= nb_states
		do
			area.put (v, i - 1)
		end

	add_keyword (word: STRING)
			-- Insert `word' in the keyword list.
		do
			keywords_list.finish
			keywords_list.put_right (word)
		end

	include (fa: PDFA; shift: INTEGER)
			-- Copy `fa' with state numbers shifted
			-- by `shift' positions in the transitions.
			-- Do not preserve the `final' values.
		require
			same_inputs: greatest_input = fa.greatest_input
			nb_states_large_enough: nb_states >= fa.nb_states + shift
		local
			index, last_index: INTEGER
			input_doc: INTEGER
			set: detachable FIXED_INTEGER_SET
		do
			e_include (fa, shift)
			from
				input_doc := -1
			until
				input_doc = greatest_input
			loop
				input_doc := input_doc + 1
				set := fa.input_array.item (input_doc)
				if set /= Void then
					last_index := set.largest
					from
						index := set.smallest
					until
						index > last_index
					loop
						set_transition (index + shift, input_doc, index + shift + 1)
						index := set.next (index)
					end
				end
			end
			if fa.has_letters then
				has_letters := True
			end
		end

	remove_case_sensitiveness
			-- Remove case sensitiveness.
		require
			z_possible: greatest_input >= Lower_z
		local
			input_doc: INTEGER
			upper_set, lower_set: detachable FIXED_INTEGER_SET
		do
			if has_letters then
				from
					input_doc := Lower_a - 1
				until
					input_doc = Lower_z
				loop
					input_doc := input_doc + 1
					lower_set := input_array.item (input_doc)
					upper_set := input_array.item (input_doc - Case_diff)
					if upper_set = Void then
						if lower_set /= Void then
							input_array.put (lower_set, input_doc - Case_diff)
						end
					elseif lower_set = Void then
						input_array.put (upper_set, input_doc)
					else
						upper_set := upper_set or lower_set
						input_array.put (upper_set, input_doc)
						input_array.put (upper_set, input_doc - Case_diff)
					end
				end
			end
		end

feature -- Removal

	delete_transition (source, input_doc, target: INTEGER)
			-- Delete transition from `source' to `target' on `input_doc'.
		require else
			source_in_automaton: source >= 1 and source <= nb_states
			target_in_automaton: target >= 1 and target <= nb_states
			possible_input_doc: input_doc >= 0 and input_doc <= greatest_input
			good_successor: target = source + 1
		do
			if attached input_array.item (input_doc) as l_input_array_item then
				l_input_array_item.remove (source)
			end
		end

feature -- Output

	trace
			-- Output an internal representation
			-- of the current automaton.
		local
			index, input_doc: INTEGER
			set: detachable FIXED_INTEGER_SET
			epsilon_list: detachable LINKED_LIST [INTEGER]
		do
			debug ("lex_output")
				from
				until
					index = nb_states
				loop
					index := index + 1
					io.put_string (" State # ")
					io.put_integer (index)
					if final_array.item (index) /= 0 then
						io.put_string (" final state of token type: ")
						io.put_integer (final_array.item (index))
					end
					io.new_line
					io.put_string (" Epsilon transitions to: ")
					epsilon_list := item (index)
					if epsilon_list /= Void then
						from
							epsilon_list.start
						until
							epsilon_list.after or epsilon_list.is_empty
						loop
							io.put_integer (epsilon_list.item)
							io.put_string (" ")
							epsilon_list.forth
						end
					end
					io.put_string ("%N Inputs with a transition to the following state:%N")
					from
						input_doc := -1
					until
						input_doc = greatest_input
					loop
						input_doc := input_doc + 1
						set := input_array.item (input_doc)
						if set /= Void and then set.has (index) then
							io.put_integer (input_doc)
							io.new_line
						end
					end
					io.new_line
				end
			end
		end

feature -- Comparison

	is_equal (other: like Current): BOOLEAN
			-- <Precursor>
		do
			if other = Current then
				Result := True
			elseif area.count = other.area.count then
				Result := area.same_items (other.area, 0, 0, area.count)
			end
		end

feature -- Duplication

	copy (other: like Current)
			-- <Precursor>
		do
			if other /= Current then
				standard_copy (other)
				area := other.area.twin
			end
		end

feature {PDFA} -- Implementation: Access

	area: SPECIAL [detachable LINKED_LIST [INTEGER]]
			-- Storage.

feature {NONE} -- Implementation

	closure (state: INTEGER): FIXED_INTEGER_SET
			-- Epsilon_closure of ith state which means
			-- set of NDFA state reachable from ith
			-- state on epsilon-transition alone.
		require else
			state_in_automaton: state > 0 and state <= nb_states
		local
			stack: LINKED_STACK [INTEGER]
			top, int: INTEGER
		do
			create stack.make
			create Result.make (nb_states)
			Result.put (state)
			from
				stack.put (state)
			until
				stack.is_empty
			loop
				top := stack.item
				stack.remove
				if attached item (top) as e_successors_list then
					from
						e_successors_list.start
					until
						e_successors_list.after or e_successors_list.is_empty
					loop
						int := e_successors_list.item
						if not Result.has (int) then
							Result.put (int)
							stack.put (int)
						end
						e_successors_list.forth
					end
				end
			end
		ensure then
			result_attached: Result /= Void
			state_in_closure: Result.has (state)
		end

	move (initial_set: FIXED_INTEGER_SET; i: INTEGER): detachable FIXED_INTEGER_SET
			-- Set of NDFA states to which there is a transition on
			-- input i from some NDFA state s of initial_set.
			-- Void if the set if empty.
		require else
			possible_input: i >= 0 and i <= greatest_input
			set_not_void: initial_set /= Void
		do
			if attached input_array [i] as l_input_array_item then
				Result := initial_set and l_input_array_item
				if not Result.is_empty then
					Result := Result.right_shifted (1)
				else
					Result := Void
				end
			end
		end

	initial_final_designation
			-- Set the final and initial attributes of the dfa,
			-- consistent with those of the current automaton.
		local
			index: INTEGER
			l_array: like final_array
		do
			if attached dfa as l_dfa and attached sets_list as l_sets_list then
				l_array := final_array
				l_dfa.set_start (1)
				from
				until
					index = nb_states
				loop
					index := index + 1
					if l_array.item (index) /= 0 then
						from
							l_sets_list.start
						until
							l_sets_list.after or l_sets_list.is_empty
						loop
							if l_sets_list.item.has (index) then
								dfa_set_final (l_sets_list.index, l_array.item (index))
							end
							l_sets_list.forth
						end
					end
				end
			end
		end

	dfa_set_final (s, f: INTEGER)
			-- Make `f' the `final' state for `s'.
		do
			if attached dfa as l_dfa and then attached l_dfa.item (s) as l_state_of_dfa then
				l_state_of_dfa.set_final (final_array.item (f))
			end
		end

	e_include (fa: PDFA; shift: INTEGER)
			-- Copy the fa epsilon transition in Current
			-- with state numbers shifted in the transitions.
			-- The attributes are not preserved.
		require
			nb_states_large_enough: nb_states >= fa.nb_states + shift
		local
			index, last_index: INTEGER
		do
			last_index := fa.nb_states
			from
			until
				index = last_index
			loop
				index := index + 1
				if attached fa.item (index) as l_list then
					from
						l_list.start
					until
						l_list.after
					loop
						set_e_transition (index + shift, l_list.item + shift)
						l_list.forth
					end
				end
			end
		end

	find_successors (source, input_doc: INTEGER): detachable LINKED_LIST [INTEGER]
			-- Successors of `source' on `input_doc';
			-- void if no successor.
		require else
			source_in_automaton: source >= 1 and source <= nb_states
			possible_input_doc: input_doc >= 0 and input_doc <= greatest_input
		do
			if attached input_array.item (input_doc) as l_fixed_integer_set and then l_fixed_integer_set.has (source) then
				create Result.make
				Result.put_right (source + 1)
			end
		end

	find_e_successors (source: INTEGER): detachable LINKED_LIST [INTEGER]
			-- Epsilon successors of source;
			-- Void if no successor.
		require else
			source_in_automaton: source >= 1 and source <= nb_states
		do
			Result := item (source)
		end

	set_state
			-- This routine is deferred in NDFA,
			-- but is useless in PDFA.
		do
		end

note
	comment: "[
			 These PDFA have a very special structure.
			 They are NDFA but for each state, only one successor is
			 possible, if the input is different of epsilon,
			 and this successor is the following state.
			 For the epsilon transitions each state can have as many
			 successors as possible.
			 Thus, the structure is different for the epsilons transitions,
			 which are recorded in an ARRAY [LINKED_LIST [INTEGER]],
			 and for the others transitions, which are recorded, for
			 each input, in a FIXED_INTEGER_SET.

			 For the use in a regular expression context, keywords
			 can be associated with Current.
		]"
	date: "$Date$"
	revision: "$Revision$"
	copyright:	"Copyright (c) 1984-2017, Eiffel Software and others"
	license:	"Eiffel Forum License v2 (see http://www.eiffel.com/licensing/forum.txt)"
	source: "[
			Eiffel Software
			5949 Hollister Ave., Goleta, CA 93117 USA
			Telephone 805-685-1006, Fax 805-685-6869
			Website http://www.eiffel.com
			Customer support http://support.eiffel.com
		]"

end