TCP-UDP-Protocol-Implementation/match_test.cpp at master · GeorgeGrasu/TCP-UDP-Protocol-Implementation · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <vector>
#include <string>
#include <set>

using namespace std;

bool is_match_recursive(const vector<string>& t_parts, const vector<string>& p_parts, int t_idx, int p_idx) {
    // Base cases
    if (p_idx == (int)p_parts.size() && t_idx == (int)t_parts.size()) return true;
    if (p_idx == (int)p_parts.size()) return false;

    // If pattern part is "*"
    if (p_parts[p_idx] == "*") {
        // If * is the last part, it matches everything remaining
        if (p_idx + 1 == (int)p_parts.size()) return true;

        // Try skipping k parts of topic (consuming 0 to N parts)
        // Correct logic: * matches ANY sequence of parts (0 or more).
        // So we can proceed with p_idx + 1 and ANY t_idx >= current t_idx
        for (int k = t_idx; k < (int)t_parts.size(); k++) {
             if (is_match_recursive(t_parts, p_parts, k, p_idx + 1)) return true;
        }

        // Handling the case where * matches the REST (if rest is valid for next pattern? No).
        // Wait, if * matches "upb/ec", and next is "pressure".
        // t: upb/ec/pressure. p: */pressure.
        // k=t_idx(0)->upb. try match(upb.., pressure).
        // The recursive call tries to match p_parts[p_idx+1] ("pressure") with t_parts[k] ("upb"). False.

        // k loop goes up to size-1?
        // t_parts.size().
        // If k=size. is_match(empty, pressure). returns false.

        // What if * matches the LAST part of topic too?
        // t: upb/pressure. p: */pressure.
        // k=0. match(upb.., pressure). 'upb'!='pressure'.
        // k=1. match(pressure, pressure). 'pressure'=='pressure'. True.

        // What if t: pressure. p: */pressure.
        // k=0. match(pressure, pressure). True.

        // Seems correct.
        return false;
    }

    if (t_idx == (int)t_parts.size()) return false; // Pattern remaining but no topic parts

    if (p_parts[p_idx] == "+" || p_parts[p_idx] == t_parts[t_idx]) {
        return is_match_recursive(t_parts, p_parts, t_idx + 1, p_idx + 1);
    }

    return false;
}

bool match_wrapper(const string& topic, const string& pattern) {
     vector<string> topic_parts;
    vector<string> pattern_parts;

    size_t pos = 0;
    string s = topic;
    while ((pos = s.find("/")) != string::npos) {
        topic_parts.push_back(s.substr(0, pos));
        s.erase(0, pos + 1);
    }
    topic_parts.push_back(s);

    pos = 0;
    string p = pattern;
    while ((pos = p.find("/")) != string::npos) {
        pattern_parts.push_back(p.substr(0, pos));
        p.erase(0, pos + 1);
    }
    pattern_parts.push_back(p);

    return is_match_recursive(topic_parts, pattern_parts, 0, 0);
}

int main() {
    // Failing cases
    // star wildcard
    cout << "*/pressure vs upb/ec/100/pressure: " << match_wrapper("upb/ec/100/pressure", "*/pressure") << endl;
    cout << "upb/precis/elevator/*/floor vs upb/precis/elevator/1/floor: " << match_wrapper("upb/precis/elevator/1/floor", "upb/precis/elevator/*/floor") << endl;
    cout << "upb/precis/* vs upb/precis/elevator/1/floor: " << match_wrapper("upb/precis/elevator/1/floor", "upb/precis/*") << endl;
    cout << "* vs upb/ec/100/pressure: " << match_wrapper("upb/ec/100/pressure", "*") << endl;

    // compound wildcard
    cout << "upb/+/100/+ vs upb/precis/100/temperature: " << match_wrapper("upb/precis/100/temperature", "upb/+/100/+") << endl;
    cout << "upb/+/100/* vs upb/precis/100/temperature: " << match_wrapper("upb/precis/100/temperature", "upb/+/100/*") << endl;
    cout << "*/100/+ vs upb/precis/100/temperature: " << match_wrapper("upb/precis/100/temperature", "*/100/+") << endl;

    return 0;
}