[TypeScript] Help with State-Delta system

[hidden cradle]

I have a State that I want to update every Step.
One can step forward, backward, or "play" which just does those every a certain amount of ms.

Therefore I had 3 appraoches

1. Make a stepForward and stepBackward methods that logically manipulate the State each time they're called properly

• I tried that initially, and while it works, it can often be really annoying, some of those represent array sorting algorithms. Therefore, it's SO MUCH more elegant to just write the actual sort method as it is and record various States than somehow make a weird version of it that makes 1 mutation every time it is called.

2. Save a list of States and just pick the one with the current index

• I didn't even try it. This will be the EASIEST of the bunch by far, however it could get very memory intensive. Imagine a BubbleSort with an array of length 30, you could potentially reach 900 steps, each containing a 30 long array(and even more data but you get my point)... Ik it's not the end of the world in this specific example but my point is it's really bad memory wise

3. A "Delta" system that only records changes rather than the entire array

• So... I did do that. I made a generic, type-safe and dare I say robust Delta system... problem is it lacks in many fields... I struggled to make a type-safe way to modify nested objects/arrays, I struggled to deal with removal of elements from an array (and having the step backward un-do them) etc, and my specific system really started showing it wasn't up for the task...

I still believe a form of "Delta" system is the BEST appraoch for this method, but maybe there's just something I'm not thinking about...

My question is:
How would you handle the situation I am in rn? Do you have better solutions in mind?

(Btw you can write examples in whatever language I'll write it in TypeScript myself later, also if anyone needs extra context like code snippets or whatnot lmk I'll send, tho I think I covered quite a bit of context)

[silk pendant]

Can you provide some code examples those three options, it's a bit hard to understand exactly what you mean. I'm especially confused about the fact that you talk about updating a State object and then you talk about arrays. Are you mutating the same instance of State or creating several instances? Anyway code examples would help.

[hidden cradle]

Yeah gladly

So the context:
I'm making an algorithm visualizer (using Vue.JS).

A certain component receives a State object, and uses its values to display whatever needs to be displayed.
There are "backward", "forward" and a "play/pause" buttons for various controls, I want to be able to pause the animation and see each individual step as well as reverting it.

An example algorithm I made was BubbleSort
The state looks like this:
{ array: number[], idArray: number[], done: boolean, sortedIndex: number, scanningIndex: number }

there are methods named stepForward and stepBackward which progress and revert the animation by changing the state(affecting the state directly affects the component's visuals)

my first method had a processForward and processBackward methods called respectively, which changed the state in a computed manner, so each call for processForward would change the state in a way that progressed "one step"

Example:

stepForward(): void {
  if (this.IsComplete)
    return;

  frame++;
  this.processForward();
}

But logically it was extremely messy and annoying to deal with(instead of just writing a simple bubble sort you gotta make a state machine and split it into sections so that the whole sort doesn't run at once, it was really annoying...)

I then thought of the idea of having a list of State that is precomputed (which lets me write the simple bubble sort algorithm and simply record the array whenever I change it), and a frame index, making the current State: states[frame].... but this can get SUPER memory intensive which... I'm no fan of

finally... I thought of deltas - changes of the array

I can't avoid regular fields like sortedIndex from just being contained wholely when they're changed, but that's fine, I just mostly wanted to avoid storing the entire array for every change I make in it

at first I made a State and Step object and a method called generateSteps which... well it made a list of Steps
each step mutates the State both forward and backward (super important) so that I can also revert it

it works but my previous setup was very tedius (completely manual, prone to human error - so lots of debugging, and had a lot of albeit very small, but annoying steps)

so I overcomplicated and made a big generic system to do it for me

export type ArraySwapDelta<State> = {
  [Key in ArrayKeys<State>]: {
    __brand__: typeof arraySwapTag;
    name: Key;
    index1: number;
    index2: number;
  };
}[ArrayKeys<State>];

export function createArraySwapDelta<State, Key extends ArrayKeys<State>>(
  name: Key,
  index1: number,
  index2: number,
): ArraySwapDelta<State> {
  return { __brand__: arraySwapTag, name, index1, index2 } as ArraySwapDelta<State>;
}

export function createArraySwapOperation<State>(): DeltaOperation<State, ArraySwapDelta<State>> {
  return {
    forward: (state, { name, index1, index2 }) => {
      const array = state[name] as ArrayElement<State[typeof name]>[];
      [array[index1], array[index2]] = [array[index2]!, array[index1]!];
    },
    backward: (state, { name, index1, index2 }) => {
      const array = state[name] as ArrayElement<State[typeof name]>[];
      [array[index1], array[index2]] = [array[index2]!, array[index1]!];
    },
  } as DeltaOperation<State, ArraySwapDelta<State>>;
}

Here's a snippet of a swap operation between two indices of an array
This perfectly finds all the fields inside a generic given State which are arrays and autocompletes them in the method paramters(super awesome feature from TypeScript, gotta say), creating this ArraySwapDelta object which I store in a list of Deltas, and then the DeltaOperation uses this object to perform forward and backward

[steel mortar]

@hidden cradle, your codeblock was automatically pasted to https://paste.myst.rs/fq1zvtso

[hidden cradle]

I had another operation for SET (just setting a regular variable), and ARRAY_SET (setting an item in an array)

but this system struggles quite a bit with removal and especially nested things (for example if you have a nested array)

the usage of nested is practically non existent so I'm not too stressed on that tho it's pretty nice to have...
I'm more so worried about the difficulty to perform proper array slicing, of course I mean reverting it is the problem

I also kind of think I SUPER overcomplicated and I can go WAY easier

    const state = this.CurrentState;
    const array = state.array;

    const length = array.length;

    for (let i = 0; i < length - 1; i++) {
      this.addStep(b => b 
        .set("sortedIndex", length - i)
        .set("swapped", false));

      let swapped = false;

      for (let j = 0; j < length - i - 1; j++) {
        this.addStep(b => b.set("scanningIndex", j));

        if (array[j]! > array[j + 1]!) {
          this.addStep(b => b
            .arraySwap("array", j, j + 1)
            .arraySwap("idArray", j, j + 1)
            .set("swapped", true));
          swapped = true;
        }
      }

      if (!swapped) break;
    }

I will say tho: it makes the code really nice to work with (in comparison to the first delta system which was HORRID in terms of usage, and the original, purely commutative solution, which was a massive headache)

[steel mortar]

@hidden cradle, your codeblock was automatically pasted to https://paste.myst.rs/vtg27rvv

[hidden cradle]

This is the bubble sort's generateSteps btw

[silk pendant]

Funny, I actually worked on a project exactly like this one, about 3 years ago, but for visualizing the Floyd-Marshall algorithm. On top of visualizing the algorithm on a grid, I also had a time travel debugger displaying the actual code of the algorithm as you stepped forward or backwards through it. I don't remember where I left things off but I think it was close to done. Here's the repo: "https://github.com/snowfrogdev/floyd-warshall" it's an Angular project, similar enough to Vue that you should be able to understand what is going on.

But essentially, I use a buffer of state objects. I use a web worker to generate the "frames" to the buffer, the main thread reads the buffer. I only generate enough frames to fill the buffer, that way I control how much memory is used.

[hidden cradle]

Oooh I'll take a look into it

I'll update when I have a question or reach a conclusion, just currently heading to sleep

[hidden cradle]

I'll be honest, it really confused me ngl, I can prob give it another look but I figured due to the small dimensions of my project I won't die if I just store an array of states