• Matthias Walter (23/23) Mar 08 2012 Hi,
• Ellery Newcomer (21/24) Mar 08 2012

Matthias Walter <xammy xammy.homelinux.net> writes:

Hi,

I wanted to have a binary heap where I can update entries and restore
the heap structure.

1. First I observed that due to the implementation of
std.container.BinaryHeap, keeping track of the position of a certain
value in the heap cannot be done directly, but it would be helpful to
pass a "Swapper" object (or function) to the methods that may change the
order of the elements such that this Swapper is called for every swap()
operation such that the user of the BinaryHeap can keep track of the
permutation.

2. I tried to create a heap structure on my own, using
std.container.Array as a store. Of course, it I also needs to perform
swap operations, but the following did not work:

std.algorithm.swap(arrayInstance[i], arrayInstance[j]);

Also there is no usable swap() method of Array. So do I really have to
perform the swap on my own? I mean, 3 lines of code aren't that much but
I really expected an easy way.

3. For my structure I wanted to check the heap structure in an
invariant(). Unfortunately, accessing stored elements of Array is no
const operation, hence I could not implement such an invariant.

Maybe I'm not using it correctly, so any help or comments would be nice.

Best regards,

Matthias

Ellery Newcomer <ellery-newcomer utulsa.edu> writes:

On 03/08/2012 03:21 AM, Matthias Walter wrote:
 Hi,

 I wanted to have a binary heap where I can update entries and restore
 the heap structure.

<shameless plug>

I totally built this functionality in to multi_index's red black tree, 
hash table, and heap indeces.

-------------------------------------------------
alias MultiIndexContainer!(int, IndexedBy!(Heap!())) C1;

C1 c = new C1;
c.insert([1,2,3,4,5]);

auto rng = c[];

<point rng to item you want>

// modify the value, then heap is restored by container
c.modify(rng, (ref int i){ i = 42; });
-------------------------------------------------

If you have a more complicated type, you can also set up a signals and 
slots thing so you can keep a reference to your object and modify it and 
the container will automatically fix the heap without you having to use 
modify.

I also started on converting ranges from one index to ranges of another 
for e.g. using a hash table to reference your value/object, but I'm 
waiting on compiler bugs.

</shameless plug>