CODEWITHSUNDEEP
c++algorithmset-intersectionset-union
Pauete Galopa
Pauete Galopa

Reputation: 153

Simultaneous Union and Intersection between two maps in C++

While doing a college project I came upon the following problem: I have two maps (Kmer1 and Kmer2) which are composed by a string(key) and a int(value). I have to calculate the distance which follows this formula

[1-(I/U)]*100

Where...
     ...U = the sum of all int values inside Kmer1 U Kmer2
     ...I = the sum of all int values inside Kmer1 ∩ Kmer2

Consider that...
             ... The U and ∩ are made evaluating the keys (strings)
             ... When an element is in both maps:
                 - At the Union we add the one with higher int value
                 - At the Intersection we add the one with lower int value

Example:

Kmer1 = AAB¹ AAC¹ AAG³
Kmer2 = AAG¹ AAT² ABB¹

Union = AAB¹ AAC¹ AAG³ AAT² ABB¹   U= 8
Intersection = AAG¹                I= 1
Distance = 87.5

Code time! I've been trying to solve it but all solutions are like.. partially right, not all cases are covered. So when I tried to cover them, I ended in infinite loops, exceptions rising, long long nests of if-else (which were awfull..) anyway, here is the the least worse and non working try:

The setup:

Species::Kmer Kmer1, Kmer2;        //The two following lines get the Kmer from another
Kmer1 = esp1->second.query_kmer(); //object.
Kmer2 = esp2->second.query_kmer(); 

Species::Kmer::const_iterator it1, it2, last1, last2;
it1 = Kmer1.cbegin();           //Both Kmer are maps, therefore they are ordered and
it2 = Kmer2.cbegin();           //whitout duplicates.
last1 = --Kmer1.cend();
last2 = --Kmer2.cend();

double U, I;
U = I = 0;

The loop where the formula is applied:

while (it1 != Kmer1.cend() and it2 != Kmer2.cend()){
    if (it1->first == it2->first) {         
        if (it1->second > it2->second) {
            U += it1->second;
            I += it2->second;
        } else {
            U += it2->second;
            I += it1->second;
        }
        ++it1;
        ++it2;

    } else if (it1->first < it2->first) {
        U += it1->second;
        ++it1;
    } else {
        U += it2->second;
        ++it2;
    }
}

Note that instead of first creating the Union and the intersection and then doing the total sum of each, I jumped directly to the sum of the values. I know maybe it's not that hard but I've been trying to solve it but I'm pretty much stuck...

I've uploaded the whole code at Github: (Maybe it helps)
    - There is a makefile to build the code
    - There is a file called input.txt with a sample for this specific problem
    - Also inside the input.txt, after line13 (fin) I've added the expected output
    - Executing ./program.exe < input.txt should be enough to test it.

https://github.com/PauGalopa/Cpp-Micro-Projects/tree/master/Release

IMPORTANT Yes! I'm aware of almost all the STL functionality that could do this in a few lines BUT... Since this is a college project i'm bound to the limitations of the sillabus so consider that I'm only allowed to use "map" "string" "vector" and a few more. No, I can't use "algorithm" (I really wish I could) I'll clarify any doubt about which things I can do or use in the coments.

Upvotes: 2

Views: 179

Answers (4)

Mad Physicist
Mad Physicist

Reputation: 114320

A slightly cleaner approach for unordered_mapping, but which would still work with mapping would be to add all the elements of Kmer1 to U, and shared elements to I. Then add all the unshared elements of Kmer2 to U:

for(it1 = Kmer1.cbegin(); it1 != Kmer1.cend(); it1++) {
    auto other = Kmer2.find(it1->first);
    if(other == Kmer2.cend()) {
        U += it1->second;
    } else {
        U += max(it1->second, other->second);
        I += min(it1->second, other->second);
    }
}
for(it2 = Kmer2.cbegin(); it2 != Kmer2.cend(); it2++) {
    if(Kmer1.count(it2->first) == 0) {
        U += it2->second
    }
}

For a properly implemented unordered_mapping (hash table), the find operation will be O(1), not O(log(n), making it a bit faster.

Upvotes: 1

Damien
Damien

Reputation: 4864

Here is a rather simple solution, using only some propoerties of std::map, with no iterator. I hope you are allowed to use this kind of solution. 

#include <iostream>
#include <map>
#include <string>

int main () {
    std::map <std::string, int> A = {{"AAB", 1}, {"AAC", 1}, {"AAG", 3}};
    std::map <std::string, int> B = {{"AAG", 1}, {"AAT", 2}, {"ABB", 1}};

    std::map <std::string, int> Union;
    int sum_A = 0, sum_B = 0, sum_Union = 0, sum_Inter = 0;;

    for (auto &x: A) {
        Union[x.first] = std::max (Union[x.first], x.second);
        sum_A += x.second;
    }
    for (auto &x: B) {
        Union[x.first] = std::max (Union[x.first], x.second);
        sum_B += x.second;
    }   
    for (auto &x: Union) {
        sum_Union += x.second;
    }
    sum_Inter = sum_A + sum_B - sum_Union;
    double distance = 100.0 * (1.0 - double(sum_Inter)/sum_Union);

    std::cout << "sum_Union = " << sum_Union << " sum_Inter = " << sum_Inter << "\n";
    std::cout << "Distance = " << distance << "\n";
}

Upvotes: 2

Slava
Slava

Reputation: 44258

This loop should work:

while ( true ){
    bool end1 = it1 == Kmer1.cend();
    bool end2 = it2 == Kmer2.cend();
    if( end1 and end2 )
        break;

    if( end2 or it1->first < it2->first ) {
        U += (it1++)->second;
        continue;
    }
    if( end1 or it2->first < it1->first ) {
        U += (it2++)->second;
        continue;
    }
    auto p = std::minmax( (it1++)->second, (it2++)->second );
    I += p.first;
    U += p.second;
}

Upvotes: 1

ciamej
ciamej

Reputation: 7068

Add these two loops just after your main while loop.

while (it1 != Kmer1.cend()){
    U += it1->second;
    it1++;
}
while (it2 != Kmer2.cend()){
    U += it2->second;
    it2++;
}

Upvotes: 2

Related Questions