| 1 | // |
|---|
| 2 | // C++ Interface: Locator |
|---|
| 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 | #ifndef ASAP_LOCATOR_H |
|---|
| 13 | #define ASAP_LOCATOR_H |
|---|
| 14 | |
|---|
| 15 | namespace asap { |
|---|
| 16 | |
|---|
| 17 | /** |
|---|
| 18 | * Base class for locate operation |
|---|
| 19 | * @author TakeshiNakazato |
|---|
| 20 | */ |
|---|
| 21 | template <class T> class Locator { |
|---|
| 22 | public: |
|---|
| 23 | // Default constructor. |
|---|
| 24 | Locator(); |
|---|
| 25 | |
|---|
| 26 | // Construct with data. |
|---|
| 27 | // @param[in] v pointer to input data. |
|---|
| 28 | // @param[in] n length of the data. |
|---|
| 29 | // @param[in] copystorage whether allocate internal memory or not. |
|---|
| 30 | // @see set() |
|---|
| 31 | Locator(T *v, unsigned int n, bool copystorage=true); |
|---|
| 32 | |
|---|
| 33 | // Set data. The data must be sorted in either ascending or descending |
|---|
| 34 | // order, and must not have any duplicate elements. |
|---|
| 35 | // @param[in] v pointer to input data. |
|---|
| 36 | // @param[in] n length of the data. |
|---|
| 37 | // @param[in] copystorage whether allocate internal memory or not. |
|---|
| 38 | // |
|---|
| 39 | // Setting copystorage=false is bit faster since it directly points |
|---|
| 40 | // to the input array instead to allocate memory and copy input array. |
|---|
| 41 | // However, you have to be careful to set copystorage to false since |
|---|
| 42 | // it will take a risk to allow to edit the data to be searched from |
|---|
| 43 | // outside the class. |
|---|
| 44 | void set(T *v, unsigned int n, bool copystorage=true); |
|---|
| 45 | |
|---|
| 46 | // Destructor. |
|---|
| 47 | virtual ~Locator(); |
|---|
| 48 | |
|---|
| 49 | // Return right hand side index of location. |
|---|
| 50 | // @param[in] x input value to be located. |
|---|
| 51 | // @return location as an index j. |
|---|
| 52 | // |
|---|
| 53 | // Returned index j satisfies x_[j-1] < x <= x_[j] for ascending |
|---|
| 54 | // case while x_[j-1] > x >= x_[j] for descending case. |
|---|
| 55 | // Returned value 0 or x.nelements() indicates out of range. |
|---|
| 56 | virtual unsigned int locate(T x) = 0; |
|---|
| 57 | |
|---|
| 58 | protected: |
|---|
| 59 | // Bisection search. |
|---|
| 60 | // @param[in] x input value to be located. |
|---|
| 61 | // @param[in] left the leftmost index to search. |
|---|
| 62 | // @param[in] right the rightmost index to search. |
|---|
| 63 | unsigned int bisection(T x, unsigned int left, unsigned int right); |
|---|
| 64 | |
|---|
| 65 | // Pointer to the data. |
|---|
| 66 | T *x_; |
|---|
| 67 | |
|---|
| 68 | // Length of the data. |
|---|
| 69 | unsigned int n_; |
|---|
| 70 | |
|---|
| 71 | // Is data ascending or descending? |
|---|
| 72 | bool ascending_; |
|---|
| 73 | |
|---|
| 74 | // Is internal storage allocated? |
|---|
| 75 | bool copy_; |
|---|
| 76 | }; |
|---|
| 77 | |
|---|
| 78 | } |
|---|
| 79 | |
|---|
| 80 | #include "Locator.tcc" |
|---|
| 81 | |
|---|
| 82 | #endif |
|---|
