note
	description: "Cache for data, the index is an integer number"
	legal: "See notice at end of class."
	status: "See notice at end of class.";
	date: "$Date$";
	revision: "$Revision$"

class CACHE [T -> IDABLE]

inherit
	TO_SPECIAL [detachable SPECIAL [H_CELL [T]]]
		export
			{NONE} all
		end

	SHARED_CONFIGURE_RESOURCES

create
	make

feature -- Initialisation

	make
			-- Creates a table of Cache_size hash_entry
		local
			s, i: INTEGER
			l_special: like last_item_special
		do
			s := Cache_size
			count := 0
			size := s
			make_filled_area (Void, s)
			create history.make (s)
			create index.make_filled (0, s)
			create free_h_cells.make_empty (1)
			from
			until
				i = s
			loop
					-- Hard coded size for initial setup.
				create l_special.make_empty (5)
				area.put (l_special, i)
				i := i + 1
			end
		end

feature -- Cache manipulations

	has_id (id: INTEGER): BOOLEAN
			-- Is an item of id `i' in the cache ?
		require
			not_void: id /= 0
		local
			i, j: INTEGER
			l_special: like last_item_special
		do
			i := id \\ Size
			from
				l_special := area.item (i)
				j := l_special.count
			until
				j = 0 or else Result
			loop
				j := j - 1
				Result := l_special.item (j).item.id = id
			end

			debug ("CACHE")
				if Size < 500 then
					from
						i :=  0
						j := Size
					until
						i = j
					loop
						io.put_integer (area.item (i).count)
						if i /= 0 and then i \\ 80 = 0 then
							io.put_string (" \%N")
						else
							io.put_string ("-")
						end
						i := i + 1
					end
				end

				io.put_string ("%N")
				io.put_string (generator)
				io.put_string (" has a total of: ")
				io.put_integer (Count)
				io.put_string ("%N")
				io.put_string ("Result of the has_id: ")
				io.put_boolean (Result)
				io.put_string ("%N%N")
			end

			debug ("CACHE_STAT")
				nb_has_id := nb_has_id + 1
				if Result then
					nb_has_id_succeded := nb_has_id_succeded + 1
				end
				success_has_id := (nb_has_id_succeded / nb_has_id).truncated_to_real
				success := ((nb_has_id_succeded + nb_item_id_succeded) / (nb_has_id + nb_item_id)).truncated_to_real
				io.put_string (generator)
				io.put_string ("%NNumber of has_id: ")
				io.put_integer (nb_has_id)
				io.put_string ("%NProportion of has_id succeded: ")
				io.put_real (success_has_id)
				io.put_string ("%NProportion of access succeded: ")
				io.put_real (success)
				io.put_string ("%N%N")
			end
		end

	item_id (id: INTEGER): T
			-- Item which id is `an_id'
			-- Void if not found
		require
			not_void: id /= 0
		local
			i, j: INTEGER
			l_special: like last_item_special
			tmp: H_CELL [T]
			found: BOOLEAN
		do
			i := id \\ Size
			from
				l_special := area.item (i)
				j := l_special.count
			until
				j = 0 or else found
			loop
				j := j - 1
				found := l_special.item (j).item.id = id
			end
			if found then
					-- we make the accessed item younger
				tmp := l_special.item (j)
				Result := tmp.item
				history.make_younger (tmp.index)
				tmp.set_index (history.younger)
				last_item_special := l_special
				last_item_pos := j
			end

			debug ("CACHE")
				if Size < 500 then
					from
						i :=  0
						j := Size
					until
						i = j
					loop
						io.put_integer (area.item (i).count)
						if i /= 0 and then i \\ 80 = 0 then
							io.put_string (" \%N")
						else
							io.put_string ("-")
						end
						i := i + 1
					end
				end
				io.put_string ("%N")
				io.put_string (generator)
				io.put_string (" has a total of: ")
				io.put_integer (Count)
				io.put_string ("%NResult of the item_id:")
				io.put_boolean (found)
				io.put_string ("%N%N")
			end

			debug ("CACHE_STAT")
				nb_item_id := nb_item_id + 1
				if found then
					nb_item_id_succeded := nb_item_id_succeded + 1
				end
				success_item_id := (nb_item_id_succeded / nb_item_id).truncated_to_real
				success := ((nb_has_id_succeded + nb_item_id_succeded) / (nb_has_id + nb_item_id)).truncated_to_real
				io.put_string (generator)
				io.put_string ("%NNumber of item_id: ")
				io.put_integer (nb_item_id)
				io.put_string ("%NProportion of item_id succeded: ")
				io.put_real (success_item_id)
				io.put_string ("%NProportion of access succeded: ")
				io.put_real (success)
				io.put_string ("%N%N")
			end
		end

	remove_id (id: INTEGER)
			-- Remove item of id `i' form cache.
			-- better use force instead
		require
			not_void: id /= 0
		local
			i, j, nb: INTEGER
			found: BOOLEAN
			l_special: like last_item_special
			tmp: H_CELL [T]
			l_default: T
		do
			i := id \\ Size
			from
				l_special := area.item (i)
				nb := l_special.count
				j := nb
			until
				j = 0 or else found
			loop
				j := j - 1
				found := l_special.item (j).item.id = id
			end
			debug ("CACHE_RESEARCH")
				if not found then
					io.put_string ("Be carefull: object not found%N")
				end
			end
			if found then
				count := count - 1
				tmp := l_special.item (j)
				last_removed_item := tmp.item
				history.remove (tmp.index)
				if j < nb - 1 then
					l_special.overlapping_move (j + 1, j, nb - j - 1)
				end
				if free_h_cells.count = free_h_cells.capacity then
					free_h_cells := free_h_cells.aliased_resized_area (free_h_cells.count * 2)
				end
				tmp.set_item (l_default)
				free_h_cells.extend (tmp)
				l_special.remove_tail (1)
			end
		end

	force (e: T)
			-- like put if full remove an element
			-- to put our new one
		require
			not_void: e /= Void
			not_has_id: not has_id (e.id)
		local
			i, t: INTEGER
			l_special: like last_item_special
			h_cell: H_CELL [T]
			to_remove: T
			l_default: T
		do
			i := e.id \\ Size
			l_special := area.item (i)
			history.add (e)
			to_remove := history.to_remove
			if to_remove /= Void then
				internal_remove (to_remove)
			else
				last_removed_item := l_default
				count := count + 1
			end
			if free_h_cells.count >= 1 then
				h_cell := free_h_cells.item (free_h_cells.count - 1)
				free_h_cells.remove_tail (1)
				h_cell.make (e, history.younger)
			else
				create h_cell.make (e, history.younger)
			end
			t := l_special.capacity
			if l_special.count = t then
				l_special := l_special.aliased_resized_area (2 * t)
				area.put (l_special, i)
			end
			l_special.extend (h_cell)
		end

	is_full: BOOLEAN
			-- is the cache full ?
		do
			Result := count >= size
		end

	is_empty: BOOLEAN
			-- is the cache empty ?
		do
			Result := count = 0
		end

	wipe_out
			-- wipe all out
		local
			s: INTEGER
			l_area: like area
		do
			from
				s := Size
				l_area := area
			until
				s = 0
			loop
				s := s - 1
				l_area.item (s).wipe_out
			end
			history.wipe_out
			count := 0
			after := True
			free_h_cells.wipe_out
			free_h_cells := free_h_cells.aliased_resized_area (5)
		end

	change_last_item (e: T)
			-- make e take the place of the last item consulted
		local
			tmp: H_CELL [T]
		do
			tmp := last_item_special.item (last_item_pos)
			tmp.set_item (e)
			history.set_item (e,tmp.index)
		end

	history: CACHE_HISTORY [T]
			-- history of the arrivals in the cache

	index: SPECIAL [INTEGER]
			-- index of each item in the history

	count: INTEGER
			-- number of item currently in the cache

	size: INTEGER
			-- maximum number of items in the cache

	last_removed_item: T
			-- last automaticly removed item by function force

feature -- linear iteration

	start
			-- put item_for_iteration on the first element of the cache
		do
			if is_empty then
				after := True
			else
				last_item_array_number := 0
				last_item_pos := -1
				after := False
				forth
			end
		end

	after: BOOLEAN

	forth
			-- put item_for_iteration on the next element of the cache
		local
			item_array, item_number: INTEGER
			l_special: like last_item_special
			l_area: like area
			found: BOOLEAN
		do
			from
				l_area := area
				item_array := last_item_array_number
				item_number := last_item_pos + 1
			until
				found or else item_array = size
			loop
				l_special:= l_area.item (item_array)
				found := item_number < l_special.count
				if not found then
					item_array := item_array + 1
					item_number := 0
				end
			end
			if not found then
				after := True
			else
				last_item_special := l_special
				last_item_array_number := item_array
				last_item_pos := item_number
			end
		end

	item_for_iteration: T
			-- give the item in a linear ?????
		do
			Result := last_item_special.item (last_item_pos).item
		end

feature {NONE} -- Implementation

	cache_size: INTEGER
			-- Cache size
		local
			s: STRING
			l_int: INTERNAL
		do
			create l_int
			if l_int.generic_count (Current) > 0 then
				s := l_int.class_name_of_type (l_int.generic_dynamic_type (Current, 1))
			else
				s := generator
			end
			s.to_lower
			Result := Configure_resources.get_integer (s, default_value)

			debug ("CACHE_SERVER")
				io.error.put_string ("Size of ")
				io.error.put_string (generator)
				io.error.put_string (" is ")
				io.error.put_integer (Result)
				io.error.put_new_line
			end
		end;

	default_value: INTEGER
			-- Default value of cache
		do
			Result :=  Configure_resources.get_integer (r_cache_size, 20)
		end;

	last_item_special: SPECIAL [detachable H_CELL [T]]
		-- the array in which the last searched item
		-- was found

	last_item_pos: INTEGER
		-- the position in which the last
		-- searched item was found

	last_item_array_number: INTEGER
		-- the number of last_item_special	

feature {NONE} -- to implement force

	internal_remove (e: T)
			-- Remove item of id `i' from cache.
			-- but do not touch the history nor count
		require
			not_void: e /= Void
		local
			i, j, nb: INTEGER
			found: BOOLEAN
			id: INTEGER
			l_special: like last_item_special
			tmp: H_CELL [T]
			l_default: T
		do
			id := e.id
			i := id \\ Size
			from
				l_special := area.item (i)
				nb := l_special.count
				j := nb
			until
				j = 0 or else found
			loop
				j := j - 1
				found := l_special.item (j).item.id = id
			end
			debug ("CACHE_RESEARCH")
				if not found then
					io.put_string ("Be carefull: object not found%N")
				end
			end
			if found then
					-- found IS true
					-- the if is to avoid a bug I didn't find (yet)
					-- in the cache history
				tmp := l_special.item (j)
				last_removed_item := tmp.item
				if j < nb - 1 then
						-- Shift right elements to the left only if they are right elements
					l_special.overlapping_move (j + 1, j, nb - j - 1)
				end
				if free_h_cells.count = free_h_cells.capacity then
					free_h_cells := free_h_cells.aliased_resized_area (free_h_cells.count * 2)
				end
				tmp.set_item (l_default)
				free_h_cells.extend (tmp)
				l_special.remove_tail (1)
			end
		end

feature {NONE} -- statistics

	nb_has_id: INTEGER
		-- number of call to has_id

	nb_item_id: INTEGER
		-- number of call to item_id

	nb_has_id_succeded: INTEGER
		-- number of succeded call to has_id

	nb_item_id_succeded: INTEGER
		-- number of succeded call to item_id

	success_has_id: REAL
		-- proportion of successful calls to has_id

	success_item_id: REAL
		-- proportion of successful calls to item_id

	success: REAL
		-- proportion of successful researchs in the cache

	free_h_cells: SPECIAL [H_CELL [T]];
			-- Buffer for unused H_CELL instances.

note
	copyright:	"Copyright (c) 1984-2011, Eiffel Software"
	license:	"GPL version 2 (see http://www.eiffel.com/licensing/gpl.txt)"
	licensing_options:	"http://www.eiffel.com/licensing"
	copying: "[
			This file is part of Eiffel Software's Eiffel Development Environment.
			
			Eiffel Software's Eiffel Development Environment is free
			software; you can redistribute it and/or modify it under
			the terms of the GNU General Public License as published
			by the Free Software Foundation, version 2 of the License
			(available at the URL listed under "license" above).
			
			Eiffel Software's Eiffel Development Environment is
			distributed in the hope that it will be useful, but
			WITHOUT ANY WARRANTY; without even the implied warranty
			of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
			See the GNU General Public License for more details.
			
			You should have received a copy of the GNU General Public
			License along with Eiffel Software's Eiffel Development
			Environment; if not, write to the Free Software Foundation,
			Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
		]"
	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 CACHE