From b586d9dea17496bcedee37320841020592db35bd Mon Sep 17 00:00:00 2001 From: Stephen Blott Date: Thu, 28 Jan 2016 16:21:44 +0000 Subject: Simplify hint-string generation --- content_scripts/link_hints.coffee | 49 +++++++++++++-------------------------- 1 file changed, 16 insertions(+), 33 deletions(-) diff --git a/content_scripts/link_hints.coffee b/content_scripts/link_hints.coffee index 8fc1446b..68cbb915 100644 --- a/content_scripts/link_hints.coffee +++ b/content_scripts/link_hints.coffee @@ -440,39 +440,22 @@ class AlphabetHints # may be of different lengths. # hintStrings: (linkCount) -> - # Determine how many digits the link hints will require in the worst case. Usually we do not need - # all of these digits for every link single hint, so we can show shorter hints for a few of the links. - digitsNeeded = Math.ceil(@logXOfBase(linkCount, @linkHintCharacters.length)) - # Short hints are the number of hints we can possibly show which are (digitsNeeded - 1) digits in length. - shortHintCount = Math.floor( - (Math.pow(@linkHintCharacters.length, digitsNeeded) - linkCount) / - @linkHintCharacters.length) - longHintCount = linkCount - shortHintCount - - hintStrings = [] - - if (digitsNeeded > 1) - for i in [0...shortHintCount] - hintStrings.push(numberToHintString(i, @linkHintCharacters, digitsNeeded - 1)) - - start = shortHintCount * @linkHintCharacters.length - for i in [start...(start + longHintCount)] - hintStrings.push(numberToHintString(i, @linkHintCharacters, digitsNeeded)) - - @shuffleHints(hintStrings, @linkHintCharacters.length) - - # - # This shuffles the given set of hints so that they're scattered -- hints starting with the same character - # will be spread evenly throughout the array. - # - shuffleHints: (hints, characterSetLength) -> - buckets = ([] for i in [0...characterSetLength] by 1) - for hint, i in hints - buckets[i % buckets.length].push(hint) - result = [] - for bucket in buckets - result = result.concat(bucket) - result + return [] if linkCount == 0 + + # In the following: + # - at no point is any hint in hints a prefix of any other hint + # - the shorter hints are always at the start of the list + hints = [""] + offset = 0 + while hints.length - offset < linkCount or hints.length == 1 + hint = hints[offset++] + hints.push hint + ch for ch in @linkHintCharacters + hints = hints[offset...offset+linkCount] + + # This shuffles the hints so that they're scattered; hints starting with the same character are spread + # evenly throughout the array. We reverse each hint, then sort them then reverse again. + hints = (hint.split("").reverse().join "" for hint in hints).sort() + return (hint.split("").reverse().join "" for hint in hints[...linkCount]) getMatchingHints: (hintMarkers) -> matchString = @hintKeystrokeQueue.join "" -- cgit v1.2.3 From 75463367b337bd600e9c8a9e4d56ca06da341527 Mon Sep 17 00:00:00 2001 From: Stephen Blott Date: Thu, 28 Jan 2016 16:37:41 +0000 Subject: Simplify hint-string generation; tweaks. --- content_scripts/link_hints.coffee | 9 ++------- 1 file changed, 2 insertions(+), 7 deletions(-) diff --git a/content_scripts/link_hints.coffee b/content_scripts/link_hints.coffee index 68cbb915..4ced15f6 100644 --- a/content_scripts/link_hints.coffee +++ b/content_scripts/link_hints.coffee @@ -440,11 +440,6 @@ class AlphabetHints # may be of different lengths. # hintStrings: (linkCount) -> - return [] if linkCount == 0 - - # In the following: - # - at no point is any hint in hints a prefix of any other hint - # - the shorter hints are always at the start of the list hints = [""] offset = 0 while hints.length - offset < linkCount or hints.length == 1 @@ -453,9 +448,9 @@ class AlphabetHints hints = hints[offset...offset+linkCount] # This shuffles the hints so that they're scattered; hints starting with the same character are spread - # evenly throughout the array. We reverse each hint, then sort them then reverse again. + # evenly throughout the array. We reverse each hint, then sort them, then reverse them again. hints = (hint.split("").reverse().join "" for hint in hints).sort() - return (hint.split("").reverse().join "" for hint in hints[...linkCount]) + return (hint.split("").reverse().join "" for hint in hints) getMatchingHints: (hintMarkers) -> matchString = @hintKeystrokeQueue.join "" -- cgit v1.2.3 From 4c6c3210639bcf23f33b419963d930743062811a Mon Sep 17 00:00:00 2001 From: Stephen Blott Date: Thu, 28 Jan 2016 16:59:46 +0000 Subject: Simplify hint-string generation; simplification. --- content_scripts/link_hints.coffee | 9 ++++----- lib/utils.coffee | 1 + 2 files changed, 5 insertions(+), 5 deletions(-) diff --git a/content_scripts/link_hints.coffee b/content_scripts/link_hints.coffee index 4ced15f6..61ea1e37 100644 --- a/content_scripts/link_hints.coffee +++ b/content_scripts/link_hints.coffee @@ -444,13 +444,12 @@ class AlphabetHints offset = 0 while hints.length - offset < linkCount or hints.length == 1 hint = hints[offset++] - hints.push hint + ch for ch in @linkHintCharacters + hints.push ch + hint for ch in @linkHintCharacters hints = hints[offset...offset+linkCount] - # This shuffles the hints so that they're scattered; hints starting with the same character are spread - # evenly throughout the array. We reverse each hint, then sort them, then reverse them again. - hints = (hint.split("").reverse().join "" for hint in hints).sort() - return (hint.split("").reverse().join "" for hint in hints) + # Shuffle the hints so that they're scattered; hints starting with the same character are spread evenly + # throughout the array. + return hints.sort().map (str) -> str.reverse() getMatchingHints: (hintMarkers) -> matchString = @hintKeystrokeQueue.join "" diff --git a/lib/utils.coffee b/lib/utils.coffee index b69b926b..c255102e 100644 --- a/lib/utils.coffee +++ b/lib/utils.coffee @@ -281,6 +281,7 @@ Array.copy = (array) -> Array.prototype.slice.call(array, 0) String::startsWith = (str) -> @indexOf(str) == 0 String::ltrim = -> @replace /^\s+/, "" String::rtrim = -> @replace /\s+$/, "" +String::reverse = -> @split("").reverse().join "" globalRoot = window ? global globalRoot.extend = (hash1, hash2) -> -- cgit v1.2.3 From 811b3bb0280a624b6a3e17c0199ec78a1aef7e07 Mon Sep 17 00:00:00 2001 From: Stephen Blott Date: Thu, 28 Jan 2016 17:06:43 +0000 Subject: Simplify hint-string generation; fix tests. --- tests/dom_tests/dom_tests.coffee | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) diff --git a/tests/dom_tests/dom_tests.coffee b/tests/dom_tests/dom_tests.coffee index e814ec76..1d4703c1 100644 --- a/tests/dom_tests/dom_tests.coffee +++ b/tests/dom_tests/dom_tests.coffee @@ -149,10 +149,8 @@ context "Alphabetical link hints", document.getElementById("test-div").innerHTML = "" should "label the hints correctly", -> - # TODO(philc): This test verifies the current behavior, but the current behavior is incorrect. - # The output here should be something like aa, ab, b. hintMarkers = getHintMarkers() - expectedHints = ["aa", "ba", "ab"] + expectedHints = ["aa", "b", "ab"] for hint, i in expectedHints assert.equal hint, hintMarkers[i].hintString -- cgit v1.2.3 From d6a7ea0094f8071f1785539ccd167ed371bd3bb9 Mon Sep 17 00:00:00 2001 From: Stephen Blott Date: Fri, 29 Jan 2016 07:44:13 +0000 Subject: Simplify hint-string generation; filtered hints. --- content_scripts/link_hints.coffee | 30 ++++++------------------------ 1 file changed, 6 insertions(+), 24 deletions(-) diff --git a/content_scripts/link_hints.coffee b/content_scripts/link_hints.coffee index 61ea1e37..1bb40b90 100644 --- a/content_scripts/link_hints.coffee +++ b/content_scripts/link_hints.coffee @@ -483,7 +483,12 @@ class FilterHints @labelMap[forElement] = labelText generateHintString: (linkHintNumber) -> - numberToHintString linkHintNumber, @linkHintNumbers.toUpperCase() + base = @linkHintNumbers.length + hint = [] + while 0 < linkHintNumber + hint.push @linkHintNumbers[Math.floor linkHintNumber % base] + linkHintNumber = Math.floor linkHintNumber / base + hint.reverse().join "" generateLinkText: (element) -> linkText = "" @@ -615,29 +620,6 @@ spanWrap = (hintString) -> innerHTML.push("" + char + "") innerHTML.join("") -# -# Converts a number like "8" into a hint string like "JK". This is used to sequentially generate all of the -# hint text. The hint string will be "padded with zeroes" to ensure its length is >= numHintDigits. -# -numberToHintString = (number, characterSet, numHintDigits = 0) -> - base = characterSet.length - hintString = [] - remainder = 0 - loop - remainder = number % base - hintString.unshift(characterSet[remainder]) - number -= remainder - number /= Math.floor(base) - break unless number > 0 - - # Pad the hint string we're returning so that it matches numHintDigits. - # Note: the loop body changes hintString.length, so the original length must be cached! - hintStringLength = hintString.length - for i in [0...(numHintDigits - hintStringLength)] by 1 - hintString.unshift(characterSet[0]) - - hintString.join("") - # Suppress all keyboard events until the user stops typing for sufficiently long. class TypingProtector extends Mode constructor: (delay, callback) -> -- cgit v1.2.3 From 5e65d6bb14c86be2cac95e6d7b61a0fbde1c76cc Mon Sep 17 00:00:00 2001 From: Stephen Blott Date: Fri, 29 Jan 2016 08:11:02 +0000 Subject: Simplify hint-string generation; tweaks. --- content_scripts/link_hints.coffee | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) diff --git a/content_scripts/link_hints.coffee b/content_scripts/link_hints.coffee index 1bb40b90..07deaf61 100644 --- a/content_scripts/link_hints.coffee +++ b/content_scripts/link_hints.coffee @@ -416,8 +416,6 @@ class LinkHintsMode # Use characters for hints, and do not filter links by their text. class AlphabetHints - logXOfBase: (x, base) -> Math.log(x) / Math.log(base) - constructor: -> @linkHintCharacters = Settings.get "linkHintCharacters" # We use the keyChar from keydown if the link-hint characters are all "a-z0-9". This is the default @@ -447,8 +445,8 @@ class AlphabetHints hints.push ch + hint for ch in @linkHintCharacters hints = hints[offset...offset+linkCount] - # Shuffle the hints so that they're scattered; hints starting with the same character are spread evenly - # throughout the array. + # Shuffle the hints so that they're scattered; hints starting with the same character and short hints are + # spread evenly throughout the array. return hints.sort().map (str) -> str.reverse() getMatchingHints: (hintMarkers) -> -- cgit v1.2.3