[2732] | 1 | // |
---|
| 2 | // C++ Implementation: HuntLocator |
---|
| 3 | // |
---|
| 4 | // Description: |
---|
| 5 | // |
---|
| 6 | // |
---|
| 7 | // Author: Takeshi Nakazato <takeshi.nakazato@nao.ac.jp>, (C) 2012 |
---|
| 8 | // |
---|
| 9 | // Copyright: See COPYING file that comes with this distribution |
---|
| 10 | // |
---|
| 11 | // |
---|
| 12 | #include <assert.h> |
---|
| 13 | |
---|
| 14 | #include "HuntLocator.h" |
---|
| 15 | |
---|
| 16 | namespace asap { |
---|
| 17 | |
---|
| 18 | template <class T> HuntLocator<T>::HuntLocator() |
---|
| 19 | : Locator<T>(), |
---|
| 20 | prev_(0) |
---|
| 21 | {} |
---|
| 22 | |
---|
| 23 | template <class T> HuntLocator<T>::HuntLocator(T *v, unsigned int n, bool copystorage) |
---|
| 24 | : Locator<T>(v, n, copystorage), |
---|
| 25 | prev_(0) |
---|
| 26 | {} |
---|
| 27 | |
---|
| 28 | template <class T> HuntLocator<T>::~HuntLocator() |
---|
| 29 | {} |
---|
| 30 | |
---|
| 31 | template <class T> unsigned int HuntLocator<T>::locate(T x) |
---|
| 32 | { |
---|
| 33 | if (this->n_ == 1) |
---|
| 34 | return 0; |
---|
| 35 | |
---|
| 36 | if (this->ascending_) { |
---|
| 37 | if (x <= this->x_[0]) |
---|
| 38 | return 0; |
---|
| 39 | else if (x > this->x_[this->n_-1]) |
---|
| 40 | return this->n_; |
---|
| 41 | } |
---|
| 42 | else { |
---|
| 43 | if (x > this->x_[0]) |
---|
| 44 | return 0; |
---|
| 45 | else if (x <= this->x_[this->n_-1]) |
---|
| 46 | return this->n_; |
---|
| 47 | } |
---|
| 48 | |
---|
| 49 | unsigned int jl = 0; |
---|
| 50 | unsigned int ju = this->n_; |
---|
| 51 | |
---|
| 52 | // hunt phase |
---|
| 53 | if (prev_ > 0 && prev_ < this->n_) { |
---|
| 54 | jl = prev_; |
---|
| 55 | hunt(x, jl, ju); |
---|
| 56 | } |
---|
| 57 | |
---|
| 58 | // final bisection phase |
---|
| 59 | unsigned int j = this->bisection(x, jl, ju); |
---|
| 60 | prev_ = (j > 0) ? j - 1 : 0; |
---|
| 61 | return j; |
---|
| 62 | } |
---|
| 63 | |
---|
| 64 | template <class T> void HuntLocator<T>::hunt(T x, unsigned int &left, unsigned int &right) |
---|
| 65 | { |
---|
| 66 | unsigned int inc = 1; |
---|
| 67 | if (this->ascending_) { |
---|
| 68 | // ascending order |
---|
| 69 | if (x >= this->x_[left]) { |
---|
| 70 | // forward hunt |
---|
| 71 | if (left >= this->n_ - 1) { |
---|
| 72 | right = this->n_; |
---|
| 73 | return; |
---|
| 74 | } |
---|
| 75 | right = left + inc; |
---|
| 76 | while (x >= this->x_[right]) { |
---|
| 77 | left = right; |
---|
| 78 | inc *= 2; |
---|
| 79 | right = left + inc; |
---|
| 80 | if (right > this->n_ - 1) { |
---|
| 81 | right = this->n_; |
---|
| 82 | break; |
---|
| 83 | } |
---|
| 84 | } |
---|
| 85 | } |
---|
| 86 | else { |
---|
| 87 | // backward hunt |
---|
| 88 | if (left == 0) { |
---|
| 89 | right = 0; |
---|
| 90 | return; |
---|
| 91 | } |
---|
| 92 | right = left; |
---|
| 93 | left -= inc; |
---|
| 94 | while (x < this->x_[left]) { |
---|
| 95 | right = left; |
---|
| 96 | inc *= 2; |
---|
| 97 | if (inc >= right) { |
---|
| 98 | left = 0; |
---|
| 99 | break; |
---|
| 100 | } |
---|
| 101 | left = right - inc; |
---|
| 102 | } |
---|
| 103 | } |
---|
| 104 | } |
---|
| 105 | else { |
---|
| 106 | // descending order |
---|
| 107 | if (x < this->x_[left]) { |
---|
| 108 | // forward hunt |
---|
| 109 | if (left >= this->n_ - 1) { |
---|
| 110 | right = this->n_; |
---|
| 111 | return; |
---|
| 112 | } |
---|
| 113 | right = left + inc; |
---|
| 114 | while (x < this->x_[right]) { |
---|
| 115 | left = right; |
---|
| 116 | inc *= 2; |
---|
| 117 | right = left + inc; |
---|
| 118 | if (right > this->n_ - 1) { |
---|
| 119 | right = this->n_; |
---|
| 120 | break; |
---|
| 121 | } |
---|
| 122 | } |
---|
| 123 | } |
---|
| 124 | else { |
---|
| 125 | // backward hunt |
---|
| 126 | if (left == 0) |
---|
| 127 | return; |
---|
| 128 | right = left; |
---|
| 129 | left -= inc; |
---|
| 130 | while (x >= this->x_[left]) { |
---|
| 131 | right = left; |
---|
| 132 | inc *= 2; |
---|
| 133 | if (inc >= right) { |
---|
| 134 | left = 0; |
---|
| 135 | break; |
---|
| 136 | } |
---|
| 137 | left = right - inc; |
---|
| 138 | } |
---|
| 139 | } |
---|
| 140 | } |
---|
| 141 | } |
---|
| 142 | } |
---|