var margin = {top: 50, right: 20, bottom: 100, left: 40},
    width = 960 - margin.left - margin.right,
    height = 500 - margin.top - margin.bottom

var pointsNumber = 45

var ε = 1e-6
var Δ = 0.1,
    minΔ = ε,
    maxΔ = 0.5
var values = []

var x = d3.scale.linear()
    .domain([0, pointsNumber])
    .range([0, width])

var y = d3.scale.linear()
    .domain([0, 1])
    .range([height, 0])

var yAxis = d3.svg.axis()
    .scale(y)
    .orient("left")

var svg = d3.select("body").append("svg")
    .attr("width", width + margin.left + margin.right)
    .attr("height", height + margin.top + margin.bottom)

var area = svg
    .append("g")
    .attr("transform", "translate(" + margin.left + "," + margin.top + ")")

area.append("g")
    .attr("class", "axis")
    .call(yAxis)

var areaGroup = area.append('g')
var sdtLines = area.append('g')
var ffpLines = area.append('g')
var sdtGroup = area.append('g')
var ffpGroup = area.append('g')

var deltaText = area.append('text')
    .text('Δ = ' + (+Δ.toFixed(3)))
    .attr('x', 0)
    .attr('y', height + 20)


var SDTtext = area.append('text')
    .attr('x', 0)
    .attr('y', height + 50)
SDTtext.append('tspan')
    .text('SDT: ')
    .attr('fill', '#a00')
SDTtext = SDTtext.append('tspan')
    .text('0 points saved, average error is 0')

var FFPtext = area.append('text')
    .attr('x', 0)
    .attr('y', height + 80)
FFPtext.append('tspan')
    .text('FFP: ')
    .attr('fill', '#0a0')
FFPtext = FFPtext.append('tspan')
    .text('0 points saved, average error is 0')

var shadow = d3.svg.shadow()
    .color('#fff')
    .multiplication(2)
    .deviation(3)

var slider = area.append('g')

var filterId = shadow(slider)

var sliderScale = d3.scale.linear()
    .domain([0.5 - maxΔ, 0.5, 0.5 + maxΔ])
    .range([maxΔ, minΔ, maxΔ])
    .clamp(true)

var drag = d3.behavior.drag()
    .on("drag", update)

var upperPoint = slider.append('circle')
    .attr('cy', y(0.5 + Δ))

var lowerPoint = slider.append('circle')
    .attr('cy', y(0.5 - Δ))

slider.selectAll('circle')
    .attr('cx', 0)
    .attr('r', 5)
    .attr('fill', '#fff')
    .attr('stroke', '#000')
    .attr('filter',"url(#" + filterId + ")")
    .call(drag)

function update() {
    Δ = sliderScale(y.invert(d3.event.y))
    upperPoint.attr('cy', y(0.5 + Δ))
    lowerPoint.attr('cy',y(0.5 - Δ))
    deltaText.text('Δ = ' + (+Δ.toFixed(3)))
    draw()
}

function filterDataSDT(d, Δ){
    d = d.slice()
    var start = 0,
        result =[],
        trendBoundaries = [Infinity, -Infinity],
        currentPointBoundaries = [],
        prevTrendBoundaries = [],
        newY = d[0],
        lower = 0,
        upper = 1,
        pushPoint = function () { result.push({ x: start, y: newY }) }
    pushPoint()
    for (var i = 0; i < d.length; i++) {
        currentPointBoundaries = [
            (d[i] - d[start] + Δ) / (i - start),
            (d[i] - d[start] - Δ) / (i - start)
        ]
        prevTrendBoundaries = trendBoundaries.slice()
        if (trendBoundaries[upper] < currentPointBoundaries[upper] + ε) {
            trendBoundaries[upper] = currentPointBoundaries[upper]
        }
        if (currentPointBoundaries[lower] < trendBoundaries[lower] + ε) {
            trendBoundaries[lower] = currentPointBoundaries[lower]
        }
        if (trendBoundaries[lower] < trendBoundaries[upper] + ε) {
            trendBoundaries = [Infinity, -Infinity]
            i--
            newY = d3.sum(prevTrendBoundaries) * (i - start) / 2 + d[start]

            start = i
            d[start] = newY

            pushPoint()
        }
    }
    i--
    if (d.length > 1) newY = d3.sum(trendBoundaries) * (i - start) / 2 + d[start]
    start = i
    pushPoint()
    return result
}

function filterDataFFP(d, Δ) {
    d = d.slice()
    var start = 0,
        result = [],
        trendBoundaries = [Infinity, -Infinity],
        currentPointBoundaries = [],
        currentPointTrend,
        farthestFeasible = 0,
        lower = 0,
        upper = 1,
        pushPoint = function () { result.push({ x: farthestFeasible, y: d[farthestFeasible] }) }
    pushPoint()
    while (farthestFeasible < d.length - 1) {
        for (var i = start; i < d.length; i++) {
            currentPointBoundaries = [
                (d[i] - d[start] + Δ) / (i - start),
                (d[i] - d[start] - Δ) / (i - start)
            ]
            if (trendBoundaries[upper] < currentPointBoundaries[upper] + ε) {
                trendBoundaries[upper] = currentPointBoundaries[upper]
            }
            if (currentPointBoundaries[lower] < trendBoundaries[lower] + ε) {
                trendBoundaries[lower] = currentPointBoundaries[lower]
            }
            currentPointTrend = (d[i] - d[start]) / (i - start)
            if (trendBoundaries[upper] < currentPointTrend + ε && currentPointTrend < trendBoundaries[lower] + ε) {
                farthestFeasible = i
            } else if (trendBoundaries[lower] < trendBoundaries[upper] + ε) {
                trendBoundaries = [Infinity, -Infinity]
                i = start = farthestFeasible
                pushPoint()
            }
        }
        trendBoundaries = [Infinity, -Infinity]
        start = farthestFeasible
        pushPoint()
    }
    return result
}
function calculateErr(data, filteredData) {
    var filteredX = filteredData.map(function(d) {
        return d.x
    })
    var filteredY = filteredData.map(function(d) {
        return d.y
    })
    var filteredDataScale = d3.scale.linear()
        .domain(filteredX)
        .range(filteredY)

    var averageError = d3.mean(data, function(d, i) {
        return Math.abs(d - filteredDataScale(i))
    })
    return +(averageError).toFixed(4)
}
function drawArrow(values, filteredData){
    var lines = filteredData.map(function(d) {
        console.log(values[d.x])
        return [{x: x(d.x), y: y(values[d.x])}, {x: x(d.x), y: y(d.y)}]
    })
    var arrowData = []
    lines.forEach(function(d) {
        arrowData.push(d)
        var sign = (d[0].y == d[1].y)? 0:(d[0].y - d[1].y)/Math.abs(d[0].y - d[1].y)
        arrowData.push([{x: d[0].x - 2, y: d[1].y + 6 * sign}, d[1]])
        arrowData.push([{x: d[0].x + 2, y: d[1].y + 6 * sign}, d[1]])
    })

    var arrows = areaGroup.selectAll('line')
        .data(arrowData, function (d) { return d[0].x + " " + d[0].y + " " + d[1].x + " " + d[1].y})
    arrows.exit().remove()

    arrows.enter().append('line')
        .attr('stroke', '#a00')
        .attr('opacity', 0.5)
        .attr('x1', function(d) { return d[0].x })
        .attr('y1', function(d) { return d[0].y })
        .attr('x2', function(d) { return d[1].x })
        .attr('y2', function(d) { return d[1].y })
}
var i = 0
var currentValue = 0.5
var limit = d3.scale.linear().clamp(true)

function draw() {
    var circles = areaGroup.selectAll('circle')
        .data(values)
    circles.exit().remove()

    circles
        .enter().append('circle')
        .attr('cx', function(d, i) { return x(i) })
        .attr('cy', function(d) { return y(d) })
        .attr('fill', '#ddd')
        .attr('r', 2)

    var dataFFP = filterDataFFP(values, Δ)
    var dataSDT = filterDataSDT(values, Δ)
    function filteredPointID(d) { return d.x + " " + d.y }

    var filteredSDT = sdtGroup.selectAll('circle')
        .data(dataSDT, filteredPointID)
    filteredSDT.exit().remove()

    filteredSDT
        .enter().append('circle')
        .attr('cx', function(d) { return x(d.x) })
        .attr('cy', function(d) { return y(d.y) })
        .attr('fill', '#a00')
        .attr('r', 2)
    drawArrow(values, dataSDT)
    var filteredFFP = ffpGroup.selectAll('circle')
        .data(dataFFP, filteredPointID)
    filteredFFP.exit().remove()

    filteredFFP
        .enter().append('circle')
        .attr('cx', function(d) { return x(d.x) })
        .attr('cy', function(d) { return y(d.y) })
        .attr('fill', '#0a0')
        .attr('r', 2)

    var boundariesSDT = []
    var boundariesFFP = []

    function offsetLine (line, offset) {
        return [{x: line[0].x, y: line[0].y + offset}, {x: line[1].x, y: line[1].y + offset}]
    }
    d3.pairs(dataFFP).forEach(function(d) {
        boundariesFFP.push(offsetLine(d, Δ))
        boundariesFFP.push(offsetLine(d, -Δ))
    })
    d3.pairs(dataSDT).forEach(function(d) {
        boundariesSDT.push(offsetLine(d, Δ))
        boundariesSDT.push(offsetLine(d, -Δ))
    })
    function linesID(d) { return d[0].x + " " + d[0].y + " " + d[1].x + " " + d[1].y}
    var linesSDT = sdtLines.selectAll('line')
        .data(boundariesSDT, linesID)
    linesSDT.exit().remove()

    linesSDT.enter().append('line')
        .attr('stroke', '#a00')
        .attr('opacity', 0.3)
        .attr('x1', function(d) { return x(d[0].x) })
        .attr('y1', function(d) { return y(d[0].y) })
        .attr('x2', function(d) { return x(d[1].x) })
        .attr('y2', function(d) { return y(d[1].y) })

    var linesFFP = ffpLines.selectAll('line')
        .data(boundariesFFP, linesID)
    linesFFP.exit().remove()

    linesFFP.enter().append('line')
        .attr('stroke', '#0a0')
        .attr('opacity', 0.3)
        .attr('x1', function(d) { return x(d[0].x) })
        .attr('y1', function(d) { return y(d[0].y) })
        .attr('x2', function(d) { return x(d[1].x) })
        .attr('y2', function(d) { return y(d[1].y) })
    if (values.length > 1){
        SDTtext.text(dataSDT.length + ' points saved, average error is ' + calculateErr(values, dataSDT))
        FFPtext.text(dataFFP.length + ' points saved, average error is ' + calculateErr(values, dataFFP))
    }
}

setInterval(function() {
    if (i < pointsNumber) {
        values.push(currentValue)
        currentValue = limit(currentValue + .3 * Math.random() - .15 + .01 * Math.cos(i * 5))
        draw()
        i++
    }
}, 300)