indexing

	description: "[

		Lagrante interpolator.

	]"
	date: "$Date$"
	revision: "$Revision$"

class	EM_LAGRANGE_INTERPOLATOR[NUM -> NUMERIC]

create

	make

feature -- Initialisation

	make is
			-- Init
		do
			create gamma.make
		end

feature -- Access

	evaluate (x: NUM): NUM is
			-- Evaluate lagrange polynomial at position x.
		local
			c: DS_LINEAR_CURSOR[EM_PAIR[NUM,NUM]]
			i,j: INTEGER
			g: NUM
		do
			Result := Result.zero
			from
				gamma.start
				i:=0
			until
				gamma.after
			loop

				from
					c := samples.new_cursor
					c.start
					j := 0
					g := g.one
				until
					c.after
				loop
					if j /= i then
						g := g * (x - c.item.first)
					end
					c.forth
					j := j + 1
				end
				Result := Result + g * gamma.item_for_iteration
				gamma.forth
				i := i + 1
			end
		end

feature -- Element change

	set_samples (some_samples: DS_LINEAR[EM_PAIR[NUM,NUM]]) is
			-- Set sample points
		require
			some_samples_not_void: some_samples /= Void
		local
			c1,c2: DS_LINEAR_CURSOR[EM_PAIR[NUM,NUM]]
			i,j: INTEGER
			g: NUM
		do
			create gamma.make
			samples := some_samples
			from
				c1 := samples.new_cursor
				c1.start
				i := 0
			until
				c1.after
			loop
				from
					c2 := samples.new_cursor
					c2.start
					j := 0
					g := g.one
				until
					c2.after
				loop
					if j /= i then
						g := g * (c1.item.first - c2.item.first)
					end
					c2.forth
					j := j + 1
				end
				gamma.put_last (c1.item.second / g)
				c1.forth
				i := i + 1
			end
		end

feature {NONE} -- Implementation

	samples: DS_LINEAR[EM_PAIR[NUM,NUM]]
			-- Samples used for interpolation

	gamma: DS_LINKED_LIST[NUM]
			-- Gamma holds the constant factors of the polynomial

invariant
	count_equal: samples /= Void implies gamma.count = samples.count

end