SHARE
TWEET

Untitled

a guest May 19th, 2019 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class RangeTree<T> {
  2.    
  3.     private var value: [T]
  4.     private(set) var range: Range<Int>
  5.     private var leftLeaf: RangeTree<T>?
  6.     private var rightLeaf: RangeTree<T>?
  7.    
  8.     convenience init(array: [T]) {
  9.         self.init(array: array, range: 0 ..< array.count)
  10.     }
  11.    
  12.     init(array: [T], range: Range<Int>) {
  13.         self.range = range
  14.        
  15.         if range.lowerBound == range.upperBound {
  16.             if array.indices.contains(range.upperBound) {
  17.                 self.value = [array[range.lowerBound]]
  18.             } else {
  19.                 self.value = []
  20.             }
  21.         } else {
  22.             let middle = (range.lowerBound + range.upperBound) / 2
  23.             leftLeaf = RangeTree(array: array, range: range.lowerBound ..< middle)
  24.             rightLeaf = RangeTree(array: array, range: (middle + 1)..<range.upperBound)
  25.            
  26.             value = leftLeaf!.value + rightLeaf!.value
  27.         }
  28.     }
  29.    
  30.     func token(by range: NSRange) -> [T] {
  31.         return self.token(by: range.lowerBound..<range.upperBound)
  32.     }
  33.    
  34.     func token(by range: Range<Int>) -> [T] {
  35.         if self.range.lowerBound == range.lowerBound && self.range.upperBound <= range.upperBound {
  36.             return self.value
  37.         }
  38.        
  39.         guard let leftChild = self.leftLeaf else { return [] }
  40.         guard let rightChild = self.rightLeaf else { return [] }
  41.        
  42.         if leftChild.range.upperBound < range.lowerBound {
  43.             return rightChild.token(by: range)
  44.         } else if rightChild.range.lowerBound > range.upperBound {
  45.             return leftChild.token(by: range)
  46.         } else {
  47.             let leftResult = leftChild.token(by: range)
  48.             let rightResult = rightChild.token(by: range)
  49.             return leftResult + rightResult
  50.         }
  51.     }
  52.    
  53. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top