Algorithm optimizations

Disclamer:

In fact, I use a lot more different optimizations, but only the most important ones are documented!

Node traversal queue:

After creating a good graph structure, all I have to take care of is the structure for the "traversal queue".

Key operations:

• insert in front and tail
• pop from front
• ordered middle insertion
• move an item to the desired location (after reweight)

So special for this project I wrote list_on_array. Now it is part of my libft. HERE is wiki page for it.

asymptotic analysis for node traversal queue:

n - current number of elements in traversal queue

• insert in front and tail - O(1)
• pop from front - O(1)
• ordered middle insertion - O(n) for search and O(1) for insert
• move an item to the desired location - O(n) for search and O(1) for insert

You may notice, that O(n) - isn't good, BUT! We always handle node from queue with minimum weight. So the worst case for us - skip nodes with same weight as processed node! And THIS is about O(1)!!! Pretty good, right?

As well as in all other places - 1 piece of memory - good caching and access - good performance.