text:
################################################################################
#
#  Deepcopy
#
################################################################################

function Base.deepcopy_internal(x::NfRelOrdElem, dict::IdDict)
  z = parent(x)()
  z.elem_in_nf = Base.deepcopy_internal(x.elem_in_nf, dict)
  if x.has_coord
    z.has_coord = true
    z.coordinates = Base.deepcopy_internal(x.coordinates, dict)
  end
  return z
end

################################################################################
#
#  Parent object overloading
#
################################################################################

@doc Markdown.doc"""
      (O::NfRelOrd)(a::NumFieldElem, check::Bool = true) -> NfRelOrdElem

Given an element $a$ of the ambient number field of $\mathcal O$, this
function coerces the element into $\mathcal O$. If `check` is `true`
it will be checked that $a$ is contained in $\mathcal O$.
"""
function (O::NfRelOrd)(a::NumFieldElem{T}, check::Bool = true) where T
  if check
    x, y = _check_elem_in_order(a, O)
    !x && error("Number field element not in the order.")
    return NfRelOrdElem{T}(O, deepcopy(a), y)
  else
    return NfRelOrdElem{T}(O, deepcopy(a))
  end
end

@doc Markdown.doc"""
      (O::NfRelOrd)(a::NfRelOrdElem, check::Bool = true) -> NfRelOrdElem

Given an element $a$ of some order in the ambient number field of
$\mathcal O$, this function coerces the element into $\mathcal O$.
If `check` is `true` it will be checked that $a$ is contained in
$\mathcal O$.
"""
(O::NfRelOrd)(a::NfRelOrdElem{T}, check::Bool = true) where {T} = O(nf(O)(a.elem_in_nf), check)

function (O::NfRelOrd)(a::Vector{T}, check::Bool = true) where T
  t = nf(O)()
  basis = basis_nf(O, copy = false)
  for i = 1:degree(O)
    t += a[i]*basis[i]
  end
  s = O(t, check)
  s.coordinates = a
  s.has_coord = true
  return s
end

(O::NfRelOrd)(a::NfOrdElem, check::Bool = true) = O(nf(O)(a.elem_in_nf), check)

(O::NfRelOrd)(a::Union{fmpz, Integer}) = O(nf(O)(a))

@doc Markdown.doc"""
      (O::NfRelOrd)() -> NfRelOrdElem

Constructs a new element of $\mathcal O$ which is set to $0$.
"""
(O::NfRelOrd{T, S})() where {T, S} = NfRelOrdElem{T}(O)

################################################################################
#
#  Parent
#
################################################################################

@doc Markdown.doc"""
      parent(a::NfRelOrdElem) -> NfRelOrd

Returns the order of which $a$ is an element.
"""
parent(x::NfRelOrdElem{T}) where {T <: NumFieldElem{S} where {S}} = x.parent

parent(x::NfRelOrdElem{nf_elem}) = x.parent

################################################################################
#
#  Element in number field
#
################################################################################

@doc Markdown.doc"""
      elem_in_nf(a::NfRelOrdElem) -> NumFieldElem

Returns the element $a$ considered as an element of the ambient number field.
"""

function elem_in_nf(a::NfRelOrdElem; copy::Bool = true)
  if isdefined(a, :elem_in_nf)
    if copy
      return deepcopy(a.elem_in_nf)
    else
      return a.elem_in_nf
    end
  end
  error("Not a valid order element.")
end

_elem_in_algebra(a; copy::Bool = true) = elem_in_nf(a, copy = copy)

################################################################################
#
#  "Assure" functions for fields
#
################################################################################

function assure_has_coord(a::NfRelOrdElem)
  if a.has_coord
    return nothing
  else
    x, y = _check_elem_in_order(a.elem_in_nf, parent(a))
    !x && error("Not a valid order element.")
    a.coordinates = y
    a.has_coord = true
    return nothing
  end
end

################################################################################
#
#  Coordinates
#
################################################################################

@doc Markdown.doc"""
      coordinates(a::NfRelOrdElem{T}) -> Vector{T}

Returns the coefficient vector of $a$.
"""
function coordinates(a::NfRelOrdElem; copy::Bool = true)
  assure_has_coord(a)
  if copy
    return deepcopy(a.coordinates)
  else
    return a.coordinates
  end
end

################################################################################
#
#  Equality
#
################################################################################

==(a::Hecke.NfRelOrdElem, b::Hecke.NfRelOrdElem) = parent(a) == parent(b) && a.elem_in_nf == b.elem_in_nf

################################################################################
#
#  Special elements
#
################################################################################

@doc Markdown.doc"""
      zero(O::NfRelOrd) -> NfRelOrdElem

Returns the zero element of $\mathcal O$.
"""
zero(O::NfRelOrd) = O(0)

@doc Markdown.doc"""
      one(O::NfRelOrd) -> NfRelOrdElem

Returns the one element of $\mathcal O$.
"""
one(O::NfRelOrd) = O(1)

@doc Markdown.doc"""
      zero(a::NfRelOrdElem) -> NfRelOrdElem

Returns the zero element of the parent of $a$.
"""
zero(a::NfRelOrdElem) = parent(a)(0)

@doc Markdown.doc"""
      one(a::NfRelOrdElem) -> NfRelOrdElem

Returns the one element of the parent of $a$.
"""

one(a::NfRelOrdElem) = parent(a)(1)

################################################################################
#
#  isone/iszero
#
################################################################################

@doc Markdown.doc"""
      isone(a::NfRelOrd) -> Bool

Tests if $a$ is one.
"""

isone(a::NfRelOrdElem) = isone(a.elem_in_nf)

@doc Markdown.doc"""
      iszero(a::NfRelOrd) -> Bool

Tests if $a$ is zero.
"""

iszero(a::NfRelOrdElem) = iszero(a.elem_in_nf)

################################################################################
#
#  String I/O
#
################################################################################

function show(io::IO, a::NfRelOrdElem)
  print(io, a.elem_in_nf)
end

################################################################################
#
#  Unary operations
#
################################################################################

@doc Markdown.doc"""
      -(a::NfRelOrdElem) -> NfRelOrdElem

Returns the additive inverse of $a$.
"""
function -(a::NfRelOrdElem)
  b = parent(a)()
  b.elem_in_nf = - a.elem_in_nf
  if a.has_coord
    b.coordinates = map(x -> -x, a.coordinates)
    b.has_coord = true
  end
  return b
end

################################################################################
#
#  Binary operations
#
################################################################################

@doc Markdown.doc"""
      *(a::NfRelOrdElem, b::NfRelOrdElem) -> NfRelOrdElem

Returns $a \cdot b$.
"""
function *(a::NfRelOrdElem, b::NfRelOrdElem)
  check_parent(a, b)
  c = parent(a)()
  c.elem_in_nf = a.elem_in_nf*b.elem_in_nf
  return c
end

@doc Markdown.doc"""
      +(a::NfRelOrdElem, b::NfRelOrdElem) -> NfRelOrdElem

Returns $a + b$.
"""
function +(a::NfRelOrdElem, b::NfRelOrdElem)
  check_parent(a, b)
  c = parent(a)()
  c.elem_in_nf = a.elem_in_nf + b.elem_in_nf
  if a.has_coord && b.has_coord
    c.coordinates = [ a.coordinates[i] + b.coordinates[i] for i = 1:degree(parent(a))]
    c.has_coord = true
  end
  return c
end

@doc Markdown.doc"""
      -(a::NfRelOrdElem, b::NfRelOrdElem) -> NfRelOrdElem

Returns $a - b$.
"""
function -(a::NfRelOrdElem, b::NfRelOrdElem)
  check_parent(a, b)
  c = parent(a)()
  c.elem_in_nf = a.elem_in_nf - b.elem_in_nf
  if a.has_coord && b.has_coord
    c.coordinates = [ a.coordinates[i] - b.coordinates[i] for i = 1:degree(parent(a))]
    c.has_coord = true
  end
  return c
end

@doc Markdown.doc"""
      divexact(a::NfRelOrdElem, b::NfRelOrdElem, check::Bool) -> NfRelOrdElem

Returns $a/b$. It is assumed that $a/b$ is an element of the same order
as $a$.
"""
function divexact(a::NfRelOrdElem, b::NfRelOrdElem, check::Bool = true)
  t = divexact(a.elem_in_nf, b.elem_in_nf)
  if check
    if !in(t, parent(a))
      error("Quotient not an element of the order.")
    end
  end
  c = parent(a)(t)
  return c
end

################################################################################
#
#  Ad hoc operations
#
################################################################################

for T in [Integer, fmpz]
  @eval begin
    @doc Markdown.doc"""
              *(a::NfRelOrdElem, b::Union{Integer, fmpz}) -> NfRelOrdElem

    > Returns $a \cdot b$.
    """
    function *(a::NfRelOrdElem, b::$T)
      c = parent(a)()
      c.elem_in_nf = a.elem_in_nf*b
      if a.has_coord
        c.coordinates = map(x -> b*x, a.coordinates)
        c.has_coord = true
      end
      return c
    end

    *(a::$T, b::NfRelOrdElem) = b*a

    @doc Markdown.doc"""
              divexact(a::NfRelOrdElem, b::Union{Integer, fmpz}, check::Bool) -> NfRelOrdElem

    > Returns $a/b$. It is assumed that $a/b$ is an element of the same order
    > as $a$.
    """
    function divexact(a::NfRelOrdElem, b::$T, check::Bool = true)
      t = divexact(a.elem_in_nf, b)
      if check
        if !in(t, parent(a))
          error("Quotient not an element of the order.")
        end
      end
      c  = parent(a)(t)
      return c
    end
  end
end

################################################################################
#
#  Exponentiation
#
################################################################################

@doc Markdown.doc"""
    ^(a::NfRelOrdElem, b::Union{fmpz, Int}) -> NfRelOrdElem

Returns $a^b$.
"""
function ^(a::NfRelOrdElem, b::Union{fmpz, Int})
  c = parent(a)()
  c.elem_in_nf = a.elem_in_nf^b
  return c
end

################################################################################
#
#  Unsafe operations
#
################################################################################

function add!(c::NfRelOrdElem, a::NfRelOrdElem, b::NfRelOrdElem)
  c.elem_in_nf = add!(c.elem_in_nf, a.elem_in_nf, b.elem_in_nf)
  c.has_coord = false
  return c
end

function mul!(c::NfRelOrdElem, a::NfRelOrdElem, b::NfRelOrdElem)
  c.elem_in_nf = mul!(c.elem_in_nf, a.elem_in_nf, b.elem_in_nf)
  c.has_coord = false
  return c
end

################################################################################
#
#  Trace
#
################################################################################

@doc Markdown.doc"""
      tr(a::NfRelOrdElem{T}) -> T

Returns the trace of $a$.
"""
tr(a::NfRelOrdElem) = tr(a.elem_in_nf)

################################################################################
#
#  Norm
#
################################################################################

@doc Markdown.doc"""
      norm(a::NfRelOrdElem{T}) -> T

Returns the norm of $a$.
"""
norm(a::NfRelOrdElem) = norm(a.elem_in_nf)

norm(a::NfRelOrdElem, k::Union{ NfRel, AnticNumberField, NfRel_ns, FlintRationalField }) = norm(a.elem_in_nf, k)

absolute_norm(a::NfRelOrdElem) = absolute_norm(a.elem_in_nf)

################################################################################
#
#  Conversion
#
################################################################################

(K::NfRel)(a::NfRelOrdElem) = elem_in_nf(a)

(K::NfRel_ns)(a::NfRelOrdElem) = elem_in_nf(a)

################################################################################
#
#  Representation matrix
#
################################################################################

function representation_matrix(a::NfRelOrdElem)
  O = parent(a)
  A = representation_matrix(elem_in_nf(a))
  A = basis_matrix(O, copy = false)*A*basis_mat_inv(O, copy = false)
  return A
end


text:
mutable struct JacobianWrapper{fType, pType}
    f::fType
    p::pType
end

(uf::JacobianWrapper)(u) = uf.f(u, uf.p)
(uf::JacobianWrapper)(res, u) = uf.f(res, u, uf.p)

struct ImmutableJacobianWrapper{fType, pType}
    f::fType
    p::pType
end

(uf::ImmutableJacobianWrapper)(u) = uf.f(u, uf.p)

function calc_J(solver, cache)
    @unpack u, f, p, alg = solver
    @unpack uf = cache
    uf.f = f
    uf.p = p
    J = jacobian(uf, u, solver)
    return J
end

function calc_J(solver, uf::ImmutableJacobianWrapper)
    @unpack u, f, p, alg = solver
    J = jacobian(uf, u, solver)
    return J
end

function jacobian(f, x, solver)
    if alg_autodiff(solver.alg)
        J = ForwardDiff.jacobian(f, x)
    else
        J = FiniteDiff.finite_difference_jacobian(f, x, solver.alg.diff_type, eltype(x))
    end
    return J
end

function calc_J!(J, solver, cache)
    @unpack f, u, p, alg = solver
    @unpack du1, uf, jac_config = cache

    uf.f = f
    uf.p = p

    jacobian!(J, uf, u, du1, solver, jac_config)
end

function jacobian!(J, f, x, fx, solver, jac_config)
    alg = solver.alg
    if alg_autodiff(alg)
        ForwardDiff.jacobian!(J, f, fx, x, jac_config)
    else
        FiniteDiff.finite_difference_jacobian!(J, f, x, jac_config)
    end
    nothing
end

ext: jl


text:
#**************************************************************************************
# Output_Interface.jl
# =============== part of the GeoEfficiency.jl package.
#
# all the output of the package either to the console or to the csv files is handled here.
#
#**************************************************************************************

#------------------------- consts - globals - imports ----------------

using Compat
using Compat.DelimitedFiles
import Compat: @info, @error

@compat isconst(@__MODULE__, :resultsFolder) || const resultsFolder = "results";
const resultdir	        = joinpath(dataDir, resultsFolder);
const resultdir_pnt     = joinpath(resultdir, "Point");
const resultdir_nonPnt  = joinpath(resultdir, "non-Point");
global countDetectors = 1;

#------------------ checkResultsDirs ----------------------------------

"""# UnExported

	checkResultsDirs()

make sure that directories for saving the results are already exist or create
them if necessary.

"""
function checkResultsDirs()
	mkpath(resultdir_pnt)
	mkpath(resultdir_nonPnt)
	return nothing
end
checkResultsDirs()

#--------------------------- calc ---------------------------------------

"""

	calc(detector::Detector = Detector(), aSource::Tuple{Point, Float64, Float64,} = source())

calculate and display on the `console` the `geometrical efficiency` of the
detector `detector` for the tuple `aSource` describing the source.

**`Throw`** an Error if the source location is inappropriate.

**see also:** [`geoEff(::Detector, ::Tuple{Point, Float64, Float64})`](@ref)

!!! note
     if source description `aSource` alone or even both source description and detector `detect`
     are missing, the method prompt the user to complete the missing data via the `console`.

"""
function calc(detector::RadiationDetector = RadiationDetector(), aSource::Tuple{Point, Real, Real} = source())

	aPnt, srcRadius, srcLength = aSource
	printstyled("\n<$(countDetectors)> $(id(detector))", color=:yellow)
	println("\n - Source(", id(aPnt), ", srcRadius=",srcRadius, ", srcLength=", srcLength, ")")

	calculatedEff::Float64 = geoEff(detector, aPnt, srcRadius, srcLength)
	println("\n - The detector Geometrical Efficiency = ", calculatedEff)

	global countDetectors += 1
	printstyled(repeat(" =",36),"\n\n", color=:red)
	return nothing

end #function

#------------------------ calcN ------------------------------------

"""

    calcN()

calculate and display the `geometrical efficiency` repeatedly.
Prompt the user to input a `detector` and a `source` from the `console`.
Prompt the user `repeatedly` until it exit (give a choice to use the same
detector or a new detector).

"""
function calcN(	detector:: RadiationDetector = RadiationDetector())

	while (true)

		try	calc(detector) end

		res = input("""\n
    	I- To continue make a choice:
			> using the same detector Press 'd'|'D'
			> using a new detector Press 'n'|'N'\n
    	II- To quit just press return\n
			\n\tyour Choice: """, :red) |> lowercase;
		if res == "n"
            detector = RadiationDetector()

		elseif res == "d"
            continue

		else
			break

		end #if

	end #while
	print("\n\t"); @info("The 'calcN' had terminated, Thank you\n")
end #function

#---------------- writecsv_head -----------------------------

""" # unexported

	writecsv_head(filename::AbstractString, content, head=[])

Write `content` to the comma delimited values file `filename`.
optionally with header `head`.

"""
function writecsv_head(filename::AbstractString, content, head=[])
	open(filename, "w") do io
		writedlm(io, head, ',')
		writedlm(io, content, ',')
	end #do
end #function

#---------------- batch() ----------------------------------

"""

    batch()

provide batch calculation of the `geometrical efficiency` based on the information provided
by the **``CSV``** files by default located in **``$(dataDir)``**.

results are saved on a **``CSV``**  file(s) named after the detector(s). the **``CSV``**  file(s)
by default found in **``$(resultdir)``**, also a log of the results are displayed on the `console`.

**for more information on batch refer to [`batchInfo`](@ref).**

"""
batch() = batch(read_batch_info()...)

"""

    batch(
		detector::Detector,
		srcHeights_array::Vector{S},
		srcRhos_array::Vector{S}=[0.0],
		srcRadii_array::Vector{S}=[0.0],
		srcLengths_array::Vector{S}=[0.0],
		ispoint::Bool=true
	) where S <: Real

provide batch calculation of the `geometrical efficiency` for the detector `detector`.
results are saved on a **``CSV``**  file named after the detector.
the **``CSV``**  file by default found in **``$(resultdir)``**. this method return the actual
path to the **``CSV``** file.
also a log of the results are displayed on the `console`.

*  `srcHeights_array`: list of source heights to feed to batch.
*  `srcRhos_array`: list of source off-axis distances to feed to batch.
*  `srcRadii_array`: list of source radii to feed to batch.
*  `srcLengths_array`: list of source lengths to feed to batch.

A set of sources is constructed of every valid **combination** of parameter in the `srcRhos_array`,
`srcRadii_array` and `srcLengths_array` arrays with conjunction with `ispoint`.

!!! warning
    *  If `ispoint` is ``true`` the source type is a point source and the parameters
       in `srcRadii_array` and `srcLengths_array` arrays is completely ignored.
    *  If `ispoint` is ``false`` the parameters in srcRhos_array is completely ignored.

"""
function batch(	detector::RadiationDetector,
				srcHeights_array::Vector{S},
				srcRhos_array::Vector{S}=[0.0],
				srcRadii_array::Vector{S}=[0.0],
				srcLengths_array::Vector{S}=[0.0],
				ispoint::Bool=true) where S <: Real

	return _batch(Val{ispoint},
				detector::RadiationDetector,
				srcHeights_array,
				srcRhos_array,
				srcRadii_array,
				srcLengths_array
				)[3]
end #function

"""

    batch(
		detectors_array::Vector{<: Detector},
	    srcHeights_array::Vector{S},
	    srcRhos_array::Vector{S}=[0.0],
	    srcRadii_array::Vector{S}=[0.0],
	    srcLengths_array::Vector{S}=[0.0],
		ispoint::Bool=true
	) where S <: Real

**same as [`batch(::Detector, ...)`](@ref)** but accept a list of detectors `detectors_array`.
return a list of paths to the **``CSV``** of files (file for each detector) storing the results.

"""
function batch( detectors_array::Vector{T},
	       srcHeights_array::Vector{S},
	       srcRhos_array::Vector{S}=[0.0],
	       srcRadii_array::Vector{S}=[0.0],
	       srcLengths_array::Vector{S}=[0.0],
	       ispoint::Bool=true) where T <: RadiationDetector where S <: Real

	outpaths::Vector{String} = String[]
	for detector = detectors_array
		push!(outpaths ,
			batch(detector,
					srcHeights_array,
					srcRhos_array,
					srcRadii_array,
					srcLengths_array,
					ispoint))

	end # detectors_array

	print("\n\t"); @info("The program terminated, Thank you >>>>\n")
	return outpaths

end #function

"""

    batch(
		detector_info_array::Matrix{S},
		srcHeights_array::Vector{S},
		srcRhos_array::Vector{S}=[0.0],
		srcRadii_array::Vector{S}=[0.0],
		srcLengths_array::Vector{S}=[0.0],
		ispoint::Bool=true
	) where S <: Real

**same as [`batch(::Vector{<: Detector},...)`](@ref)** but provide batch calculation of the
`geometrical efficiency` for the detector in the `detector_info_array` after applying `getDetectors`.
return a list of paths to the **``CSV``** of files (file for each detector) storing the results.

"""
function batch(	detector_info_array::Matrix{S},
				srcHeights_array::Vector{S},
				srcRhos_array::Vector{S}=[0.0],
				srcRadii_array::Vector{S}=[0.0],
				srcLengths_array::Vector{S}=[0.0],
				ispoint::Bool=true) where S <: Real

	return  batch(	getDetectors(detector_info_array),
					srcHeights_array,
					srcRhos_array,
					srcRadii_array,
					srcLengths_array,
					ispoint)
end #function

"""# UnExported

    _batch(
		::Val(true),
		detector::RadiationDetector,
		srcHeights_array::Vector{Float64},
		srcRhos_array::Vector{Float64},
		srcRadii_array::Vector{Float64},
		srcLengths_array::Vector{Float64}
		)

batch calculation for specialized for **``point``** sources.
return a tuple of three arrays the `detector`, the `results`and the path of the **``CSV``**
file containing results.

The `results` has columns of headers `Height`, `Rho`, `GeoEfficiency`.

!!! note
     for all arrays `srcHeights_array`, `srcRhos_array`, `srcRadii_array` and `srcLengths_array`
     element type should be ``Float64``. if any of them have other numerical element type it
     should converted to ``Float64`` using `float` before passing it to this method.

!!! warning
     both `srcRadii_array`, `srcLengths_array` are completely ignored as this method is for point sources.

"""
function _batch(
		::Type{Val{true}},
		detector::RadiationDetector,
		srcHeights_array::Vector{Float64},
		srcRhos_array::Vector{Float64},
		srcRadii_array::Vector{Float64},
		srcLengths_array::Vector{Float64},
		)

	aPnt::Point = Point(0.0, 0.0)
	calculatedEff::Float64 = 0.0
	out_results::Vector{Float64} = Float64[];
	cellLabel = "\n\n<$(countDetectors)>$(id(detector))\n"
	for srcHeight = srcHeights_array
		for srcRho = srcRhos_array
		aPnt = Point(srcHeight, srcRho)

			calculatedEff = try	geoEff(detector, aPnt); catch err;	NaN64 end
			push!(out_results, aPnt.Height, aPnt.Rho, calculatedEff)

			printstyled(cellLabel, color=:yellow)
			println(" - Source: ", id(aPnt))
			println()
			println(" - The detector Geometrical Efficiency = ", calculatedEff)
			printstyled(repeat(" =",36),"\n", color=:red)

		end #for_Rho

	end #for_Height
	results::Matrix{Float64} = reshape(out_results, 3, :) |> transpose
	@info("Saving <$countDetectors> to '$(id(detector)).csv'......\n")
	path = joinpath(resultdir_pnt,  "$(id(detector)).csv")
	try
		writecsv_head(path, results, ["Height" "Rho" "GeoEfficiency"])

	catch err
		@error("'.$(id(detector)).csv': can't be created,\n trying to save results in an alternative file")
		checkResultsDirs() # to make sure the directories do exist
		path = joinpath(resultdir_pnt,  "_$(id(detector)).csv")
		writecsv_head(path, results, ["Height" "Rho" "GeoEfficiency"])

	end #try
	global countDetectors += 1;
	return (detector, results, path) # detector, results are for test purpose

end #function

"""# UnExported

    _batch(
		::Val(false),
		detector::RadiationDetector,
		srcHeights_array::Vector{Float64},
		srcRhos_array::Vector{Float64},
		srcRadii_array::Vector{Float64},
		srcLengths_array::Vector{Float64},
		)

batch calculation for specialized for **``non-point``** sources.
return a tuple of three arrays the `detector`, the `results`and the path of the **``CSV``**
file containing results.

The `results` has columns of headers
`AnchorHeight`, `AnchorRho`, `srcRadius`, `srcLength`, `GeoEfficiency`.

!!! note
    for all arrays `srcHeights_array`, `srcRhos_array`, `srcRadii_array` and `srcLengths_array`
    element type should be ``Float64``. if any of them have other numerical element type it
    should converted to ``Float64`` using `float` before passing it to this method.

"""
function _batch(
		::Type{Val{false}},
		detector::RadiationDetector,
		srcHeights_array::Vector{Float64},
		srcRhos_array::Vector{Float64},
		srcRadii_array::Vector{Float64},
		srcLengths_array::Vector{Float64},
		)

	aPnt::Point = Point(0.0, 0.0)
	out_results::Vector{Float64} = Float64[];
	calculatedEff::Float64 = 0.0
	cellLabel = "\n\n<$(countDetectors)>$(id(detector))\n"
	for srcHeight = srcHeights_array
		for srcRho = srcRhos_array
		aPnt = Point(srcHeight, srcRho)
			for  srcLength = srcLengths_array;
				for srcRadius = srcRadii_array
					try
						calculatedEff = geoEff(detector, aPnt, srcRadius , srcLength)

					catch err
						#isa(err, AssertionError) && @goto(Next_srcLength)
						calculatedEff = NaN

					end #try

					push!(out_results, aPnt.Height, aPnt.Rho, srcRadius, srcLength, calculatedEff)

					printstyled(cellLabel, color=:yellow)
					println(" - Source[Anchor_", id(aPnt), ", srcRadius=",srcRadius, ", srcLength=", srcLength, "]")
					println()
					println(" - The detector Geometrical Efficiency = ", calculatedEff)
					printstyled(repeat(" =",36),"\n", color=:red)

				end #for_srcRadius

			@label(Next_srcLength)
			end #for_srcLength

		end #for_Rho

	@label(Next_Height)
	end #for_Height

	results::Matrix{Float64} = reshape(out_results, 5, :) |> transpose
	@info("Saving <$countDetectors> to '$(id(detector)).csv'......\n")
	path = joinpath(resultdir_nonPnt, "$(id(detector)).csv")
	try
		writecsv_head(path, results, ["AnchorHeight" "AnchorRho" "srcRadius" "srcLength" "GeoEfficiency"])

	catch err
		@error("'$(id(detector)).csv': can't be created,\n trying to save results in an alternative file")
		checkResultsDirs() # to make sue that the directories do exist
		path = joinpath(resultdir_nonPnt, "_$(id(detector)).csv")
		writecsv_head(path, results, ["AnchorHeight" "AnchorRho" "srcRadius" "srcLength" "GeoEfficiency"])

	end #try
	global countDetectors += 1;
	return (detector, results, path) # detector, results are for test purpose

end #function

#------------------- :batchInfo -----------------

"""

The function `batch()` can be called with or without arrangement(s).
The without argument version relay on previously prepared Comma Saved
Values [CSV] files, that can be easily edit by Microsoft Excel,
by default located in the directory **``$dataDir``** .

results of batch calculation are saved on a **``CSV``**  file(s) named after the detector(s).
the **``CSV``**  file by default found in **``$(resultdir)``**.

# CSV input files

*  ``Detectors.csv`` contains the detectors description; The line format is:

		 Crystal_Radius | Crystal_Length | Hole_Radius | Hole_Depth |
    	 ---------------| ---------------|-------------|----------- |

*  ``srcHeights.csv`` contains the source heights;

    	 Source_Heights |
		 ---------------|

*  ``srcRhos.csv`` contains the source off-axis distances;

		 Source_Rhos |
     	 ------------|

*  ``srcRadii.csv`` contains the source radii for disc and cylindrical sources;

		 Source_Radii|
		 ------------|

*  ``srcLengths.csv`` contains the source length for cylindrical sources;

		 Source_Lengths|
		 --------------|

 # CSV results files
 **``CSV``**  file containing the results has columns of headers
 `AnchorHeight`, `AnchorRho`, `srcRadius`, `srcLength`, `GeoEfficiency` for `non-point` sources
 and columns of headers `Height`, `Rho`, `GeoEfficiency` for `point` sources.

!!! note
     for Comma Saved Values [CSV] files each line represent an entry,
     the first line is always treated as the header.

!!! warning
     the program expect each line to contain one number for all CSV files except
     for ``Detectors.csv`` each line should contain at least one number or at
     most four separated numbers.

"""
const batchInfo = nothing


text:
### A Pluto.jl notebook ###
# v0.14.2

using Markdown
using InteractiveUtils

# This Pluto notebook uses @bind for interactivity. When running this notebook outside of Pluto, the following 'mock version' of @bind gives bound variables a default value (instead of an error).
macro bind(def, element)
    quote
        local el = $(esc(element))
        global $(esc(def)) = Core.applicable(Base.get, el) ? Base.get(el) : missing
        el
    end
end

# ╔═╡ a4937996-f314-11ea-2ff9-615c888afaa8
begin
    import Pkg
    Pkg.activate(mktempdir())
    Pkg.add([
        Pkg.PackageSpec(name="Images", version="0.23"),
        Pkg.PackageSpec(name="ImageMagick", version="1"),
        Pkg.PackageSpec(name="TestImages", version="1"),
        Pkg.PackageSpec(name="ImageFiltering", version="0.6"),
        Pkg.PackageSpec(name="PlutoUI", version="0.7"),
        Pkg.PackageSpec(name="BenchmarkTools", version="0.6"),
    ])
    using Images, TestImages, ImageFiltering, Statistics, PlutoUI, BenchmarkTools
end

# ╔═╡ e6b6760a-f37f-11ea-3ae1-65443ef5a81a
md"_homework 3, version 3_"

# ╔═╡ 85cfbd10-f384-11ea-31dc-b5693630a4c5
md"""

# **Homework 4**: _Dynamic programming_
`18.S191`, Spring 2021

This notebook contains _built-in, live answer checks_! In some exercises you will see a coloured box, which runs a test case on your code, and provides feedback based on the result. Simply edit the code, run it, and the check runs again.

_For MIT students:_ there will also be some additional (secret) test cases that will be run as part of the grading process, and we will look at your notebook and write comments.

Feel free to ask questions!
"""

# ╔═╡ 33e43c7c-f381-11ea-3abc-c942327456b1
# edit the code below to set your name and kerberos ID (i.e. email without @mit.edu)

student = (name = "Vidhi Katkoria", kerberos_id = "vidhi")

# you might need to wait until all other cells in this notebook have completed running.
# scroll around the page to see what's up

# ╔═╡ ec66314e-f37f-11ea-0af4-31da0584e881
md"""

Submission by: **_$(student.name)_** ($(student.kerberos_id)@mit.edu)
"""

# ╔═╡ 938185ec-f384-11ea-21dc-b56b7469f798
md"""
#### Intializing packages
_When running this notebook for the first time, this could take up to 15 minutes. Hang in there!_
"""

# ╔═╡ 0f271e1d-ae16-4eeb-a8a8-37951c70ba31
all_image_urls = [
	"https://wisetoast.com/wp-content/uploads/2015/10/The-Persistence-of-Memory-salvador-deli-painting.jpg" => "Salvador Dali — The Persistence of Memory (replica)",
	"https://i.imgur.com/4SRnmkj.png" => "Frida Kahlo — The Bride Frightened at Seeing Life Opened",
	"https://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/Hilma_af_Klint_-_Group_IX_SUW%2C_The_Swan_No._1_%2813947%29.jpg/477px-Hilma_af_Klint_-_Group_IX_SUW%2C_The_Swan_No._1_%2813947%29.jpg" => "Hilma Klint - The Swan No. 1",
	"https://upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Piet_Mondriaan%2C_1930_-_Mondrian_Composition_II_in_Red%2C_Blue%2C_and_Yellow.jpg/300px-Piet_Mondriaan%2C_1930_-_Mondrian_Composition_II_in_Red%2C_Blue%2C_and_Yellow.jpg" => "Piet Mondriaan - Composition with Red, Blue and Yellow",
	"https://user-images.githubusercontent.com/6933510/110993432-950df980-8377-11eb-82e7-b7ce4a0d04bc.png" => "Mario",
]

# ╔═╡ 6dabe5e2-c851-4a2e-8b07-aded451d8058
md"""
### Choose your image

 $(@bind image_url Select(all_image_urls))

Maximum image size: $(@bind max_height_str Select(string.([50,100,200,500]))) pixels. _(Using a large image might lead to long runtimes in the later exercises.)_
"""

# ╔═╡ 0d144802-f319-11ea-0028-cd97a776a3d0
img_original = load(download(image_url));

# ╔═╡ a5271c38-ba45-416b-94a4-ba608c25b897
max_height = parse(Int, max_height_str)

# ╔═╡ 365349c7-458b-4a6d-b067-5112cb3d091f
"Decimate an image such that its new height is at most `height`."
function decimate_to_height(img, height)
	factor = max(1, 1 + size(img, 1) ÷ height)
	img[1:factor:end, 1:factor:end]
end

# ╔═╡ ab276048-f34b-42dd-b6bf-0b83c6d99e6a
img = decimate_to_height(img_original, max_height)

# ╔═╡ b49e8cc8-f381-11ea-1056-91668ac6ae4e
md"""
## Cutting a seam

Below is a function called `remove_in_each_row(img, pixels)`. It takes a matrix `img` and a vector of integers, `pixels`, and shrinks the image by 1 pixel in width by removing the element `img[i, pixels[i]]` in every row. This function is one of the building blocks of the Image Seam algorithm we saw in the lecture.

Read it and convince yourself that it is correct.
"""

# ╔═╡ 90a22cc6-f327-11ea-1484-7fda90283797
function remove_in_each_row(img::Matrix, column_numbers::Vector)
	m, n = size(img)
	@assert m == length(column_numbers) # same as the number of rows

	local img′ = similar(img, m, n-1) # create a similar image with one column less

	for (i, j) in enumerate(column_numbers)
		img′[i, 1:j-1] .= @view img[i, 1:(j-1)]
		img′[i, j:end] .= @view img[i, (j+1):end]
	end
	img′
end

# ╔═╡ 5370bf57-1341-4926-b012-ba58780217b1
removal_test_image = Gray.(rand(4,4))

# ╔═╡ c075a8e6-f382-11ea-2263-cd9507324f4f
md"Let's use our function to remove the _diagonal_ from our image. Take a close look at the images to verify that we removed the diagonal. "

# ╔═╡ 52425e53-0583-45ab-b82b-ffba77d444c8
let
	seam = [3,2,3,4]
	remove_in_each_row(removal_test_image, seam)
end

# ╔═╡ a09aa706-6e35-4536-a16b-494b972e2c03
md"""
Removing the seam `[1,1,1,1]` is equivalent to removing the first column:
"""

# ╔═╡ 268546b2-c4d5-4aa5-a57f-275c7da1450c
let
	seam = [1,1,1,1]
	remove_in_each_row(removal_test_image, seam)
end

# ╔═╡ 6aeb2d1c-8585-4397-a05f-0b1e91baaf67
md"""
If we remove the same seam twice, we remove the first two rows:
"""

# ╔═╡ 2f945ca3-e7c5-4b14-b618-1f9da019cffd
let
	seam = [1,1,1,1]

	result1 = remove_in_each_row(removal_test_image, seam)
	result2 = remove_in_each_row(result1, seam)
	result2
end

# ╔═╡ 318a2256-f369-11ea-23a9-2f74c566549b
md"""
## _Brightness and Energy_
"""

# ╔═╡ 7a44ba52-f318-11ea-0406-4731c80c1007
md"""
First, we will define a `brightness` function for a pixel (a color) as the mean of the red, green and blue values.

You should use this function whenever the problem set asks you to deal with _brightness_ of a pixel.
"""

# ╔═╡ 6c7e4b54-f318-11ea-2055-d9f9c0199341
begin
	brightness(c::RGB) = mean((c.r, c.g, c.b))
	brightness(c::RGBA) = mean((c.r, c.g, c.b))
	brightness(c::Gray) = gray(c)
end

# ╔═╡ 74059d04-f319-11ea-29b4-85f5f8f5c610
Gray.(brightness.(img))

# ╔═╡ 0b9ead92-f318-11ea-3744-37150d649d43
md"""We provide you with a convolve function below.
"""

# ╔═╡ d184e9cc-f318-11ea-1a1e-994ab1330c1a
convolve(img, k) = imfilter(img, reflect(k)) # uses ImageFiltering.jl package
# behaves the same way as the `convolve` function used in our lectures and homeworks

# ╔═╡ cdfb3508-f319-11ea-1486-c5c58a0b9177
float_to_color(x) = RGB(max(0, -x), max(0, x), 0)

# ╔═╡ 5fccc7cc-f369-11ea-3b9e-2f0eca7f0f0e
md"""
finally we define the `energy` function which takes the Sobel gradients along x and y directions and computes the norm of the gradient for each pixel.
"""

# ╔═╡ e9402079-713e-4cfd-9b23-279bd1d540f6
energy(∇x, ∇y) = sqrt.(∇x.^2 .+ ∇y.^2)

# ╔═╡ 6f37b34c-f31a-11ea-2909-4f2079bf66ec
function energy(img)
	∇y = convolve(brightness.(img), Kernel.sobel()[1])
	∇x = convolve(brightness.(img), Kernel.sobel()[2])
	energy(∇x, ∇y)
end

# ╔═╡ 9fa0cd3a-f3e1-11ea-2f7e-bd73b8e3f302
float_to_color.(energy(img))

# ╔═╡ 87afabf8-f317-11ea-3cb3-29dced8e265a
md"""
## **Exercise 1** - _Building up to dynamic programming_

In this exercise and the following ones, we will use the computational problem of Seam carving. We will think through all the "gut reaction" solutions, and then finally end up with the dynamic programming solution that we saw in the lecture.

In the process we will understand the performance and accuracy of each iteration of our solution.

### How to implement the solutions:

For every variation of the algorithm, your job is to write a function which takes a matrix of energies, and an index for a pixel on the first row, and computes a "seam" starting at that pixel.

The function should return a vector of as many integers as there are rows in the input matrix where each number points out a pixel to delete from the corresponding row. (it acts as the input to `remove_in_each_row`).
"""

# ╔═╡ 8ba9f5fc-f31b-11ea-00fe-79ecece09c25
md"""
#### Exercise 1.1 - _The greedy approach_

The first approach discussed in the lecture (included below) is the _greedy approach_: you start from your top pixel, and at each step you just look at the three neighbors below. The next pixel in the seam is the neighbor with the lowest energy.

"""

# ╔═╡ f5a74dfc-f388-11ea-2577-b543d31576c6
html"""
<iframe width="100%" height="450px" src="https://www.youtube.com/embed/rpB6zQNsbQU?start=777&end=833" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
"""

# ╔═╡ 2f9cbea8-f3a1-11ea-20c6-01fd1464a592
random_seam(m, n, i) = reduce((a, b) -> [a..., clamp(last(a) + rand(-1:1), 1, n)], 1:m-1; init=[i])

# ╔═╡ c3543ea4-f393-11ea-39c8-37747f113b96
md"""
👉 Implement the greedy approach.
"""

# ╔═╡ a4e8e45c-9455-11eb-2f8d-c1cf300290c9
function getIndexOfMinimum(v)
	(value, idx) = findmin(v)
	return idx
end

# ╔═╡ 1342aff4-945a-11eb-3e71-e36d9a405a1f
function extend(v::AbstractVector, i)
	println(i)
	if i<1
		return v[1]
	end
	if i>length(v)
		return v[length(v)]
	end
	return v[i]
end

# ╔═╡ abf20aa0-f31b-11ea-2548-9bea4fab4c37
function greedy_seam(energies, starting_pixel::Int)
	m,n = size(energies)
	seam = zeros(Int, m)
	least_neighbour = 1
	least_neighbour_index = -1
	seam[1] = starting_pixel
	j = starting_pixel
	for i ∈ 2:m
		least_neighbour = 1
		for x ∈ -1:1
			if j+x>=1 && j+x<=n && energies[i, j+x]<least_neighbour
				least_neighbour = energies[i, j+x]
				least_neighbour_index = j+x
			end
		end
		j = least_neighbour_index
		seam[i] = least_neighbour_index
	end
	vec(seam)
end

# ╔═╡ 5430d772-f397-11ea-2ed8-03ee06d02a22
md"Before we apply your function to our test image, let's try it out on a small matrix of energies (displayed here in grayscale), just like in the lecture snippet above (clicking on the video will take you to the right part of the video). Light pixels have high energy, dark pixels signify low energy."

# ╔═╡ a4d14606-7e58-4770-8532-66b875c97b70
grant_example = [
	1 8 8 3 5 4
	7 8 1 0 8 4
	8 0 4 7 2 9
	9 0 0 5 9 4
	2 4 0 2 4 5
	2 4 2 5 3 0
] ./ 10

# ╔═╡ 6f52c1a2-f395-11ea-0c8a-138a77f03803
md"Starting pixel: $(@bind greedy_starting_pixel Slider(1:size(grant_example, 2); show_value=true, default=5))"

# ╔═╡ 5057652e-2f88-40f1-82f0-55b1b5bca6f6
greedy_seam_result = greedy_seam(grant_example, greedy_starting_pixel)

# ╔═╡ 2643b00d-2bac-4868-a832-5fb8ad7f173f
let
	s = sum(grant_example[i,j] for (i,j) in enumerate(greedy_seam_result))
	md"""
	**Total energy:** $(round(s,digits=1))
	"""
end

# ╔═╡ 38f70c35-2609-4599-879d-e032cd7dc49d
Gray.(grant_example)

# ╔═╡ 9945ae78-f395-11ea-1d78-cf6ad19606c8
md"_Let's try it on the bigger image!_"

# ╔═╡ 6bac615e-9463-11eb-2210-afa3f2307aa4
greedy_seam, img, grant_example

# ╔═╡ 87efe4c2-f38d-11ea-39cc-bdfa11298317
begin
	# reactive references to uncheck the checkbox when the functions are updated
	greedy_seam, img, grant_example

	md"Compute shrunk image: $(@bind shrink_greedy CheckBox())"
end

# ╔═╡ 52452d26-f36c-11ea-01a6-313114b4445d
md"""
#### Exercise 1.2 - _Recursion_

A common pattern in algorithm design is the idea of solving a problem as the combination of solutions to subproblems.

The classic example, is a [Fibonacci number](https://en.wikipedia.org/wiki/Fibonacci_number) generator.

The recursive implementation of Fibonacci looks something like this
"""

# ╔═╡ 2a98f268-f3b6-11ea-1eea-81c28256a19e
function fib(n)
    # base case (basis)
	if n == 0 || n == 1      # `||` means "or"
		return 1
	end

    # recursion (induction)
	return fib(n-1) + fib(n-2)
end

# ╔═╡ 32e9a944-f3b6-11ea-0e82-1dff6c2eef8d
md"""
Notice that you can call a function from within itself which may call itself and so on until a base case is reached. Then the program will combine the result from the base case up to the final result.

In the case of the Fibonacci function, we added the solutions to the subproblems `fib(n-1)`, `fib(n-2)` to produce `fib(n)`.

An analogy can be drawn to the process of mathematical induction in mathematics. And as with mathematical induction there are parts to constructing such a recursive algorithm:

- Defining a base case
- Defining an recursion i.e. finding a solution to the problem as a combination of solutions to smaller problems.

"""

# ╔═╡ 9101d5a0-f371-11ea-1c04-f3f43b96ca4a
md"""
👉 Define a `least_energy` function which returns:
1. the lowest possible total energy for a seam starting at the pixel at $(i, j)$;
2. the column to jump to on the next move (in row $i + 1$),
which is one of $j-1$, $j$ or $j+1$, up to boundary conditions.

Return these two values in a tuple.
"""

# ╔═╡ 8ec27ef8-f320-11ea-2573-c97b7b908cb7
## returns lowest possible sum energy at pixel (i, j), and the column to jump to in row i+1.
function least_energy(energies, i, j)
	m, n = size(energies)

	if i == m
		return (energies[i,j], j)
	end

	lowest_energy = 1
	lowest_energy_route = j

	for x in max(1,j-1):min(n,j+1)
		y = least_energy(energies, i+1, x)[1]
		if lowest_energy > y
			lowest_energy = y
			lowest_energy_route = x
		end
	end
	return (lowest_energy + energies[i,j], lowest_energy_route)
end

# ╔═╡ ad524df7-29e2-4f0d-ad72-8ecdd57e4f02
least_energy(grant_example, 3, 2)

# ╔═╡ 1add9afd-5ff5-451d-ad81-57b0e929dfe8
grant_example

# ╔═╡ 9c5d5f94-9468-11eb-3cf2-3301537c7025
Gray.(grant_example)

# ╔═╡ 447e54f8-d3db-4970-84ee-0708ab8a9244
md"""
#### Expected output
As shown in the lecture, the optimal seam from the point (1,4) should be:
"""

# ╔═╡ 8b8da8e7-d3b5-410e-b100-5538826c0fde
grant_example_optimal_seam = [4, 3, 2, 2, 3, 3]

# ╔═╡ e1074d35-58c4-43c0-a6cb-1413ed194e25
md"""
So we expect the output of `least_energy(grant_example, 1, 4)` to be:
"""

# ╔═╡ 281b950f-2331-4666-9e45-8fd117813f45
(
	sum(grant_example[i, grant_example_optimal_seam[i]] for i in 1:6),
	grant_example_optimal_seam[2]
)

# ╔═╡ a7f3d9f8-f3bb-11ea-0c1a-55bbb8408f09
md"""
This is elegant and correct, but inefficient! Let's look at the number of accesses made to the energies array needed to compute the least energy seam of a 10x10 image:
"""

# ╔═╡ 18e0fd8a-f3bc-11ea-0713-fbf74d5fa41a
md"Whoa! We will need to optimize this later!"

# ╔═╡ cbf29020-f3ba-11ea-2cb0-b92836f3d04b
begin
	struct AccessTrackerArray{T,N} <: AbstractArray{T, N}
		data::Array{T,N}
		accesses::Ref{Int}
	end

	Base.IndexStyle(::Type{AccessTrackerArray}) = IndexLinear()

	Base.size(x::AccessTrackerArray) = size(x.data)
	Base.getindex(x::AccessTrackerArray, i::Int...) = (x.accesses[] += 1; x.data[i...])
	Base.setindex!(x::AccessTrackerArray, v, i...) = (x.accesses[] += 1; x.data[i...] = v;)

	track_access(x) = AccessTrackerArray(x, Ref(0))
	function track_access(f::Function, x::Array)
		tracked = track_access(x)
		f(tracked)
		tracked.accesses[]
	end
end

# ╔═╡ fa8e2772-f3b6-11ea-30f7-699717693164
track_access(rand(10,10)) do tracked
	least_energy(tracked, 1, 5)
end

# ╔═╡ 8bc930f0-f372-11ea-06cb-79ced2834720
md"""
#### Exercise 1.3 - _Exhaustive search with recursion_

Now use the `least_energy` function you defined above to define the `recursive_seam` function which takes the energies matrix and a starting pixel, and computes the seam with the lowest energy from that starting pixel.

This will give you the method used in the lecture to perform [exhaustive search of all possible paths](https://youtu.be/rpB6zQNsbQU?t=839).
"""

# ╔═╡ 85033040-f372-11ea-2c31-bb3147de3c0d
function recursive_seam(energies, starting_pixel)
	m, n = size(energies)
	# Replace the following line with your code.
	seam = similar(1:m, 1, m)
	seam[1] = starting_pixel
	for i in 2:m
		seam[i] = least_energy(energies, i-1, seam[i-1])[2]
	end
	return vec(seam)
end

# ╔═╡ f92ac3e4-fa70-4bcf-bc50-a36792a8baaa
md"""
We won't use this function to shrink our larger image, because it is too inefficient. (Your notebook might get stuck!) But let's try it on the small example matrix from the lecture, to verify that we have found the optimal seam.
"""

# ╔═╡ 7ac5eb8d-9dba-4700-8f3a-1e0b2addc740
recursive_seam_test = recursive_seam(grant_example, 4)

# ╔═╡ c572f6ce-f372-11ea-3c9a-e3a21384edca
md"""
#### Exercise 1.4

- State clearly why this algorithm does an exhaustive search of all possible paths.
- How does the number of possible seam grow as n increases for a `m×n` image? (Big O notation is fine, or an approximation is fine).
"""

# ╔═╡ 6d993a5c-f373-11ea-0dde-c94e3bbd1552
exhaustive_observation = md"""
• The algorithm does an exhaustive search of all possible paths because at every step, the algorithm looks for a path in 3 bottom directions and computes the total cost of the entire path and then chooses the least energy path. It does not make a local minima choice while determining the seam of the image and hence, all the paths possible will be explored while calculating the least energy path for the image.

• The number of possible seam grow as O($3^n$) as n increases in the image with dimensions mxn.
"""

# ╔═╡ ea417c2a-f373-11ea-3bb0-b1b5754f2fac
md"""
## **Exercise 2** - _Memoization_

**Memoization** is the name given to the technique of storing results to expensive function calls that will be accessed more than once.

As stated in the video, the function `least_energy` is called repeatedly with the same arguments. In fact, we call it on the order of $3^n$ times, when there are only really $m \times n$ unique ways to call it!

Lets implement memoization on this function with first a [dictionary](https://docs.julialang.org/en/v1/base/collections/#Dictionaries) for storage.
"""

# ╔═╡ 56a7f954-f374-11ea-0391-f79b75195f4d
md"""
#### Exercise 2.1 - _Dictionary as storage_

Let's make a memoized version of least_energy function which takes a dictionary and
first checks to see if the dictionary contains the key (i,j) if it does, returns the value stored in that place, if not, will compute it, and store it in the dictionary at key (i, j) and return the value it computed.

`memoized_least_energy(energies, starting_pixel, memory)`

This function must recursively call itself, and pass the same `memory` object it received as an argument.

You are expected to read and understand the [documentation on dictionaries](https://docs.julialang.org/en/v1/base/collections/#Dictionaries) to find out how to:

1. Create a dictionary
2. Check if a key is stored in the dictionary
3. Access contents of the dictionary by a key.
"""

# ╔═╡ b1d09bc8-f320-11ea-26bb-0101c9a204e2
function memoized_least_energy(energies, i, j, memory::Dict)
	m, n = size(energies)

	if i == m
		memory[(i,j)] = (energies[i,j], j)
		return memory[(i, j)]
	end

	lowest_energy = 1
	lowest_energy_route = j

	for x in max(1,j-1):min(n,j+1)
		if (haskey(memory, (i+1, x)))
			y = get(memory, (i+1, x), -1)[1]
		else
			y = memoized_least_energy(energies, i+1, x, memory)[1]
		end
		if lowest_energy > y
			lowest_energy = y
			lowest_energy_route = x
		end
	end
	memory[(i, j)] = (lowest_energy + energies[i,j], lowest_energy_route)
	return memory[(i, j)]
end

# ╔═╡ 1947f304-fa2c-4019-8584-01ef44ef2859
memoized_least_energy_test = memoized_least_energy(grant_example, 1, 4, Dict())

# ╔═╡ 8992172e-c5b6-463e-a06e-5fe42fb9b16b
md"""
Let's see how many matrix access we have now:
"""

# ╔═╡ b387f8e8-dced-473a-9434-5334829ecfd1
track_access(rand(10,10)) do tracked
	memoized_least_energy(tracked, 1, 5, Dict())
end

# ╔═╡ 3e8b0868-f3bd-11ea-0c15-011bbd6ac051
function memoized_recursive_seam(energies, starting_pixel)
	# we set up the the _memory_: note the key type (Tuple{Int,Int}) and
	# the value type (Tuple{Float64,Int}).
	# If you need to memoize something else, you can just use Dict() without types.
	memory = Dict{Tuple{Int,Int},Tuple{Float64,Int}}()

	m, n = size(energies)
	seam = similar(1:m, 1, m)
	seam[1] = starting_pixel
	for i in 2:m
		seam[i] = memoized_least_energy(energies, i-1, seam[i-1], memory)[2]
	end
	return vec(seam)
end

# ╔═╡ d941c199-ed77-47dd-8b5a-e34b864f9a79
memoized_recursive_seam(grant_example, 4)

# ╔═╡ 726280f0-682f-4b05-bf5a-688554a96287
grant_example_optimal_seam

# ╔═╡ cf39fa2a-f374-11ea-0680-55817de1b837
md"""
### Exercise 2.2 - _Matrix as storage_ (optional)

The dictionary-based memoization we tried above works well in general as there is no restriction on what type of keys can be used.

But in our particular case, we can use a matrix as a storage, since a matrix is naturally keyed by two integers.

👉 Write a variant of `matrix_memoized_least_energy` and `matrix_memoized_seam` which use a matrix as storage.
"""

# ╔═╡ c8724b5e-f3bd-11ea-0034-b92af21ca12d
function matrix_memoized_least_energy(energies, i, j, memory::Matrix)
	m, n = size(energies)

	if i == m
		memory[i,j] = (energies[i,j], j)
		return memory[i, j]
	end

	lowest_energy = 1
	lowest_energy_route = j

	for x in max(1,j-1):min(n,j+1)
		if (memory[i+1, x] != nothing)
			y = memory[i+1, x][1]
		else
			y = matrix_memoized_least_energy(energies, i+1, x, memory)[1]
		end
		if lowest_energy > y
			lowest_energy = y
			lowest_energy_route = x
		end
	end
	memory[i, j] = (lowest_energy + energies[i,j], lowest_energy_route)
	return memory[i, j]
end

# ╔═╡ be7d40e2-f320-11ea-1b56-dff2a0a16e8d
function matrix_memoized_seam(energies, starting_pixel)
	memory = Matrix{Union{Nothing, Tuple{Float64,Int}}}(nothing, size(energies))

	# use me instead of you use a different element type:
	# memory = Matrix{Any}(nothing, size(energies))

	m, n = size(energies)

# 	# Replace the following line with your code.
# 	[starting_pixel for i=1:m]

	seam = similar(1:m, 1, m)
	seam[1] = starting_pixel
	for i in 2:m
		seam[i] = matrix_memoized_least_energy(energies, i-1, seam[i-1], memory)[2]
	end
	return vec(seam)

end

# ╔═╡ 507f3870-f3c5-11ea-11f6-ada3bb087634
begin
	matrix_memoized_seam, img

	md"Compute shrunk image: $(@bind shrink_matrix CheckBox())"
end

# ╔═╡ 24792456-f37b-11ea-07b2-4f4c8caea633
md"""
## **Exercise 3** - _Dynamic programming without recursion_

Now it's easy to see that the above algorithm is equivalent to one that populates the memory matrix in a for loop.

#### Exercise 3.1

👉 Write a function which takes the energies and returns the least energy matrix which has the least possible seam energy for each pixel. This was shown in the lecture, but attempt to write it on your own.
"""

# ╔═╡ ff055726-f320-11ea-32f6-2bf38d7dd310
function least_energy_matrix(energies)
	memory = Matrix{Union{Nothing, Tuple{Float64,Int}}}(nothing, size(energies))
	result = copy(energies)
	m,n = size(energies)

	for i ∈ 1:m
		for j ∈ 1:n
			result[i,j] = matrix_memoized_least_energy(energies, i, j, memory)[1]
		end
	end

	return result
end

# ╔═╡ d3e69cf6-61b1-42fc-9abd-42d1ae7d61b2
img_brightness = brightness.(img);

# ╔═╡ 51731519-1831-46a3-a599-d6fc2f7e4224
le_test = least_energy_matrix(img_brightness)

# ╔═╡ e06d4e4a-146c-4dbd-b742-317f638a3bd8
spooky(A::Matrix{<:Real}) = map(sqrt.(A ./ maximum(A))) do x
	RGB(.8x, x, .8x)
end

# ╔═╡ 99efaf6a-0109-4b16-89b8-f8149b6b69c2
spooky(le_test)

# ╔═╡ 92e19f22-f37b-11ea-25f7-e321337e375e
md"""
#### Exercise 3.2

👉 Write a function which, when given the matrix returned by `least_energy_matrix` and a starting pixel (on the first row), computes the least energy seam from that pixel.
"""

# ╔═╡ 795eb2c4-f37b-11ea-01e1-1dbac3c80c13
function seam_from_precomputed_least_energy(energies, starting_pixel::Int)
	least_energies = least_energy_matrix(energies)
	m, n = size(least_energies)

	# # Replace the following line with your code.
	# [starting_pixel for i=1:m]

	seam = zeros(Int, m)
	seam[1] = starting_pixel
	j=starting_pixel
	least_neighbour_index = starting_pixel
	for i ∈ 2:m
		least_neighbour = 1
		for x ∈ -1:1
			if j+x>=1 && j+x<=n && least_energies[i, j+x]<least_neighbour
				least_neighbour = least_energies[i, j+x]
				least_neighbour_index = j+x
			end
		end
		j = least_neighbour_index
		seam[i] = least_neighbour_index
	end
	vec(seam)

end

# ╔═╡ 51df0c98-f3c5-11ea-25b8-af41dc182bac
begin
	img, seam_from_precomputed_least_energy
	md"Compute shrunk image: $(@bind shrink_bottomup CheckBox())"
end

# ╔═╡ 0fbe2af6-f381-11ea-2f41-23cd1cf930d9
if student.kerberos_id === "jazz"
	md"""
!!! danger "Oops!"
    **Before you submit**, remember to fill in your name and kerberos ID at the top of this notebook!
	"""
end

# ╔═╡ 6b4d6584-f3be-11ea-131d-e5bdefcc791b
md"## Function library

Just some helper functions used in the notebook."

# ╔═╡ ef88c388-f388-11ea-3828-ff4db4d1874e
function mark_path(img, path)
	img′ = RGB.(img) # also makes a copy
	m = size(img, 2)
	for (i, j) in enumerate(path)
		if size(img, 2) > 50
			# To make it easier to see, we'll color not just
			# the pixels of the seam, but also those adjacent to it
			for j′ in j-1:j+1
				img′[i, clamp(j′, 1, m)] = RGB(1,0,1)
			end
		else
			img′[i, j] = RGB(1,0,1)
		end
	end
	img′
end

# ╔═╡ 437ba6ce-f37d-11ea-1010-5f6a6e282f9b
function shrink_n(min_seam::Function, img::Matrix{<:Colorant}, n, imgs=[];
		show_lightning=true,
	)

	n==0 && return push!(imgs, img)

	e = energy(img)
	seam_energy(seam) = sum(e[i, seam[i]]  for i in 1:size(img, 1))
	_, min_j = findmin(map(j->seam_energy(min_seam(e, j)), 1:size(e, 2)))
	min_seam_vec = min_seam(e, min_j)
	img′ = remove_in_each_row(img, min_seam_vec)
	if show_lightning
		push!(imgs, mark_path(img, min_seam_vec))
	else
		push!(imgs, img′)
	end
	shrink_n(min_seam, img′, n-1, imgs; show_lightning=show_lightning)
end

# ╔═╡ f6571d86-f388-11ea-0390-05592acb9195
if shrink_greedy
	local n = min(200, size(img, 2))
	greedy_carved = shrink_n(greedy_seam, img, n)
	md"Shrink by: $(@bind greedy_n Slider(1:n; show_value=true))"
end

# ╔═╡ f626b222-f388-11ea-0d94-1736759b5f52
if shrink_greedy
	greedy_carved[greedy_n]
end

# ╔═╡ 4e3bcf88-f3c5-11ea-3ada-2ff9213647b7
begin
	# reactive references to uncheck the checkbox when the functions are updated
	img, memoized_recursive_seam, shrink_n

	md"Compute shrunk image: $(@bind shrink_dict CheckBox())"
end

# ╔═╡ 4e3ef866-f3c5-11ea-3fb0-27d1ca9a9a3f
if shrink_dict
	local n = min(50, size(img, 2))
	dict_carved = shrink_n(memoized_recursive_seam, img, n)
	md"Shrink by: $(@bind dict_n Slider(1:n, show_value=true))"
end

# ╔═╡ 6e73b1da-f3c5-11ea-145f-6383effe8a89
if shrink_dict
	dict_carved[dict_n]
end

# ╔═╡ 50829af6-f3c5-11ea-04a8-0535edd3b0aa
if shrink_matrix
	local n = min(40, size(img, 2))
	matrix_carved = shrink_n(matrix_memoized_seam, img, n)
	md"Shrink by: $(@bind matrix_n Slider(1:n, show_value=true))"
end

# ╔═╡ 9e56ecfa-f3c5-11ea-2e90-3b1839d12038
if shrink_matrix
	matrix_carved[matrix_n]
end

# ╔═╡ 51e28596-f3c5-11ea-2237-2b72bbfaa001
if shrink_bottomup
	local n = min(40, size(img, 2))
	bottomup_carved = shrink_n(seam_from_precomputed_least_energy, img, n)
	md"Shrink by: $(@bind bottomup_n Slider(1:n, show_value=true))"
end

# ╔═╡ 0a10acd8-f3c6-11ea-3e2f-7530a0af8c7f
if shrink_bottomup
	bottomup_carved[bottomup_n]
end

# ╔═╡ ef26374a-f388-11ea-0b4e-67314a9a9094
function pencil(X)
	f(x) = RGB(1-x,1-x,1-x)
	map(f, X ./ maximum(X))
end

# ╔═╡ 6bdbcf4c-f321-11ea-0288-fb16ff1ec526
function decimate(img, n)
	img[1:n:end, 1:n:end]
end

# ╔═╡ ffc17f40-f380-11ea-30ee-0fe8563c0eb1
hint(text) = Markdown.MD(Markdown.Admonition("hint", "Hint", [text]))

# ╔═╡ 9f18efe2-f38e-11ea-0871-6d7760d0b2f6
hint(md"You can call the `least_energy` function recursively within itself to obtain the least energy of the adjacent cells and add the energy at the current cell to get the total energy.")

# ╔═╡ 6435994e-d470-4cf3-9f9d-d00df183873e
hint(md"We recommend using a matrix with element type `Union{Nothing, Tuple{Float64,Int}}`, initialized to all `nothing`s. You can check whether the value at `(i,j)` has been computed before using `memory[i,j] != nothing`.")

# ╔═╡ ffc40ab2-f380-11ea-2136-63542ff0f386
almost(text) = Markdown.MD(Markdown.Admonition("warning", "Almost there!", [text]))

# ╔═╡ ffceaed6-f380-11ea-3c63-8132d270b83f
still_missing(text=md"Replace `missing` with your answer.") = Markdown.MD(Markdown.Admonition("warning", "Here we go!", [text]))

# ╔═╡ ffde44ae-f380-11ea-29fb-2dfcc9cda8b4
keep_working(text=md"The answer is not quite right.") = Markdown.MD(Markdown.Admonition("danger", "Keep working on it!", [text]))

# ╔═╡ 1413d047-099f-48c9-bbb0-ff0a3ddb4888
begin
	function visualize_seam_algorithm(test_energies, algorithm::Function, starting_pixel::Integer)
		seam = algorithm(test_energies, starting_pixel)
		visualize_seam_algorithm(test_energies, seam)
	end
	function visualize_seam_algorithm(test_energies, seam::Vector)
	display_img = RGB.(test_energies)
		for (i, j) in enumerate(seam)
			try
				display_img[i, j] = RGB(0.9, 0.3, 0.6)
			catch ex
				if ex isa BoundsError
					return keep_working("")
				end
				# the solution might give an illegal index
			end
		end
		display_img
	end
end

# ╔═╡ 2a7e49b8-f395-11ea-0058-013e51baa554
visualize_seam_algorithm(grant_example, greedy_seam_result)

# ╔═╡ ffe326e0-f380-11ea-3619-61dd0592d409
yays = [md"Great!", md"Yay ❤", md"Great! 🎉", md"Well done!", md"Keep it up!", md"Good job!", md"Awesome!", md"You got the right answer!", md"Let's move on to the next section."]

# ╔═╡ fff5aedc-f380-11ea-2a08-99c230f8fa32
correct(text=rand(yays)) = Markdown.MD(Markdown.Admonition("correct", "Got it!", [text]))

# ╔═╡ 9ff0ce41-327f-4bf0-958d-309cd0c0b6e5
if recursive_seam_test == grant_example_optimal_seam
	correct()
else
	keep_working()
end

# ╔═╡ 344964a8-7c6b-4720-a624-47b03483263b
let
	result = track_access(rand(10,10)) do tracked
		memoized_least_energy(tracked, 1, 5, Dict())
		end
	if result == 0
		nothing
	elseif result < 200
		correct()
	else
		keep_working(md"That's still too many accesses! Did you forget to add a result to the `memory`?")
	end
end

# ╔═╡ c1ab3d5f-8e6c-4702-ad40-6c7f787f1c43
let
	aresult = track_access(rand(10,10)) do tracked
		memoized_recursive_seam(tracked, 5)
	end
	if aresult < 200
		if memoized_recursive_seam(grant_example, 4) == grant_example_optimal_seam
			correct()
		else
			keep_working(md"The returned seam is not correct. Did you implement the non-memoized version correctly?")
		end
	else
		keep_working(md"Careful! Your `memoized_recursive_seam` is still making too many memory accesses, you may not want to run the visualization below.")
	end
end

# ╔═╡ 00026442-f381-11ea-2b41-bde1fff66011
not_defined(variable_name) = Markdown.MD(Markdown.Admonition("danger", "Oopsie!", [md"Make sure that you define a variable called **$(Markdown.Code(string(variable_name)))**"]))

# ╔═╡ 414dd91b-8d05-44f0-8bbd-b15981ce1210
if !@isdefined(least_energy)
	not_defined(:least_energy)
else
	let
		result1 = least_energy(grant_example, 6, 4)

		if !(result1 isa Tuple)
			keep_working(md"Your function should return a _tuple_, like `(1.2, 5)`.")
		elseif !(result1 isa Tuple{Float64,Int})
			keep_working(md"Your function should return a _tuple_, like `(1.2, 5)`.")
		else
			result = least_energy(grant_example, 1, 4)
			if !(result isa Tuple{Float64,Int})
				keep_working(md"Your function should return a _tuple_, like `(1.2, 5)`.")
			else
				a,b = result

				if a ≈ 0.3 && b == 4
					almost(md"Only search the (at most) three cells that are within reach.")
				elseif a ≈ 0.6 && b == 3
					correct()
				else
					keep_working()
				end
			end
		end
	end
end

# ╔═╡ e0622780-f3b4-11ea-1f44-59fb9c5d2ebd
if !@isdefined(least_energy_matrix)
	not_defined(:least_energy_matrix)
elseif !(le_test isa Matrix{<:Real})
	keep_working(md"`least_energy_matrix` should return a 2D array of Float64 values.")
end

# ╔═╡ 946b69a0-f3a2-11ea-2670-819a5dafe891
if !@isdefined(seam_from_precomputed_least_energy)
	not_defined(:seam_from_precomputed_least_energy)
end

# ╔═╡ fbf6b0fa-f3e0-11ea-2009-573a218e2460
function hbox(x, y, gap=16; sy=size(y), sx=size(x))
	w,h = (max(sx[1], sy[1]),
		   gap + sx[2] + sy[2])

	slate = fill(RGB(1,1,1), w,h)
	slate[1:size(x,1), 1:size(x,2)] .= RGB.(x)
	slate[1:size(y,1), size(x,2) + gap .+ (1:size(y,2))] .= RGB.(y)
	slate
end

# ╔═╡ f010933c-f318-11ea-22c5-4d2e64cd9629
hbox(
	float_to_color.(convolve(brightness.(img), Kernel.sobel()[1])),
	float_to_color.(convolve(brightness.(img), Kernel.sobel()[2])),
)

# ╔═╡ 256edf66-f3e1-11ea-206e-4f9b4f6d3a3d
vbox(x,y, gap=16) = hbox(x', y')'

# ╔═╡ 00115b6e-f381-11ea-0bc6-61ca119cb628
bigbreak = html"<br><br><br><br><br>";

# ╔═╡ c086bd1e-f384-11ea-3b26-2da9e24360ca
bigbreak

# ╔═╡ f7eba2b6-f388-11ea-06ad-0b861c764d61
bigbreak

# ╔═╡ 4f48c8b8-f39d-11ea-25d2-1fab031a514f
bigbreak

# ╔═╡ 48089a00-f321-11ea-1479-e74ba71df067
bigbreak

# ╔═╡ Cell order:
# ╟─e6b6760a-f37f-11ea-3ae1-65443ef5a81a
# ╟─ec66314e-f37f-11ea-0af4-31da0584e881
# ╟─85cfbd10-f384-11ea-31dc-b5693630a4c5
# ╠═33e43c7c-f381-11ea-3abc-c942327456b1
# ╟─938185ec-f384-11ea-21dc-b56b7469f798
# ╠═a4937996-f314-11ea-2ff9-615c888afaa8
# ╟─0f271e1d-ae16-4eeb-a8a8-37951c70ba31
# ╠═6dabe5e2-c851-4a2e-8b07-aded451d8058
# ╠═ab276048-f34b-42dd-b6bf-0b83c6d99e6a
# ╠═0d144802-f319-11ea-0028-cd97a776a3d0
# ╟─a5271c38-ba45-416b-94a4-ba608c25b897
# ╟─365349c7-458b-4a6d-b067-5112cb3d091f
# ╟─b49e8cc8-f381-11ea-1056-91668ac6ae4e
# ╠═90a22cc6-f327-11ea-1484-7fda90283797
# ╠═5370bf57-1341-4926-b012-ba58780217b1
# ╟─c075a8e6-f382-11ea-2263-cd9507324f4f
# ╠═52425e53-0583-45ab-b82b-ffba77d444c8
# ╟─a09aa706-6e35-4536-a16b-494b972e2c03
# ╠═268546b2-c4d5-4aa5-a57f-275c7da1450c
# ╟─6aeb2d1c-8585-4397-a05f-0b1e91baaf67
# ╠═2f945ca3-e7c5-4b14-b618-1f9da019cffd
# ╟─c086bd1e-f384-11ea-3b26-2da9e24360ca
# ╟─318a2256-f369-11ea-23a9-2f74c566549b
# ╟─7a44ba52-f318-11ea-0406-4731c80c1007
# ╠═6c7e4b54-f318-11ea-2055-d9f9c0199341
# ╠═74059d04-f319-11ea-29b4-85f5f8f5c610
# ╟─0b9ead92-f318-11ea-3744-37150d649d43
# ╠═d184e9cc-f318-11ea-1a1e-994ab1330c1a
# ╠═cdfb3508-f319-11ea-1486-c5c58a0b9177
# ╠═f010933c-f318-11ea-22c5-4d2e64cd9629
# ╟─5fccc7cc-f369-11ea-3b9e-2f0eca7f0f0e
# ╠═e9402079-713e-4cfd-9b23-279bd1d540f6
# ╠═6f37b34c-f31a-11ea-2909-4f2079bf66ec
# ╠═9fa0cd3a-f3e1-11ea-2f7e-bd73b8e3f302
# ╟─f7eba2b6-f388-11ea-06ad-0b861c764d61
# ╟─87afabf8-f317-11ea-3cb3-29dced8e265a
# ╟─8ba9f5fc-f31b-11ea-00fe-79ecece09c25
# ╟─f5a74dfc-f388-11ea-2577-b543d31576c6
# ╟─2f9cbea8-f3a1-11ea-20c6-01fd1464a592
# ╟─c3543ea4-f393-11ea-39c8-37747f113b96
# ╠═a4e8e45c-9455-11eb-2f8d-c1cf300290c9
# ╠═1342aff4-945a-11eb-3e71-e36d9a405a1f
# ╠═abf20aa0-f31b-11ea-2548-9bea4fab4c37
# ╟─5430d772-f397-11ea-2ed8-03ee06d02a22
# ╟─6f52c1a2-f395-11ea-0c8a-138a77f03803
# ╠═5057652e-2f88-40f1-82f0-55b1b5bca6f6
# ╠═2a7e49b8-f395-11ea-0058-013e51baa554
# ╟─2643b00d-2bac-4868-a832-5fb8ad7f173f
# ╟─a4d14606-7e58-4770-8532-66b875c97b70
# ╠═38f70c35-2609-4599-879d-e032cd7dc49d
# ╟─1413d047-099f-48c9-bbb0-ff0a3ddb4888
# ╟─9945ae78-f395-11ea-1d78-cf6ad19606c8
# ╠═6bac615e-9463-11eb-2210-afa3f2307aa4
# ╟─87efe4c2-f38d-11ea-39cc-bdfa11298317
# ╟─f6571d86-f388-11ea-0390-05592acb9195
# ╟─f626b222-f388-11ea-0d94-1736759b5f52
# ╟─52452d26-f36c-11ea-01a6-313114b4445d
# ╠═2a98f268-f3b6-11ea-1eea-81c28256a19e
# ╟─32e9a944-f3b6-11ea-0e82-1dff6c2eef8d
# ╟─9101d5a0-f371-11ea-1c04-f3f43b96ca4a
# ╠═8ec27ef8-f320-11ea-2573-c97b7b908cb7
# ╠═ad524df7-29e2-4f0d-ad72-8ecdd57e4f02
# ╠═1add9afd-5ff5-451d-ad81-57b0e929dfe8
# ╠═9c5d5f94-9468-11eb-3cf2-3301537c7025
# ╟─414dd91b-8d05-44f0-8bbd-b15981ce1210
# ╟─447e54f8-d3db-4970-84ee-0708ab8a9244
# ╠═8b8da8e7-d3b5-410e-b100-5538826c0fde
# ╟─e1074d35-58c4-43c0-a6cb-1413ed194e25
# ╠═281b950f-2331-4666-9e45-8fd117813f45
# ╟─9f18efe2-f38e-11ea-0871-6d7760d0b2f6
# ╟─a7f3d9f8-f3bb-11ea-0c1a-55bbb8408f09
# ╠═fa8e2772-f3b6-11ea-30f7-699717693164
# ╟─18e0fd8a-f3bc-11ea-0713-fbf74d5fa41a
# ╟─cbf29020-f3ba-11ea-2cb0-b92836f3d04b
# ╟─8bc930f0-f372-11ea-06cb-79ced2834720
# ╠═85033040-f372-11ea-2c31-bb3147de3c0d
# ╟─f92ac3e4-fa70-4bcf-bc50-a36792a8baaa
# ╠═7ac5eb8d-9dba-4700-8f3a-1e0b2addc740
# ╠═9ff0ce41-327f-4bf0-958d-309cd0c0b6e5
# ╟─c572f6ce-f372-11ea-3c9a-e3a21384edca
# ╠═6d993a5c-f373-11ea-0dde-c94e3bbd1552
# ╟─ea417c2a-f373-11ea-3bb0-b1b5754f2fac
# ╟─56a7f954-f374-11ea-0391-f79b75195f4d
# ╠═b1d09bc8-f320-11ea-26bb-0101c9a204e2
# ╠═1947f304-fa2c-4019-8584-01ef44ef2859
# ╟─8992172e-c5b6-463e-a06e-5fe42fb9b16b
# ╠═b387f8e8-dced-473a-9434-5334829ecfd1
# ╟─344964a8-7c6b-4720-a624-47b03483263b
# ╠═3e8b0868-f3bd-11ea-0c15-011bbd6ac051
# ╠═d941c199-ed77-47dd-8b5a-e34b864f9a79
# ╠═726280f0-682f-4b05-bf5a-688554a96287
# ╟─c1ab3d5f-8e6c-4702-ad40-6c7f787f1c43
# ╟─4e3bcf88-f3c5-11ea-3ada-2ff9213647b7
# ╟─4e3ef866-f3c5-11ea-3fb0-27d1ca9a9a3f
# ╟─6e73b1da-f3c5-11ea-145f-6383effe8a89
# ╟─cf39fa2a-f374-11ea-0680-55817de1b837
# ╠═c8724b5e-f3bd-11ea-0034-b92af21ca12d
# ╟─6435994e-d470-4cf3-9f9d-d00df183873e
# ╠═be7d40e2-f320-11ea-1b56-dff2a0a16e8d
# ╟─507f3870-f3c5-11ea-11f6-ada3bb087634
# ╟─50829af6-f3c5-11ea-04a8-0535edd3b0aa
# ╟─9e56ecfa-f3c5-11ea-2e90-3b1839d12038
# ╟─4f48c8b8-f39d-11ea-25d2-1fab031a514f
# ╟─24792456-f37b-11ea-07b2-4f4c8caea633
# ╠═ff055726-f320-11ea-32f6-2bf38d7dd310
# ╟─e0622780-f3b4-11ea-1f44-59fb9c5d2ebd
# ╠═51731519-1831-46a3-a599-d6fc2f7e4224
# ╠═99efaf6a-0109-4b16-89b8-f8149b6b69c2
# ╠═d3e69cf6-61b1-42fc-9abd-42d1ae7d61b2
# ╟─e06d4e4a-146c-4dbd-b742-317f638a3bd8
# ╟─92e19f22-f37b-11ea-25f7-e321337e375e
# ╠═795eb2c4-f37b-11ea-01e1-1dbac3c80c13
# ╟─51df0c98-f3c5-11ea-25b8-af41dc182bac
# ╟─51e28596-f3c5-11ea-2237-2b72bbfaa001
# ╟─0a10acd8-f3c6-11ea-3e2f-7530a0af8c7f
# ╟─946b69a0-f3a2-11ea-2670-819a5dafe891
# ╟─0fbe2af6-f381-11ea-2f41-23cd1cf930d9
# ╟─48089a00-f321-11ea-1479-e74ba71df067
# ╟─6b4d6584-f3be-11ea-131d-e5bdefcc791b
# ╟─437ba6ce-f37d-11ea-1010-5f6a6e282f9b
# ╟─ef88c388-f388-11ea-3828-ff4db4d1874e
# ╟─ef26374a-f388-11ea-0b4e-67314a9a9094
# ╟─6bdbcf4c-f321-11ea-0288-fb16ff1ec526
# ╟─ffc17f40-f380-11ea-30ee-0fe8563c0eb1
# ╟─ffc40ab2-f380-11ea-2136-63542ff0f386
# ╟─ffceaed6-f380-11ea-3c63-8132d270b83f
# ╟─ffde44ae-f380-11ea-29fb-2dfcc9cda8b4
# ╟─ffe326e0-f380-11ea-3619-61dd0592d409
# ╟─fff5aedc-f380-11ea-2a08-99c230f8fa32
# ╟─00026442-f381-11ea-2b41-bde1fff66011
# ╟─fbf6b0fa-f3e0-11ea-2009-573a218e2460
# ╟─256edf66-f3e1-11ea-206e-4f9b4f6d3a3d
# ╟─00115b6e-f381-11ea-0bc6-61ca119cb628


text:
# This module represents an explicit, direct sparse 2D finite-difference Poisson solver for heterogeneous media,
# i.e. media having spatially varying (space-dependent) medium parameters.
# The following functionality is currently available in this module:
# * Apply operator ``A=∇⋅(σ(x,z)∇)`` on a field ``ψ`` to get ``p``.
# * Apply ``A^{-1}`` in order to solve for ``ψ`` in ``Aψ=p``, given ``p``.
# Current implementation assumes Neumann boundary conditions at all the boundaries.

#-

# As a demo, start with loading some packages.

using SparseArrays
using StatsBase
using LinearAlgebra
using Random
using ProgressMeter
using LinearAlgebra
using Test
using ForwardDiff
using Calculus
#src # include("core.jl")
#src # include("expt.jl")

# From here on, consider the following Poisson experiment:
# ```math
# ∇⋅(σ(x,z)∇) ψ(t) = ∇⋅(Q(x,z)∇) p(t),
# ```
# ```math
# Q = k * Qv / η.
# ```
# Dimensions and spatial grids are allocated as follows.

nx=21
nz=21
nt=4
nznx=nz*nx
mgrid=[range(-div(nz,2), step=1.0, length=nz), range(-div(nx,2), step=1.0, length=nx)]
tgrid=range(0.0,step=0.5, length=nt)

# Now lets allocate the inputs for a toy experiment.

Qv=abs.(randn(nz,nx))
η=abs.(randn(nz,nx))
k=abs.(randn(nz,nx))
σ=abs.(randn(nz,nx))
p=randn(nz,nx,nt)

for it in 1:nt
	for ix in 1:nx
		for iz in 1:nz
			p[iz,ix,it]=inv(abs(iz-11)+1)*inv(abs(ix-11)+1)
		end
	end
end

# These medium parameters are used to generate the *observed* field ``ψ``.

σobs=abs.(randn(nz,nx))
Qobs=abs.(randn(nz,nx))

fill!(σobs, 1.0)
fill!(Qobs, 1.0)
fill!(Qv, 1.0)
fill!(η, 1.0)
fill!(k, 1.0)
σobs[11,11]=20.0
fill!(σ, 1.0)

# Generate the configuration for the Poisson experiment, using the arrays above.

acqgeom=J.Acquisition.Geom_circ(nss=1,nr=30,rad=[5.,5.])
#ACQ=sprandn(200,441,0.9)
ACQ=J.Acquisition.ACQmat(acqgeom,mgrid)
paE=J.Poisson.ParamExpt(p, tgrid, mgrid, Qv, k, η, σ, ACQ, σobs=σobs, Qobs=Qobs,)
#paE=J.Poisson.ParamExpt(p, tgrid, mgrid, Qv, k, η, σ, σobs=σobs, Qobs=Qobs,)

#src # J.Poisson.updateLP!(paE, paE.Q)

# Calculate the data misfit.

@time f=J.Poisson.func(σ,paE)

# Compute the gradient with finite-difference approximation.

f = x->J.Poisson.func(x, paE);
gcalc = Calculus.gradient(f);
g_fd=reshape(gcalc(vec(σ)),nz,nx);

# Compute the gradient using adjoint state method.

@time J.Poisson.mod!(paE,σ,J.Poisson.FGσ())
g=paE.g;

# Check gradient accuracy.

@test ≈(g,g_fd, rtol=1e-5)


text:
using Roots
using Test
import SpecialFunctions.erf

include("./test_find_zero.jl")
include("./test_bracketing.jl")
include("./test_derivative_free.jl")
include("./test_simple.jl")
include("./test_find_zeros.jl")
include("./test_fzero.jl")
include("./test_newton.jl")
include("./test_simple.jl")

#include("./test_composable.jl")
#include("./runbenchmarks.jl")
#include("./test_derivative_free_interactive.jl")


text:
export SparseOp

"""
    SparseOp(name::AbstractString, shape::NTuple{N,Int64}; kargs...) where N

generates the sparsifying transform (`<: AbstractLinearOperator`) given its name.

# Arguments
* `name::AbstractString`    - name of the sparsifying transform
* `shape::NTuple{N,Int64}`  - size of the Array to be transformed
* (`kargs`)                 - additional keyword arguments
"""
function SparseOp(name::AbstractString, shape::NTuple{N,Int64}; kargs...) where N
  params = Dict(kargs)
  if name=="Wavelet"
    # if get(params, :multiEcho, false)
    #   return MultiEchoWaveletOp(params[:shape], params[:numEchoes])
    # else
    #   return WaveletOp(params[:shape])
    # end
    return WaveletOp(shape)
  elseif name=="nothing"
    return opEye(prod(shape))
  else
    error("SparseOp $name is not yet defined.")
  end

  return opEye(prod(shape))
end


text:
__precompile__(true)
module MbedTLS

export
# Message digests
    MD_NONE,
    MD_MD2,
    MD_MD4,
    MD_MD5,
    MD_SHA1,
    MD_SHA224,
    MD_SHA256,
    MD_SHA384,
    MD_SHA,
    digest,
    digest!,

# Symmetric encryption,
    encrypt,
    decrypt,
    Cipher,
    CIPHER_AES,
    CIPHER_DES,
    CIPHER_3DES,
    CIPHER_CAMELLIA,
    CIPHER_BLOWFISH,
    CIPHER_ARC4,

# Types
    CtrDrbg,
    RSA,
    SSLConfig,
    Entropy,
    CRT

using Compat
import Compat: String
import Base: show

if isfile(joinpath(dirname(@__FILE__),"..","deps","deps.jl"))
    include(joinpath(dirname(@__FILE__),"..","deps","deps.jl"))
else
    error("MbedTLS not properly installed. Please run Pkg.build(\"MbedTLS\")")
end

const MBED_SUCCESS = Cint(0)

include("constants.jl")
include("error.jl")
include("md.jl")
include("cipher.jl")
include("rsa.jl")
include("entropy.jl")
include("ctr_drbg.jl")
include("pk.jl")
include("x509_crt.jl")
include("ssl.jl")

function __init__()
    __ctr_drbg__init__()
    __sslinit__()
    __entropyinit__()
end

end # module


text:
using ReachabilityAnalysis
using JuMP, Ipopt
using Plots
using LaTeXStrings

# IVP parameters
A = [0.0 1; -4π 0]
X0 = BallInf([0.0, 10.0], 0.1)
X = Universe(2)
P = @ivp(x' = A*x, x ∈ X, x(0) ∈ X0)

# varying time steps
δs = [0.02, 0.01, 0.006, 0.003]

# methods
algs = [
        (FirstOrderddt(), "d/dt"),
        (FirstOrderZonotope(), "Zonotope"),
        (CorrectionHull(order=4), "Correction hull"),
        (FirstOrder(), "First order"),
        (ForwardBackward(solver=Ipopt.Optimizer()), "Forward/backward"),
        (Forward(), "Forward")
       ]

# reachable states at time t
R(t) = linear_map(exp(A * t), X0)

# results
δ2Ω0s = []
for δ in δs
    local Ω0s = []
    for (alg, name) in algs
        local Pd = discretize(P, δ, alg)
        local Ω0 = Pd.x0
        push!(Ω0s, Ω0)
    end
    push!(δ2Ω0s, Ω0s)
end

# plot sets
colors = [:orange, :green, :blue, :purple, :red, :black]
plots = []
for (i, δ) in enumerate(δs)
    local fig = plot(leg=:bottomleft, xlab=L"\delta = %$δ")
    for (j, (alg, name)) in enumerate(algs)
        local Ω0 = δ2Ω0s[i][j]
        if name == "Forward/backward"
            Ω0 = overapproximate(Ω0, PolarDirections(30))  # workaround because σ is not available
        end
        plot!(Ω0, alpha=0, color=colors[j], linecolor=colors[j], linealpha=1, lw=2, lab="Ω₀ $(name)")
    end

    [plot!(R(δi), color=:gray, alpha=0.05, linealpha=0, lab="") for δi in range(0.0; stop=δ, length=20)]

    savefig("experiment_delta_$i.pdf")
    push!(plots, fig)
end

return plots


text:
using StaticArrays
using CLIMA.VariableTemplates
import CLIMA.DGmethods:
    BalanceLaw,
    vars_state_auxiliary,
    vars_state_conservative,
    vars_state_gradient,
    vars_state_gradient_flux,
    flux_first_order!,
    flux_second_order!,
    source!,
    compute_gradient_argument!,
    compute_gradient_flux!,
    init_state_auxiliary!,
    init_state_conservative!,
    boundary_state!,
    wavespeed,
    LocalGeometry,
    vars_gradient_laplacian,
    vars_hyperdiffusive,
    transform_post_gradient_laplacian!
using CLIMA.DGmethods.NumericalFluxes:
    NumericalFluxFirstOrder, NumericalFluxSecondOrder

abstract type HyperDiffusionProblem end
struct HyperDiffusion{dim, P} <: BalanceLaw
    problem::P
    function HyperDiffusion{dim}(
        problem::P,
    ) where {dim, P <: HyperDiffusionProblem}
        new{dim, P}(problem)
    end
end

vars_state_auxiliary(::HyperDiffusion, FT) = @vars(D::SMatrix{3, 3, FT, 9})
#
# Density is only state
vars_state_conservative(::HyperDiffusion, FT) = @vars(ρ::FT)

# Take the gradient of density
vars_state_gradient(::HyperDiffusion, FT) = @vars(ρ::FT)
# Take the gradient of laplacian of density
vars_gradient_laplacian(::HyperDiffusion, FT) = @vars(ρ::FT)

vars_state_gradient_flux(::HyperDiffusion, FT) = @vars()
# The hyperdiffusion DG auxiliary variable: D ∇ Δρ
vars_hyperdiffusive(::HyperDiffusion, FT) = @vars(σ::SVector{3, FT})

function flux_first_order!(
    m::HyperDiffusion,
    flux::Grad,
    state::Vars,
    aux::Vars,
    t::Real,
) end

"""
    flux_second_order!(m::HyperDiffusion, flux::Grad, state::Vars,
                     auxDG::Vars, auxHDG::Vars, aux::Vars, t::Real)

Computes diffusive flux `F` in:

```
∂ρ
-- = - ∇ • (σ) = - ∇ • F
∂t
```
Where

 - `σ` is hyperdiffusion DG auxiliary variable (`σ = D ∇ Δρ` with D being the hyperdiffusion tensor)
"""
function flux_second_order!(
    m::HyperDiffusion,
    flux::Grad,
    state::Vars,
    auxDG::Vars,
    auxHDG::Vars,
    aux::Vars,
    t::Real,
)
    σ = auxHDG.σ
    flux.ρ += σ
end

"""
    compute_gradient_argument!(m::HyperDiffusion, transform::Vars, state::Vars,
                   aux::Vars, t::Real)

Set the variable to take the gradient of (`ρ` in this case)
"""
function compute_gradient_argument!(
    m::HyperDiffusion,
    transform::Vars,
    state::Vars,
    aux::Vars,
    t::Real,
)
    transform.ρ = state.ρ
end

compute_gradient_flux!(m::HyperDiffusion, _...) = nothing
function transform_post_gradient_laplacian!(
    m::HyperDiffusion,
    auxHDG::Vars,
    gradvars::Grad,
    state::Vars,
    aux::Vars,
    t::Real,
)
    ∇Δρ = gradvars.ρ
    D = aux.D
    auxHDG.σ = D * ∇Δρ
end

"""
    source!(m::HyperDiffusion, _...)

There is no source in the hyperdiffusion model
"""
source!(m::HyperDiffusion, _...) = nothing

"""
    init_state_auxiliary!(m::HyperDiffusion, aux::Vars, geom::LocalGeometry)

initialize the auxiliary state
"""
function init_state_auxiliary!(
    m::HyperDiffusion,
    aux::Vars,
    geom::LocalGeometry,
)
    init_hyperdiffusion_tensor!(m.problem, aux, geom)
end

function init_state_conservative!(
    m::HyperDiffusion,
    state::Vars,
    aux::Vars,
    coords,
    t::Real,
)
    initial_condition!(m.problem, state, aux, coords, t)
end

boundary_state!(nf, ::HyperDiffusion, _...) = nothing


text:
using CompressionStreams
using BufferedStreams

if VERSION >= v"0.5-"
    using Base.Test
else
    using BaseTestNext
    const Test = BaseTestNext
end

datafile(fn) = Pkg.dir("CompressionStreams", "test", "data", fn)

@testset "Decompression of data.bin$ext" for ext in ("", ".gz")

    fn = datafile("1MiB_zeros.bin$ext")

    function read_and_check(stream)
        buf = Vector{UInt8}(2^20)
        @test readbytes!(stream, buf) == length(buf)
        @test all(buf .== 0)
    end

    @testset "File" begin
        s = cstream(fn)
        read_and_check(s)
    end

    @testset "IO" begin
        io = open(fn)
        s = cstream(io)
        read_and_check(s)
    end

    @testset "BufferedStream" begin
        bs = BufferedInputStream(open(fn))
        s = cstream(bs)
        read_and_check(s)
    end

end


text:
using doradojl
using Test

@testset "doradojl.jl" begin
    # Write your tests here.
end


text:
function lagrangian_multiplier(model::MOI.ModelLike, p, set::SOSLikeCone, q,
                               mindegree::Integer, maxdegree::Integer, T::Type)
    mindegree_q, maxdegree_q = MP.extdegree(q)
    # extdegree's that s^2 should have so that s^2 * p has degrees between mindegree and maxdegree
    mindegree_s2 = mindegree - mindegree_q
    maxdegree_s2 = maxdegree - maxdegree_q
    # extdegree's for s
    mindegree_s = max(0, div(mindegree_s2, 2))
    # If maxdegree_s2 is odd, div(maxdegree_s2,2) would make s^2 have degree up to maxdegree_s2-1
    # for this reason, we take div(maxdegree_s2+1,2) so that s^2 have degree up to maxdegree_s2+1
    maxdegree_s = div(maxdegree_s2 + 1, 2)
    # FIXME handle the case where `p`, `q_i`, ...  do not have the same variables
    # so instead of `variable(p)` we would have the union of them all
    @assert variables(q) ⊆ variables(p)
    monos = MP.monomials(MP.variables(p), mindegree_s:maxdegree_s)
    Q, variable_bridge = add_matrix_variable_bridge(
        model, matrix_cone_type(typeof(set)), length(monos), T)
    return build_gram_matrix(Q, monos), variable_bridge, monos
end

struct SOSPolynomialInSemialgebraicSetBridge{
    T, F <: MOI.AbstractVectorFunction, DT <: AbstractSemialgebraicSet,
    CT <: SOSLikeCone, VBS <: AbstractVariableBridge,
    BT <: PolyJuMP.AbstractPolynomialBasis, MT <: MP.AbstractMonomial,
    MVT <: AbstractVector{MT}, NPT <: Tuple} <: MOIB.AbstractBridge
    lagrangian_monomials::Vector{MVT}
    lagrangian_bridges::Vector{VBS}
    constraint::MOI.ConstraintIndex{F, SOSPolynomialSet{DT, CT, BT, MT, MVT, NPT}}
end

function SOSPolynomialInSemialgebraicSetBridge{T, F, DT, CT, VBS, BT, MT, MVT, NPT}(
    model::MOI.ModelLike, f::MOI.AbstractVectorFunction,
    set::SOSPolynomialSet{<:BasicSemialgebraicSet}) where {
        # Need to specify types to avoid ambiguity with the default constructor
        T, F <: MOI.AbstractVectorFunction, DT <: AbstractSemialgebraicSet,
        CT <: SOSLikeCone, VBS <: AbstractVariableBridge,
        BT <: PolyJuMP.AbstractPolynomialBasis, MT <: MP.AbstractMonomial,
        MVT <: AbstractVector{MT}, NPT <: Tuple
    }
    @assert MOI.output_dimension(f) == length(set.monomials)
    p = MP.polynomial(collect(MOIU.eachscalar(f)), set.monomials)
    n = length(set.domain.p)
    λ_monos   = Vector{MVT}(undef, n)
    λ_bridges = Vector{VBS}(undef, n)
    for (i, q) in enumerate(set.domain.p)
        λ, λ_bridges[i], λ_monos[i] = lagrangian_multiplier(
            model, p, set.cone, q, set.mindegree, set.maxdegree, T)
        p -= λ * q
    end
    monos = MP.monomials(p)
    new_set = SOSPolynomialSet(set.domain.V, set.cone, set.basis, monos,
                               set.newton_polytope, set.mindegree,
                               set.maxdegree)
    constraint = MOI.add_constraint(model, MOIU.vectorize(MP.coefficients(p)),
                                    new_set)

    return SOSPolynomialInSemialgebraicSetBridge{
        T, F, DT, CT, VBS, BT, MT, MVT, NPT}(λ_monos, λ_bridges, constraint)
end

function MOI.supports_constraint(::Type{SOSPolynomialInSemialgebraicSetBridge{T}},
                                 ::Type{<:MOI.AbstractVectorFunction},
                                 ::Type{<:SOSPolynomialSet{<:BasicSemialgebraicSet}}) where T
    return true
end
function MOIB.added_constraint_types(
    ::Type{SOSPolynomialInSemialgebraicSetBridge{T, F, DT, CT, VBS, BT, MT, MVT, NPT}}) where {T, F, DT, CT, VBS, BT, MT, MVT, NPT}
    added = [(F, SOSPolynomialSet{DT, CT, BT, MT, MVT, NPT})]
    return append_added_constraint_types(added, matrix_cone_type(CT), T)
end
function MOIB.concrete_bridge_type(::Type{<:SOSPolynomialInSemialgebraicSetBridge{T}},
                                   F::Type{<:MOI.AbstractVectorFunction},
                                   ::Type{<:SOSPolynomialSet{BasicSemialgebraicSet{S, PS, AT}, CT, BT, MT, MVT, NPT}}) where {T, S, PS, AT, CT, BT, MT, MVT, NPT}
    # promotes VectorOfVariables into VectorAffineFunction, it should be enough
    # for most use cases
    G = MOIU.promote_operation(-, T, F, MOI.VectorOfVariables)
    VBS = union_vector_bridge_types(matrix_cone_type(CT), T)
    return SOSPolynomialInSemialgebraicSetBridge{T, G, AT, CT, VBS, BT, MT, MVT, NPT}
end

# Attributes, Bridge acting as an model
function MOI.get(::SOSPolynomialInSemialgebraicSetBridge{T, F, DT, VBS, BT, MT, MVT, NPT},
                 ::MOI.NumberOfConstraints{F, SOSPolynomialSet{DT, BT, MT, MVT, NPT}}) where {T, F, DT, VBS, BT, MT, MVT, NPT}
    return 1
end
function MOI.get(b::SOSPolynomialInSemialgebraicSetBridge{T, F, DT, VBS, BT, MT, MVT, NPT},
                 ::MOI.ListOfConstraintIndices{F, SOSPolynomialSet{DT, BT, MT, MVT, NPT}}) where {T, F, DT, VBS, BT, MT, MVT, NPT}
    return [b.constraint]
end

# Indices
function MOI.delete(model::MOI.ModelLike,
                    bridge::SOSPolynomialInSemialgebraicSetBridge)
    MOI.delete(model, bridge.constraint)
    for variable_bridge in bridge.lagrangian_bridges
        MOI.delete(model, variable_bridge)
    end
end

# Attributes, Bridge acting as a constraint

# The monomials might be different from the ones of the original polynomial
# because of the ∑ λ_i s_i(x) so we don't define ConstraintPrimal and
# ConstraintDual, as the caller won't know how to reshape it
function MOI.get(model::MOI.ModelLike,
                 attr::Union{CertificateMonomials, GramMatrixAttribute,
                             MomentMatrixAttribute},
                 bridge::SOSPolynomialInSemialgebraicSetBridge)
    return MOI.get(model, attr, bridge.constraint)
end
function MOI.get(model::MOI.ModelLike, ::LagrangianMultipliers,
                 bridge::SOSPolynomialInSemialgebraicSetBridge)
    @assert eachindex(bridge.lagrangian_bridges) == eachindex(bridge.lagrangian_monomials)
    map(i -> build_gram_matrix(MOI.get(model, GramMatrixAttribute(),
                                       bridge.lagrangian_bridges[i]),
                               bridge.lagrangian_monomials[i]),
        eachindex(bridge.lagrangian_bridges))
end


text:
struct DiffusionObservationModel{S1, S2, TF} <: ObservationModel{Vector{S1}, Vector{S2}, ContinuousTime}
    n::Int
    m::Int
    observation_function::TF
end

#####################
### BASIC METHODS ###
#####################

drift(model::DiffusionObservationModel) = model.observation_function
state_dim(model::DiffusionObservationModel) = model.n
obs_dim(model::DiffusionObservationModel) = model.m
noise_dim(model::DiffusionObservationModel) = model.m

observation_function(obs_model::DiffusionObservationModel) = drift(obs_model)

function Base.show(io::IO, ::MIME"text/plain", model::DiffusionObservationModel)
    print(io, "Diffusion process model for the observation
    type of hidden state:                   ", state_dim(model),"-dimensional vector
    type of observation:                    ", obs_dim(model),"-dimensional vector
    number of independent Brownian motions: ", noise_dim(model))
end

function Base.show(io::IO, model::DiffusionObservationModel)
    print(io, obs_dim(model),"-dimensional diffusion with ", noise_dim(model), "-dimensional Brownian motion")
end

function Base.show(io::IO, ::MIME"text/plain", model::Type{DiffusionObservationModel{S,T}}) where {S,T}
    print(io, "DiffusionObservationModel{", S, ",", T, "}")
end

function Base.show(io::IO, model::Type{DiffusionObservationModel{S,T}}) where {S,T}
    print(io, "DiffusionObservationModel")
end

######################
### TIME EVOLUTION ###
######################

function (model::DiffusionObservationModel{S1, S2, TF})(x::AbstractVector{S1}, dt) where {S1, S2, TF}
    dV = randn(S1, noise_dim(model))
    h  = observation_function(model)
    return h(x) * dt + dV * sqrt(dt)
end

function (model::DiffusionObservationModel)(x::AbstractMatrix{T}, dt) where T
    dV = randn(T, noise_dim(model), size(x, 2))
    h  = observation_function(model)
    return mapslices(h, x, dims=1) * dt + dV * sqrt(dt)
end

function (model::DiffusionObservationModel{S1, S2, TF})(x::AbstractVector{Vector{S1}}, dt) where {S1, S2, TF}
    return [model(y, dt) for y in x]
end

################################
### CONVENIENCE CONSTRUCTORS ###
################################

function ScalarDiffusionObservationModel(h::Function, n = 1)
    if n == 1
        H1(x) = [h(x[1])]
        return DiffusionObservationModel{Float64, Float64, typeof(H1)}(n, 1, H1)
    elseif n > 1
        H2(x) = [h(x)]
        return DiffusionObservationModel{Float64, Float64, typeof(H2)}(n, 1, H2)
    end

end

max_stars_repo_name: simsurace/FeedbackParticleFilters

max_issues_repo_name: simsurace/FeedbackParticleFilters

max_forks_repo_name: simsurace/FeedbackParticleFilters


text:
## Types:

abstract type Value{T} end

abstract type Tracked{T} <: Value{T} end

mutable struct Param{T} <: Tracked{T}
    value::T
    opt
    Param{T}(v,o) where {T} = new(v,o)
    Param{T}(v,o) where {T<:Value} = error("Param cannot take $T as arg.")
end

mutable struct Result{T} <: Tracked{T}
    value::Union{T,Nothing}     # gcnode sets this to nothing to save memory
    func
    args
    kwargs
    Result{T}(v,f,a,k) where {T} = new(v,f,a,k)
    Result{T}(v,f,a,k) where {T<:Value} = error("Result cannot take $T as arg.")
end

struct Bcasted{T} <: Value{T}
    value::T
    Bcasted{T}(v) where {T} = new(v)     # Bcasted{Tracked} is the only Value{Value} allowed
    Bcasted{T}(v) where {T<:Bcasted} = v # We do not want Bcasted{Bcasted}
end

mutable struct Node
    Value::Tracked
    parents::Vector{Node}
    children::Vector{Node}
    outgrad
    Node(v::Tracked) = new(v, Node[], Node[], nothing)
end

mutable struct Tape
    dict::IdDict{Tracked,Node}
    list::Vector{Node}
    Tape() = new(IdDict{Tracked,Node}(), Vector{Node}())
end

abstract type Arg{N} end

## Broadcasting: non-primitive fns broadcasted over Value args call themselves with Bcasted args

import .Broadcast: BroadcastStyle, broadcastable, broadcasted
using .Broadcast: Style, Broadcasted
BroadcastStyle(::Type{<:Value}) = Style{Value}()
BroadcastStyle(s::Style{Value}, ::BroadcastStyle) = s
broadcastable(x::Value) = x     # This is necessary, default is collect(x) which loses Value
Bcasted(v::T) where {T} = Bcasted{T}(v)
broadcasted(::Style{Value}, f, args...) = recording() ? f(Bcasted.(args)...).value : broadcasted(f, value.(args)...)
Base.copyto!(x::Value,y) = copyto!(x.value,y) # This is used by p .-= g when p is Param.

## Recording: primitive fns with Value args call forw

const _tapes = Tape[]
recording() = !isempty(_tapes)

# forw() is called with primitive functions that have Tracked or Bcasted args
function forw(f, args...; kwargs...)
    @timer "forwargs"        ((f, nobcast, novalue) = forwargs(f, args))
    @timer ftimer(f,novalue) (v = f(novalue...; kwargs...))
    if recording()
        if v isa Broadcasted
            @timer "unfuse"  (v = copy(v))
        end
        if novalue !== nobcast  # there are tracked args
            @timer "record"  (v = Result(v, f, nobcast, kwargs))
        end
        if nobcast !== args     # there are bcasted args
            @timer "bcasted" (v = Bcasted(v))
        end
    end
    return v
end

# Return two arg lists, one stripped of Bcasted and one stripped of all Values.
# Do not allocate unless necessary.
function forwargs(f, args)
    nobcast = novalue = args
    @inbounds for i in 1:length(args)
        if isa(nobcast[i], Bcasted)
            if nobcast === args; nobcast = Any[args...]; end
            if novalue === args; novalue = nobcast; end
            nobcast[i] = nobcast[i].value
            @assert !isa(nobcast[i], Bcasted) "Illegal value recursion: $(typeof(args[i]))"
        end
        if isa(novalue[i], Value)
            if novalue === args; novalue = Any[args...]
            elseif novalue === nobcast; novalue = copy(nobcast); end
            novalue[i] = value(novalue[i])
        end
    end
    @assert novalue !== args "forw called without Value args"
    if nobcast !== args
        @assert recording() "Bcasted args out of recording context"
        if f !== broadcasted
            pushfirst!(nobcast, f)
            if novalue !== nobcast; pushfirst!(novalue, f); end
            f = broadcasted
        end
    end
    return (f, nobcast, novalue)
end

function Result(v::T, f, args, kwargs) where {T}
    record!(t::Tape, v::Tracked) = (n = get(t.dict, v, nothing); n === nothing ? record!(t, Node(v)) : n)
    record!(t::Tape, n::Node) = (t.dict[n.Value] = n; push!(t.list, n); n)
    result = Result{T}(v, f, args, kwargs)
    narg = length(args)
    for tape in _tapes
        node = Node(result)
        node.parents = Array{Node}(undef, narg)
        @inbounds for i = 1:narg
            if isa(args[i], Tracked)
                node.parents[i] = record!(tape, args[i])
                push!(node.parents[i].children, node)
            end
        end
        record!(tape, node)
    end
    return result
end

Result(v::T, f, args, kwargs) where {T<:Tracked} = v  # Issue #106: no need to record twice

## Differentiate: call f recording primitives on tape, then call back on each primitive

function differentiate(f, x...; o...)
    duplicate(x)=(isa(x,Value) ? identity(x) : x)
    if !isempty(_tapes)       # PR#75: to avoid tape confusion
        x = map(duplicate,x)  # duplicate tracked function arguments.
        o = isempty(o) ? () : pairs(map(duplicate,values(o)))
    end
    tape = Tape()
    push!(_tapes, tape)
    result = nothing
    try
        result = f(x...; o...)
        if isa(result,Param); result = identity(result); end # fix #101.1: turn Param->Result
    catch e
        Base.show_backtrace(stdout, Base.catch_backtrace()); println()
        pop!(_tapes); throw(e)
    end
    tape1 = pop!(_tapes)
    @assert tape1 === tape "Tape stack error"
    if !isa(result,Result); return result; end
    @assert isa(result.value, Number) "Only scalar valued functions supported."
    resultnode = findresult(tape, result)
    resultnode.outgrad = one(result.value)
    @inbounds for ti in length(tape.list):-1:1
        n = tape.list[ti]
        if n.outgrad == nothing; continue; end
        r = n.Value
        @inbounds for i in 1:length(n.parents)
            if !isassigned(n.parents, i); continue; end
            # We cannot support all operations back may use, so at this point we need to get rid of Sparse
            if n.outgrad isa Sparse; n.outgrad = full(n.outgrad); end
            p = n.parents[i]
            @timer btimer(tape,ti,i,r) (g = back(r.func, Arg{i}, n.outgrad, r, r.args...; r.kwargs...))
            @timer stimer(tape,ti,i)   (p.outgrad = addto!(p.outgrad, g))
        end
        if isempty(_tapes) && isa(r,Result) && n !== resultnode; gcnode[](n,tape); end  # save memory
    end
    return tape
end

# back is defined by the @primitive macro
back(x...; o...) = throw(MethodError(back,x)) # fix #101.2: error instead of nothing

# Used by @timer
btimer(tape::Tape,ti::Int,i::Int,r::Result)=(r.func===broadcasted ? "[$ti]$(r.args[1]).[$(i-1)]" : "[$ti]$(r.func)[$i]")
stimer(tape::Tape,ti::Int,i::Int)="[$ti]addto![$i]"
function ftimer(f::Function,a::Array{Any})
    t = (isempty(_tapes) ? "" : "[>$(1+length(_tapes[end].list))]")
    (f===broadcasted ? "$t$(a[1])." : "$t$f")
end

# 99% result will be on tape.list[end], this handles the other 1% where the loss fn computes
# stuff recorded on tape after result but returns result at the end.
function findresult(tape::Tape, result::Result)
    if tape.list[end].Value === result; return tape.list[end]; end
    @inbounds for i in (length(tape.list)-1):-1:1
        if tape.list[i].Value === result
            tape.list = tape.list[1:i]
            break
        end
    end
    @assert tape.list[end].Value === result "result not found on tape"
    return tape.list[end]
end

## Exported functions:

Param(v::T,o=nothing) where {T} = Param{T}(v,o)

# This allows argument expressions like @diff sin(sqrt(x)) which fail with differentiate
# because arguments get evaluated before the tape gets created.
macro diff(fx); :(differentiate(()->$(esc(fx)))); end

# value() should give a regular (non-Value) result regardless of recursion
value(x) = x
value(x::Value) = x.value
value(x::Value{<:Value}) = error("Illegal type recursion $(typeof(x))")
value(x::Bcasted{<:Tracked}) = value(x.value) # Only type of Value recursion allowed
value(t::Tape)=(isempty(t.list) ? nothing : t.list[end].Value.value)

# New style grad
grad(t,x)=nothing
grad(t::Tape,x::Tracked)=(n=get(t.dict,x,nothing); n===nothing ? n : n.outgrad)

# Old style grad and gradloss
function grad(fun::Function, argnum::Int=1, loss=false)
    function gradfun(args...; kwargs...)
        arg_wrt = args[argnum]
        if !isa(arg_wrt,Value); arg_wrt = Param(arg_wrt); end
        args = Any[args...]
        args[argnum] = arg_wrt
        result = differentiate(fun, args...; kwargs...)
        xgrad = isa(result, Tape) ? full(result.list[1].outgrad) : nothing
        return loss ? (xgrad,value(result)) : xgrad
    end
    return gradfun
end

gradloss(f,a=1)=grad(f,a,true)

# Override gcnode for memory cleanup during back pass
default_gc(n::Node, t::Tape) = nothing # (n.outgrad=nothing; n.Value.value=nothing)
const gcnode = Ref{Any}(default_gc)
set_gc_function(f::Function) = (gcnode[] = f)