note description: "Implementation of DICTIONARY that stores entries in a sorted array and uses binary search to retrieve them" legal: "See notice at end of class." status: "See notice at end of class." date: "$Date: 2006-10-02 09:59:08 (Mon, 02 Oct 2006)$" revision: "$Revision$" class I18N_BINARY_SEARCH_ARRAY_DICTIONARY -- the `array' should be sorted -- the `size' of `array' should be given by its client,which is not the case any more -- the index of `array' arranges from 1 to max_index, but which could also be resible -- max_index should be >=1 -- I think there is something wrong with `array.full' in class ARRAY, that is implemation from Eiffel inherit I18N_DICTIONARY redefine make end create make feature {NONE} --Creation make (a_plural_form: INTEGER) -- create the datastructure do Precursor (a_plural_form) create array.make_empty current_index := 1 end feature --Insertion extend (a_entry: I18N_DICTIONARY_ENTRY) -- a_entry is not duplicated, duplicate is precondition -- add an entry to `array' without sorting it -- auto resize when the capacity of `array' is filled -- without duplicate check, let insertion_sort do it do array.force (a_entry, current_index) current_index := current_index + 1 search_index_and_insert end feature {NONE} -- help functions search_index_and_insert -- `array' is sorted except the last inserted element -- after every `insert' is insertion_sort is called -- compare with its neighbour recursively until the right_index for it is found -- subcopy `array' from the right_index to current_index-2 to position from right_index-1 -- put the last_input in `array' with right_index local left, right, middle: INTEGER cur_entry, l_entry1, l_entry2: detachable I18N_DICTIONARY_ENTRY mid_entry: detachable I18N_DICTIONARY_ENTRY right_index: INTEGER l_last_index: INTEGER do -- one element case will do nothing l_last_index := current_index - 1 if (l_last_index > 1) then cur_entry := array.item (l_last_index) l_entry1 := array.item (1) l_entry2 := array.item (l_last_index - 1) if cur_entry < l_entry1 then right_index := 1 elseif cur_entry > l_entry2 then right_index := l_last_index else --cur_entry < array.item (l_last_index-1) and cur_entry > array.item(1) -- search the right index for the last inserted elem -- with binary search from left := 2 right := l_last_index - 2 until left > right loop middle := ((left + right).as_natural_32 |>> 1).as_integer_32 mid_entry := array.item (middle) if cur_entry < mid_entry then right := middle - 1 else left := middle + 1 end end right_index := left end -- put the last inserted elem in the right index if right_index /= l_last_index then array.subcopy (array, right_index, l_last_index - 1, right_index + 1) array.put (cur_entry, right_index) end end end has_index (a_id: READABLE_STRING_GENERAL): INTEGER -- does the dictionary have this entry? -- use binary search algorithm -- require `array' is sorted -- return the Index of the found item -- return -1 if not found -- based only on the `key item', no info about translation items require original_not_void: a_id /= Void local left, right, middle: INTEGER m_string: STRING_32 found: BOOLEAN l_id: STRING_32 l_last_index: INTEGER do from l_last_index := current_index - 1 left := min_index right := l_last_index l_id := a_id.as_string_32 invariant right < l_last_index implies (attached array.item (right + 1) as l_item1 and then attached array.item (l_last_index) as l_item2 and then l_item1 <= l_item2) left <= l_last_index and left > min_index implies (attached array.item (left - 1) as l_item3 and then attached array.item (l_last_index) as l_item4 and then l_item3 <= l_item4) until left > right or found loop middle := ((left + right).as_natural_32 |>> 1).as_integer_32 if attached array.item (middle) as l_m then m_string := l_m.identifier else check always_has_item: False end create m_string.make_empty end if l_id < m_string then right := middle - 1 elseif l_id > m_string then left := middle + 1 ---?? i do not know whether original could be used or not else --Found found := True Result := middle left := left + 1 -- not nice but required to decrease variant end variant right - left + 1 end if found = False then Result := -1 end end feature -- Query has_in_context (original: READABLE_STRING_GENERAL; a_context: detachable READABLE_STRING_GENERAL): BOOLEAN -- Does the dictionary have this entry? -- use binary search algorithm -- require `array'is sorted -- use has_index has a help function local index: INTEGER do index := has_index (id_from_original_and_context (original, a_context)) if index /= -1 then Result := True end end singular_in_context (original: READABLE_STRING_GENERAL; a_context: detachable READABLE_STRING_GENERAL): detachable STRING_32 -- Singular form local index: INTEGER do index := has_index (id_from_original_and_context (original, a_context)) if index /= -1 and then attached array.item (index) as l_entry then Result := l_entry.singular_translation end end plural_in_context (original_singular, original_plural: READABLE_STRING_GENERAL; plural_number: INTEGER; a_context: detachable READABLE_STRING_GENERAL): detachable STRING_32 -- Plural form local index: INTEGER do index := has_index (id_from_original_and_context (original_singular, a_context)) if index /= -1 and then attached array.item (index) as l_entry and then l_entry.has_plural then Result := l_entry.plural_translations.item (reduce (plural_number)) end end feature --Information count: INTEGER do Result := current_index - 1 end feature {NONE} -- Implementation array: ARRAY [I18N_DICTIONARY_ENTRY] min_index: INTEGER = 1 current_index: INTEGER -- the index which is to be filled next invariant count_equal_current_index: count = current_index - 1 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