Hylograph.Internal.Selection.Join

computeJoin :: forall datum. Eq datum => Array datum -> Array (ElementBinding datum) -> JoinSets datum

Pure join algorithm matching D3 semantics with support for duplicate datums

This implements the data join pattern:

1. New data not in old elements -> enter
2. Data matching existing elements -> update
3. Old elements not in new data -> exit

Handles duplicates correctly by matching in order. For example, if old data is "HELLO" and new data is "WORLD", the two 'L's in "HELLO" will match correctly with elements in order.

Users control identity semantics via their Eq instance:

instance Eq Node where
  eq (Node a) (Node b) = a.id == b.id  -- Identity by ID

Time complexity: O(n * m) worst case, where n = new data length, m = old elements length Space complexity: O(m) for tracking remaining elements

Properties:

• Disjoint: No element appears in multiple sets
• Complete: All new data appears in enter ∪ update
• Complete: All old elements appear in update ∪ exit
• Order: enter and update preserve input order
• Duplicates: Handles duplicate datums by matching in order

computeJoinWithKey :: forall datum key. Eq key => Array datum -> Array (ElementBinding datum) -> (datum -> key) -> JoinSets datum

Pure join algorithm with custom key function

Like computeJoin, but uses a key function to extract comparable keys instead of requiring Eq on the data itself.

This is essential for data types that don't have lawful Eq instances (e.g., opaque foreign types like D3Link_Swizzled).

Example:

computeJoinWithKey newLinks oldLinks (\l -> unsafeCoerce l # _.id)

type ElementBinding datum = { datum :: datum, element :: Element }

Represents an element with its bound datum

type EnterBinding datum = { datum :: datum, newIndex :: Int }

Represents a datum entering with its index in the new data array

type UpdateBinding datum = { element :: Element, newDatum :: datum, newIndex :: Int, oldDatum :: datum }

Represents an element being updated from old to new datum

type JoinSets datum = { enter :: Array (EnterBinding datum), exit :: Array (ElementBinding datum), update :: Array (UpdateBinding datum) }

The three disjoint sets resulting from a join