Use non-overlapping interval list in selections structure

3 files changed, 319 insertions, 20 deletions

diff --git a/lib/interval.js b/lib/interval.js
new file mode 100644
index 0000000..d0cf69a
--- /dev/null
+++ b/lib/interval.js
@@ -0,0 +1,37 @@
+class Interval {
+  constructor (from, to, data) {
+    if (typeof from !== 'number' || typeof to !== 'number') {
+      throw new Error('from and to must be a number')
+    }
+
+    this.from = from
+    this.to = to
+    this.data = data
+  }
+
+  get from () {
+    return this.from
+  }
+
+  get to () {
+    return this.to
+  }
+
+  get priority () {
+    return this.data
+  }
+
+  setFrom (from) {
+    if (typeof from !== 'number') throw new Error('from must be a number')
+    if (from > this.to) throw new Error('from must be lower than to')
+    this.from = from
+  }
+
+  setTo (to) {
+    if (typeof to !== 'number') throw new Error('to must be a number')
+    if (this.from > to) throw new Error('from must be lower than to')
+    this.to = to
+  }
+}
+
+module.exports = Interval
diff --git a/lib/nonoverlapping-interval-list.js b/lib/nonoverlapping-interval-list.js
new file mode 100644
index 0000000..48e19b7
--- /dev/null
+++ b/lib/nonoverlapping-interval-list.js
@@ -0,0 +1,245 @@
+const { IntervalTree } = require('node-interval-tree')
+const Interval = require('./interval')
+
+class NonOverlappingIntervalList {
+  constructor (opts = {}) {
+    if (opts.equals && typeof opts.equals !== 'function') throw new Error('equals must be a function')
+
+    this._list = []
+    this._equals = equals || this._defaultEquals
+  }
+
+  /**
+  * "from" and "to" are both inclusive
+  */
+  add (from, to, data = null) {
+    if (typeof from !== 'number' || typeof to !== 'number') throw new Error('from and to must be numbers')
+    if (from > to) throw new Error('from must be smaller or equal than to')
+
+    const currentInsertion = new IntervalTree()
+    currentInsertion.insert({ low: from, high: to })
+
+    // Check if there are conflicting intervals
+    let overlappingIntervals
+    while (true) {
+      overlappingIntervals = this._findOverlappingInterval(from, to)
+      if (overlappingIntervals.length === 0) break
+
+      const conflictingIntervals = overlappingIntervals.filter(i => {
+        return !this._equals(i.data, data)
+      })
+      if (conflictingIntervals.length === 0) break
+
+      const firstConflictingInterval = conflictingIntervals[0]
+
+      // Get overlappig zone
+      const [overlappingFrom, overlappingTo] = this._getOverlappingZone(firstConflictingInterval, from, to)
+
+      const newIntervals = this._calculateNewIntervals(firstConflictingInterval, overlappingFrom, overlappingTo, data)
+      this._findAndReplace(firstConflictingInterval, newIntervals)
+
+      // Try to merge neighbouring intervals
+      this._tryMerge(this._list.indexOf(newIntervals[0]))
+      if (newIntervals.length > 1) {
+        this._tryMerge(this._list.indexOf(newIntervals[newIntervals.length - 1]))
+      }
+    }
+
+    // Remove overlappings from current insertion
+    for (const interval of overlappingIntervals) {
+      const [overlappingFrom, overlappingTo] = this._getOverlappingZone(interval, from, to)
+      currentInsertion.remove({ low: overlappingFrom, high: overlappingTo })
+    }
+
+    // Check if there are more insertions
+    if (currentInsertion.size() > 0) {
+      for (const key of currentInsertion.keys()) {
+        this._insertToList(key.low, key.high, data)
+      }
+    }
+  }
+
+  remove (from, to) {
+    if (typeof from !== 'number' || typeof to !== 'number') throw new Error('from and to must be numbers')
+    if (from > to) throw new Error('from must be smaller or equal than to')
+
+    // Find overlapping intervals
+    const intervals = this._findOverlappingInterval(from, to)
+
+    for (const interval of intervals) {
+      // Check if whole interval is out
+      if (from <= interval && interval.to <= to) {
+        const intervalIndex = this._list.indexOf(interval)
+        this._list.splice(intervalIndex, 1)
+        continue
+      }
+
+      // Partial interval out: just resize the interval
+      const [overlappingFrom, overlappingTo] = this._getOverlappingZone(interval, from, to)
+      if (overlappingFrom > interval.from) {
+        interval.from = overlappingFrom
+      }
+      if (overlappingTo < interval.to) {
+        interval.to = overlappingTo
+      }
+    }
+  }
+
+  getList () {
+    return this._list
+  }
+
+  size () {
+    return this._list.length
+  }
+
+  _defaultEquals (a, b) {
+    return a === b
+  }
+
+  _insertToList (from, to, data = null) {
+    if (this._list.length === 0) {
+      this._list.push(new Interval(from to, data))
+      return
+    }
+
+    let leftIndex = 0
+    let leftInterval = this._list[leftIndex]
+    let rightIndex = this._list.length - 1
+    let rightInterval = this._list[rightIndex]
+
+    let foundIndex = null
+    let foundInterval = null
+
+    if (from < leftInterval.from) {
+      // Add it to the left
+      foundIndex = leftIndex
+    } else if (rightInterval.to < from) {
+      // Add it to the right
+      foundIndex = rightIndex + 1
+    }
+
+    while (foundIndex !== null && foundInterval !== null) {
+      if (leftInterval.from <= from && from <= leftInterval.to) {
+        // Add it to left interval
+        foundInterval = leftInterval
+        break
+      } else if (rightInterval.from <= from && from <= rightInterval.to) {
+        // Add it to right interval
+        foundInterval = rightInterval
+        break
+      } else {
+        if ((rightIndex - leftIndex) === 1) {
+          // Add it between left and right
+          foundIndex = rightIndex
+          break
+        }
+
+        // Calculate new indices
+        const middleIndex = Math.floor((rightIndex - leftIndex) / 2)
+        const middleInterval = this._list[middleIndex]
+
+        if (middleInterval.to < from) {
+          leftIndex = middleIndex
+          leftInterval = middleInterval
+        } else if (from < middleInterval.from) {
+          rightIndex = middleIndex
+          rightInterval = middleInterval
+        } else {
+          // Add it in the middle interval
+          foundInterval = middleInterval
+          break
+        }
+      }
+    }
+
+    if (foundInterval) {
+      // Split found interval
+      const newIntervals = this._calculateNewIntervals(foundInterval, from, to, data)
+      this._findAndReplace(foundInterval, newIntervals)
+    } else if (foundIndex) {
+      // Add it there
+      const newInterval = new Interval(from, to, data)
+      this._list.splice(foundIndex, 0, newInterval)
+    } else {
+      // This should never happen
+      throw new Error('No index found to insert (this should never happen)')
+    }
+  }
+
+  _getOverlappingZone (interval, from, to) {
+    const overlappingFrom = Math.max(interval.from, from)
+    const overlappingTo = Math.max(interval.to, to)
+
+    return [overlappingFrom, overlappingTo]
+  }
+
+  _findOverlappingIntervals (from, to) {
+    const res = []
+
+    // Optimize: use binary search?
+    for (let i = 0; i < this._list.length; i++) {
+      const entry = this._list[i]
+
+      // Check overlapping
+      if (from <= entry.to && entry.from <= to) {
+        res.push(entry)
+      }
+    }
+
+    return res
+  }
+
+  _calculateNewIntervals (conflictingInterval, from, to, data) {
+    if (conflictingInterval.from <= from - 1) {
+      const leftNewInterval = new Interval(foundInterval.from, from - 1, foundInterval.data)
+      res.push(leftNewInterval)
+    }
+    const middleNewInterval = new Interval(from, to, data)
+    res.push(middleNewInterval)
+    if (to + 1 <= conflictingInterval.to) {
+      const rightNewInterval = new Interval(to + 1, conflictingInterval.to, foundInterval.data)
+      res.push(rightNewInterval)
+    }
+    return res
+  }
+
+  _findAndReplace (interval, newIntervals) {
+    const index = this._list.indexOf(interval)
+    if (index === -1) return
+
+    // Remove previous
+    this._list.splice(index, 1)
+
+    // Add list of intervals
+    for (let i = 0; i < newIntervals.length; i++) {
+      const newInterval = newIntervals[i]
+      this._list.splice(index + i, 0, newInterval)
+    }
+  }
+
+  _tryMerge (index) {
+    const interval = this._list[index]
+    if (!interval) return
+
+    // Check left side
+    const leftInterval = this._list[index - 1]
+    if (leftInterval && ((interval.from - leftInterval.to) <= 1)
+        && this._equals(interval.data, leftInterval.data)) {
+      const newInterval = new Interval(leftInterval.from, interval.to, interval.data)
+      // Remove and replace
+      this._list.splice(index - 1, 2, newInterval)
+    }
+
+    // Check right side
+    const rightInterval = this._list[index + 1]
+    if (rightInterval && ((rightInterval.from - interval.to) <= 1)
+        && this._equals(interval.data, rightInterval.data)) {
+      const newInterval = new Interval(interval.from, rightInterval.to, interval.data)
+      // Remove and replace
+      this._list.splice(index, 2, newInterval)
+    }
+  }
+}
+
+module.exports = NonOverlappingIntervalList
diff --git a/lib/torrent.js b/lib/torrent.js
index 24e7b44..9339ec5 100644
--- a/lib/torrent.js
+++ b/lib/torrent.js
@@ -104,6 +104,7 @@ class Torrent extends EventEmitter {
 
     this._amInterested = false
     this._selections = []
+    this._selectionNotifications = new IntervalTree()
     this._critical = []
 
     this.wires = [] // open wires (added *after* handshake)
@@ -916,15 +917,13 @@ class Torrent extends EventEmitter {
 
     this._debug('select %s-%s (priority %s)', start, end, priority)
 
-    this._selections.push({
-      from: start,
-      to: end,
+    this._selections.add(start, end, {
       offset: 0,
       priority,
       notify: notify || noop
     })
 
-    this._selections.sort((a, b) => b.priority - a.priority)
+    //this._selections.sort((a, b) => b.priority - a.priority)
 
     this._updateSelections()
   }
@@ -1186,27 +1185,45 @@ class Torrent extends EventEmitter {
    * Garbage collect selections with respect to the store's current state.
    */
   _gcSelections () {
-    for (let i = 0; i < this._selections.length; ++i) {
-      const s = this._selections[i]
-      const oldOffset = s.offset
+    const selectionList = this._selections.getList()
+    if (this._selections.size() === 0) return
+
+    let i = 0
+    let s = selectionList[0]
+    const lastTo = selectionList[selectionList.length - 1].to
+
+    // TODO: fix this
+
+    while (s) {
+      const oldFrom = s.from
 
       // check for newly downloaded pieces in selection
-      while (this.bitfield.get(s.from + s.offset) && s.from + s.offset < s.to) {
-        s.offset += 1
+      while (this.bitfield.get(s.from) && s.from < s.to) {
+        s.setFrom(s.from + 1)
+      }
+      if (s.from === s.to && !this.bitfield.get(s.from)) s.setFrom(s.from - 1)
+
+      if (oldFrom !== s.from) {
+        // TODO: Add notifications
+        const notifications = this.selectionNotifications.search({ low: oldFrom, high: s.from })
+        //s.notify()
       }
+      if (s.from !== s.to) continue
+      if (!this.bitfield.get(newFrom)) continue
+
+      // remove fully downloaded selection
+      this._selections.remove(s.from, s.to)
 
-      if (oldOffset !== s.offset) s.notify()
-      if (s.to !== s.from + s.offset) continue
-      if (!this.bitfield.get(s.from + s.offset)) continue
+      // decrement i to offset splice
+      i -= 1
 
-      this._selections.splice(i, 1) // remove fully downloaded selection
-      i -= 1 // decrement i to offset splice
+      s = this._selections.next
 
-      s.notify()
+      //s.notify()
       this._updateInterest()
     }
 
-    if (!this._selections.length) this.emit('idle')
+    if (this._selections.size() === 0) this.emit('idle')
   }
 
   /**
@@ -1289,7 +1306,7 @@ class Torrent extends EventEmitter {
         const next = self._selections[i]
         let piece
         if (self.strategy === 'rarest') {
-          const start = next.from + next.offset
+          const start = next.from
           const end = next.to
           const len = end - start + 1
           const tried = {}
@@ -1304,7 +1321,7 @@ class Torrent extends EventEmitter {
             tries += 1
           }
         } else {
-          for (piece = next.to; piece >= next.from + next.offset; --piece) {
+          for (piece = next.from; piece <= next.to; piece++) {
             if (!wire.peerPieces.get(piece)) continue
             if (self._request(wire, piece, false)) return
           }
@@ -1364,7 +1381,7 @@ class Torrent extends EventEmitter {
 
         let piece
         if (self.strategy === 'rarest') {
-          const start = next.from + next.offset
+          const start = next.from
           const end = next.to
           const len = end - start + 1
           const tried = {}
@@ -1390,7 +1407,7 @@ class Torrent extends EventEmitter {
             return true
           }
         } else {
-          for (piece = next.from + next.offset; piece <= next.to; piece++) {
+          for (piece = next.from; piece <= next.to; piece++) {
             if (!wire.peerPieces.get(piece) || !rank(piece)) continue
 
             while (self._request(wire, piece, self._critical[piece] || hotswap)) {