#include <assert.h> #include <stdlib.h> #include "fibnacci.h" namespace JTL // Jack's template library { template <typename T> void Vector<T>::copy_from(T const* A, Rank lo, Rank hi) { _elem = new T[_capacity = 2 * (hi - lo)]; _size = 0; while (lo < hi) { _elem[_size++] = A[lo++]; } } template <typename T> void Vector<T>::expand() { if (_size < _capacity) { return; } if (_capacity < DEFAULT_CAPACITY) { _capacity = DEFAULT_CAPACITY; } T* old_elem = _elem; _elem = new T[_capacity <<= 1]; for (int i = 0; i < _size; i++) { _elem[i] = old_elem[i]; } delete[] old_elem; } template <typename T> int Vector<T>::disordered() const { int n = 0; for (int i = 1; i < _size; i++) { if (_elem[i - 1] > _elem[i]) { n++; } } return n; } template <typename T> Rank Vector<T>::find(T const& e, Rank lo, Rank hi) const { assert(0 <= lo); assert(lo < hi); assert(hi <= _size); while ((lo < hi--) && (e != _elem[hi])) {} return hi; } template <typename T> Rank Vector<T>::search(T const& e, Rank lo, Rank hi) const { assert(0 <= lo); assert(lo < hi); assert(hi <= _size); //return (rand() % 2) ? // binary_search(_elem, e, lo, hi) : fibnacci_search(_elem, e, lo, hi); return fibnacci_search(_elem, e, lo, hi); } template <typename T> Rank Vector<T>::binary_search(T* A, T const& e, Rank lo, Rank hi) { assert(0 <= lo); assert(lo <= hi); //assert(hi <= _size); #define USE_VERSION_3 // version 1 #ifdef USE_VERSION_1 while (lo < hi) { // ÿ����������Ҫ�����αȽ��жϣ���������֧ Rank mi = (lo + hi) >> 1; if (e < A[mi]) { hi = mi; } else if (A[i] < e) { lo = mi + 1; } else { return mi; } } return -1; // �ж������Ԫ��ʱ�����ܱ�֤����������ߣ� // ����ʧ��ʱ���ط���-1��������ֻ��ʧ�ܵ�λ�� #endif // version 2 #ifdef USE_VERSION_2 while (1 < hi - lo) { // ÿ����������һ�αȽ� Rank mi = (lo + hi) >> 1; (e < A[mi]) ? hi = mi : lo = mi; }// ����ʱhi = lo + 1�������������һ��Ԫ��A[lo] return (e == A[lo]) ? lo : -1; // ���ҳɹ�ʱ���ض�Ӧ���ȣ�����ͳһ����-1 // �ж������Ԫ��ʱ�����ܱ�֤����������ߣ� // ����ʧ��ʱ���ط���-1��������ֻ��ʧ�ܵ�λ�� #endif // version 3 #ifdef USE_VERSION_3 while (lo < hi) { // ÿ����������һ�αȽ� Rank mi = (lo + hi) >> 1; (e < A[mi]) ? hi = mi : lo = mi + 1; }// �ɹ����Ҳ�����ǰ��ֹ return --lo;//ѭ������ʱ��loΪ����e��Ԫ�ص���С�ȣ���lo-1��������e��Ԫ�ص������ // �ж������Ԫ��ʱ�����ܱ�֤����������� // ����ʧ��ʱ���ܹ�����ʧ�ܵ�λ�� #endif } template <typename T> Rank Vector<T>::fibnacci_search(T* A, T const& e, Rank lo, Rank hi) { assert(0 <= lo); assert(lo <= hi); //assert(hi <= A->_size); #define USE_VERSION_2 #ifdef USE_VERSION_1 Fibnacci fib(hi - lo); while (lo < hi) { while (hi - lo < fib.get()) { fib.prev(); } Rank mi = lo + fib.get() - 1; if (e < A[mi]) { hi = mi; } else if (A[mi] < e) { lo = mi + 1; } else { return mi; } } return -1; // �ж��Ԫ������ʱ�����ܱ�֤����������� // ����ʧ��ʱ���ط���-1��������ֻ��ʧ�ܵ�λ�� #endif #ifdef USE_VERSION_2 Fibnacci fib(hi - lo); while (lo < hi) { while (hi - lo < fib.get()) { fib.prev(); } Rank mi = lo + fib.get() - 1; (e < A[mi]) ? hi = mi : lo = mi + 1; }// �ɹ����Ҳ�����ǰ��ֹ return --lo;//ѭ������ʱ��loΪ����e��Ԫ�ص���С�ȣ���lo-1��������e��Ԫ�ص������ // �ж������Ԫ��ʱ�����ܱ�֤����������� // ����ʧ��ʱ���ܹ�����ʧ�ܵ�λ�� #endif } template <typename T> Rank Vector<T>::interpolation_search(T* A, T const& e, Rank lo, Rank hi) { assert(0 <= lo); assert(lo <= hi); assert(hi <= A->_size); while (A[lo] <= e && e <= A[hi]) { Rank mi = lo + (hi - lo) * (e - A[lo]) / (A[hi] - A[lo]); if (A[mi] < e) { lo = mi + 1; } else if (e < A[mi]) { hi = mi - 1; } else { return mi; } } if (A[lo] == e) { return lo; } else { return -1; } } template <typename T> void Vector<T>::shrink() { if (_capacity < DEFAULT_CAPACITY << 1) { return; } if (_size << 2 > _capacity) { return; } T* old_elem = _elem; _elem = new T[_capacity >= 1]; for (int i = 0; i < _size; i++) { _elem[i] = old_elem[i]; } delete[] old_elem; } template <typename T> bool Vector<T>::bubble(Rank lo, Rank hi) { bool sorted = true; while (++lo < hi) { if (_elem[lo - 1] > _elem[lo]) { sorted = false; swap(_elem[lo - 1], _elem[lo]); } } return sorted; } template <typename T> void Vector<T>::bubble_sort(Rank lo, Rank hi) { assert(0 <= lo); assert(lo < hi); assert(hi <= _size); while (!bubble(lo, hi--)) {} } template <typename T> Rank Vector<T>::bubble_fast(Rank lo, Rank hi) { Rank last = lo; while (++lo < hi) { if (_elem[lo - 1] > _elem[lo]) { last = lo; swap(_elem[lo - 1], _elem[lo]); } } return last; } template <typename T> void Vector<T>::bubble_sort_fast(Rank lo, Rank hi) { assert(0 <= lo); assert(lo < hi); assert(hi <= _size); while (lo < (hi = bubble_fast(lo, hi))) {} } template <typename T> void Vector<T>::merge(Rank lo, Rank mi, Rank hi) { T* A = _elem + lo; int lb = mi - lo; T* B = new T[lb]; // [lo, mi) for (int i = 0; i < lb; i++) { B[i] = A[i]; } T* C = _elem + mi; // [mi, hi) int lc = hi - mi; for (int i = 0, j = 0, k = 0; (j < lb) || (k < lc);) { if ((j < lb) && (!(k < lc) || B[j] <= C[k])) { A[i++] = B[j++]; } if ((k < lc) && (!(j < lb) || C[k] < B[j])) { A[i++] = C[k++]; } } delete[] B; } template <typename T> void Vector<T>::merge_sort(Rank lo, Rank hi) { assert(0 <= lo); assert(lo < hi); assert(hi <= _size); if (hi - lo < 2) return; Rank mi = (hi + lo) >> 1; merge_sort(lo, mi); merge_sort(mi, hi); merge(lo, mi, hi); } template <typename T> T& Vector<T>::operator[] (Rank r) const { assert(r >= 0 && r < _size); return _elem[r]; } template <typename T> Vector<T>& Vector<T>::operator= (Vector<T> const& V) { if (_elem) { delete[] _elem; } copy_from(V._elem, 0, V._size); return *this; } template <typename T> int Vector<T>::remove(Rank lo, Rank hi) { assert(lo >= 0 && lo <= hi && hi <= _size); if (lo == hi) { return 0; } while (hi < _size) { _elem[lo++] = _elem[hi++]; } _size = lo; shrink(); return hi - lo; } template <typename T> T Vector<T>::remove(Rank r) { assert(r >= 0 && r < _size); T e = _elem[r]; remove(r, r + 1); return e; } template <typename T> Rank Vector<T>::insert(Rank r, T const& e) { assert(r >= 0 && r <= _size); expand(); for (int i = _size; i > r; i--) { _elem[i] = _elem[i - 1]; } _elem[r] = e; _size++; return r; } template <typename T> void Vector<T>::sort(Rank lo, Rank hi) { /*switch (rand() % 2) { case 0: bubble_sort_fast(lo, hi); break; case 1: merge_sort(lo, hi); break; }*/ merge_sort(lo, hi); } template <typename T> void Vector<T>::unsort(Rank lo, Rank hi) { T* V = _elem + lo; for (Rank i = hi - lo; i > 0; i--) { swap(V[i] - 1, V[rand() % i]); } } template <typename T> int Vector<T>::deduplicate() { int old_size = _size; int i = 1; while (i < _size) { (find(_elem[i], 0, i) < 0) ? i++ : remove(i); } return old_size - _size; } template <typename T> int Vector<T>::uniquify() { Rank i = 0, j = 0; while (++j < _size) { if (_elem[i] != _elem[j]) { _elem[++i] = _elem[j]; } } _size = ++i; shrink(); return j - i; } };