1 | /* -*- c-basic-offset: 2 -*- */ |
2 | /* Copyright(C) 2011 Brazil |
3 | |
4 | This library is free software; you can redistribute it and/or |
5 | modify it under the terms of the GNU Lesser General Public |
6 | License version 2.1 as published by the Free Software Foundation. |
7 | |
8 | This library is distributed in the hope that it will be useful, |
9 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
10 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
11 | Lesser General Public License for more details. |
12 | |
13 | You should have received a copy of the GNU Lesser General Public |
14 | License along with this library; if not, write to the Free Software |
15 | Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
16 | */ |
17 | |
18 | #include "prefix-cursor.hpp" |
19 | |
20 | #include <algorithm> |
21 | |
22 | #include "trie.hpp" |
23 | |
24 | namespace grn { |
25 | namespace dat { |
26 | |
27 | PrefixCursor::PrefixCursor() |
28 | : trie_(NULL), |
29 | offset_(0), |
30 | limit_(MAX_UINT32), |
31 | flags_(PREFIX_CURSOR), |
32 | buf_(), |
33 | cur_(0), |
34 | end_(0) {} |
35 | |
36 | PrefixCursor::~PrefixCursor() {} |
37 | |
38 | void PrefixCursor::open(const Trie &trie, |
39 | const String &str, |
40 | UInt32 min_length, |
41 | UInt32 offset, |
42 | UInt32 limit, |
43 | UInt32 flags) { |
44 | GRN_DAT_THROW_IF(PARAM_ERROR, (str.ptr() == NULL) && (str.length() != 0)); |
45 | GRN_DAT_THROW_IF(PARAM_ERROR, min_length > str.length()); |
46 | |
47 | flags = fix_flags(flags); |
48 | PrefixCursor new_cursor(trie, offset, limit, flags); |
49 | new_cursor.init(str, min_length); |
50 | new_cursor.swap(this); |
51 | } |
52 | |
53 | void PrefixCursor::close() { |
54 | PrefixCursor new_cursor; |
55 | new_cursor.swap(this); |
56 | } |
57 | |
58 | const Key &PrefixCursor::next() { |
59 | if (cur_ == end_) { |
60 | return Key::invalid_key(); |
61 | } |
62 | if ((flags_ & ASCENDING_CURSOR) == ASCENDING_CURSOR) { |
63 | return trie_->get_key(buf_[cur_++]); |
64 | } else { |
65 | return trie_->get_key(buf_[--cur_]); |
66 | } |
67 | } |
68 | |
69 | PrefixCursor::PrefixCursor(const Trie &trie, |
70 | UInt32 offset, UInt32 limit, UInt32 flags) |
71 | : trie_(&trie), |
72 | offset_(offset), |
73 | limit_(limit), |
74 | flags_(flags), |
75 | buf_(), |
76 | cur_(0), |
77 | end_(0) {} |
78 | |
79 | UInt32 PrefixCursor::fix_flags(UInt32 flags) const { |
80 | const UInt32 cursor_type = flags & CURSOR_TYPE_MASK; |
81 | GRN_DAT_THROW_IF(PARAM_ERROR, (cursor_type != 0) && |
82 | (cursor_type != PREFIX_CURSOR)); |
83 | flags |= PREFIX_CURSOR; |
84 | |
85 | const UInt32 cursor_order = flags & CURSOR_ORDER_MASK; |
86 | GRN_DAT_THROW_IF(PARAM_ERROR, (cursor_order != 0) && |
87 | (cursor_order != ASCENDING_CURSOR) && |
88 | (cursor_order != DESCENDING_CURSOR)); |
89 | if (cursor_order == 0) { |
90 | flags |= ASCENDING_CURSOR; |
91 | } |
92 | |
93 | const UInt32 cursor_options = flags & CURSOR_OPTIONS_MASK; |
94 | GRN_DAT_THROW_IF(PARAM_ERROR, cursor_options & ~EXCEPT_EXACT_MATCH); |
95 | |
96 | return flags; |
97 | } |
98 | |
99 | void PrefixCursor::init(const String &str, UInt32 min_length) { |
100 | if ((limit_ == 0) || (offset_ > (str.length() - min_length))) { |
101 | return; |
102 | } |
103 | |
104 | UInt32 node_id = ROOT_NODE_ID; |
105 | UInt32 i; |
106 | for (i = 0; i < str.length(); ++i) { |
107 | const Base base = trie_->ith_node(node_id).base(); |
108 | if (base.is_linker()) { |
109 | const Key &key = trie_->get_key(base.key_pos()); |
110 | if ((key.length() >= min_length) && (key.length() <= str.length()) && |
111 | (str.substr(0, key.length()).compare(key.str(), i) == 0) && |
112 | ((key.length() < str.length()) || |
113 | ((flags_ & EXCEPT_EXACT_MATCH) != EXCEPT_EXACT_MATCH))) { |
114 | buf_.push_back(base.key_pos()); |
115 | } |
116 | break; |
117 | } |
118 | |
119 | if ((i >= min_length) && |
120 | (trie_->ith_node(node_id).child() == TERMINAL_LABEL)) { |
121 | const Base linker_base = |
122 | trie_->ith_node(base.offset() ^ TERMINAL_LABEL).base(); |
123 | if (linker_base.is_linker()) { |
124 | buf_.push_back(linker_base.key_pos()); |
125 | } |
126 | } |
127 | |
128 | node_id = base.offset() ^ str[i]; |
129 | if (trie_->ith_node(node_id).label() != str[i]) { |
130 | break; |
131 | } |
132 | } |
133 | |
134 | if ((i == str.length()) && |
135 | ((flags_ & EXCEPT_EXACT_MATCH) != EXCEPT_EXACT_MATCH)) { |
136 | const Base base = trie_->ith_node(node_id).base(); |
137 | if (base.is_linker()) { |
138 | const Key &key = trie_->get_key(base.key_pos()); |
139 | if ((key.length() >= min_length) && (key.length() <= str.length())) { |
140 | buf_.push_back(base.key_pos()); |
141 | } |
142 | } else if (trie_->ith_node(node_id).child() == TERMINAL_LABEL) { |
143 | const Base linker_base = |
144 | trie_->ith_node(base.offset() ^ TERMINAL_LABEL).base(); |
145 | if (linker_base.is_linker()) { |
146 | buf_.push_back(linker_base.key_pos()); |
147 | } |
148 | } |
149 | } |
150 | |
151 | if (buf_.size() <= offset_) { |
152 | return; |
153 | } |
154 | |
155 | if ((flags_ & ASCENDING_CURSOR) == ASCENDING_CURSOR) { |
156 | cur_ = offset_; |
157 | end_ = (limit_ < (buf_.size() - cur_)) ? (cur_ + limit_) : buf_.size(); |
158 | } else { |
159 | cur_ = buf_.size() - offset_; |
160 | end_ = (limit_ < cur_) ? (cur_ - limit_) : 0; |
161 | } |
162 | } |
163 | |
164 | void PrefixCursor::swap(PrefixCursor *cursor) { |
165 | std::swap(trie_, cursor->trie_); |
166 | std::swap(offset_, cursor->offset_); |
167 | std::swap(limit_, cursor->limit_); |
168 | std::swap(flags_, cursor->flags_); |
169 | buf_.swap(&cursor->buf_); |
170 | std::swap(cur_, cursor->cur_); |
171 | std::swap(end_, cursor->end_); |
172 | } |
173 | |
174 | } // namespace dat |
175 | } // namespace grn |
176 | |