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 "id-cursor.hpp"
19
20 #include <algorithm>
21
22 #include "trie.hpp"
23
24 namespace grn {
25 namespace dat {
26
IdCursor()27 IdCursor::IdCursor()
28 : trie_(NULL),
29 offset_(0),
30 limit_(MAX_UINT32),
31 flags_(ID_RANGE_CURSOR),
32 cur_(INVALID_KEY_ID),
33 end_(INVALID_KEY_ID),
34 count_(0) {}
35
~IdCursor()36 IdCursor::~IdCursor() {}
37
open(const Trie & trie,const String & min_str,const String & max_str,UInt32 offset,UInt32 limit,UInt32 flags)38 void IdCursor::open(const Trie &trie,
39 const String &min_str,
40 const String &max_str,
41 UInt32 offset,
42 UInt32 limit,
43 UInt32 flags) {
44 UInt32 min_id = INVALID_KEY_ID;
45 if (min_str.ptr() != NULL) {
46 UInt32 key_pos;
47 GRN_DAT_THROW_IF(PARAM_ERROR,
48 !trie.search(min_str.ptr(), min_str.length(), &key_pos));
49 min_id = trie.get_key(key_pos).id();
50 }
51
52 UInt32 max_id = INVALID_KEY_ID;
53 if (max_str.ptr() != NULL) {
54 UInt32 key_pos;
55 GRN_DAT_THROW_IF(PARAM_ERROR,
56 !trie.search(max_str.ptr(), max_str.length(), &key_pos));
57 max_id = trie.get_key(key_pos).id();
58 }
59
60 open(trie, min_id, max_id, offset, limit, flags);
61 }
62
open(const Trie & trie,UInt32 min_id,UInt32 max_id,UInt32 offset,UInt32 limit,UInt32 flags)63 void IdCursor::open(const Trie &trie,
64 UInt32 min_id,
65 UInt32 max_id,
66 UInt32 offset,
67 UInt32 limit,
68 UInt32 flags) {
69 flags = fix_flags(flags);
70
71 IdCursor new_cursor(trie, offset, limit, flags);
72 new_cursor.init(min_id, max_id);
73 new_cursor.swap(this);
74 }
75
close()76 void IdCursor::close() {
77 IdCursor new_cursor;
78 new_cursor.swap(this);
79 }
80
next()81 const Key &IdCursor::next() {
82 if (count_ >= limit_) {
83 return Key::invalid_key();
84 }
85 while (cur_ != end_) {
86 const Key &key = trie_->ith_key(cur_);
87 if ((flags_ & ASCENDING_CURSOR) == ASCENDING_CURSOR) {
88 ++cur_;
89 } else {
90 --cur_;
91 }
92 if (key.is_valid()) {
93 ++count_;
94 return key;
95 }
96 }
97 return Key::invalid_key();
98 }
99
IdCursor(const Trie & trie,UInt32 offset,UInt32 limit,UInt32 flags)100 IdCursor::IdCursor(const Trie &trie,
101 UInt32 offset,
102 UInt32 limit,
103 UInt32 flags)
104 : trie_(&trie),
105 offset_(offset),
106 limit_(limit),
107 flags_(flags),
108 cur_(INVALID_KEY_ID),
109 end_(INVALID_KEY_ID),
110 count_(0) {}
111
fix_flags(UInt32 flags) const112 UInt32 IdCursor::fix_flags(UInt32 flags) const {
113 const UInt32 cursor_type = flags & CURSOR_TYPE_MASK;
114 GRN_DAT_THROW_IF(PARAM_ERROR, (cursor_type != 0) &&
115 (cursor_type != ID_RANGE_CURSOR));
116 flags |= ID_RANGE_CURSOR;
117
118 const UInt32 cursor_order = flags & CURSOR_ORDER_MASK;
119 GRN_DAT_THROW_IF(PARAM_ERROR, (cursor_order != 0) &&
120 (cursor_order != ASCENDING_CURSOR) &&
121 (cursor_order != DESCENDING_CURSOR));
122 if (cursor_order == 0) {
123 flags |= ASCENDING_CURSOR;
124 }
125
126 const UInt32 cursor_options = flags & CURSOR_OPTIONS_MASK;
127 GRN_DAT_THROW_IF(PARAM_ERROR,
128 cursor_options & ~(EXCEPT_LOWER_BOUND | EXCEPT_UPPER_BOUND));
129
130 return flags;
131 }
132
init(UInt32 min_id,UInt32 max_id)133 void IdCursor::init(UInt32 min_id, UInt32 max_id) {
134 if (min_id == INVALID_KEY_ID) {
135 min_id = trie_->min_key_id();
136 } else if ((flags_ & EXCEPT_LOWER_BOUND) == EXCEPT_LOWER_BOUND) {
137 ++min_id;
138 }
139
140 if (max_id == INVALID_KEY_ID) {
141 max_id = trie_->max_key_id();
142 } else if ((flags_ & EXCEPT_UPPER_BOUND) == EXCEPT_UPPER_BOUND) {
143 --max_id;
144 }
145
146 if ((max_id < min_id) || ((max_id - min_id) < offset_)) {
147 return;
148 }
149
150 if ((flags_ & ASCENDING_CURSOR) == ASCENDING_CURSOR) {
151 cur_ = min_id;
152 end_ = max_id + 1;
153 for (UInt32 i = 0; (i < offset_) && (cur_ != end_); ++i) {
154 while (cur_ != end_) {
155 if (trie_->ith_key(cur_++).is_valid()) {
156 break;
157 }
158 }
159 }
160 } else {
161 cur_ = max_id;
162 end_ = min_id - 1;
163 for (UInt32 i = 0; (i < offset_) && (cur_ != end_); ++i) {
164 while (cur_ != end_) {
165 if (trie_->ith_key(cur_--).is_valid()) {
166 break;
167 }
168 }
169 }
170 }
171 }
172
swap(IdCursor * cursor)173 void IdCursor::swap(IdCursor *cursor) {
174 std::swap(trie_, cursor->trie_);
175 std::swap(offset_, cursor->offset_);
176 std::swap(limit_, cursor->limit_);
177 std::swap(flags_, cursor->flags_);
178 std::swap(cur_, cursor->cur_);
179 std::swap(end_, cursor->end_);
180 std::swap(count_, cursor->count_);
181 }
182
183 } // namespace dat
184 } // namespace grn
185