fenwick_tree 1.0.0

  • Readme
  • Changelog
  • Example
  • Installing
  • 58

fenwick_tree #

extra_pedantic on pub.dev Travis CI Codecov License Pub.dev Github Stars Twitter Follow GitHub Follow

A simple Fenwick Tree (also known as Binary Indexed Tree and BIT) in Dart.

Based on Princeton, FenwickTree.java

import 'package:abstract_dart/abstract_dart.dart';
import 'package:fenwick_tree/fenwick_tree.dart';

void example() {
  // A Fenwick Tree needs addition, subtraction and identity which are provided
  // in form of a Group. See https://pub.dev/packages/abstract_dart
  final tree = FenwickTree(group: const DoubleSumGroup(), size: 5);
  // or
  final tree2 = FenwickTree<double>.create(
    identity: () => 0.0,
    addition: (a, b) => a + b,
    subtraction: (a, b) => a - b,
    size: 5,
  );

  tree.update(0, 1.0);
  tree.update(1, 2.0);
  tree.update(2, 3.0);
  tree.update(3, 4.0);
  tree.update(4, 5.0);

  print(tree.sum(4)); // 15 (1+2+3+4+5)
  print(tree.rangeSum(3, 5)); // 9 (4+5)
  print(tree.length()); // 5
}

1.0.0 #

  • clean up, CI, examples and documentation added

0.1.0+1 #

  • Initial release

example/main.dart

import 'package:abstract_dart/abstract_dart.dart';
import 'package:fenwick_tree/fenwick_tree.dart';

void example() {
  // A Fenwick Tree needs addition, subtraction and identity which are provided
  // in form of a Group. See https://pub.dev/packages/abstract_dart
  final tree = FenwickTree(group: const DoubleSumGroup(), size: 5);
  // or
  final tree2 = FenwickTree<double>.create(
    identity: () => 0.0,
    addition: (a, b) => a + b,
    subtraction: (a, b) => a - b,
    size: 5,
  );

  tree.update(0, 1.0);
  tree.update(1, 2.0);
  tree.update(2, 3.0);
  tree.update(3, 4.0);
  tree.update(4, 5.0);

  print(tree.sum(4)); // 15 (1+2+3+4+5)
  print(tree.rangeSum(3, 5)); // 9 (4+5)
  print(tree.length()); // 5
}

void example2() {
  print("\t\t\tInit");
  const size = 10000000;

  final list = List.generate(size, (a) => a.toDouble());
  final tree = FenwickTree(group: const DoubleSumGroup(), size: size);

  list.asMap().entries.forEach((i) => tree.update(i.key, i.value));
  print("\t\t\tTree Updated");

  print("\t\t\tList.reduce");
  for (int i = 0; i <= 10; i++) {
    print(list.reduce((a, b) => a + b));
  }

  print("\t\t\tFenwickTree.sum");
  for (int i = 0; i <= 10; i++) {
    print(tree.sum(list.length - 1));
  }

  print("\t\t\tEnd");
}

void main() {
  example();
//  example2();
}

Use this package as a library

1. Depend on it

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


dependencies:
  fenwick_tree: ^1.0.0

2. Install it

You can install packages from the command line:

with pub:


$ pub get

with Flutter:


$ flutter pub get

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

3. Import it

Now in your Dart code, you can use:


import 'package:fenwick_tree/fenwick_tree.dart';
  
Popularity:
Describes how popular the package is relative to other packages. [more]
15
Health:
Code health derived from static analysis. [more]
100
Maintenance:
Reflects how tidy and up-to-date the package is. [more]
100
Overall:
Weighted score of the above. [more]
58
Learn more about scoring.

We analyzed this package on Jan 19, 2020, and provided a score, details, and suggestions below. Analysis was completed with status completed using:

  • Dart: 2.7.0
  • pana: 0.13.4

Dependencies

Package Constraint Resolved Available
Direct dependencies
Dart SDK >=2.2.2 <3.0.0
abstract_dart ^1.0.1 1.0.2
meta ^1.0.0 1.1.8
Transitive dependencies
decimal 0.3.5
rational 0.3.7
Dev dependencies
extra_pedantic ^1.1.1
test ^1.5.0
test_coverage ^0.2.0