Latest 0.1.0
Homepage https://github.com/ben-ng/swift-range-tree
License MIT
Platforms ios 10.0, osx 10.11
Authors

CI Status
Version
License
Platform

A range tree allows you to perform orthorgonal range searches in polylogarithmic time. i.e. If you had a bunch of points in two-dimensional space, and you want to quickly figure out what points have an x coordinate between a and b, and a y coordinate between c and d, this is the module for you.

This module implements an n-dimensional range tree. You define how many dimensions you need by implementing the RangeTreePoint protocol. Note that you will see a performance penalty versus a naive Array.filter if your dataset is too small. See the section on performance to gauge if your dataset is large enough to benefit from this data structure.

Usage

  1. Implement the RangeTreePoint protocol (it’s already implemented on Int, Double, and CGPoint for you as part of this module)

    public protocol RangeTreePoint {
        associatedtype Position: Comparable
        static var dimensions: Int { get}
        func positionIn(dimension: Int) -> Position
    }
    
    // Sample implementation
    extension CGPoint: RangeTreePoint {
        public typealias Position = CGFloat
        public static var dimensions = 2
        public func positionIn(dimension: Int) -> Position {
            return dimension == 0 ? self.x : self.y
        }
    }
  2. Construct a RangeTree

    let a = RangeTree<Double>(values: [8, 1, 10, 4, 2, 7, 5, 3, 9, 6])
  3. Query for a range

    a.valuesInRange(rangePerDimension: (3.0, 6.0)) // => [3.0, 4.0, 5.0, 6.0]
  4. Modify the RangeTree

    a.insert(4.5)
    a.valuesInRange(rangePerDimension: (3.0, 6.0)) // => [3.0, 4.0, 4.5, 5.0, 6.0]

Performance

Quad-core 2.8 GHz i7 Retina MacBook Pro:

  • Constructing a tree
    • 1000 points: 0.133s
    • 10000 points: 1.104s
    • 100000 points: 8.420s
    • 1000000 points: 55.377s
  • Querying a tree
    • 1000 points: 0.001s (naive Array.filter: 0.000s) — slower
    • 10000 points: 0.002s (naive Array.filter: 0.004s) — 2x faster
    • 100000 points: 0.008s (naive Array.filter: 0.029s) – 3.6x faster
    • 1000000 points: 0.056s (naive Array.filter: 0.266s) – 4.8x faster

1.3 GHz Core m7 12" MacBook:

  • Constructing a tree
    • 1000 points: 0.206s
    • 10000 points: 1.323s
    • 100000 points: 10.413s
    • 1000000 points: 85.719s
  • Querying a tree
    • 1000 points: 0.002s (naive Array.filter: 0.001s) — slower
    • 10000 points: 0.004s (naive Array.filter: 0.007s) — 1.8x faster
    • 100000 points: 0.013s (naive Array.filter: 0.038s) — 2.9x faster
    • 1000000 points: 0.089s (naive Array.filter: 0.436s) — 4.9x faster

Example & Tests

To run the example project, clone the repo, and run pod install from the Example directory first.

Installation

RangeTree is available through CocoaPods. To install
it, simply add the following line to your Podfile:

pod "RangeTree"

Author

Ben Ng, [email protected]

License

RangeTree is available under the MIT license. See the LICENSE file for more info.

Latest podspec

{
    "name": "RangeTree",
    "version": "0.1.0",
    "summary": "Orthorgonal range searches in logarithmic time",
    "description": "A range tree allows you to perform orthorgonal range searches in logarithmic time.",
    "homepage": "https://github.com/ben-ng/swift-range-tree",
    "license": {
        "type": "MIT",
        "file": "LICENSE"
    },
    "authors": {
        "Ben Ng": "[email protected]"
    },
    "source": {
        "git": "https://github.com/ben-ng/swift-range-tree.git",
        "tag": "0.1.0"
    },
    "social_media_url": "https://twitter.com/_benng",
    "platforms": {
        "ios": "10.0",
        "osx": "10.11"
    },
    "source_files": "RangeTree/Classes/**/*"
}

Pin It on Pinterest

Share This