note
	description: "Data structure that indexes items with a string_32 key by constructing a tree of characters."
	legal: "See notice at end of class."
	status: "See notice at end of class."
	date: "$Date$"
	revision: "$Revision$"

class
	CHARACTER_TREE [G -> ANY]

create
	default_create,
	make

feature {NONE} -- Creation

	make (a_key: STRING_32; a_character_list: LINKED_LIST[CHARACTER_TREE[G]])
			-- Make a tree with `a_key' as a key and `a_character_list' as a character list.
		require
			a_key_not_exists: a_key /= Void
			a_character_list_exists: a_character_list /= Void
		do
			key := a_key
			character_trees_list := a_character_list
		end

feature -- Modification

	insert (a_item: G; a_key: STRING_32)
			-- Insert an `a_item' with `a_key' as key in Current tree.
		require
			item_and_key_exist: a_item /= Void and a_key /= Void
			not_yet_in_tree: not has (a_item, a_key)
		local
			tree_el: detachable CHARACTER_TREE[G]
			l_list: like character_trees_list
			distance: INTEGER
			l_tree, r_tree: CHARACTER_TREE [G]
			r_key: detachable STRING_32
		do
			if attached key as l_key then
				if not is_leaf then
						-- It is a node.
					tree_el:= search_character_tree (a_key.substring (l_key.count+1, a_key.count))
					if tree_el = Void or not a_key.substring (1,l_key.count).is_equal (l_key) then
							-- Element is not in the node.
						insert_character_tree (a_item, a_key)
					else
							-- Similar element is in the node, insert there.
						tree_el.insert (a_item,a_key.substring (l_key.count+1, a_key.count))
					end
				else
						-- It is a 1-element leaf, we split.
					create l_list.make
					character_trees_list := l_list

					distance := minimum_distance (a_key, l_key)

					create l_tree
					check attached item as l_item then
						l_tree.insert (l_item, l_key.substring (distance+1, l_key.count))
					end

					l_list.put_front (l_tree)

					r_key := a_key.substring (distance+1, a_key.count)
					create r_tree
					r_tree.insert (a_item, r_key)
					l_list.put_front (r_tree)
					key := l_key.substring (1, distance)
					item := default_item
				end
			else
					-- It is an empty leaf.
				key := a_key
				item := a_item
			end
		end

feature -- Access

	get (a_key: STRING_32): detachable G
			-- Get item with `a_key' as key.
		require
			a_key_exists: a_key /= Void
			a_key_in_tree: get_item_with_key (a_key) /= Void
		local
			tree_el: like search_character_tree
		do
			if not is_leaf then
				if attached key as l_key then
					tree_el := search_character_tree (a_key.substring (l_key.count +1, a_key.count))
					if tree_el /= Void then
						Result := tree_el.get (a_key.substring (l_key.count +1, a_key.count))
					end
				end
			else
				Result := item
			end
		end

	has (a_item: G; s: STRING_32): BOOLEAN
			-- Does current tree have `a_item' with `s' as a key?
		require
			a_item_not_void: a_item /= Void
			s_not_void: s /= Void
		local
			tree_el: detachable CHARACTER_TREE[G]
		do
			if not is_leaf then
				if attached key as l_key then
					tree_el := search_character_tree (s.substring (l_key.count + 1, s.count))
					Result := tree_el /= Void and then tree_el.has (a_item, s.substring (l_key.count + 1, s.count))
				end
			else
				Result := (s ~ key and then a_item ~ item)
			end
		end

	get_item_with_key (s: STRING_32): detachable G
			-- Get an item in the tree that has as key `s',
			-- return Void otherwise.
		require
			a_key_exists: s /= Void
		local
			tree_el: detachable CHARACTER_TREE[G]
		do
			if not is_leaf then
				if attached key as l_key then
					tree_el := search_character_tree (s.substring (l_key.count + 1, s.count))
					if tree_el /= Void then
						Result := tree_el.get_item_with_key (s.substring (l_key.count + 1, s.count))
					end
				end
			elseif key ~ s then
				Result := item
			end
		end

feature {CHARACTER_TREE} -- Information

	key_corresponds (a_key: STRING_32): BOOLEAN
			-- Does `a_key' correspond to a_string?
		require
			a_string_not_void: a_key /= Void
		do
			if key /= Void then
				Result := minimum_distance (a_key, key) > 0
			end
		end

feature {NONE} -- character_trees_list

	character_trees_list: detachable LINKED_LIST [CHARACTER_TREE[G]]
			-- List of all subtrees

	search_character_tree (a_string: STRING_32): detachable CHARACTER_TREE[G]
			-- Search for a tree that represents a_string,
			-- return Void if not found.
		require
			a_string_not_void: a_string /= Void
		local
			l_tree: detachable CHARACTER_TREE [G]
		do
			if attached character_trees_list as l_list then
					-- User move to front method.
				from
					l_list.start
				until
					Result /= Void or l_list.after
				loop
					if l_list.item.key_corresponds(a_string) then
						l_tree := l_list.item
						check l_tree /= Void end
						Result := l_tree
						Result := Result.twin
						l_list.remove
						l_list.put_front (Result)
						l_list.start
	 					Result := l_list.item
					else
						l_list.forth
					end
				end
			end
		end

	insert_character_tree (a_item: G; a_key: STRING_32)
			-- If `key' and `character_trees_list' are set, insert in
			-- `character_trees_list' a subtree with `a_item' as an
			-- element and `a_key' as a key. If necessary, update `key'
			-- and all keys of the subtrees.
		local
			l_tree, new_tree: CHARACTER_TREE[G]
			distance: INTEGER
			l_str: STRING_32
			l_list: like character_trees_list
		do
			l_list := character_trees_list
			if attached key as l_key and l_list /= Void then
				distance := minimum_distance (a_key, l_key)
				if distance < l_key.count  then
					l_str := l_key.substring (distance+1, l_key.count)
					create new_tree.make (l_str, l_list)

					create l_list.make
					l_list.extend (new_tree)
					character_trees_list := l_list
					l_key.keep_head (distance)
				end
				create l_tree
				l_tree.insert (a_item, a_key.substring (l_key.count+1, a_key.count))
				l_list.put_front (l_tree)
			end
		end

feature {NONE} -- Information

	is_leaf: BOOLEAN
			-- Is current element a leaf?
		do
			Result := character_trees_list = Void
		end

	key: detachable STRING_32

	prepend_to_key (a_string: STRING_32)
			-- Prepend `a_string' to `key' if set.
		require
			a_string_not_void: a_string /= Void
		do
			if attached key as l_key then
				key := a_string + l_key
			end
		end

	item: detachable G

	default_item: detachable G
		do
		end

feature {NONE} -- Measurement

	minimum_distance (a_key: STRING_32; a_reference_key: detachable STRING_32): INTEGER
			-- Find distance between `a_key' and `a_reference_key', and `0' if `a_reference_key' is not set.
			-- Result is the amount of equal characters from the beginning
			-- of the two strings
		require
			a_key_not_void: a_key /= Void
		do
			if a_reference_key /= Void then
				from
					Result := 1
				until
					Result > a_key.count.min (a_reference_key.count) or else
					a_key.item (Result) /= a_reference_key.item (Result)
				loop
					Result := Result + 1
				end
				Result := Result - 1
			else
				Result := 0
			end
		end

feature -- Output

	print_tree (t: INTEGER): STRING_32
			-- Printable representation of the current tree,
			-- `t' is a depth of the current item.
		local
			i : INTEGER
			spaces: STRING_32
			l_key, l_item: STRING
		do
			create spaces.make_filled (' ', t*2)
			if attached key as k then
				l_key := k.out
			else
				l_key := ""
			end
			if attached item as it then
				l_item := it.out
			else
				l_item := ""
			end
			if is_leaf then
				Result := spaces + "LEAF with item: " + l_item + " (" + l_key + ")%N"
			else
				if attached character_trees_list as l_list then
					Result := spaces+"NODE with key: "+l_key+"%N"
					from
						l_list.start
						i := 1
					until
						l_list.after
					loop
						spaces.make_filled (' ', (t + 1) * 2)
						Result.append (spaces+i.out+"th child%N"+l_list.item.print_tree (t+2))
						l_list.forth
						i := i + 1
					end
				else
					Result := {STRING_32} "Empty node%N"
				end
			end
		end


invariant
	is_leaf_implies_character_trees_list: is_leaf implies character_trees_list = Void
	is_leaf_implies_key_not_void: not is_leaf implies key /= Void and character_trees_list /= Void

note
	library:   "Internationalization library"
	copyright: "Copyright (c) 1984-2014, 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 -- Class CHARACTER_TREE