diff options
| -rw-r--r-- | playlist-utils.js | 248 |
1 files changed, 248 insertions, 0 deletions
diff --git a/playlist-utils.js b/playlist-utils.js index 452b705..1413fb8 100644 --- a/playlist-utils.js +++ b/playlist-utils.js @@ -653,6 +653,224 @@ function getCorrespondingPlayableForFile(item) { return parent.items.find(item => isPlayable(item) && path.basename(item.url, path.extname(item.url)) === basename) } +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) +} + +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 +} + module.exports = { parentSymbol, updatePlaylistFormat, updateGroupFormat, updateTrackFormat, @@ -673,6 +891,36 @@ module.exports = { searchForItem, getCorrespondingFileForItem, getCorrespondingPlayableForFile, + getPathScore, + findTrackObject, isGroup, isTrack, isOpenable, isPlayable } + +if (require.main === module) { + 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'} + ]} + ]} + */ + ]}) + )) +} |