Add iterator merge

[bharath2438]

@hameerabbasi, I've written the merge function which outputs a compressed level...I'm working on intersection and union loops, should they also be functions in this file?

[hameerabbasi]

This is a two way merge. Please look at the codegen algorithm. You will take a binary constexpr function as a template parameter and codegen a merge from that based on iteration.

[bharath2438]

@hameerabbasi I have finished most of what is to be done in the iterator, I just need help to resolve a few things.

1. The second parameter of the iterator, I couldn't make it work with a tuple of optional PKs, since all of them were optional and I couldn't get the type of each PK.
2. For calling the locate of a particular level, we would require knowing pkm1, and moreover, the PK can be taken from the iterator itself, which I have implemented for now.
3. I am confused about how to go about implementing the == and != operators, how exactly are we going to use the consteval function to implement them...

[hameerabbasi]

1. The second parameter of the iterator, I couldn't make it work with a tuple of optional PKs, since all of them were optional and I couldn't get the type of each PK.

You can use declval and decltype for that.

2. For calling the locate of a particular level, we would require knowing pkm1, and moreover, the PK can be taken from the iterator itself, which I have implemented for now.

Use a class within a class, similar to the iter_helper class. Accept pkm1 and I... there.

3. I am confused about how to go about implementing the == and != operators, how exactly are we going to use the consteval function to implement them...

You need to compare the end of each iterator it_i != iterhelper_i.end(), make a tuple of that, feed it to the bool consteval, and what you get will be the result of !=.

Edit: The last thing comes with caveats: You cannot use it when you have locate types in the mix, since they won't have iterators.

[bharath2438]

@hameerabbasi I've added the == and != operators, turns out both sides of the operators have the iterator tuples in them and comparing these tuples should give us the required result.

[bharath2438]

@hameerabbasi I have changed the level tuple to take the reference and not the copy using std::tie. As for the == and != overrides, just the element-wise comparison of the LHS iterators tuple to the RHS "end" tuple will tell whether we have reached the end or not. I've also tested with two levels on my machine and it is able to output the pair.

[hameerabbasi]

While that's true, it will almost definitely decrease performance. It will cause us to iterate until all iterators are exhausted, rather than only the necessary ones.

[bharath2438]

@hameerabbasi This is the backtrace of the SIGSEGV that occurs, the same as in CI.

#0  xsparse::levels::singleton<std::tuple<>, unsigned long, unsigned long, xsparse::util::container_traits<std::vector, std::unordered_set, std::unordered_map>, xsparse::level_properties<true, true, true, true, true> >::pos_access(unsigned long, std::tuple<>) const (this=0x7ffedc0d8be0, pk=0, i=...)
--Type <RET> for more, q to quit, c to continue without paging--
    at ./singleton.hpp:85
85                  return m_crd[pk];
(gdb) bt
#0  xsparse::levels::singleton<std::tuple<>, unsigned long, unsigned long, xsparse::util::container_traits<std::vector, std::unordered_set, std::unordered_map>, xsparse::level_properties<true, true, true, true, true> >::pos_access(unsigned long, std::tuple<>) const (this=0x7ffedc0d8be0, pk=0, i=empty std::tuple)
    at ./singleton.hpp:85
#1  0x000055d08c7d9f1a in xsparse::level_capabilities::coordinate_position_iterate<xsparse::levels::singleton, std::tuple<>, unsigned long, unsigned long, xsparse::util::container_traits<std::vector, std::unordered_set, std::unordered_map>, xsparse::level_properties<true, true, true, true, true> >::iteration_helper::iterator::operator*() const (this=0x7ffedc0d8990)
    at ./../level_capabilities/coordinate_iterate.hpp:200```

[hameerabbasi]

It's possible that the level itself has gone out of scope and you are accessing it via an invalid reference.

[bharath2438]

@hameerabbasi The CI is now passing, and I've fixed the inline functions and the const correctness everywhere. The only place where we are using two std::apply is in the begin and end functions, but combining them into a single std::apply gives a segfault for the same reason that we witnessed in yesterday's meeting, so I've not made that change.

[hameerabbasi]

Okay, I will give this a thorough review today evening.

[bharath2438]

@hameerabbasi So do we intend to do away with coiteration_helper class altogether and just have a Coiterate outer class? Because, right now, Coiterate has a coiter_helper function that returns an instance of the coiteration_helper class.

[hameerabbasi]

The idea is to just have I and PKM1 in the coiteration_helper

[bharath2438]

@hameerabbasi We can co-iterate over levels of different sizes, right? The second test case has 3 dense levels of sizes 5, 5 and 4.

[hameerabbasi]

I mean the size of the dimension, not the number of coordinates in it. So, to co iterate between two regular dense arrays, you'd need them to be the same dimension.

[hameerabbasi]

For example, .m_size should be 3 for both

[bharath2438]

@hameerabbasi Then I guess we will have to compare the size of LowerLevels..., as the m_size of each level gives the no. of coordinates?

[hameerabbasi]

Nope, only the current level is sufficient.

[bharath2438]

Nope, only the current level is sufficient.

But the .m_size of the levels refers to the coordinates, so should we actually check if the no. of levels that are wrapping around the given levels, is equal?

[hameerabbasi]

Actually, we need to check the size of a particular level. Think of shape in NumPy for example: We need shapes to be equal for an element-wise operation to work. But for shapes to be the same, it is necessary and sufficient to just ensure they are the same at each level.

That's all we need: To ensure that for a + b, a.shape[i] == b.shape[i] for a particular value of i. The other values of i will be checked elsewhere.

[bharath2438]

@hameerabbasi I've got it now, but the only problem is that the m_size of the levels is currently private, is it safe to make them public, also they only exist after the object creation so should we use static_assert or only assert?

[hameerabbasi]

I think an accessor method named size() should be added, and we should raise an exception.

[bharath2438]

@hameerabbasi Is the exception proper? It compares the sizes of all levels and raises a std::runtime_error.

[bharath2438]

LGTM @bharath2438! Thanks for your patience and attitude during the review process. I appreciate the work done so far!

Thanks a ton for the multiple rounds of reviews and helping me optimize the code, the help with debugging and cleaning up the errors. I had an amazing time working on Co-iteration!