001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package com.db4o.internal.btree;
022:
023: /**
024: * @exclude
025: */
026: public class Searcher {
027:
028: private int _lower;
029:
030: private int _upper;
031:
032: private int _cursor;
033:
034: private int _cmp;
035:
036: private final SearchTarget _target;
037:
038: private final int _count;
039:
040: public Searcher(SearchTarget target, int count) {
041: if (count < 0) {
042: throw new IllegalArgumentException();
043: }
044: _target = target;
045: _count = count;
046: _cmp = -1;
047: if (count == 0) {
048: complete();
049: return;
050: }
051: _cursor = -1;
052: _upper = count - 1;
053: adjustCursor();
054: }
055:
056: private void adjustBounds() {
057: if (_cmp > 0) {
058: _upper = _cursor - 1;
059: if (_upper < _lower) {
060: _upper = _lower;
061: }
062: return;
063: }
064:
065: if (_cmp < 0) {
066: if (_lower == _cursor && _lower < _upper) {
067: _lower++;
068: } else {
069: _lower = _cursor;
070: }
071: return;
072: }
073:
074: if (_target == SearchTarget.ANY) {
075: _lower = _cursor;
076: _upper = _cursor;
077: } else if (_target == SearchTarget.HIGHEST) {
078: _lower = _cursor;
079: } else if (_target == SearchTarget.LOWEST) {
080: _upper = _cursor;
081: } else {
082: throw new IllegalStateException("Unknown target");
083: }
084:
085: }
086:
087: private void adjustCursor() {
088: int oldCursor = _cursor;
089: if (_upper - _lower <= 1) {
090: if ((_target == SearchTarget.LOWEST) && (_cmp == 0)) {
091: _cursor = _lower;
092: } else {
093: _cursor = _upper;
094: }
095: } else {
096: _cursor = _lower + ((_upper - _lower) / 2);
097: }
098: if (_cursor == oldCursor) {
099: complete();
100: }
101: }
102:
103: public boolean afterLast() {
104: if (_count == 0) {
105: return false; // _cursor is 0: not after last
106: }
107: return (_cursor == _count - 1) && _cmp < 0;
108: }
109:
110: public boolean beforeFirst() {
111: return (_cursor == 0) && (_cmp > 0);
112: }
113:
114: private void complete() {
115: _upper = -2;
116: }
117:
118: public int count() {
119: return _count;
120: }
121:
122: public int cursor() {
123: return _cursor;
124: }
125:
126: public boolean foundMatch() {
127: return _cmp == 0;
128: }
129:
130: public boolean incomplete() {
131: return _upper >= _lower;
132: }
133:
134: public void moveForward() {
135: _cursor++;
136: }
137:
138: public void resultIs(int cmp) {
139: _cmp = cmp;
140: adjustBounds();
141: adjustCursor();
142: }
143:
144: public boolean isGreater() {
145: return _cmp < 0;
146: }
147:
148: }
|