Follow @nxtchg

Author Topic: Code Puzzles  (Read 541 times)

NxtChg

  • Overlord
  • *****
  • Posts: 1114
  • Respect: +61
    • View Profile
Code Puzzles
« on: January 13, 2016, 09:53:34 am »
0
For the programmers in the audience.

I noticed that I use the same setup in several places and decided to make a stand-alone class for that.

The class combines a ring (a fixed-length array, which wraps around as you add items into it) and an efficient key-pointer storage (kps).

This way I have both linear workflow and extremely fast searching by a key.

kps has add(ptr), remove(key) and find(key) and it always returns the latest object, since add() overwrites the pointer if the key is the same.

All objects have a key() method that returns its key.

If there are multiple objects with the same key, they are arranged in a linked list: each object has a 'prev' pointer that points to the previous object with the same key.

Here's some code to illustrate:

Code: [Select]
thing* add(thing &t)
{
thing *n      = ring.add(t);
if(n) n->prev =  kps.add(n);

return n;
}

When we add a new item we overwrite it in kps and if there was a previous one in it we point our 'prev' to it.

So far so good.

Now I want to add a swap() function, which would allow exchanging any two elements. I already have it in the ring as ring.swap(idx1, idx2).

The problem is that it ruins the linked list and kps pointer. If it was a simple array and not a ring that can wrap around, the problem would be a bit easier.

So the question is: what is the simplest and most efficient way to implement the swap() in such a way as to preserve monotonic 'prev' order after the swap?

(The ring can be huge and contain millions of objects).

My best guess so far is to convert all pointers into absolute ring indexes, then convert them into relative indexes, so I have monotonic order again.

The code would still be quite messy, so maybe somebody has a better solution.
Tentacle Overlord, The Deranged Genius of The Abyss

NxtChg

  • Overlord
  • *****
  • Posts: 1114
  • Respect: +61
    • View Profile
Re: Code Puzzles
« Reply #1 on: January 13, 2016, 10:07:06 am »
0
Here's a picture to make things clearer:



We have items 6,4,2,1 with the same key linked inside the ring.
Tentacle Overlord, The Deranged Genius of The Abyss

wizzardTim

  • Jr. Minion
  • **
  • Posts: 80
  • Respect: +5
    • View Profile
Re: Code Puzzles
« Reply #2 on: January 14, 2016, 11:34:44 am »
0
Some thoughts (maybe not so helpful, because I am confused about the kps):

If you try to include the changing of the "previous" pointers of the next items (from those that will be swapped), inside of the swap function (that would require a search inside the ring  before the swap in order to find which pointer pointed to the to-be-swapped item), and also changing the previous pointers of the swapped items (between them), that would save the kps validity and functionality?

Also, what if every element knows of the total number of elements with the same key..that would help avoid some searches inside the ring




NxtChg

  • Overlord
  • *****
  • Posts: 1114
  • Respect: +61
    • View Profile
Re: Code Puzzles
« Reply #3 on: January 14, 2016, 04:43:43 pm »
0
Also, what if every element knows of the total number of elements with the same key..that would help avoid some searches inside the ring

Yes, this is one of the ideas - to add a counter to kps and then just do a loop instead of relying on NULL pointer at the end. The problem is - it's very hard to add a counter into kps due to its design. But that's still on the table.

So far I made this function, which at least solves the pointer wrap around problem:

Code: [Select]
bool between(thing *a, thing *p, thing *b)
{
if(b < a) b += size;

return (a < p && p < b);
}

This way I don't need to convert to indexes.

Then I do 4 passes by the linked lists: 2 to remove swapped elements and 2 to reinsert them at correct positions.

That's something I'm not happy about, but the number of items with the same key should be relatively small most of the time.

For cases where it's not true, I am considering a double-linked list at the cost of yet another pointer per item...

Not happy with any solutions so far, but need to pick something good enough and move on.
Tentacle Overlord, The Deranged Genius of The Abyss