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