A few days ago I started brainstorming how we might go about handling input in a way that actually satisfies the continuous and temporal nature of FRP *behaviors*. Today, let’ take a deeper dive into one possible implementation.

## Understanding the Problem

The problem can essentially be broken down into the following goals:

- Storage of historical input data
- Efficient interpolation between discrete inputs

For input handling, there are two basic types: digital and analog. The digital input is `on`

or `off`

, and the analog input is a value that ranges between two `min`

and `max`

values for the input. However, since all of our input is made up of discreet inputs, the problem is nearly identical.

Here is a sample scatter-plot graph of a keypress:

```
│
1 ┤ ▪ ▪ ▪ ▪ ▪
│
│
0 └────────▪──────────▪──────▪───────────▪──────────▪───────▶ t
```

Each of the `▪`

represent an actual input change for the button on the time. Of course, the problem with this plot above is that there is no `f(t)`

that results in a value for every value of `t`

. We need to interpolate that graph:

```
│
1 ┼────▪───┐ ▪──┐ ▪───┐ ▪───────┐ ▪────┐
│ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │
0 └────────▪───────┴──▪──┴───▪───┴───────▪─────┴────▪───────▶ t
t₀ t₁ t₂ t₃ t₄ t₅ t₆ t₇ t₈ t₉
```

This provides us with a nice step-graph. Now, we can most definitely provide an answer for `f(t)`

given any `t`

that has occurred.

## Basic Approach

Let’ start thinking about the shape of the algorithm. The simplest approach is to simply loop through the input and return the correct value based on the time range.

Here is a sample program based on the above input graph:

```
let t₀ = 0, t₁ = 4, t₂ = 8, t₃ = 10, t₄ = 12
let t₅ = 15, t₆ = 18, t₇ = 22, t₈ = 25, t₉ = 28
let up = 1, down = 0
struct Range { let start: Int, end: Int }
struct Input { let range: Range, value: Int }
var inputs: [Input] = []
// Simulate an input stream...
inputs.append(Input(range: Range(start: t₀, end: t₁), value: up))
inputs.append(Input(range: Range(start: t₁, end: t₂), value: down))
inputs.append(Input(range: Range(start: t₂, end: t₃), value: up))
inputs.append(Input(range: Range(start: t₃, end: t₄), value: down))
inputs.append(Input(range: Range(start: t₄, end: t₅), value: up))
inputs.append(Input(range: Range(start: t₅, end: t₆), value: down))
inputs.append(Input(range: Range(start: t₆, end: t₇), value: up))
inputs.append(Input(range: Range(start: t₇, end: t₈), value: down))
inputs.append(Input(range: Range(start: t₈, end: t₉), value: up))
inputs.append(Input(range: Range(start: t₉, end: Int.max), value: down))
func f(t: Int) -> Int {
for input in inputs {
if input.range.start <= t && t < input.range.end {
return input.value
}
}
return inputs.last?.value ?? Int.min
}
```

Then we can simply call the function to get our results:

```
f(0) // -> 1
f(29) // -> 0
f(16) // -> 0
f(22) // -> 0
```

Notice that we can call `f(t)`

in any order and it all works.

## Optimization

Now, there is a problem with the above implementation: as the game progresses, more and more input will be generated. This is not good‚Ä¶ this is an `O(n)`

algorithm. What we want to as close to is the `O(1)`

algorithm that is available to us in non-FRP world.

Well, one simple approach is to use the previous result as a hint. Here’ the new function `f(t)`

.

```
func f(t: Int, _ index: Int? = nil) -> (value: Int, index: Int) {
let start = index ?? 0
let forward = 1, reverse = -1
let len = inputs.count
let step = t < inputs.get(start)?.range.start ? reverse : forward
// search loop
for var idx = start; 0 <= idx && idx < len; idx += step {
let input = inputs[idx]
if input.range.start <= t && t < input.range.end {
return (input.value, idx)
}
}
let value = (step == forward) ?
inputs.last?.value ?? Int.min :
inputs.first?.value ?? Int.min;
return (value, 0)
}
```

The major updates are:

- Return a tuple
`(value, index)`

that can provide us a hint as to the index into the`inputs`

history to start at. - Based on the given
`index`

, we can also determine the search order.

Note:I’m using an extension to`Array`

; you can find it here: Array.get.

The updated usage code:

```
let f₀ = f(0)
let f₁₆ = f(16, f₀.index + 1)
let f₂₂ = f(22, f₁₆.index + 1)
let f₂₉ = f(29, f₂₂.index + 1)
```

When they are called in the expected time order, the number of times through the “search loop” above is reduced from 25 down to 10. The thing to note from the value 10 here, is that this is the *minimum* number of searches required for this approach.

That’ great!

Also, imagine if there were thousands of inputs. The value of 25 above would be *significantly* higher as each search would be starting at index 0. With this new optimized approach, the number searches will be bound by the number of inputs that have happened since the last call of `f(t)`

.

It’s good to note that you could still call this version of the function in any order and all should still be good. The the index hint is only used as the starting search point in the `inputs`

array.

# Summary

This approach is looking pretty solid to me, though, I’ve only really played around with it in the playground and with fake, simulated input data. Next time, I’ll explore out how this algorithm looks with real input handling code.