1 /**
2  * Copyright (c) 2007-2012, Timothy Stack
3  *
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions are met:
8  *
9  * * Redistributions of source code must retain the above copyright notice, this
10  * list of conditions and the following disclaimer.
11  * * Redistributions in binary form must reproduce the above copyright notice,
12  * this list of conditions and the following disclaimer in the documentation
13  * and/or other materials provided with the distribution.
14  * * Neither the name of Timothy Stack nor the names of its contributors
15  * may be used to endorse or promote products derived from this software
16  * without specific prior written permission.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ''AS IS'' AND ANY
19  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21  * DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY
22  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
25  * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28  */
29 
30 #ifndef sequence_matcher_hh
31 #define sequence_matcher_hh
32 
33 #include <list>
34 #include <string>
35 #include <vector>
36 
37 #include "byte_array.hh"
38 
39 class sequence_matcher {
40 public:
41     typedef std::vector<std::string> field_row_t;
42     typedef std::list<field_row_t>   field_col_t;
43 
44     typedef byte_array<2, uint64_t>    id_t;
45 
46     enum field_type_t {
47         FT_VARIABLE,
48         FT_CONSTANT,
49     };
50 
51     struct field {
fieldsequence_matcher::field52         field() : sf_type(FT_VARIABLE) { };
53 
54         field_type_t sf_type;
55         field_row_t  sf_value;
56     };
57 
58     sequence_matcher(field_col_t &example);
59 
60     void identity(const std::vector<std::string> &values, id_t &id_out);
61 
62     template<typename T>
match(const std::vector<std::string> & values,std::vector<T> & state,T index)63     bool match(const std::vector<std::string> &values,
64                std::vector<T> &state,
65                T index)
66     {
67         bool index_match = true;
68         int  lpc         = 0;
69 
70 retry:
71         for (std::list<field>::iterator iter = this->sm_fields.begin();
72              iter != this->sm_fields.end();
73              ++iter, lpc++) {
74             if (iter->sf_type != sequence_matcher::FT_CONSTANT) {
75                 continue;
76             }
77 
78             if (iter->sf_value[state.size()] != values[lpc]) {
79                 if (!state.empty()) {
80                     state.clear();
81                     lpc = 0;
82                     goto retry;
83                 }
84                 else {
85                     index_match = false;
86                     break;
87                 }
88             }
89         }
90 
91         if (index_match) {
92             state.push_back(index);
93         }
94 
95         return (size_t)this->sm_count == state.size();
96     };
97 
98 private:
99     int sm_count;
100     std::list<field> sm_fields;
101 };
102 #endif
103