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-1335 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
PrefixCursor()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
~PrefixCursor()36 PrefixCursor::~PrefixCursor() {}
37
open(const Trie & trie,const String & str,UInt32 min_length,UInt32 offset,UInt32 limit,UInt32 flags)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
close()53 void PrefixCursor::close() {
54 PrefixCursor new_cursor;
55 new_cursor.swap(this);
56 }
57
next()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
PrefixCursor(const Trie & trie,UInt32 offset,UInt32 limit,UInt32 flags)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
fix_flags(UInt32 flags) const79 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
init(const String & str,UInt32 min_length)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
swap(PrefixCursor * cursor)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