note
	description: "[
		Tool bar items grouping algorithm. Huffman alogrithm.
		This class has no relationship with SD_TOOL_BAR_GROUP_INFO.
		Only SD_TOOL_BAR_GROUP_DIVIDER use this class.
		]"
	legal: "See notice at end of class."
	status: "See notice at end of class."
	date: "$Date$"
	revision: "$Revision$"

class
	SD_HUFFMAN_ALGORITHM

create
	make

feature {NONE} -- Creation

	make (a_max_group_count: INTEGER; a_items_width: like item_width)
			-- Create an object with `a_max_group_count' number of groups and `a_items_width' widths of items.
		require
			valid: a_max_group_count >= 0
			not_void: a_items_width /= Void
		do
			max_group_count := a_max_group_count
			group_count := 1
			item_width := a_items_width
			create all_best_grouping.make (max_group_count)
			calculate_all_best_grouping
		ensure
			set: max_group_count = a_max_group_count
			set: item_width = a_items_width
		end

feature -- Command

	set_group_count (a_group_count: INTEGER)
			-- Set `group_count'
		require
			valid: a_group_count > 0 and a_group_count <= max_group_count
		do
			group_count := a_group_count
		ensure
			set: a_group_count = group_count
		end

feature -- Query

	best_grouping: ARRAYED_LIST [ARRAYED_LIST [INTEGER_32]]
			-- Best grouping. Integer is the group index.
		do
			Result := best_grouping_when (group_count)
		ensure
			not_void: Result /= Void
			right_order: is_right_order (Result)
			right_count: is_right_count (Result)
		end

	best_grouping_when (a_group_count: INTEGER): ARRAYED_LIST [ARRAYED_LIST [INTEGER_32]]
			-- Best grouping when `a_group_count'
		require
			valid: a_group_count >= 1 and a_group_count <= max_group_count
		do
			check
				from_precondition: attached all_best_grouping.item (a_group_count) as r
			then
				Result := r
			end
		ensure
			not_void: Result /= Void
			valid: Result.count = a_group_count
			right_order: is_right_order (Result)
			right_count: is_right_count (Result)
		end

	is_right_order (a_grouping: like best_grouping): BOOLEAN
			-- If a_grouping integer which indicate index of `item_width' order right?
		require
			not_void: a_grouping /= Void
		local
			l_one_group: ARRAYED_LIST [INTEGER]
			l_check_index: INTEGER
		do
			Result := True
			l_check_index := a_grouping.first.first
			from
				a_grouping.start
			until
				a_grouping.after or not Result
			loop
				l_one_group := a_grouping.item
				from
					l_one_group.start
				until
					l_one_group.after or not Result
				loop
					if l_check_index /= l_one_group.item then
						Result := False
					end
					l_check_index := l_check_index + 1
					l_one_group.forth
				end
				a_grouping.forth
			end
		end

	is_right_count (a_group_info: like best_grouping): BOOLEAN
			-- If a_group_info count right?
		require
			not_void: a_group_info /= Void
			set: item_width /= Void
		local
			l_item_count: INTEGER
		do
			from
				a_group_info.start
			until
				a_group_info.after
			loop
				l_item_count := a_group_info.item.count + l_item_count
				a_group_info.forth
			end
			Result := l_item_count = item_width.count
		end

	item_width: ARRAYED_LIST [INTEGER]
			-- Groups to be calculated. Integer is each group width.

	group_count: INTEGER
			-- Group count is how many group excepted to divide.

	maximum_group_width (a_group_count: INTEGER): INTEGER
			-- Maximum width when divide group number to a_group_count.
		require
			valid: a_group_count > 0 and a_group_count <= max_group_count
		do
			Result := maximum_row_width (best_grouping_when (a_group_count))
		end

	maximum_group_width_index (a_group_count: INTEGER): INTEGER
			-- Maximum width group index when divide group number to a_group_count.
		require
			valid: a_group_count > 0 and a_group_count <= max_group_count
		do
			maximum_row_width (best_grouping_when (a_group_count)).do_nothing
			Result := internal_maximum_group_index
		ensure
			valid: Result >0 and Result <= max_group_count
		end

	max_group_count: INTEGER
			-- Maximum group count.

feature {NONE} -- Implementation functions

	calculate_all_best_grouping
			-- Calculate all best groupings, added the result to `all_best_grouping'.
		local
			l_group_count: INTEGER
			l_last_best_grouping: detachable like best_grouping
		do
			from
				all_best_grouping.wipe_out
				l_group_count := max_group_count

			until
				l_group_count < 1
			loop

				if l_group_count = max_group_count then
					l_last_best_grouping := start_condition
				else
					check
						attached l_last_best_grouping -- Implied by `next_best_grouping's result not void and `start_condition' not void
					then
						l_last_best_grouping := next_best_grouping (l_last_best_grouping)
					end
				end

				check count_right: l_last_best_grouping.count = l_group_count end
				all_best_grouping.extend (l_last_best_grouping, l_group_count)

				l_group_count := l_group_count - 1
			end
		end

	next_best_grouping (a_previous_info: like best_grouping): like best_grouping
			-- Next best grouping info of `a_previous_infos'.
		local
			l_group_index: INTEGER
			l_group: ARRAYED_LIST [INTEGER]
		do
			Result := a_previous_info.deep_twin
			l_group_index := minimum_two_group_index (a_previous_info)
			Result.go_i_th (l_group_index)

			-- Remove two minimum group items, add one which is combination of the two removed.
			l_group := Result.item
			l_group.append (Result.i_th (l_group_index + 1))

			Result.remove
			Result.replace (l_group)
		ensure
			not_same: Result /= a_previous_info
			group_count_right: Result.count = a_previous_info.count - 1
		end

	all_best_grouping: HASH_TABLE [like best_grouping, INTEGER]
			-- 2nd INTEGER parameter is group count.

	start_condition: like best_grouping
			-- Prepare start condition
		require
			set: item_width /= Void
		local
			l_item_count, l_max_count: INTEGER
			l_item: ARRAYED_LIST [INTEGER]
		do
			from
				l_item_count := 1
				l_max_count := item_width.count
				create Result.make (l_max_count)
			until
				l_item_count > l_max_count
			loop
				create l_item.make (1)
				l_item.extend (l_item_count)
				Result.extend (l_item)
				l_item_count := l_item_count + 1
			end
		ensure
			not_void: Result /= Void
			valid: attached item_width as l_item_width implies Result.count = l_item_width.count
		end

	minimum_two_group_index (a_condition: like best_grouping): INTEGER
			-- Which two items should be together. Result is first index, second item index is Result + 1.
			-- Huffman alogrithm, for example:
			-- After calculation:  	  11  2	  2	  2	  2   10
			-- Before calculation:	10	1	1	1	1	1	9
			-- Then Result is 2, bacause item 2 and item 3 should be together.
		require
			not_void: a_condition /= Void
			valid: a_condition.count > 1
		local
			l_minimum_two_width: INTEGER
			l_temp_two_width: INTEGER
		do
			from
				l_minimum_two_width := {INTEGER}.max_value
				a_condition.start
			until
				-- We stop at the 2nd last item
				a_condition.index >= a_condition.count
			loop
				l_temp_two_width := one_group_width (a_condition.item) + one_group_width (a_condition.i_th (a_condition.index + 1))
				if l_temp_two_width < l_minimum_two_width then
					l_minimum_two_width := l_temp_two_width
					Result := a_condition.index
				end
				a_condition.forth
			end
		ensure
			valid: 0 < Result and Result < a_condition.count
		end

	maximum_row_width (a_group: like best_grouping): INTEGER
			-- Maximum row width of a_group
		require
			not_void: a_group /= Void
		local
			l_one_group_width: INTEGER
		do
			from
				a_group.start
			until
				a_group.after
			loop
				l_one_group_width := one_group_width (a_group.item)

				if Result < l_one_group_width then
					Result := l_one_group_width
					internal_maximum_group_index := a_group.index
				end

				a_group.forth
			end
		ensure
			valid: Result > 0
		end

	internal_maximum_group_index: INTEGER
			-- Maximum width group index.

	one_group_width (a_group: ARRAYED_LIST [INTEGER]): INTEGER
			-- Width of `a_group'.
		require
			not_void: a_group /= Void
			at_leaat_one: a_group.count >= 1
			set: item_width /= Void
		local
			l_item_width: like item_width
		do
			from
				l_item_width := item_width
				a_group.start
			until
				a_group.after
			loop
				Result := l_item_width.i_th (a_group.item) + Result
				a_group.forth
			end
		ensure
			valid: Result > 0
		end

invariant
	valid: group_count >= 1 and group_count <= max_group_count
	attached_item_width: attached item_width

note
	library: "SmartDocking: Library of reusable components for Eiffel."
	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