A Simple State-Based Synchronization Algorithm

import crypto from 'crypto'; // For stable hashing

// --- Data Structures ---

class Item {
    // Make id readonly after construction
    public readonly id: string;
    public content: string;

    constructor(id: string, content: string) {
        this.id = id;
        this.content = content;
    }

    toString(): string {
        // Simple representation for logging
        return `Item(id='${this.id}', content='${this.content}')`;
    }
}

// Use Map for stores: { item_id => Item }
type Store = Map<string, Item>;

// Use Map for status: { item_id => [etag_A | null, etag_B | null] }
// Tuple represents etags from the *last* sync
type StatusMap = Map<string, [string | null, string | null]>;

// --- Helper Functions ---

function getEtag(item: Item | null | undefined): string | null {
    """Calculates a stable SHA1 etag for an item's content."""
    if (!item) {
        return null;
    }
    // Use crypto for stable hashing
    const hash = crypto.createHash('sha1');
    hash.update(item.content, 'utf-8');
    return hash.digest('hex');
}

function copyItem(sourceStore: Store, destStore: Store, itemId: string): void {
    """Copies item content from source to destination."""
    const sourceItem = sourceStore.get(itemId);
    if (sourceItem) {
        // Create a new Item object to avoid shared references
        destStore.set(itemId, new Item(sourceItem.id, sourceItem.content));
        console.log(`SYNC: Copied item '${itemId}' from source to destination.`);
    } else {
        console.log(`SYNC WARNING: Tried to copy non-existent item '${itemId}' from source.`);
    }
}

function deleteItem(store: Store, itemId: string): void {
    """Deletes an item from a store."""
    if (store.has(itemId)) {
        store.delete(itemId);
        console.log(`SYNC: Deleted item '${itemId}' from store.`);
    }
}

function resolveConflict(
    itemId: string,
    itemA: Item | undefined,
    itemB: Item | undefined,
    storeA: Store,
    storeB: Store
): [string | null, string | null] {
    """
    Handles conflicts based on a predefined strategy.
    Returns the etags [etag_a, etag_b] that should be stored in the status map
    after resolution.
    """
    console.log(`CONFLICT DETECTED for item '${itemId}'!`);

    // --- Implement your conflict resolution strategy here ---
    // Strategy: Simple "A wins" (if A exists)
    if (itemA) {
        console.log(`RESOLUTION: '${itemId}' - Applying 'A wins'. Copying A -> B.`);
        copyItem(storeA, storeB, itemId);
        // Both sides now match A's content. Need to get the potentially updated item B
        const resolvedItemA = storeA.get(itemId); // Should be itemA
        const resolvedItemB = storeB.get(itemId); // Now matches itemA
        const etagA = getEtag(resolvedItemA);
        const etagB = getEtag(resolvedItemB);
        return [etagA, etagB];
    } else if (itemB) {
        // A doesn't exist, but B does (e.g., Case 10 where A was deleted before sync)
        console.log(`RESOLUTION: '${itemId}' - A missing, keeping B. Copying B -> A.`);
        copyItem(storeB, storeA, itemId);
        const resolvedItemA = storeA.get(itemId); // Now matches itemB
        const resolvedItemB = storeB.get(itemId); // Should be itemB
        const etagA = getEtag(resolvedItemA);
        const etagB = getEtag(resolvedItemB);
        return [etagA, etagB];
    } else {
        // Should not happen if called correctly, but handle defensively
        console.error(`RESOLUTION ERROR: '${itemId}' - Both items missing during conflict resolution.`);
        return [null, null];
    }

    // --- Other possible strategies ---
    // Strategy: "B wins"
    // Strategy: "Duplicate" (create item_a_conflict, item_b_conflict) - More complex
    // Strategy: "Ask User" (requires interactive input)
    // Strategy: "Merge" (requires understanding item content)
}


// --- The Synchronization Algorithm ---

function synchronize(storeA: Store, storeB: Store, status: StatusMap): StatusMap {
    """
    Performs a two-way sync between storeA and storeB using the status map.
    Modifies storeA and storeB in place (as Maps are reference types).
    Returns the updated status map.
    """
    console.log("\n--- Starting Synchronization ---");
    const newStatus: StatusMap = new Map();

    // Get current states efficiently
    const currentItemsA = new Map(storeA); // Shallow copy items for iteration safety if needed
    const currentItemsB = new Map(storeB);
    const currentEtagsA: Map<string, string | null> = new Map();
    currentItemsA.forEach((item, id) => currentEtagsA.set(id, getEtag(item)));
    const currentEtagsB: Map<string, string | null> = new Map();
    currentItemsB.forEach((item, id) => currentEtagsB.set(id, getEtag(item)));

    // Combine all unique IDs from current state and previous status
    const allIds = new Set([...currentItemsA.keys(), ...currentItemsB.keys(), ...status.keys()]);

    // Process in a consistent order (optional but good for debugging)
    const sortedIds = Array.from(allIds).sort();

    for (const itemId of sortedIds) {
        console.log(`\nProcessing ID: '${itemId}'`);
        const inA = currentItemsA.has(itemId);
        const inB = currentItemsB.has(itemId);
        const inStatus = status.has(itemId);

        const currentEtagA = currentEtagsA.get(itemId) ?? null;
        const currentEtagB = currentEtagsB.get(itemId) ?? null;
        const [prevEtagA, prevEtagB] = status.get(itemId) ?? [null, null];

        const itemA = currentItemsA.get(itemId);
        const itemB = currentItemsB.get(itemId);

        // Determine the case based on presence in A, B, and Status
        if (inA && inB && inStatus) {
            // Item exists everywhere - check for modifications
            console.log(" State: In A, In B, In Status");
            const changedA = currentEtagA !== prevEtagA;
            const changedB = currentEtagB !== prevEtagB;

            if (changedA && !changedB) { // Case 7: Modified on A only
                console.log(" Action: Modified on A. Copying A -> B.");
                copyItem(storeA, storeB, itemId);
                // Etag B might change representationally, recalculate for status
                newStatus.set(itemId, [currentEtagA, getEtag(storeB.get(itemId))]);
            } else if (!changedA && changedB) { // Case 8: Modified on B only
                console.log(" Action: Modified on B. Copying B -> A.");
                copyItem(storeB, storeA, itemId);
                newStatus.set(itemId, [getEtag(storeA.get(itemId)), currentEtagB]);
            } else if (changedA && changedB) { // Case 9: Modified on both (Conflict)
                console.log(" Action: Modified on both sides.");
                const resolvedEtags = resolveConflict(itemId, itemA, itemB, storeA, storeB);
                newStatus.set(itemId, resolvedEtags);
            } else { // No change
                console.log(" Action: No change detected.");
                newStatus.set(itemId, [currentEtagA, currentEtagB]);
            }

        } else if (inA && inB && !inStatus) { // Case 10: Exists on A, B, but new to status (Potential conflict)
            console.log(" State: In A, In B, NOT In Status");
            console.log(" Action: New on both sides or first sync.");
            // Before declaring conflict, check if content is actually different
            // Note: Direct etag comparison is sufficient if etags are reliable content hashes
            if (currentEtagA === currentEtagB) { // Assuming reliable etags represent content
                console.log("  Content matches based on etag. Adding to status.");
                newStatus.set(itemId, [currentEtagA, currentEtagB]);
            } else {
                 // Could add an explicit content check here if etags might differ for same content
                 // if (itemA && itemB && itemA.content === itemB.content) { ... } else { resolve...}
                const resolvedEtags = resolveConflict(itemId, itemA, itemB, storeA, storeB);
                newStatus.set(itemId, resolvedEtags);
            }

        } else if (inA && !inB && inStatus) { // Case 3: Deleted on B
            console.log(" State: In A, NOT In B, In Status");
            console.log(" Action: Deleted on B. Deleting from A.");
            deleteItem(storeA, itemId);
            // Removed from status implicitly (not added to newStatus)

        } else if (!inA && inB && inStatus) { // Case 4: Deleted on A
            console.log(" State: NOT In A, In B, In Status");
            console.log(" Action: Deleted on A. Deleting from B.");
            deleteItem(storeB, itemId);
            // Removed from status implicitly

        } else if (inA && !inB && !inStatus) { // Case 1: Created on A
            console.log(" State: In A, NOT In B, NOT In Status");
            console.log(" Action: Created on A. Copying A -> B.");
            copyItem(storeA, storeB, itemId);
            newStatus.set(itemId, [currentEtagA, getEtag(storeB.get(itemId))]);

        } else if (!inA && inB && !inStatus) { // Case 2: Created on B
            console.log(" State: NOT In A, In B, NOT In Status");
            console.log(" Action: Created on B. Copying B -> A.");
            copyItem(storeB, storeA, itemId);
            newStatus.set(itemId, [getEtag(storeA.get(itemId)), currentEtagB]);

        } else if (!inA && !inB && inStatus) { // Case 6: Deleted on both sides
            console.log(" State: NOT In A, NOT In B, In Status");
            console.log(" Action: Deleted on both sides. Removing from status.");
            // Removed from status implicitly

        } else if (!inA && !inB && !inStatus) {
            // This case should ideally not happen if allIds is constructed correctly
            console.log(` State WARNING: Item '${itemId}' somehow not found anywhere?`);
        }
    } // End for loop

    console.log("\n--- Synchronization Complete ---");
    return newStatus;
}


// --- Example Usage ---

// Initial State
let storeA: Store = new Map([
    ["item1", new Item("item1", "Content A v1")],
    ["item2", new Item("item2", "Shared Content v1")],
    ["item3", new Item("item3", "Only A Content")],
]);
let storeB: Store = new Map([
    ["item1", new Item("item1", "Content B v1")], // Different content initially
    ["item2", new Item("item2", "Shared Content v1")],
    ["item4", new Item("item4", "Only B Content")],
]);
// Start with an empty status for the first sync
let status: StatusMap = new Map();


console.log("=== Initial State ===");
console.log("Store A:", storeA);
console.log("Store B:", storeB);
console.log("Status :", status);

// --- First Sync ---
status = synchronize(storeA, storeB, status);

console.log("\n=== State After First Sync ===");
console.log("Store A:", storeA);
console.log("Store B:", storeB);
console.log("Status :", status); // Should now contain etags for item1, item2, item3, item4


// --- Make some changes before the second sync ---
console.log("\n=== Making Changes Before Second Sync ===");
// Modify item on A
storeA.get("item1")?.content = "Content A v2";
// Modify item on B
storeB.get("item2")?.content = "Shared Content v2";
// Delete item from A
storeA.delete("item3");
// Add new item to B
storeB.set("item5", new Item("item5", "New B Content"));
// Modify item on both sides (will cause conflict)
// Note: Item 4 was copied from B to A in the first sync. Now modify both.
storeA.get("item4")?.content = "Only A Content Now";
storeB.get("item4")?.content = "Only B Content v2";


console.log("Store A (Changes):", storeA);
console.log("Store B (Changes):", storeB);


// --- Second Sync ---
status = synchronize(storeA, storeB, status);

console.log("\n=== State After Second Sync ===");
console.log("Store A:", storeA);
console.log("Store B:", storeB);
console.log("Status :", status);

// Expected outcome after second sync (with "A wins" conflict resolution):
// item1: B should now have "Content A v2"
// item2: A should now have "Shared Content v2"
// item3: Should be deleted from B (as it was deleted from A)
// item4: Conflict resolved ("A wins"), B should have "Only A Content Now"
// item5: Should be copied from B to A