source: trunk/src/HuntLocator.tcc@ 3075

Last change on this file since 3075 was 2732, checked in by Takeshi Nakazato, 12 years ago

New Development: No

JIRA Issue: Yes CAS-4770

Ready for Test: Yes

Interface Changes: Yes/No

What Interface Changed: Please list interface changes

Test Programs: List test programs

Put in Release Notes: Yes/No

Module(s): Module Names change impacts.

Description: Describe your changes here...

Commit .tcc files for Locator classes.


File size: 2.7 KB
RevLine 
[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
16namespace asap {
17
18template <class T> HuntLocator<T>::HuntLocator()
19 : Locator<T>(),
20 prev_(0)
21{}
22
23template <class T> HuntLocator<T>::HuntLocator(T *v, unsigned int n, bool copystorage)
24 : Locator<T>(v, n, copystorage),
25 prev_(0)
26{}
27
28template <class T> HuntLocator<T>::~HuntLocator()
29{}
30
31template <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
64template <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}
Note: See TracBrowser for help on using the repository browser.