interval_skip_list 0.1.0

  • README.md
  • CHANGELOG.md
  • Example
  • Installing
  • Versions
  • 0

Interval Skip List

This data structure maps intervals to values and allows you to find all intervals that contain an index in O(ln(n)), where n is the number of intervals stored. This implementation is based on Atom's interval-skip-list, which is in turn based on the paper The Interval Skip List by Eric N. Hanson.

Build Status Coverage Status

Basic Usage Example

import 'package:interval_skip_list/interval_skip_list.dart';

final list = new IntervalSkipList(minIndex: -0x80000000, maxIndex: 0x7FFFFFFF);

list.insert('a', 2, 7);
list.insert('b', 1, 5);
list.insert('c', 8, 8);

print(list.findContaining([1]));
// ['b']
print(list.findContaining([2]));
// ['b', 'a']
print(list.findContaining([8]));
// ['c']

list.remove('b');

print(list.findContaining([2]));
// ['a']

Using a Custom Comparator

You can also supply a custom comparator function with corresponding min and max index values. The following example uses lists expressing coordinate pairs instead of the default numeric values:

final list = new IntervalSkipList(
    minIndex: [-0x80000000],
    maxIndex: [0x7FFFFFFF], compare: (a, b) {
  if (a[0] < b[0]) return -1;
  else if (a[0] > b[0]) return 1;
  else {
    if (a[1] < b[1]) return -1;
    else if (a[1] > b[1]) return 1;
    else return 0;
  }
});

list.insert("a", [1, 2], [3, 4]);
list.insert("b", [2, 1], [3, 10]);

Changelog

0.1.0

  • Turn on strong mode and fix warnings and errors.
  • Breaking change - minIndex and maxIndex arguments of IntervalSkipList constructor are no longer optional.

0.0.3

  • Add clear().

0.0.2

  • Add findFirstAfterMin() and findLastBeforeMax().

0.0.1

  • Initial version

example/interval_skip_list.dart

// Copyright (c) 2015, <your name>. All rights reserved. Use of this source code
// is governed by a BSD-style license that can be found in the LICENSE file.

library interval_skip_list.example;

import 'package:interval_skip_list/interval_skip_list.dart';

main() {
  final list =
      new IntervalSkipList(minIndex: -0x80000000, maxIndex: 0x7FFFFFFF);

  list.insert('a', 2, 7);
  list.insert('b', 1, 5);
  list.insert('c', 8, 8);

  print(list.findContaining([1]));
  // ['b']
  print(list.findContaining([2]));
  // ['b', 'a']
  print(list.findContaining([8]));
  // ['c']

  list.remove('b');

  print(list.findContaining([2]));
  // ['a']
}

Use this package as a library

1. Depend on it

Add this to your package's pubspec.yaml file:


dependencies:
  interval_skip_list: ^0.1.0

2. Install it

You can install packages from the command line:

with pub:


$ pub get

Alternatively, your editor might support pub get. Check the docs for your editor to learn more.

3. Import it

Now in your Dart code, you can use:


import 'package:interval_skip_list/interval_skip_list.dart';
  
Version Uploaded Documentation Archive
0.1.0 Oct 31, 2016 Go to the documentation of interval_skip_list 0.1.0 Download interval_skip_list 0.1.0 archive
0.0.3 Nov 6, 2015 Go to the documentation of interval_skip_list 0.0.3 Download interval_skip_list 0.0.3 archive
0.0.2 Nov 4, 2015 Go to the documentation of interval_skip_list 0.0.2 Download interval_skip_list 0.0.2 archive
0.0.1 Nov 2, 2015 Go to the documentation of interval_skip_list 0.0.1 Download interval_skip_list 0.0.1 archive
Popularity:
Describes how popular the package is relative to other packages. [more]
0
Health:
Code health derived from static analysis. [more]
--
Maintenance:
Reflects how tidy and up-to-date the package is. [more]
--
Overall:
Weighted score of the above. [more]
0
Learn more about scoring.

The package version is not analyzed, because it does not support Dart 2. Until this is resolved, the package will receive a health and maintenance score of 0.

Analysis issues and suggestions

Support Dart 2 in pubspec.yaml.

The SDK constraint in pubspec.yaml doesn't allow the Dart 2.0.0 release. For information about upgrading it to be Dart 2 compatible, please see https://www.dartlang.org/dart-2#migration.

Maintenance issues and suggestions

Running dartdoc failed. (-10 points)

Make sure dartdoc runs without any issues.

Dependencies

Package Constraint Resolved Available
Direct dependencies
Dart SDK >=1.8.0 <2.0.0