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

var pointsNumber = 45
var Δ = 0.1

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 ffpGroup = area.append('g')

var ε = 1e-6

function filterData(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
}

var i = 0
var currentValue = Math.random()
var values = []
var limit = d3.scale.linear().clamp(true)

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

        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('r', 0)
            .attr('fill', '#aaa')
            .transition()
            .attr('r', 1.5)

        var data = filterData(values, Δ)

        var filteredDots = ffpGroup.selectAll('circle')
            .data(data, function (d) { return d.x + " " + d.y })
        filteredDots.exit().remove()

        filteredDots
            .enter().append('circle')
            .attr('cx', function(d) { return x(d.x) })
            .attr('cy', function(d) { return y(d.y) })
            .attr('fill', '#000')
            .attr('r', 0)
            .transition()
            .attr('r', 1.5)

        var boundaries = []
        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(data).forEach(function(d) {
            boundaries.push(d)
            boundaries.push(offsetLine(d, Δ))
            boundaries.push(offsetLine(d, -Δ))
        })

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

        lines.enter().append('line')
            .attr('stroke', '#ccc')
            .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) })
        i++
    }
}, 500)