interval_skip_list 0.1.0

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

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']
}

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

with Flutter:


$ flutter packages get

Alternatively, your editor might support pub get or packages 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

Analysis

This feature is new.
We welcome feedback.
More details: scoring.

We analyzed this package, and provided a score, details, and suggestions below.

  • completed on Feb 3, 2018
  • Dart: 2.0.0-dev.20.0
  • pana: 0.10.1

Scores

Popularity:
Describes how popular the package is relative to other packages. [more]
5 / 100
Health:
Code health derived from static analysis. [more]
100 / 100
Maintenance:
Reflects how tidy and up-to-date the package is. [more]
74 / 100
Overall score:
Weighted score of the above. [more]
47

Platforms

Detected platforms: Flutter, web, other

No platform restriction found in primary library package:interval_skip_list/interval_skip_list.dart.

Suggestions

  • Package is pre-v1 release.

    While there is nothing inherently wrong with versions of 0.*.*, it usually means that the author is still experimenting with the general direction API.

  • Use analysis_options.yaml.

    Rename old .analysis_options file to analysis_options.yaml.

Dependencies

Package Constraint Resolved Available
Direct dependencies
Dart SDK >=1.8.0 <2.0.0
meta ^1.0.4 1.1.2
Dev dependencies
test >=0.12.0 <0.13.0