1 /* Copyright (C) 2004 - 2009  Versant Inc.  http://www.db4o.com */
2 
3 using System;
4 using Db4objects.Db4o.Internal.Btree;
5 
6 namespace Db4objects.Db4o.Internal.Btree
7 {
8 	/// <exclude></exclude>
9 	public sealed class Searcher
10 	{
11 		private int _lower;
12 
13 		private int _upper;
14 
15 		private int _cursor;
16 
17 		private int _cmp;
18 
19 		private readonly SearchTarget _target;
20 
21 		private readonly int _count;
22 
Searcher(SearchTarget target, int count)23 		public Searcher(SearchTarget target, int count)
24 		{
25 			if (count < 0)
26 			{
27 				throw new ArgumentException();
28 			}
29 			_target = target;
30 			_count = count;
31 			_cmp = -1;
32 			if (count == 0)
33 			{
34 				Complete();
35 				return;
36 			}
37 			_cursor = -1;
38 			_upper = count - 1;
39 			AdjustCursor();
40 		}
41 
AdjustBounds()42 		private void AdjustBounds()
43 		{
44 			if (_cmp > 0)
45 			{
46 				_upper = _cursor - 1;
47 				if (_upper < _lower)
48 				{
49 					_upper = _lower;
50 				}
51 				return;
52 			}
53 			if (_cmp < 0)
54 			{
55 				if (_lower == _cursor && _lower < _upper)
56 				{
57 					_lower++;
58 				}
59 				else
60 				{
61 					_lower = _cursor;
62 				}
63 				return;
64 			}
65 			if (_target == SearchTarget.Any)
66 			{
67 				_lower = _cursor;
68 				_upper = _cursor;
69 			}
70 			else
71 			{
72 				if (_target == SearchTarget.Highest)
73 				{
74 					_lower = _cursor;
75 				}
76 				else
77 				{
78 					if (_target == SearchTarget.Lowest)
79 					{
80 						_upper = _cursor;
81 					}
82 					else
83 					{
84 						throw new InvalidOperationException("Unknown target");
85 					}
86 				}
87 			}
88 		}
89 
AdjustCursor()90 		private void AdjustCursor()
91 		{
92 			int oldCursor = _cursor;
93 			if (_upper - _lower <= 1)
94 			{
95 				if ((_target == SearchTarget.Lowest) && (_cmp == 0))
96 				{
97 					_cursor = _lower;
98 				}
99 				else
100 				{
101 					_cursor = _upper;
102 				}
103 			}
104 			else
105 			{
106 				_cursor = _lower + ((_upper - _lower) / 2);
107 			}
108 			if (_cursor == oldCursor)
109 			{
110 				Complete();
111 			}
112 		}
113 
AfterLast()114 		public bool AfterLast()
115 		{
116 			if (_count == 0)
117 			{
118 				return false;
119 			}
120 			// _cursor is 0: not after last
121 			return (_cursor == _count - 1) && _cmp < 0;
122 		}
123 
BeforeFirst()124 		public bool BeforeFirst()
125 		{
126 			return (_cursor == 0) && (_cmp > 0);
127 		}
128 
Complete()129 		private void Complete()
130 		{
131 			_upper = -2;
132 		}
133 
Count()134 		public int Count()
135 		{
136 			return _count;
137 		}
138 
Cursor()139 		public int Cursor()
140 		{
141 			return _cursor;
142 		}
143 
FoundMatch()144 		public bool FoundMatch()
145 		{
146 			return _cmp == 0;
147 		}
148 
Incomplete()149 		public bool Incomplete()
150 		{
151 			return _upper >= _lower;
152 		}
153 
MoveForward()154 		public void MoveForward()
155 		{
156 			_cursor++;
157 		}
158 
ResultIs(int cmp)159 		public void ResultIs(int cmp)
160 		{
161 			_cmp = cmp;
162 			AdjustBounds();
163 			AdjustCursor();
164 		}
165 
IsGreater()166 		public bool IsGreater()
167 		{
168 			return _cmp < 0;
169 		}
170 	}
171 }
172