Update the timestamps of cached history entries when a new site is visited.

This allows the vomnibar rankings to properly rank sites you've visited recently,
after it populated its original cache.

2 files changed, 90 insertions, 7 deletions

diff --git a/background_scripts/completion.coffee b/background_scripts/completion.coffee
index 0a9daed0..64039b5f 100644
--- a/background_scripts/completion.coffee
+++ b/background_scripts/completion.coffee
@@ -160,9 +160,10 @@ class DomainCompleter
       @domains = {}
       history.forEach (entry) =>
         # We want each key in our domains hash to point to the most recent History entry for that domain.
-        # Thankfully, the domains in HistoryCache are sorted from oldest to most recent.
         domain = @parseDomain(entry.url)
-        @domains[domain] = entry if domain
+        if domain
+          previousEntry = @domains[domain]
+          @domains[domain] = entry if !previousEntry || (previousEntry.lastVisitTime < entry.lastVisitTime)
       chrome.history.onVisited.addListener(@onPageVisited.proxy(this))
       onComplete()
 
@@ -249,6 +250,10 @@ HistoryCache =
   size: 20000
   history: null # An array of History items returned from Chrome.
 
+  reset: ->
+    @history = null
+    @callbacks = null
+
   use: (callback) ->
     return @fetchHistory(callback) unless @history?
     callback(@history)
@@ -257,16 +262,43 @@ HistoryCache =
     return @callbacks.push(callback) if @callbacks
     @callbacks = [callback]
     chrome.history.search { text: "", maxResults: @size, startTime: 0 }, (history) =>
-      # sorting in ascending order. We will push new items on to the end as the user navigates to new pages.
-      history.sort((a, b) -> (a.lastVisitTime || 0) - (b.lastVisitTime || 0))
+      history.sort @compareHistoryByUrl
       @history = history
       chrome.history.onVisited.addListener(@onPageVisited.proxy(this))
       callback(@history) for callback in @callbacks
       @callbacks = null
 
+  compareHistoryByUrl: (a, b) ->
+    return 0 if a.url == b.url
+    return 1 if a.url > b.url
+    -1
+
   onPageVisited: (newPage) ->
-    firstTimeVisit = (newSite.visitedCount == 1)
-    @history.push(newSite) if firstTimeVisit
+    i = HistoryCache.binarySearch(newPage, @history, @compareHistoryByUrl)
+    pageWasFound = (@history[i].url == newPage.url)
+    if pageWasFound
+      @history[i] = newPage
+    else
+      @history.splice(i, 0, newPage)
+
+# Returns the matching index or the closest matching index if the element is not found. That means you
+# must check the element at the returned index to know whether the element was actually found.
+HistoryCache.binarySearch = (targetElement, array, compareFunction) ->
+  high = array.length - 1
+  low = 0
+
+  while (low <= high)
+    middle = Math.floor((low + high) / 2)
+    element = array[middle]
+    compareResult = compareFunction(element, targetElement)
+    if (compareResult > 0)
+      high = middle - 1
+    else if (compareResult < 0)
+      low = middle + 1
+    else
+      return middle
+  # We didn't find the element. Return the position where it should be in this array.
+  return if compareFunction(element, targetElement) < 0 then middle + 1 else middle
 
 root = exports ? window
 root.Suggestion = Suggestion
diff --git a/tests/completion_test.coffee b/tests/completion_test.coffee
index 531d06b1..ed864151 100644
--- a/tests/completion_test.coffee
+++ b/tests/completion_test.coffee
@@ -22,9 +22,60 @@ context "bookmark completer",
     @completer.filter(["mark2"], (@results) =>)
     assert.arrayEqual [@bookmark2.url], @results.map (suggestion) -> suggestion.url
 
+context "HistoryCache",
+  context "binary search",
+    setup ->
+      @compare = (a, b) -> a - b
+
+    should "find elements to the left of the middle", ->
+      assert.equal 0, HistoryCache.binarySearch(3, [3, 5, 8], @compare)
+
+    should "find elements to the right of the middle", ->
+      assert.equal 2, HistoryCache.binarySearch(8, [3, 5, 8], @compare)
+
+    context "unfound elements",
+      should "return 0 if it should be the head of the list", ->
+        assert.equal 0, HistoryCache.binarySearch(1, [3, 5, 8], @compare)
+
+      should "return length - 1 if it should be at the end of the list", ->
+        assert.equal 0, HistoryCache.binarySearch(3, [3, 5, 8], @compare)
+
+      should "found return the position if it's between two elements", ->
+        assert.equal 1, HistoryCache.binarySearch(4, [3, 5, 8], @compare)
+        assert.equal 2, HistoryCache.binarySearch(7, [3, 5, 8], @compare)
+
+  context "fetchHistory",
+    setup ->
+      @history1 = { url: "b.com", lastVisitTime: 5 }
+      @history2 = { url: "a.com", lastVisitTime: 10 }
+      history = [@history1, @history2]
+      @onVisitedListener = null
+      global.chrome.history =
+        search: (options, callback) -> callback(history)
+        onVisited: { addListener: (@onVisitedListener) => }
+      HistoryCache.reset()
+
+    should "store visits sorted by url ascending", ->
+      HistoryCache.use (@results) =>
+      assert.arrayEqual [@history2, @history1], @results
+
+    should "add new visits to the history", ->
+      HistoryCache.use () ->
+      newSite = { url: "ab.com" }
+      @onVisitedListener(newSite)
+      HistoryCache.use (@results) =>
+      assert.arrayEqual [@history2, newSite, @history1], @results
+
+    should "replace new visits in the history", ->
+      HistoryCache.use (@results) =>
+      assert.arrayEqual [@history2, @history1], @results
+      newSite = { url: "a.com", lastVisitTime: 15 }
+      @onVisitedListener(newSite)
+      HistoryCache.use (@results) =>
+      assert.arrayEqual [newSite, @history1], @results
+
 context "history completer",
   setup ->
-    # history2 is more recent than history1.
     @history1 = { title: "history1", url: "history1.com", lastVisitTime: hours(1) }
     @history2 = { title: "history2", url: "history2.com", lastVisitTime: hours(5) }