| 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
|
|---|
