diff options
Diffstat (limited to 'core/sort.h')
| -rw-r--r-- | core/sort.h | 197 |
1 files changed, 90 insertions, 107 deletions
diff --git a/core/sort.h b/core/sort.h index fd3b57251a..8ec1cc6bd1 100644 --- a/core/sort.h +++ b/core/sort.h @@ -34,26 +34,24 @@ @author ,,, <red@lunatea> */ -template<class T> +template <class T> struct _DefaultComparator { - inline bool operator()(const T&a,const T&b) const { return (a<b); } + inline bool operator()(const T &a, const T &b) const { return (a < b); } }; -template<class T, class Comparator=_DefaultComparator<T> > +template <class T, class Comparator = _DefaultComparator<T> > class SortArray { enum { - INTROSORT_TRESHOLD=16 + INTROSORT_TRESHOLD = 16 }; public: - Comparator compare; - - inline const T& median_of_3(const T& a, const T& b, const T& c) const { + inline const T &median_of_3(const T &a, const T &b, const T &c) const { if (compare(a, b)) if (compare(b, c)) @@ -70,8 +68,6 @@ public: return b; } - - inline int bitlog(int n) const { int k; for (k = 0; n != 1; n >>= 1) @@ -79,10 +75,9 @@ public: return k; } - /* Heap / Heapsort functions */ - inline void push_heap(int p_first,int p_hole_idx,int p_top_index,T p_value,T* p_array) const { + inline void push_heap(int p_first, int p_hole_idx, int p_top_index, T p_value, T *p_array) const { int parent = (p_hole_idx - 1) / 2; while (p_hole_idx > p_top_index && compare(p_array[p_first + parent], p_value)) { @@ -94,25 +89,24 @@ public: p_array[p_first + p_hole_idx] = p_value; } - inline void pop_heap(int p_first, int p_last, int p_result, T p_value, T* p_array) const { + inline void pop_heap(int p_first, int p_last, int p_result, T p_value, T *p_array) const { - p_array[p_result]=p_array[p_first]; - adjust_heap(p_first,0,p_last-p_first,p_value,p_array); + p_array[p_result] = p_array[p_first]; + adjust_heap(p_first, 0, p_last - p_first, p_value, p_array); } - inline void pop_heap(int p_first,int p_last,T* p_array) const { + inline void pop_heap(int p_first, int p_last, T *p_array) const { - pop_heap(p_first,p_last-1,p_last-1,p_array[p_last-1],p_array); + pop_heap(p_first, p_last - 1, p_last - 1, p_array[p_last - 1], p_array); } - inline void adjust_heap(int p_first,int p_hole_idx,int p_len,T p_value,T* p_array) const { - + inline void adjust_heap(int p_first, int p_hole_idx, int p_len, T p_value, T *p_array) const { int top_index = p_hole_idx; int second_child = 2 * p_hole_idx + 2; while (second_child < p_len) { - if (compare(p_array[p_first + second_child],p_array[p_first + (second_child - 1)])) + if (compare(p_array[p_first + second_child], p_array[p_first + (second_child - 1)])) second_child--; p_array[p_first + p_hole_idx] = p_array[p_first + second_child]; @@ -124,22 +118,22 @@ public: p_array[p_first + p_hole_idx] = p_array[p_first + (second_child - 1)]; p_hole_idx = second_child - 1; } - push_heap(p_first, p_hole_idx, top_index, p_value,p_array); + push_heap(p_first, p_hole_idx, top_index, p_value, p_array); } - inline void sort_heap(int p_first,int p_last,T* p_array) const { + inline void sort_heap(int p_first, int p_last, T *p_array) const { - while(p_last-p_first > 1) { + while (p_last - p_first > 1) { - pop_heap(p_first,p_last--,p_array); + pop_heap(p_first, p_last--, p_array); } } - inline void make_heap(int p_first, int p_last,T* p_array) const { + inline void make_heap(int p_first, int p_last, T *p_array) const { if (p_last - p_first < 2) return; int len = p_last - p_first; - int parent = (len - 2)/2; + int parent = (len - 2) / 2; while (true) { adjust_heap(p_first, parent, len, p_array[p_first + parent], p_array); @@ -149,174 +143,163 @@ public: } } - inline void partial_sort(int p_first,int p_last,int p_middle,T* p_array) const { + inline void partial_sort(int p_first, int p_last, int p_middle, T *p_array) const { - make_heap(p_first,p_middle,p_array); - for(int i=p_middle;i<p_last;i++) - if (compare( p_array[i],p_array[p_first])) - pop_heap(p_first,p_middle,i,p_array[i],p_array); - sort_heap(p_first,p_middle,p_array); + make_heap(p_first, p_middle, p_array); + for (int i = p_middle; i < p_last; i++) + if (compare(p_array[i], p_array[p_first])) + pop_heap(p_first, p_middle, i, p_array[i], p_array); + sort_heap(p_first, p_middle, p_array); } - inline void partial_select(int p_first,int p_last,int p_middle,T* p_array) const { + inline void partial_select(int p_first, int p_last, int p_middle, T *p_array) const { - make_heap(p_first,p_middle,p_array); - for(int i=p_middle;i<p_last;i++) - if (compare( p_array[i],p_array[p_first])) - pop_heap(p_first,p_middle,i,p_array[i],p_array); + make_heap(p_first, p_middle, p_array); + for (int i = p_middle; i < p_last; i++) + if (compare(p_array[i], p_array[p_first])) + pop_heap(p_first, p_middle, i, p_array[i], p_array); } - inline int partitioner(int p_first, int p_last, T p_pivot, T* p_array) const { + inline int partitioner(int p_first, int p_last, T p_pivot, T *p_array) const { while (true) { - while (compare(p_array[p_first],p_pivot)) + while (compare(p_array[p_first], p_pivot)) p_first++; p_last--; - while (compare(p_pivot,p_array[p_last])) + while (compare(p_pivot, p_array[p_last])) p_last--; if (!(p_first < p_last)) return p_first; - SWAP(p_array[p_first],p_array[p_last]); + SWAP(p_array[p_first], p_array[p_last]); p_first++; } } - inline void introsort(int p_first, int p_last, T* p_array, int p_max_depth) const { + inline void introsort(int p_first, int p_last, T *p_array, int p_max_depth) const { - while( p_last - p_first > INTROSORT_TRESHOLD ) { + while (p_last - p_first > INTROSORT_TRESHOLD) { if (p_max_depth == 0) { - partial_sort(p_first,p_last,p_last,p_array); + partial_sort(p_first, p_last, p_last, p_array); return; } p_max_depth--; int cut = partitioner( - p_first, - p_last, - median_of_3( - p_array[p_first], - p_array[p_first + (p_last-p_first)/2], - p_array[p_last-1] - ), - p_array - ); - - introsort(cut,p_last,p_array,p_max_depth); - p_last=cut; - + p_first, + p_last, + median_of_3( + p_array[p_first], + p_array[p_first + (p_last - p_first) / 2], + p_array[p_last - 1]), + p_array); + + introsort(cut, p_last, p_array, p_max_depth); + p_last = cut; } - } + } - inline void introselect(int p_first, int p_nth, int p_last, T* p_array, int p_max_depth) const { + inline void introselect(int p_first, int p_nth, int p_last, T *p_array, int p_max_depth) const { - while( p_last - p_first > 3 ) { + while (p_last - p_first > 3) { if (p_max_depth == 0) { - partial_select(p_first,p_nth+1,p_last,p_array); - SWAP(p_first,p_nth); + partial_select(p_first, p_nth + 1, p_last, p_array); + SWAP(p_first, p_nth); return; } p_max_depth--; int cut = partitioner( - p_first, - p_last, - median_of_3( - p_array[p_first], - p_array[p_first + (p_last-p_first)/2], - p_array[p_last-1] - ), - p_array - ); - - if (cut<=p_nth) - p_first=cut; + p_first, + p_last, + median_of_3( + p_array[p_first], + p_array[p_first + (p_last - p_first) / 2], + p_array[p_last - 1]), + p_array); + + if (cut <= p_nth) + p_first = cut; else - p_last=cut; - + p_last = cut; } - insertion_sort(p_first,p_last,p_array); + insertion_sort(p_first, p_last, p_array); } - inline void unguarded_linear_insert(int p_last,T p_value,T* p_array) const { + inline void unguarded_linear_insert(int p_last, T p_value, T *p_array) const { - int next = p_last-1; - while (compare(p_value,p_array[next])) { - p_array[p_last]=p_array[next]; + int next = p_last - 1; + while (compare(p_value, p_array[next])) { + p_array[p_last] = p_array[next]; p_last = next; next--; } p_array[p_last] = p_value; } - inline void linear_insert(int p_first,int p_last,T*p_array) const { + inline void linear_insert(int p_first, int p_last, T *p_array) const { T val = p_array[p_last]; if (compare(val, p_array[p_first])) { - for (int i=p_last; i>p_first; i--) - p_array[i]=p_array[i-1]; + for (int i = p_last; i > p_first; i--) + p_array[i] = p_array[i - 1]; p_array[p_first] = val; } else unguarded_linear_insert(p_last, val, p_array); } - inline void insertion_sort(int p_first,int p_last,T* p_array) const { + inline void insertion_sort(int p_first, int p_last, T *p_array) const { - if (p_first==p_last) + if (p_first == p_last) return; - for (int i=p_first+1; i!=p_last ; i++) - linear_insert(p_first,i,p_array); + for (int i = p_first + 1; i != p_last; i++) + linear_insert(p_first, i, p_array); } - inline void unguarded_insertion_sort(int p_first,int p_last,T* p_array) const { + inline void unguarded_insertion_sort(int p_first, int p_last, T *p_array) const { - for (int i=p_first; i!=p_last ; i++) - unguarded_linear_insert(i,p_array[i],p_array); + for (int i = p_first; i != p_last; i++) + unguarded_linear_insert(i, p_array[i], p_array); } - inline void final_insertion_sort(int p_first,int p_last,T* p_array) const { + inline void final_insertion_sort(int p_first, int p_last, T *p_array) const { if (p_last - p_first > INTROSORT_TRESHOLD) { - insertion_sort(p_first,p_first+INTROSORT_TRESHOLD,p_array); - unguarded_insertion_sort(p_first+INTROSORT_TRESHOLD,p_last,p_array); + insertion_sort(p_first, p_first + INTROSORT_TRESHOLD, p_array); + unguarded_insertion_sort(p_first + INTROSORT_TRESHOLD, p_last, p_array); } else { - insertion_sort(p_first,p_last,p_array); - + insertion_sort(p_first, p_last, p_array); } - } + } - inline void sort_range(int p_first, int p_last,T* p_array) const { + inline void sort_range(int p_first, int p_last, T *p_array) const { if (p_first != p_last) { - introsort(p_first, p_last,p_array,bitlog(p_last - p_first) * 2); + introsort(p_first, p_last, p_array, bitlog(p_last - p_first) * 2); final_insertion_sort(p_first, p_last, p_array); } } - inline void sort(T* p_array,int p_len) const { + inline void sort(T *p_array, int p_len) const { - sort_range(0,p_len,p_array); + sort_range(0, p_len, p_array); } - inline void nth_element(int p_first,int p_last,int p_nth,T* p_array) const { + inline void nth_element(int p_first, int p_last, int p_nth, T *p_array) const { - if (p_first==p_last || p_nth==p_last) + if (p_first == p_last || p_nth == p_last) return; - introselect(p_first,p_nth,p_last,p_array,bitlog(p_last - p_first) * 2); + introselect(p_first, p_nth, p_last, p_array, bitlog(p_last - p_first) * 2); } - }; - - - #endif |