New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Fibonacci Heap `isEmpty()` returns opposite of expected #929

Open
davidabrahams opened this Issue Aug 20, 2017 · 10 comments

Comments

Projects
None yet
3 participants
@davidabrahams

davidabrahams commented Aug 20, 2017

using node to run code.

test.js:

var math = require('mathjs');

console.log('test');

var fib = new math.type.FibonacciHeap();
console.log(fib);
console.log(fib.isEmpty());
fib.insert(1, 1);
console.log();
console.log(fib);
console.log(fib._minimum);
console.log(!fib._minimum);
console.log(!!fib._minimum);
console.log();
console.log(fib.isEmpty());

Running node_modules/.bin/node test.js:

test
FibonacciHeap { _minimum: null, _size: 0 }
false

FibonacciHeap {
  _minimum: 
   { key: 1,
     value: 1,
     degree: 0,
     left: [Circular],
     right: [Circular] },
  _size: 1 }
{ key: 1,
  value: 1,
  degree: 0,
  left: [Circular],
  right: [Circular] }
false
true

true

@josdejong josdejong added the bug label Aug 21, 2017

@josdejong

This comment has been minimized.

Owner

josdejong commented Aug 21, 2017

Thanks for reporting this bug David.

So if I see it correctly, the implementation of isEmpty() has one ! too many, and should be return !this._minimum.

@josdejong

This comment has been minimized.

Owner

josdejong commented Aug 21, 2017

This is fixed now in the develop branch.

@davidabrahams

This comment has been minimized.

davidabrahams commented Aug 24, 2017

Not an issue, but, I'm having trouble figuring out how to properly import and use this library. Could you provide a code snippet for utilizing _decreaseKey?

@josdejong

This comment has been minimized.

Owner

josdejong commented Aug 24, 2017

_decreaseKey is an internal function used by FibbonacciHeap, it's not part of the public API.

@davidabrahams

This comment has been minimized.

davidabrahams commented Aug 24, 2017

@josdejong

This comment has been minimized.

Owner

josdejong commented Aug 26, 2017

I'm not very familiar with Fibbonacci heap, isn't decreasing a key value automatically done when removing a node with FibonacciHeap.remove?

@josdejong josdejong closed this in e45a00c Aug 28, 2017

@josdejong

This comment has been minimized.

Owner

josdejong commented Aug 28, 2017

The original issue (isEmpty returning wrong result) should be fixed now in v3.16.3.

I will keep the issue open to continue the discussion on any missing methods.

@josdejong josdejong reopened this Aug 28, 2017

@harrysarson

This comment has been minimized.

Collaborator

harrysarson commented Jan 18, 2018

Can the bug label now be removed?

@josdejong

This comment has been minimized.

Owner

josdejong commented Jan 18, 2018

ha ha, true

@josdejong josdejong added feature and removed bug labels Jan 18, 2018

@josdejong

This comment has been minimized.

Owner

josdejong commented Jan 18, 2018

I will keep the issue open to continue the discussion on any missing methods.

Hm, I don't remember what these exact missing methods are?...

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment