text:
#
#
# A general framework for solvers of problems on Manifolds
#
# This file introduces fallbacks for not yet implemented parts and the general
# function to run the solver
export decorateOptions
export initializeSolver!, doSolverStep!, getSolverResult, stopSolver!
export solve
@doc doc"""
    decorateOptions(o)

decorate the [`Options`](@ref)` o` with specific decorators.

# Optional Arguments
optional arguments provide necessary details on the decorators. A specific
one is used to activate certain decorators.

* `debug` – (`Array{Union{Symbol,DebugAction,String,Int},1}()`) a set of symbols
  representing [`DebugAction`](@ref)s, `Strings` used as dividers and a subsampling
  integer. These are passed as a [`DebugGroup`](@ref) within `:All` to the
  [`DebugOptions`](@ref) decorator dictionary. Only excention is `:Stop` that is passed to `:Stop`.
* `record` – (`Array{Union{Symbol,RecordAction,Int},1}()`) specify recordings
  by using `Symbol`s or [`RecordAction`](@ref)s directly. The integer can again
  be used for only recording every $i$th iteration.

# See also
[`DebugOptions`](@ref), [`RecordOptions`](@ref)
"""
function decorateOptions(o::O;
        debug::Union{Missing, # none
                    DebugAction, # single one for :All
                    Array{DebugAction,1}, # a group that's put into :All
                    Dict{Symbol,DebugAction}, # the most elaborate, a dictionary
                    Array{<:Any,1}, # short hand for Factory.
                    }=missing,
        record::Union{Missing, # none
                    RecordAction, # single action
                    Array{RecordAction,1}, # a group to be set in :All
                    Dict{Symbol,RecordAction}, # a dictionary for precise settings
                    Array{<:Any,1} # a formated string with symbols or Actions
                    }=missing,
    ) where {O <: Options}
    o = ismissing(debug) ? o : DebugOptions(o,debug)
    o = ismissing(record) ? o : RecordOptions(o,record)
    return o
end
"""
    initializeSolver!(p,o)

Initialize the solver to the optimization [`Problem`](@ref) by initializing all
values in the [`Options`](@ref)` o`.
"""
function initializeSolver!(p::P,o::O) where {P <: Problem, O <: Options}
    sig1 = string( typeof(p) )
    sig2 = string( typeof(o) )
    throw( ErrorException("Initialization of a solver corresponding to the $sig1 and $sig2 not yet implemented." ) )
end
"""
    doSolverStep!(p,o,iter)

Do one iteration step (the `iter`th) for [`Problem`](@ref)` p` by modifying
the values in the [`Options`](@ref) `o`.
"""
function doSolverStep!(p::P,o::O, iter) where {P <: Problem, O <: Options}
    sig1 = string( typeof(p) )
    sig2 = string( typeof(o) )
    throw( ErrorException("Initialization of a solver corresponding to the $sig1 and $sig2 not yet implemented." ) )
end
"""
    getSolverResult(p,o)

Return the final result after all iterations that is stored within the
(modified during the iterations) [`Options`](@ref) `o`.
"""
function getSolverResult(p::P,o::O) where {P <: Problem, O <: Options}
    sig1 = string( typeof(p) )
    sig2 = string( typeof(o) )
    throw( ErrorException("Initialization of a solver corresponding to the $sig1 and $sig2 not yet implemented." ) )
end
"""
    stopSolver!(p,o,i)

depending on the current [`Problem`](@ref) `p`, the current state of the solver
stored in [`Options`](@ref) `o` and the current iterate `i` this function determines
whether to stop the solver by calling the [`StoppingCriterion`](@ref).
"""
stopSolver!(p::P,o::O, i::Int) where {P <: Problem, O <: Options} = o.stop(p,o,i)

"""
    solve(p,o)

run the solver implemented for the [`Problem`](@ref)` p` and the
[`Options`](@ref)` o` employing [`initializeSolver!`](@ref), [`doSolverStep!`](@ref),
as well as the [`stopSolver!`](@ref) of the solver.
"""
function solve(p::P, o::O) where {P <: Problem, O <: Options}
    iter::Integer = 0
    initializeSolver!(p,o)
    while !stopSolver!(p,o,iter)
        iter = iter+1
        doSolverStep!(p,o,iter)
    end
    return o
end


text:
include("../functions/Functions.jl")
include("../evaluate/Evaluate.jl")
include("../opt/sgd.jl")
include("../data/data.jl")
include("../plot/Plotting.jl")

using Plotting

X, y = getOldData()

x0 = zeros(size(X,2),1)

lambda = 0.1

iter = 15000
step = 0.0001

#f = f_logreg(X,y,x0,lambda)
#g = sub_g_logreg()

f = f_svm(X,y,x0,lambda)
g = sub_g_svm()

@time (theta,state,val_array,stop_array) = sgd(X,y,x0,f,g,1e-8,lambda,iter,step,size(X,1))

plotArray(val_array, "sgd1.svg")

grad = g_logreg(X,y,theta,lambda)(theta)
grad_norm = norm(grad, Inf)
@printf("Inf-Norm of gradient is %f.\n",grad_norm)
println(evaluate(X,y,theta,"svm",false))

ext: jl

max_stars_repo_name: zagazao/num-opt

max_issues_repo_name: zagazao/num-opt

max_forks_repo_name: zagazao/num-opt


text:
"""
order of queues
1)   Left FP
2)   Left FN
3)   Right FP
4)   Right FN
5)   Posterior FP
6)   Posterior FN
7)   Anterior FP
8)   Anterior FN
9)   Top FP
10)   Top FN
11)   Bottom FP
12)   Bottom FN
13)   main block Fp
14)   main block Fn

15)   total block Fp
16)   total block Fn

In order to simplify the structure all will be represented as the UInt32  even values that are really booleans
in those cases false will be 0 and true 32 ...

"""
module MetaDataUtils
using CUDA
export @setMeta,@accMeta,getIsToBeAnalyzedNumb,getIsToBeActivatedInSegmNumb,getIsToBeActivatedInGoldNumb,getFullInSegmNumb,getFullInGoldNumb,setBlockasCurrentlyActiveInGold,setBlockasCurrentlyActiveInSegm,getActiveGoldNumb,getActiveSegmNumb,getResOffsetsBeg,getOldCountersBeg,getNewCountersBeg,getBeginingOfFpFNcounts,getBeginingOfXYZ,setBlockasCurrentlyActiveInGold,setBlockasCurrentlyActiveInSegm

"""
it will be 4 dimensional array - where fourth dimension will store actual data  in UInt32 format
    -even Bool will be UInt32 for simplicity
1)activeInGold::Bool
2)activeInSegm::Bool
3)fullInGold::Bool
4)fullInSegm::Bool

5)isToBectivatedGold::Bool
6)isToBeActivatedSegm::Bool
7-9)x,y,z coordinates ::UInt32
10-24) getIsToBeAnalyzedNumb::Bool
25-41) fpFNcounts::UInt32 last 2 will be totals

42-56) resOffsets::UInt32
57-59) totalOffsetBeginingAndEnd UInt32
60-74) oldCounters ::UInt32
75-89) newCounters::UInt32

arrDims - dimensions of the main data array
dataBDims - dimensions of the data block - part of the main array that is to be analyzed by single block
creates empty metadata on the basis of the main array dimensions and data block dimensions
"""
function allocateMetadata(arrDims,dataBDims)
    return CUDA.zeros(UInt32,cld(arrDims[1],dataBDims[1] )
            ,cld(arrDims[2],dataBDims[2] )
            ,cld(arrDims[2],dataBDims[3] )
            ,90 )
end
"""
value pointing out where we start in 4th dimension counters
it is begining -1 as we will add thread idx to it ...
"""
function getBeginingOfFpFNcounts()::UInt32
    return UInt32(24)
end
"""
value pointing out where we start in 4th dimension x y z position (usfull when we have access only to linear index)
it is begining -1 as we will add thread idx to it ...
"""
function getBeginingOfXYZ()::UInt32
    return UInt32(6)
end

######## simple accessors - kept so we can easily can change metadata organisation if needed
function getActiveGoldNumb()::UInt32 return  1 end
function getActiveSegmNumb()::UInt32 return  2 end

function getFullInGoldNumb()::UInt32 return  3 end
function getFullInSegmNumb()::UInt32 return  4 end

function getIsToBeActivatedInGoldNumb()::UInt32 return  5 end
function getIsToBeActivatedInSegmNumb()::UInt32 return  6 end

function getIsToBeAnalyzedNumb()::UInt32 return  9 end

function getResOffsetsBeg()::UInt32 return  41 end

function getOldCountersBeg()::UInt32 return  59 end
function getNewCountersBeg()::UInt32 return  74 end

"""
making access to the metaData Easier
we assume that linIdexMeta, xMeta, zMeta,yMeta are available
"""
    # nn = $numb
    # CUDA.@cuprint("xMeta $(xMeta+1) yMeta $(yMeta+1)  zMeta $(zMeta+1) numb $(nn) \n  ")

macro accMeta(numb)
    return esc(quote
        metaData[xMeta+1,yMeta+1,zMeta+1,$numb]
    end)

end
"""
making setting value  to the metaData Easier
we assume that linIdexMeta, xMeta, zMeta,yMeta are available
"""
macro setMeta(numb,value)
    return esc(quote
        metaData[(xMeta+1),(yMeta+1),(zMeta+1),($numb)]=($value)
    end)

end

"""
make is block currently active to true for gold standard pass
"""
function setBlockasCurrentlyActiveInGold(metaData, xMeta,yMeta,zMeta)
    metaData[xMeta,yMeta,zMeta,getActiveGoldNumb()]=1
end

"""
sets is active of given block to true for not gold pass
"""
function setBlockasCurrentlyActiveInSegm(metaData, xMeta,yMeta,zMeta)
    metaData[xMeta,yMeta,zMeta,getActiveSegmNumb()]=1
 end

"""
given linear index that is telling us about x,y,z location in one number (linIndex) and number that is the position in fourth dimesnsion (locFourthDim)
it will give us back this entryin meta data (metaData)
for reducing the need of recalculations we will supply also the metaData3dimProd to speed up calculations
    metaDataDims dimensions of the meta data
        """
function getMetaDataFieldFromLin(metaData,metaDataDims,linIndex,locFourthDim )
    return metaData[]
end

"""
given linear index that is telling us about x,y,z location in one number (linIndex) and number that is the position in fourth dimesnsion (locFourthDim)
it will set  this entry in meta data (metaData) to value (valuee)
"""
function setMetaDataFieldFromLin(metaData,metaDataDims,linIndex,locFourthDim,valuee)

end

"""
sets is active of given block to true for gold standard pass
"""
function setBlockToActiveInGold(metaData,linIndex)
    setMetaDataFieldFromLin(metaData,linIndex,1,UInt32(1))
end

    """
is block set to be activated for gold standard pass
"""
function isBlockToBeActivatedInGold(metaData, linIndex)
   return getMetaDataFieldFromLin(metaData,5,locFourthDim)
end

"""
true if block is full for gold standard pass
"""
function isBlockFullInGold(metaData, linIndex)
  return  getMetaDataFieldFromLin(metaData,linIndex,3)
end

"""
is block currently Active for gold standard pass
"""
function isBlockCurrentlyActiveInGold(metaData, linIndex)
   getMetaDataFieldFromLin(metaData,1,locFourthDim)
    end

"""
true if block is full for not gold pass
"""
function isBlockFullInSegm(metaData, linIndex)
   getMetaDataFieldFromLin(metaData,linIndex,4)

    end
"""
is block set to be activated for not gold pass
"""
function isBlockToBeActivatedInSegm(metaData, linIndex)

   getMetaDataFieldFromLin(metaData,6,locFourthDim)

    end
"""
is block currently Active for not gold pass
"""
function isBlockCurrentlyActiveInSegm(metaData, linIndex)
   getMetaDataFieldFromLin(metaData,2,locFourthDim)

    end
"""
make is block currently active to true for not gold pass
"""
function setBlockasCurrentlyActiveInSegm(metaData, linIndex)
    setMetaDataFieldFromLin(metaData,2,locFourthDim,UInt32(1))

    end

"""
1)   Left FP
2)   Left FN
3)   Right FP
4)   Right FN
5)   Posterior FP
6)   Posterior FN
7)   Anterior FP
8)   Anterior FN
9)   Top FP
10)   Top FN
11)   Bottom FP
12)   Bottom FN
13)   Total block Fp
14)   Total block Fn
checks is the total counter for the given result queue is smaller than the total amount of fp or fn for given list
and sets appropriate variable isTpBeAnalyzed
Important!!! we need to take into account corners so if we look from the top we only care of the top process
    or we also needs tops of the sides and anterior posterior paddings? - this needs to be adressed
"""
macro setIstoBeAnalyzed(numb, mataData,linIndex,resShmem)

krowa

   getMetaDataFieldFromLin(metaData,linIndex,locFourthDim)
    setMetaDataFieldFromLin(metaData,linIndex,locFourthDim,valuee)

    end

"""
1)   Left FP
2)   Left FN
3)   Right FP
4)   Right FN
5)   Posterior FP
6)   Posterior FN
7)   Anterior FP
8)   Anterior FN
9)   Top FP
10)   Top FN
11)   Bottom FP
12)   Bottom FN
13)   Total block Fp
14)   Total block Fn
#in order to be able to skip some of the validations we will load now informations about this block and neighbouring blocks
#like for example are there any futher results to be written in this block including border queues
#and is there sth in border queues of the neighbouring data blocks
basically give back the booleans that were calculated in setIstoBeAnalyzed
we will store the results in a corner of res shmem
"""
macro getIstoBeAnalyzed(resShmem,metaData,linIndex,isGold)
   getMetaDataFieldFromLin(metaData,linIndex,locFourthDim)
    setMetaDataFieldFromLin(metaData,linIndex,locFourthDim,valuee)

    end

"""
get data is to be analyzed that was set in setIstoBeAnalyzed
and loaded into res shmem in getIstoBeAnalyzed
this function only return boolean from resshmem that tell us about wheather it makes sense to analyze the data inside
    the data block - so it cares about total data block fp or fn not yet covered
"""
function getIsTotalFPorFNnotYetCovered(resshmem ,isGold)
   getMetaDataFieldFromLin(metaData,linIndex,locFourthDim)
    setMetaDataFieldFromLin(metaData,linIndex,locFourthDim,valuee)

    end

"""
We just access data from res shmem that was loaded into resshmem in getIstoBeAnalyzed
dim can be 1,2,3 and tell in what dimension is the plane of our analysis
            isStart may be either 1 or end of data block   - on this basis we can establish which padding is of our intrest ...
"""
function isPaddingToBeAnalyzed(resShmem,dim,isStart )

   getMetaDataFieldFromLin(metaData,linIndex,locFourthDim)
    setMetaDataFieldFromLin(metaData,linIndex,locFourthDim,valuee)

    end

"""
1)   Left FP
2)   Left FN
3)   Right FP
4)   Right FN
5)   Posterior FP
6)   Posterior FN
7)   Anterior FP
8)   Anterior FN
9)   Top FP
10)   Top FN
11)   Bottom FP
12)   Bottom FN
13)   Total block Fp
14)   Total block Fn
sets values for amount of fp and fn in all of the ques specified above
"""
function setMetaFPandFN(numb, mataData,linIndex,valuee)

    setMetaDataFieldFromLin(metaData,linIndex,numb+24,valuee)

    end

#set the x,y,z coordinates - so we will able to query it efficiently also with linear index
#what is important later as we will use only part of meta data this indicies will need to be updated
function setMetaDataXYZ(metaData, xOuter,yOuter,zOuter  )
    setMetaDataFieldFromLin(metaData,linIndex,7,UInt32(xOuter))
    setMetaDataFieldFromLin(metaData,linIndex,8,UInt32(yOuter))
    setMetaDataFieldFromLin(metaData,linIndex,9,UInt32(zOuter))

    end

"""
reduce the values of selected metadata block by the supplied values
"""
function reduceMetaDataXYZ(metaData, minX,minY,minZ, linIndex  )
                 #   krowa ...
    setMetaDataFieldFromLin(metaData,linIndex,7,UInt32(xOuter))
    setMetaDataFieldFromLin(metaData,linIndex,8,UInt32(yOuter))
    setMetaDataFieldFromLin(metaData,linIndex,9,UInt32(zOuter))
    end

"""
1)   Left FP
2)   Left FN
3)   Right FP
4)   Right FN
5)   Posterior FP
6)   Posterior FN
7)   Anterior FP
8)   Anterior FN
9)   Top FP
10)   Top FN
11)   Bottom FP
12)   Bottom FN
13)   Data Main Fp
14)   Data Main Fn

accordin numb will invoke function that will give the number of fp and fn in given border or main part
    numb - will  tell what value as seen above we want
    mataData - metadata of data blocks
    linIndex- linear index of given block in metadata

    IMPORTANT if we will have numb above 14 we should just return 0 ///

"""
function getMetaResFPOrFNcount(numb, mataData,linIndex )
   getMetaDataFieldFromLin(metaData,linIndex,locFourthDim)
    setMetaDataFieldFromLin(metaData,linIndex,locFourthDim,valuee)

    end

"""
1)   Left FP
2)   Left FN
3)   Right FP
4)   Right FN
5)   Posterior FP
6)   Posterior FN
7)   Anterior FP
8)   Anterior FN
9)   Top FP
10)   Top FN
11)   Bottom FP
12)   Bottom FN
13)   Data Main Fp
14)   Data Main Fn

accordin numb will invoke function that will give the result offset associated with values above
    numb - will  tell what value as seen above we want
    mataData - metadata of data blocks
    linIndex- linear index of given block in metadata

"""
function getMetaResOffsets(numb, mataData,linIndex )
   getMetaDataFieldFromLin(metaData,linIndex,locFourthDim)
    setMetaDataFieldFromLin(metaData,linIndex,locFourthDim,valuee)

    end

"""
1)   Left FP
2)   Left FN
3)   Right FP
4)   Right FN
5)   Posterior FP
6)   Posterior FN
7)   Anterior FP
8)   Anterior FN
9)   Top FP
10)   Top FN
11)   Bottom FP
12)   Bottom FN
13)   Data Main Fp
14)   Data Main Fn

accordin numb will invoke function that will set  the result offset associated with values above
    numb - will  tell what value as seen above we want
    mataData - metadata of data blocks
    linIndex- linear index of given block in metadata
    value - value to et

"""
function setMetaResOffsets(numb, mataData,linIndex,value )
   getMetaDataFieldFromLin(metaData,linIndex,locFourthDim)
    setMetaDataFieldFromLin(metaData,linIndex,locFourthDim,valuee)

    end

"""
1)   Left FP
2)   Left FN
3)   Right FP
4)   Right FN
5)   Posterior FP
6)   Posterior FN
7)   Anterior FP
8)   Anterior FN
9)   Top FP
10)   Top FN
11)   Bottom FP
12)   Bottom FN
13)   Data Main Fp
14)   Data Main Fn
get old result counters for the result lsts as seen above
"""
function getOldCount(numb, mataData,linIndex)
   getMetaDataFieldFromLin(metaData,linIndex,locFourthDim)
    setMetaDataFieldFromLin(metaData,linIndex,locFourthDim,valuee)

    end
"""
1)   Left FP
2)   Left FN
3)   Right FP
4)   Right FN
5)   Posterior FP
6)   Posterior FN
7)   Anterior FP
8)   Anterior FN
9)   Top FP
10)   Top FN
11)   Bottom FP
12)   Bottom FN
13)   Data Main Fp
14)   Data Main Fn
get new counter value of result queues as specified above
"""
function getNewCount(numb, mataData,linIndex)
   getMetaDataFieldFromLin(metaData,linIndex,locFourthDim)
    setMetaDataFieldFromLin(metaData,linIndex,locFourthDim,valuee)

    end

"""
1)   Left FP
2)   Left FN
3)   Right FP
4)   Right FN
5)   Posterior FP
6)   Posterior FN
7)   Anterior FP
8)   Anterior FN
9)   Top FP
10)   Top FN
11)   Bottom FP
12)   Bottom FN
13)   Data Main Fp
14)   Data Main Fn

will return the diffrence between current counter value and old one for the result set lists associated with
    quantities described just above
"""
function getCounterDiffrence(numb, mataData,linIndex)

   getMetaDataFieldFromLin(metaData,linIndex,locFourthDim)
    setMetaDataFieldFromLin(metaData,linIndex,locFourthDim,valuee)

    end

"""
1)   Left FP
2)   Left FN
3)   Right FP
4)   Right FN
5)   Posterior FP
6)   Posterior FN
7)   Anterior FP
8)   Anterior FN
9)   Top FP
10)   Top FN
11)   Bottom FP
12)   Bottom FN
13)   Data Main Fp
14)   Data Main Fn

decrement value of a associated counter (look above ) by 1
"""
function decrCounterByOne(numb, mataData,linIndex)

   getMetaDataFieldFromLin(metaData,linIndex,locFourthDim)
    setMetaDataFieldFromLin(metaData,linIndex,locFourthDim,valuee)

    end
"""
on the basis of linear index we will find the  metadata x,y,Z
then on the basis of available maxX, maxY, maxZ of metadata we will establish is
in dimension supplied and in direction known from numb we will return boolean
 that will e true if we have some block existing
"""
function isNextBlockExists(metaData,dim, numb ,linIter, isPassGold, maxX,maxY,maxZ)::Bool
   getMetaDataFieldFromLin(metaData,linIndex,locFourthDim)
    setMetaDataFieldFromLin(metaData,linIndex,locFourthDim,valuee)

    end

"""
set block is to be activated property to be true
"""
function  setAsToBeActivated(metaData,linIndex,isPassGold)
   getMetaDataFieldFromLin(metaData,linIndex,locFourthDim)
    setMetaDataFieldFromLin(metaData,linIndex,locFourthDim,valuee)

    end

"""
given metadata it pushes the result to the result list
    metadata is needed mainly to push result into correct queue that is described by
    appropriate offset and counter
"""
function appendResultPadding(metaData, linIndex, x,y,z,iterationnumber, dim,numb)

   getMetaDataFieldFromLin(metaData,linIndex,locFourthDim)
    setMetaDataFieldFromLin(metaData,linIndex,locFourthDim,valuee)

    end

"""
we are adding the result to appropriate spot in the result list
on the basis of the main part offset from the  metadata
"""
function appendResultMainPart(metaData, linIndex, x,y,z,iterationnumber, direction)
   getMetaDataFieldFromLin(metaData,linIndex,locFourthDim)
    setMetaDataFieldFromLin(metaData,linIndex,locFourthDim,valuee)

    end

end#MetaDataUtils


text:
module SimpleSMC

using RNGPool
import Statistics.mean
using Random

include("structures.jl")
include("subroutines.jl")
include("resample.jl")
include("algorithms.jl")
include("interface.jl")

export smc!, csmc!, SMCIO

end # module


text:
using PCRE2

@static VERSION < v"0.7.0-DEV" ? (using Base.Test) : (using Test)


text:
struct RandomScheduler <: ScheduleStrategy end

function scheduler(::RandomScheduler, m::Model)
    return shuffle(allids(m))
end

struct ById <: ScheduleStrategy end

function scheduler(::ById, m::Model)
    return sort(allids(m))
end


text:
# Copyright notice: this file contains several functions derived from Julia's profile.jl

# ip = instruction pointer
# li = line-info

__precompile__()
module FProfile

export @fprofile, backtraces, tree, flat
export get_stackframe, get_method, get_specialization, get_file, get_function, get_module,
       is_C_call, is_inlined, filter_bloodline, prune, details

using Profile
using Base.Core: MethodInstance
using Profile: ProfileFormat, LineInfoFlatDict, LineInfoDict, StackFrame,
    flatten, purgeC, tree_format, UNKNOWN, show_spec_linfo,
    rtruncto, ltruncto, tree_format_linewidth, count_flat, parse_flat, flatten
using DataFrames
using DataStructures: OrderedDict, Accumulator, counter
using Requires

const BackTraces = Vector{Tuple{Int64,Vector{StackFrame}}}

module MissingInfo   # placeholders
missing_info() = nothing
missing_info()  # call it to generate a specialization
const missing_info_method_instance = let res=nothing
    Base.visit(spec->(res=spec;), methods(missing_info).ms[1].specializations)
    res
end
end
using .MissingInfo: missing_info, missing_info_method_instance

struct ProfileData  # a mere container for Base.Profile data
    data::Vector
    lidict::Profile.LineInfoDict
end
ProfileData() = ProfileData(Profile.retrieve()...)
Base.length(pd::ProfileData) = mapreduce(first, +, 0, backtraces(pd))
Base.show(io::IO, pd::ProfileData) =
    write(io, "ProfileData($(length(pd)) backtraces)")
Profile.print(pd::ProfileData; kwargs...) = Profile.print(pd.data, pd.lidict; kwargs...)

""" `@fprofile(expr, delay=0.001, n=1000000)` profiles the execution of `expr`, taking a
snapshot (backtrace) every `delay` seconds (up to `n` backtraces). It returns the
profiling results as a `ProfileData` object. """
macro fprofile(expr, delay=0.001, n=1000000)
    esc(quote
        Profile.clear()
        Profile.init(; n=$n, delay=$delay)
        @profile $expr
        res = $FProfile.ProfileData()
        end)
end

""" `@fprofile(niter::Int, expr)` is shorthand for

```julia
    @fprofile for _ in 1:niter
        expr
    end
```
"""
macro fprofile(niter::Int, expr, args...)
    esc(quote
        $FProfile.@fprofile(for _ in 1:$niter; $expr end, $(args...))
        end)
end

################################################################################
# Accessor functions

get_line(obj)::Int = get_stackframe(obj).line
get_file(obj)::String = get_method(obj).file
get_specialization(obj)::MethodInstance =
    get(get_stackframe(obj).linfo, missing_info_method_instance)
get_method(obj)::Method = get_specialization(obj).def
function get_function(sf)::Function
    met = get_method(sf)
    ftype = fieldtype(met.sig, 1)
    return isdefined(ftype, :instance) ? ftype.instance : missing_info
end
get_module(obj)::Module = get_method(obj).module

get_stackframe(sf::StackFrame) = sf
get_specialization(mi::MethodInstance) = mi
get_method(met::Method) = met
get_function(fun::Function) = fun
get_line(line::Int) = line
get_file(file::Symbol) = file
get_module(m::Module) = m

is_C_call(sf::StackFrame) = sf.from_c
is_inlined(sf::StackFrame) = sf.inlined

const symbol2accessor_dict = OrderedDict(:stackframe=>get_stackframe,
                                         # The line is already part of :stackframe, and
                                         # grouping on :stackframe makes more sense
                                         # anyway.  :line=>get_line,
                                         :specialization=>get_specialization,
                                         :method=>get_method,
                                         :file=>get_file,
                                         :function=>get_function,
                                         :module=>get_module)
const type2symbol_dict = Dict(StackFrame=>:stackframe,
                              MethodInstance=>:specialization,
                              Method=>:method,
                              String=>:file,
                              Function=>:function,
                              Module=>:module)::Any

function symbol2accessor(sym::Symbol)
    @assert(haskey(symbol2accessor_dict, sym),
            "Invalid accessor/combiner: $sym. Must be one of $(collect(Base.keys(symbol2accessor_dict)))")
    symbol2accessor_dict[sym]
end

function type2symbol(T)
    for (typ, sym) in type2symbol_dict
        if T <: typ; return sym; end
    end
    error("Can only handle objects of types $(collect(keys(type2symbol)))")
end
type2accessor(x::Type) = symbol2accessor(type2symbol(x))

################################################################################
# backtraces

""" `backtraces(pd::ProfileData; flatten=true, C=false)` returns a vector of `(count,
backtrace)`, where `backtrace` is a `Vector{StackFrame}` which occurred `count`
times during the profiler run. If `C` is `false`, C function calls are excluded. """
function backtraces(pd::ProfileData; flatten=true, C=false)
    data, lidict = pd.data, pd.lidict
    if flatten
        data, lidict = Profile.flatten(data, lidict)
    end
    data, counts = Profile.tree_aggregate(data)
    out = BackTraces(0)
    for (count, backtrace) in zip(counts, data)
        new_trace = StackFrame[lidict[d] for d in backtrace if C || !is_C_call(lidict[d])]
        if !isempty(new_trace)
            push!(out, (count, new_trace))
        end
    end
    return out
end

function select_backtrace_neighborhoods(btraces::BackTraces, pred::Function,
                                        neighborhood::UnitRange)
    # Returns a vector of traces, possibly longer than the input, that contains every
    # neighborhood centered around where `pred(::StackFrame)` is true. Neighborhood
    # that touch/overlap are merged.
    out = BackTraces(0)
    for (count, trace) in btraces
        hits = find(pred, trace)
        in_hood(i) = any(i in neighborhood+h for h in hits)
        positions = 1:length(trace)
        i = 1
        while true
            start = findnext(in_hood, positions, i)
            if start != 0
                stop = findnext(!in_hood, positions, start)
                if stop == 0
                    push!(out, (count, trace[start:end]))
                    break
                else
                    push!(out, (count, trace[start:stop-1]))
                    i = stop
                end
            else
                break
            end
        end
    end
    return out
end

################################################################################
# tree view

""" `Node(object, count::Int, children::Vector{Node})` represents the `tree`
view of the profiling data. `object` is a `StackFrame`, unless combineby is specified. """
mutable struct Node
    obj
    count::Int
    children::Vector{Node}
end
Node(node::Node, children::Vector{Node}) = Node(node.obj, node.count, children)
Base.getindex(node::Node, i::Int) = node.children[i]
Base.getindex(node::Node, i::Int, args...) = node[i][args...]
Base.length(node::Node) = length(node.children)
for acc in (:get_stackframe, :get_specialization, :get_method, :get_file, :get_function,
            :get_module)
    @eval $acc(node::Node) = $acc(node.obj)
end

# This filter code was taken from TraceCalls.jl
filter_descendents(f, node) = # helper
    # Special casing because of #18852
    isempty(node.children) ? Node[] : Node[n for child in node.children
                                           for n in filter_(f, child)]
filter_(f, node) =
    (f(node) ? [Node(node, filter_descendents(f, node))] :
     filter_descendents(f, node))
Base.filter(f::Function, node::Node) = Node(node, filter_descendents(f, node))
Base.map(f::Function, node::Node) =
    # Apply f(::Node), leaves first
    f(Node(node, Node[map(f, child) for child in node.children]))

prune(node::Node, i=0) =
    i<=0 ? Node(node, Node[]) : Node(node, Node[prune(n, i-1) for n in node.children])

const empty_node_dummy = Node(UNKNOWN, -1, [])

"""    filter_bloodline(f::Function, node::Node; keep_descendents=true, keep_ancestors=true)

keeps all nodes in the tree for which `f(::Trace)` is true of some of its descendents OR
ancestors. """
function filter_bloodline(f::Function, node::Node; keep_descendents=true,
                          keep_ancestors=true)
    if !keep_ancestors
        return filter_bloodline(f, Node(UNKNOWN, -1, find_nodes(f, node));
                                keep_descendents=keep_descendents)
    elseif f(get_stackframe(node))
        return keep_descendents ? node : prune(node)
    else
        children0 = Node[filter_bloodline(f, sub_node; keep_descendents=keep_descendents)
                         for sub_node in node.children]
        children = filter(c->c!==empty_node_dummy, children0)
        return isempty(children) ? empty_node_dummy : Node(node, children)
    end
end

""" `find_nodes(f, node)` returns a vector of all nodes satisfying `f` """
function find_nodes(f::Function, node::Node)
    out = Node[]
    function trav(n)
        if f(n) push!(out, n) end
        foreach(trav, n.children)
    end
    trav(node)
    out
end

tree_line_string(obj, ntext::Int) = rtruncto(string(obj), ntext)

function tree_line_string(li::Union{StackFrame, Method}, ntext::Int)
    widthfile = floor(Integer, 0.4ntext)
    widthfunc = floor(Integer, 0.6ntext)
    if li != UNKNOWN
        if li isa StackFrame && li.line == li.pointer
            return string("unknown function (pointer: 0x",
                          hex(li.pointer,2*sizeof(Ptr{Void})),
                          ")")
        else
            fname = string(get_function(li))
            if li isa Method
                fname = sprint(Base.show_tuple_as_call, li.name, li.sig)
            elseif !li.from_c && !isnull(li.linfo)
                fname = sprint(show_spec_linfo, li)
            end
            return string(rtruncto(string(li.file), widthfile),
                          ":",
                          li.line == -1 ? "?" : string(li.line),
                          "; ",
                          ltruncto(fname, widthfunc))
        end
    else
        return nothing
    end
end

function Profile.tree_format(obj, count::Int, level::Int, cols::Int,
                             ndigcounts::Int, ndigline::Int)
    nindent = min(cols>>1, level)
    ntext = cols - nindent - ndigcounts - ndigline - 5
    base = " "^nindent
    if level > nindent
        nextra = level - nindent
        nindent -= ndigits(nextra) + 2
        base = string(base, "+", nextra, " ")
    end
    base = string(base, rpad(string(count), ndigcounts, " "), " ")
    line = tree_line_string(obj, ntext)
    return line === nothing ? nothing : base*line
end

# tree_format_linewidth is just the width of the line number, which is used to center
# the printing and provide the most useful information. 0 is a cop-out; FIXME
Base.Profile.tree_format_linewidth(x) = 0

function Base.show(io::IO, node::Node)
    cols::Int = Base.displaysize(io)[2]
    level = get(io, :profile_tree_level, 0)
    str = tree_format(node.obj, node.count, level, cols,
                      get(io, :profile_ndigcounts, ndigits(node.count)),
                      get(io, :profile_ndigline, tree_format_linewidth(node.obj)))
    if str !== nothing println(io, str) end
    if !isempty(node.children)
        io2 = IOContext(io,
                        profile_tree_level=level+1,
                        profile_ndigcounts=maximum(ndigits(child.count)
                                                   for child in node.children),
                        profile_ndigline=maximum(tree_format_linewidth(child.obj)
                                                 for child in node.children))
        for c in node.children
            show(io2, c)
        end
    end
end

""" `tree(pd::ProfileData; C = false, mincount::Int = 0, maxdepth=-1)` displays a tree
of function calls, along with the number of backtraces going through each call.

 - `C` -- If `true`, backtraces from C and Fortran code are shown (normally they are excluded).

 - `maxdepth` -- Limits the depth higher than `maxdepth` in the `:tree` format.

 - `mincount` -- Limits the printout to only those lines with at least `mincount` occurrences.
 - `combineby` -- Aggregate by `:specialization, :method, :file, :function`, or `:module`
"""
tree(pd::ProfileData; C = false, mincount::Int = 0, maxdepth=-1, combineby=:stackframe) =
    tree(backtraces(pd; C=C); mincount=mincount, maxdepth=maxdepth, combineby=combineby)
function tree(bt::BackTraces; mincount::Int = 0, maxdepth=-1, combineby=:stackframe)
    # We start with an empty Node tree, then iterate over every trace, adding counts and
    # new branches.
    combiner = symbol2accessor(combineby)
    root = Node(UNKNOWN, -1, [])
    for (count, trace) in bt
        node = root
        prev_obj = nothing
        for sf in trace
            let obj=combiner(sf) # for speed - see #15276
                if !(obj isa StackFrame) && prev_obj == obj
                    continue
                end
                prev_obj = obj
                # Speed note: now that Node.obj is untyped, this line might be a
                # bottleneck.
                i = findfirst(n->n.obj==obj, node.children)
                if i == 0
                    # Make a new branch
                    next_node = Node(obj, 0, Node[])
                    push!(node.children, next_node)
                else
                    next_node = node.children[i]
                end
                next_node.count += count
                node = next_node
            end
        end
    end
    # Sort the children in each node alphabetically. See Profile.liperm.
    # root = map(n->Node(n, n.children[Profile.liperm(map(n->n.obj, n.children))]),
    #            root)
    if maxdepth != -1
        root = prune(root, maxdepth)
    end
    return filter(node->node.count >= mincount, root)
end

function tree(pd::ProfileData, object::T, neighborhood::UnitRange=-1:1; kwargs...) where T
    acc = type2accessor(T)
    tree(select_backtrace_neighborhoods(backtraces(pd),
                                        sf->acc(sf)==object, neighborhood);
         kwargs...)
end

include("tree_base.jl")

################################################################################
# flat view

function counts_from_traces(backtraces::Vector, key::Function,
                            encountered_key::Function=key)
    counts = Dict()
    encountered = Set()
    for (trace_count, trace) in backtraces
        empty!(encountered)
        for sf in trace
            ek = encountered_key(sf)
            if !(ek in encountered)
                push!(encountered, ek)
                k = key(sf)
                counts[k] = get(counts, k, 0) + trace_count
            end
        end
    end
    return counts
end

function self_counts_from_traces(backtraces::Vector, key::Function, applicable::Function)
    counts = Dict()
    for (trace_count, trace) in backtraces
        for sf in @view trace[end:-1:1]
            if applicable(sf)
                k = key(sf)
                counts[k] = get(counts, k, 0) + trace_count
                break
            end
        end
    end
    return counts
end

# -----------------------------------------------------------------------------

function is_applicable(f::Function, object)
    try
        f(object)
    catch e
        if e isa MethodError; return false else rethrow() end
    end
    true
end

"""    flat(pd::ProfileData; C=false, combineby=:stackframe, percent=true, inlined=true)

Returns aggregated profiling results as a `DataFrame`. Arguments:

 - `C=false`: whether to exclude C calls
 - `combineby`: one of `[:stackframe, :specialization, :method, :file, :function, :module]`.
   `combineby=stackframe` provides the most detailed report, with method and line number.
   The other options combine rows that have the same `combineby`.
 - `percent=true`: show percentages
 - `inlined=true`: whether to show inlined function calls
"""
flat(pd::ProfileData; C=false, combineby=:stackframe, percent=true, inlined=true,
     # internal parameter
     _module=nothing) =
   flat(backtraces(pd; flatten=true, C=C); combineby=combineby,
        percent=percent, inlined=inlined, _module=_module)

function flat(btraces::BackTraces;
              C=false,
              combineby=:stackframe,
              percent=true,
              inlined=true,
              # internal parameter
              _module=nothing)
    if _module!==nothing && combineby in (:function, :file)
        # Because a function/file isn't uniquely associated to a module
        error("Cannot combineby $combineby if a module is provided; try `combineby=:method`")
    end
    count_dict = counts_from_traces(btraces, symbol2accessor(combineby))
    keys = collect(Base.keys(count_dict))
    @assert !isempty(keys) "ProfileData contains no applicable traces"
    ntrace = sum(first, btraces)
    perc(var::Symbol, counts) =
        (percent ? Symbol(var, "_pct") => round.(counts ./ ntrace * 100, 2) :
         var => counts)
    count_cols = [perc(:count, [count_dict[sf] for sf in keys])]
    if _module !== nothing
        self_count_dict = self_counts_from_traces(btraces, symbol2accessor(combineby),
                                                sf->get_module(sf) in _module)
        push!(count_cols, perc(:self, [get(self_count_dict, sf, 0) for sf in keys]))
    end
    df = DataFrame(OrderedDict(count_cols..., combineby=>keys))
                               # Use this code to add all the remaining columns
                               # [col=>map(f, keys) for (col, f) in symbol2accessor_dict
                               #  if is_applicable(f, first(keys))]...))
    if _module !== nothing; df = df[[get_module(obj) in _module for obj in df[combineby]], :] end
    if !inlined; df = df[!is_inlined.(df[:stackframe]), :] end
    return sort(df, percent ? :count_pct : :count, rev=true)
end

flat(pd::ProfileData, _module::Tuple; kwargs...) =
    flat(pd; kwargs..., _module=_module)
flat(pd::ProfileData, _module::Module; kwargs...) =
    flat(pd; kwargs..., _module=(_module,))

""" `df_combineby(df::DataFrame)` returns by what this `df` was combined. """
df_combineby(df::DataFrame) =
    names(df)[findfirst(n->haskey(symbol2accessor_dict, n), names(df))]

tree(pd::ProfileData, df::DataFrame, nrow::Int, neighborhood::UnitRange=-1:1) =
    tree(pd, df[nrow, df_combineby(df)], neighborhood)

################################################################################
# Comparisons

function my_outer_join(df1, df2, on::Vector)
    # See DataFrames.jl#1270 for why this is necessary
    kept = setdiff(names(df1), on)
    row_vals(df, i) = map(last, DataFrameRow(df, i))
    mk_dict(df) = Dict(row_vals(df, i)=>i for i in 1:size(df, 1))
    dict1 = mk_dict(df1[:, on])
    dict2 = mk_dict(df2[:, on])
    df_keys = unique(vcat(df1, df2)[on])
    build_col(df, dict, col) = [haskey(dict, row_vals(df_keys, i)) ?
                                df[dict[row_vals(df_keys, i)], col] : 0
                                for i in 1:size(df_keys, 1)]
    df_kept = DataFrame()
    for col in kept
        col1, col2 = Symbol(col, :_1), Symbol(col, :_2)
        df_kept[col1] = build_col(df1, dict1, col)
        df_kept[col2] = build_col(df2, dict2, col)
        df_kept[Symbol(col, :_diff)] = round.(df_kept[col2] .- df_kept[col1], 2)
    end
    return hcat(df_kept, df_keys)
end

function flat(pd1::ProfileData, pd2::ProfileData; _module=nothing, kwargs...)
    df1 = flat(pd1; _module=_module, kwargs...)
    df2 = flat(pd2; _module=_module, kwargs...)
    combineby_ind = _module === nothing ? 2 : 3
    df = FProfile.my_outer_join(df1, df2, names(df1)[combineby_ind:end])
    return sort(df, names(df)[3], rev=true)
end

flat(pd1::ProfileData, pd2::ProfileData, _module::Tuple; kwargs...) =
    flat(pd1, pd2; kwargs..., _module=_module)
flat(pd1::ProfileData, pd2::ProfileData, _module::Module; kwargs...) =
    flat(pd1, pd2; kwargs..., _module=(_module,))

################################################################################
# ProfileView

@require ProfileView begin
ProfileView.view(pd::ProfileData; kwargs...) =
    ProfileView.view(pd.data; lidict=pd.lidict, kwargs...)
end

end # module


text:
mutable struct OrderBook
    bids::OrderedDict(Float64, Float64)
    asks::OrderedDict(Float64, Float64)
end


text:
export randomInv, RandomVectorSketch

"""
Solve TAx=Tb with T a random projector
"""
function randomInv(
  stp::AbstractStopping;
  is_zero_start::Bool = false,
  k = 50,
  random_func = random_matrix_1,
  kwargs...,
)
  A, b = get_matrix(stp.pb), get_vector(stp.pb)
  m = size(A, 1)

  start!(stp)
  k = Int(floor(m / 8))
  T = random_func(k, m)
  xk = T * A \ T * b

  return update_and_stop!(stp, x = xk)
end

"""
Random vector sketch

Section 3.2 in Gower, R. M., & Richtárik, P. (2015).
Randomized iterative methods for linear systems.
SIAM Journal on Matrix Analysis and Applications, 36(4), 1660-1690.
"""
function RandomVectorSketch(
  stp::AbstractStopping;
  is_zero_start::Bool = false,
  random_func = random_matrix_1,
  kwargs...,
)
  A, b = get_matrix(stp.pb), get_vector(stp.pb)
  m, n = size(A)
  x0 = stp.current_state.x
  xk = x0
  stp.current_state.res = A * xk - b
  OK = start!(stp)

  while !OK
    s = vec(random_func(1, m)')
    As = A' * s
    xk = As == 0 ? x0 : x0 - dot(s, stp.current_state.res) / dot(As, As) * As

    update!(stp.current_state, x = xk)
    stp.current_state.res = A * xk - b
    OK = stop!(stp)
    x0 = xk
  end

  return stp
end