GenericHashSync.swift

import Foundation

/// Represents side effects needed to sync dst with src
enum Effect {
  /// in dst, remove specified item in dst
  case remove(dstIndex:Int)
  /// in dst, add the specified item from src
  case add(srcIndex:Int)
}

/// any object which implements MyHashable
/// can provide a hash value, which can be used to
/// see if it is the "same" as an object in another collection
///
/// So an item in dst is the same as an item in src, if
/// they yield the same hash.
protocol MyHashable {
  associatedtype Hash:Hashable
  var hashValue:Hash { get }
}

/// Takes a collection of MyHashable items to a map from an item's hash to the item's index in the collection
func asHashToIndexDictionary<S:Collection>(_ s:S) -> [S.Iterator.Element.Hash:Int]
  where S.Iterator.Element:MyHashable
{
  var retval:[S.Iterator.Element.Hash:Int] = [:]
  for (offset,element) in s.enumerated() {
    let hash = element.hashValue
    retval[hash] = offset
  }
  return retval
}

/**
 Examines two arrays of hashable items, src and dst, and 
 returns an array of effects, which would bring dst into synchrony with src.
 
 Pure function.
 
 */
func sync<S,T>(src:[S],dst:[T]) -> [Effect]
  where S:MyHashable, T:MyHashable, S.Hash == T.Hash
{
  let srcDict = asHashToIndexDictionary(src)
  let dstDict = asHashToIndexDictionary(dst)
  
  let srcHashes:Set<S.Hash> = Set(srcDict.keys)
  let dstHashes:Set<T.Hash> = Set(dstDict.keys)
  
  let srcIndexesToAdd:[Int] = srcHashes.subtracting(dstHashes).flatMap({ srcDict[$0] } )
  let dstIndexesToRemove:[Int] = dstHashes.subtracting(srcHashes).flatMap( { dstDict[$0] } )

  return srcIndexesToAdd.map({ Effect.add(srcIndex: $0) }) + dstIndexesToRemove.map({ Effect.remove(dstIndex: $0) })
}


/// Swift Strings automatically conform to this protocol, since they already implement `hashValue:Int`

extension String: MyHashable { }

var src = ["a","b","c"]
var dst = ["c","d"]

let effects = sync(src: src, dst: dst)

// performs side-effects specified by effects
func perform(effects:[Effect]) -> Void
{
  /**
   Here we write a small interpreter, which reads every Effect and
   does something.
   
   E.g.: for S3 -> filesystem, it would download from S3 and erase files on the filesystem.
   
   E.g.: for filesystem -> .tfrecords, it would encode a file as a TFRecord object within a .tfrecords file, or remove a TFRecord object from a .tfrecord file
   
   */
}