Design how to dynamically load and forget content

[axelpale]

Tools that help in connecting tapspace front-end to backends with so much data that only a fraction can be downloaded and rendered at once.

Approaches

• quadtree
• octree
• directed graph
• state machine

Propositions

• SpaceTileTree, tap-to-split problem

[axelpale]

Issue https://github.com/taataa/tapspace/issues/105 was caused because content was removed in the middle of a gesture. The forgetting of content should happen only after gestures have ended.

[axelpale]

Solving the issue #113 will probably show us how to do this.

[axelpale]

Do we need a general depth-limited graph search algorithm?

Consider we have a tree structure where the nodes can be opened (a leaf becomes a parent for a bunch of new leaves) or closed (the children of the nodes are removed so the node becomes a leaf). Consider also a graph-based UI with a single focal point. Let the focal node be the one closest to the center of the viewport, at the tree-depth most suitable for the current scale.

The question is: when the focal node changes, how we determine which nodes to open or close.

[axelpale]

Graph traversal libs:

• https://www.npmjs.com/package/async-bfs
• https://www.npmjs.com/package/tree-crawl

Good ones are hard to find!

[axelpale]

An approach we used in Taataa, videograph example, and a school-project that starts with S:

Three layers:

• global model (servers)
• local model (caching proxy of server data)
• view model (visible portion of the local model)

In other words:

• all content
• known content
• visible content

If the view moves, we must:

• collect all content that should be visible
• show all content that should be visible
• hide all content that were visible but should no be anymore

Two cases, let us call them:

• LINKED: content items are explicitly linked
• COORDINATED: content items have global coordinates (implicitly linked)

For the case LINKED, an algorithm:

1. select a focal content item (e.g. nearest element at the middle of the screen)
   • linear search should be fast enough because the number of visible items cannot be high
2. mark every visible item for deletion
   • this way we prevent visible but unreachable islands
3. init a list for items to fetch from the global model
4. init a list for items to make visible
5. init a list for the resulting visible items
6. begin a depth-limited breadth-first traversal on the focal item
   • traverse on the local model until depth-limit or unknown adjacent
   • bfs over dfs because the items nearest to the focal item are more important and should be fetched first. The visual experience should be like a wave, not like the nibbles game.
7. for every visited item
   • unmark item from deletion
   • if item is not visible, push it to the make-visible list
   • if item is not yet at depth-limit then for each adjacent items:
     • if adjacent item is known, push it to a queue as required by the depth-first search alg
     • else mark the adjacent item for fetch. Mark also the depth
8. for each visible item
   • if the item is marked for deletion, remove it
   • else push it to the new list of visible items
9. for each make-visible item
   • make the item visible
   • push it to the new list of visible items
10. fetch the should-fetch items (async operation)
    • only if the algorithm is not cancelled (e.g. new run due to changed focal item)
11. for each fetched item
    • store item to local model
    • make the item visible
    • if depth < depth-limit, still more nodes are needed: set a repeat flag to true
12. if the repeat flag is on, restart the algorithm
    • this way fetching continues until the frontier meets the depth limit
    • performance penalty of repetition should not be an issue because the breadth-first search is done synchronously with a relatively small number of items

The async fetching should be cancellable to prevent unnecessary async API calls.

[axelpale]

For the case COORDINATED, an algorithm:

Assume there exists one-to-one mapping between ids and coordinates.

Init

• Let GLOBAL be a mapping from item ids to item models (slow async access)
• Let LOCAL be a mapping from item ids to item models (fast sync access)
• Let VISIBLE be a mapping from item ids to item models
  • the currently visible items
• Let FETCH be an empty list for item ids to fetch
• Let SHOW be an empty list for items to make visible
• Let NEXT be an empty list for items that will remain visible (next VISIBLE).

1. for each ITEM in VISIBLE, mark to be hidden: ITEM.HIDE = TRUE
2. compute ids from coordinates of items that should be visible, store ids to a list SHOULDVIS
   • the list includes ids of items that can be visible, hidden but known locally, known only globally, or do not exist at all.
3. for each ITEM in SHOULDVIS
   • if ITEM in VISIBLE
     • unmark: ITEM.HIDE = FALSE
     • push to NEXT
   • elseif ITEM in LOCAL
     • push to SHOW
   • else
     • push to FETCH
4. for each ITEM in VISIBLE
   • if ITEM.HIDE
     • hide ITEM
5. for each ITEM in SHOW
   • show ITEM
   • push to NEXT
6. Set VISIBLE = NEXT, forget previous VISIBLE
7. fetch all items in FETCH (async), store to FETCHED
8. for each ITEM in FETCHED
   • store ITEM to LOCAL
   • if not cancelled
     • show ITEM
     • store ITEM to VISIBLE

[axelpale]

Solved in tapspace 2.0.0-alpha.16 or so with tapspace.loaders.TreeLoader.