add function for finding track object by ref data

This is the start of a project to let two (or more) instances of mtui
link together and host a party where tracks are accessed on each user's
own machine. Backends will be linked so that any actions taken in one
will be reflected in another. This function is a key part of
implementing this, since mtui depends on all instances of a track be
referred to by the same JS object, and the new function allows the
(approximate) identity of a track to be serialized and transferred over
the internet (or any static format) and restored later, on another
device, and/or even in a differently structured music library.

1 files changed, 244 insertions, 0 deletions

diff --git a/playlist-utils.js b/playlist-utils.js
index 8611f06..739652f 100644
--- a/playlist-utils.js
+++ b/playlist-utils.js
@@ -717,3 +717,247 @@ export function getCorrespondingPlayableForFile(item) {
   const basename = path.basename(item.url, path.extname(item.url))
   return parent.items.find(item => isPlayable(item) && path.basename(item.url, path.extname(item.url)) === basename)
 }
+
+export function getPathScore(path1, path2) {
+  // This function is basically only used in findTrackObject, but it's kinda
+  // huge and I need to test that it works outside of that context, so I'm
+  // sticking it on the global scope. Feel free to steal for whatever your
+  // weird future need for comparing any two paths is!
+  //
+  // path1 and path2 should be arrays of group names, according to the path
+  // you'd follow to open the groups and access a contained track. They should
+  // *not* include the track name, unless you want those to be considered a
+  // valid place for the paths to cross over!
+  //
+  // --
+  //
+  // A path score is determined to be the number of groups which must be
+  // traversed across the two paths to find a matching group name and then
+  // reach the other track under that group. A lower score implies a closer
+  // match (since score increases not with "closeness" but "separation").
+  //
+  // For example, these two paths are considered to have a score of zero
+  // against each other ("T" represents the track):
+  //
+  //   X/B/C/T
+  //   Y/B/C/T
+  //
+  // Their separation is zero because, starting from the closest (i.e. top)
+  // group to either the provided track or the reference data track, it takes
+  // zero additional steps to reach a group whose name is shared between the
+  // two paths: those top groups already have the same name.
+  //
+  // The above example indicates that the pattern before the closest matching
+  // path does not matter. Indeed, the actual length of the path could be
+  // different (W/X/B/C versus Y/B/C for example), and the score would still
+  // be the same. Parts of the path prepending the closest matching group
+  // name are thus ommitted from following examples.
+  //
+  // These paths, on the other hand, have a score of one:
+  //
+  //   (...)/C/T
+  //   (...)/C/D/T
+  //
+  // The closest matching name in this path is C. It is zero steps further
+  // from the start of the first path (C is the start); on the other path,
+  // it is one step further (D must be passed first). Therefore, the total
+  // steps that must be travelled to reach the start of one path to the
+  // start of the other by passing through the closest overlapping name is
+  // one: 0 + 1 = 1.
+  //
+  // In determining which of two paths are a closer match to a provided
+  // reference path, it's important to remember that a lower score (implying
+  // less separation) is better. Though we'll see the following example is
+  // probably more common across most music libraries, a reasonably natural
+  // example of the path structures above occurring in a music library could
+  // be this: an artist directory containing both albums and stray tracks,
+  // where one track apparently appears as both a stray track file and in an
+  // adjacent album directory; or, a mixtape which contains adjacent to its
+  // mixed-segment track listing a folder of the unmixed segments.
+  //
+  // These paths have a score of two:
+  //
+  //   (...)/B/C/T
+  //   (...)/B/D/T
+  //
+  // With the above examples, this one is fairly self explanatory. In this
+  // case, the closest matching group, B, is one step away from the start
+  // point (the first group before the track, i.e, the top name in the path)
+  // in both paths. Summed, the distance (and thus the score) is two.
+  //
+  // This example demonstrates what is probably a more realistic case of two
+  // tracks resembling each other (e.g. having the same name or source) but
+  // not sharing the same path: if B represents an artist, and C & D stand in
+  // place (in this example) of the names of that artist's albums, then it is
+  // reasonable to say the directories for the album are slightly different
+  // across the two paths. This could be the case for two users who ended up
+  // naming the album directory differently, or for one user restoring from
+  // their own backend/playlist after having adjusted the naming structure of
+  // their music library. It's also possible that there could simply be two
+  // albums by the same artist which contain a track of the same name; in
+  // that case, the path score implementation is doing exactly its job by
+  // indicating that these tracks would have a greater score (meaning further
+  // separation) than when checking against the track belonging to the same
+  // release. (If there is concern that such a track should not match at all
+  // because it may be a remarkably different track, other factors of
+  // resemblance -- position in album, duration, etc -- can be used to add
+  // detail to the apparent level of resemblance then.)
+  //
+  // --
+  //
+  // A note on determining which name is the "closest" -- consider
+  // the following two paths:
+  //
+  //   A/X/B/C/D/E/T
+  //   A/Y/E/B/C/D/T
+  //
+  // There are many names which appear in both paths. So which do we treat
+  // as the closest? Well, what we're looking for is the shortest path across
+  // both paths, passing through at a particular name. To do this, we simply
+  // calculate the score for each name in the intersection of both paths
+  // (i.e. every name which shows up in both paths) using the same algorithm
+  // described above (sum of the distance from the start of either path).
+  // Then we take the lowest resultant score, and use that as the final score
+  // which is returned out of this function.
+  //
+  // TODO: There are probably optimizations to be made as far as avoiding
+  //       processing every overlapping name goes (particularly once it's
+  //       determined that no other path could be determined), but honestly
+  //       I'm pretty sure if I tried to write an algorithm taking *that*
+  //       into account, I'd end up screwing it up. :P So for now, we just
+  //       do a simple filter and reduce operation.
+  //
+  // If the intersection of the two paths is empty (i.e. there is no overlap),
+  // we return the otherwise nonsense value, -1.
+
+  const union = Array.from(new Set([...path1, ...path2]))
+  const intersection = union.filter(
+    name => path1.includes(name) && path2.includes(name))
+
+  if (!intersection.length) {
+    return -1
+  }
+
+  const reversed1 = path1.reverse()
+  const reversed2 = path2.reverse()
+
+  const scores = intersection.map(
+    name => reversed1.indexOf(name) + reversed2.indexOf(name))
+
+  return scores.reduce((a, b) => a < b ? a : b)
+}
+
+export function findTrackObject(referenceData, sourcePlaylist) {
+  // Finds the track object in the source playlist which most closely resembles
+  // the provided reference data. This is used for maintaining the identity of
+  // track objects when reloading a playlist (see serialized-backend.js). It's
+  // also usable in synchronizing the identity of tracks across linked clients
+  // (see socket.js).
+
+  // Reference data includes track NAME, track SOURCE (downloaderArg), and
+  // track PATH (names of parent groups). Specifics of how existing track
+  // objects are determined to resemble this data are laid out next to the
+  // relevant implementation code.
+  //
+  // TODO: Should track number be considered here?
+  // TODO: Should track "metadata" (duration, md5?) be considered too?
+  //       This in particular prompts questions of what the purpose of matching
+  //       tracks *is*, and in considering those I lean towards "no" here, but
+  //       it's probably worth looking at more in the future. (TM.)
+
+  function getTrackPathScore(track) {
+    if (!referenceData.path) {
+      return null
+    }
+
+    const path1 = referenceData.path.slice()
+    const path2 = getItemPath(track).slice(0, -1).map(group => group.name)
+    return getPathScore(path1, path2)
+  }
+
+  function compareName(track) {
+    return track.name === referenceData.name
+  }
+
+  function compareSource(track) {
+    return track.downloaderArg === referenceData.downloaderArg
+  }
+
+  // The only tracks which will be considered at all are those which match at
+  // least one of the reference name/source.
+  const baselineResemble = flattenGrouplike(sourcePlaylist).items.filter(
+    track => compareName(track) || compareSource(track))
+
+  // If no track matches the baseline conditions for resemblance at all,
+  // return null. It's up to the caller to decide what to do in this case,
+  // e.g. reporting that no track was found, or creating a new track object
+  // from the reference data altogether.
+  if (!baselineResemble.length) {
+    return null
+  }
+
+  // Find the "reasons" these tracks resemble the reference data; these will
+  // be used as the factors in calculating which track resembles closest.
+  const reasons = baselineResemble.map(track => ({
+    track,
+    nameMatches: compareName(track),
+    sourceMatches: compareSource(track),
+    pathScore: getTrackPathScore(track)
+  }))
+
+  // TODO: The algorithm for determining which track matches closest is
+  //       rudimentary at best right now. It would be well improved with
+  //       better-detailed reasoning! That said, here's the current code
+  //       laid out explicitly:
+  //
+  // Initial sort by matches is (NAME & SOURCE), SOURCE, NAME. Track which
+  // most closely matches path is returned thereafter, with ties broken by
+  // the initial sort. (If name, source, *and* path all are equal, first
+  // track as ordered in the source playlist/parent group is returned.)
+  // If no tracks have any path overlap, the first item in the sorted list
+  // is returned (since it is the closest match). (Again, ties here are
+  // broken according to source ordering.)
+
+  reasons.sort((a, b) =>
+    a.sourceMatches && !b.sourceMatches ? -1 :
+    !a.sourceMatches && b.sourceMatches ? 1 :
+    a.nameMatches && !b.nameMatches ? -1 :
+    !a.nameMatches && b.nameMatches ? 1 :
+    0)
+
+  let mostResembles
+  const sharePath = reasons.filter(({ pathScore }) => pathScore >= 0)
+  if (sharePath.length) {
+    mostResembles = sharePath.reduce((a, b) => a.pathScore < b.pathScore ? a : b)
+  } else {
+    mostResembles = reasons[0]
+  }
+
+  return mostResembles.track
+}
+
+/*
+console.log(getPathScore(['A', 'B', 'C'], ['A', 'B', 'C']))
+console.log(getPathScore(['A', 'B', 'C'], ['A', 'B', 'C', 'D']))
+console.log(getPathScore(['A', 'B', 'C', 'E'], ['A', 'B', 'C']))
+console.log(getPathScore(['W', 'X'], ['Y', 'Z']))
+console.log(findTrackObject(
+  {name: 'T', downloaderArg: 'foo', path: ['A', 'B', 'C']},
+  updateGroupFormat({items: [
+    {id: 1, name: 'T'},
+    {id: 2, name: 'T'},
+    {id: 3, name: 'T'},
+    // {id: 4, name: 'T', downloaderArg: 'foo'},
+    {id: 5, name: 'T'},
+    {id: 6, name: 'Y', downloaderArg: 'foo'},
+    // {name: 'A', items: [
+    //   {name: 'B', items: [
+    //     {name: 'C', items: [
+    //       {name: 'T'}
+    //     ]},
+    //     {name: 'T'}
+    //   ]}
+    // ]}
+  ]})
+))
+*/