foobar2000 SDK  2015-08-03
sort.h
Go to the documentation of this file.
1 namespace pfc {
2 
3  void swap_void(void * item1,void * item2,t_size width);
4 
5  void reorder_void(void * data,t_size width,const t_size * order,t_size num,void (*swapfunc)(void * item1,void * item2,t_size width) = swap_void);
6 
7  class NOVTABLE reorder_callback
8  {
9  public:
10  virtual void swap(t_size p_index1,t_size p_index2) = 0;
11  };
12 
13  void reorder(reorder_callback & p_callback,const t_size * p_order,t_size p_count);
14 
15  template<typename t_container>
17  {
18  public:
19  reorder_callback_impl_t(t_container & p_data) : m_data(p_data) {}
20  void swap(t_size p_index1,t_size p_index2)
21  {
22  pfc::swap_t(m_data[p_index1],m_data[p_index2]);
23  }
24  private:
25  t_container & m_data;
26  };
27 
29  {
30  public:
31  reorder_callback_impl_delta(reorder_callback & p_data,t_size p_delta) : m_data(p_data), m_delta(p_delta) {}
32  void swap(t_size p_index1,t_size p_index2)
33  {
34  m_data.swap(p_index1+m_delta,p_index2+m_delta);
35  }
36  private:
39  };
40 
41  template<typename t_container>
42  void reorder_t(t_container & p_data,const t_size * p_order,t_size p_count)
43  {
45  reorder(cb,p_order,p_count);
46  }
47 
48  template<typename t_container>
49  void reorder_partial_t(t_container & p_data,t_size p_base,const t_size * p_order,t_size p_count)
50  {
52  reorder_callback_impl_delta cb2( cb1, p_base );
53  reorder(cb2,p_order,p_count);
54 // reorder(reorder_callback_impl_delta(reorder_callback_impl_t<t_container>(p_data),p_base),p_order,p_count);
55  }
56 
57  template<typename T>
59  {
60  public:
61  reorder_callback_impl_ptr_t(T * p_data) : m_data(p_data) {}
62  void swap(t_size p_index1,t_size p_index2)
63  {
64  pfc::swap_t(m_data[p_index1],m_data[p_index2]);
65  }
66  private:
68  };
69 
70 
71  template<typename T>
72  void reorder_ptr_t(T* p_data,const t_size * p_order,t_size p_count)
73  {
74  reorder(reorder_callback_impl_ptr_t<T>(p_data),p_order,p_count);
75  }
76 
77 
78 
79  class NOVTABLE sort_callback
80  {
81  public:
82  virtual int compare(t_size p_index1, t_size p_index2) const = 0;
83  virtual void swap(t_size p_index1, t_size p_index2) = 0;
84  void swap_check(t_size p_index1, t_size p_index2) {if (compare(p_index1,p_index2) > 0) swap(p_index1,p_index2);}
85  };
86 
88  {
89  public:
91  virtual int compare(t_size p_index1, t_size p_index2) const;
92  virtual void swap(t_size p_index1, t_size p_index2);
93  private:
96  };
97 
98  void sort(sort_callback & p_callback,t_size p_count);
99  void sort_stable(sort_callback & p_callback,t_size p_count);
100 
101  void sort_void_ex(void *base,t_size num,t_size width, int (*comp)(const void *, const void *),void (*swap)(void *, void *, t_size) );
102  void sort_void(void * base,t_size num,t_size width,int (*comp)(const void *, const void *) );
103 
104  template<typename t_container,typename t_compare>
106  {
107  public:
108  sort_callback_impl_simple_wrap_t(t_container & p_data, t_compare p_compare) : m_data(p_data), m_compare(p_compare) {}
109  int compare(t_size p_index1, t_size p_index2) const
110  {
111  return m_compare(m_data[p_index1],m_data[p_index2]);
112  }
113 
114  void swap(t_size p_index1, t_size p_index2)
115  {
116  swap_t(m_data[p_index1],m_data[p_index2]);
117  }
118  private:
119  t_container & m_data;
120  t_compare m_compare;
121  };
122 
123  template<typename t_container>
125  {
126  public:
127  sort_callback_impl_auto_wrap_t(t_container & p_data) : m_data(p_data) {}
128  int compare(t_size p_index1, t_size p_index2) const
129  {
130  return compare_t(m_data[p_index1],m_data[p_index2]);
131  }
132 
133  void swap(t_size p_index1, t_size p_index2)
134  {
135  swap_t(m_data[p_index1],m_data[p_index2]);
136  }
137  private:
138  t_container & m_data;
139  };
140 
141  template<typename t_container,typename t_compare,typename t_permutation>
143  {
144  public:
145  sort_callback_impl_permutation_wrap_t(const t_container & p_data, t_compare p_compare,t_permutation const & p_permutation) : m_data(p_data), m_compare(p_compare), m_permutation(p_permutation) {}
146  int compare(t_size p_index1, t_size p_index2) const
147  {
148  return m_compare(m_data[m_permutation[p_index1]],m_data[m_permutation[p_index2]]);
149  }
150 
151  void swap(t_size p_index1, t_size p_index2)
152  {
153  swap_t(m_permutation[p_index1],m_permutation[p_index2]);
154  }
155  private:
156  const t_container & m_data;
157  t_compare m_compare;
158  t_permutation const & m_permutation;
159  };
160 
161  template<typename t_container,typename t_compare>
162  static void sort_t(t_container & p_data,t_compare p_compare,t_size p_count)
163  {
165  sort(cb,p_count);
166  }
167 
168  template<typename t_container,typename t_compare>
169  static void sort_stable_t(t_container & p_data,t_compare p_compare,t_size p_count)
170  {
172  sort_stable(cb,p_count);
173  }
174 
175  template<typename t_container,typename t_compare,typename t_permutation>
176  static void sort_get_permutation_t(const t_container & p_data,t_compare p_compare,t_size p_count,t_permutation const & p_permutation)
177  {
179  sort(cb,p_count);
180  }
181 
182  template<typename t_container,typename t_compare,typename t_permutation>
183  static void sort_stable_get_permutation_t(const t_container & p_data,t_compare p_compare,t_size p_count,t_permutation const & p_permutation)
184  {
186  sort_stable(cb,p_count);
187  }
188 
189 }
int compare(t_size p_index1, t_size p_index2) const
Definition: sort.h:109
reorder_callback_impl_t(t_container &p_data)
Definition: sort.h:19
static void sort_get_permutation_t(const t_container &p_data, t_compare p_compare, t_size p_count, t_permutation const &p_permutation)
Definition: sort.h:176
void sort(pfc::sort_callback &p_callback, t_size p_num)
Definition: sort.cpp:225
void reorder(reorder_callback &p_callback, const t_size *p_order, t_size p_count)
Definition: sort.cpp:25
void swap(t_size p_index1, t_size p_index2)
Definition: sort.h:62
void swap(t_size p_index1, t_size p_index2)
Definition: sort.h:151
reorder_callback & m_data
Definition: sort.h:37
void reorder_ptr_t(T *p_data, const t_size *p_order, t_size p_count)
Definition: sort.h:72
int compare(t1 const &p1, t2 const &p2)
Definition: pathUtils.h:29
t_container & m_data
Definition: sort.h:25
int compare(t_size p_index1, t_size p_index2) const
Definition: sort.h:128
int compare(t_size p_index1, t_size p_index2) const
Definition: sort.h:146
sort_callback_impl_simple_wrap_t(t_container &p_data, t_compare p_compare)
Definition: sort.h:108
sort_callback_impl_permutation_wrap_t(const t_container &p_data, t_compare p_compare, t_permutation const &p_permutation)
Definition: sort.h:145
void reorder_partial_t(t_container &p_data, t_size p_base, const t_size *p_order, t_size p_count)
Definition: sort.h:49
void sort_stable(sort_callback &p_callback, t_size p_count)
Definition: sort.cpp:261
void reorder_t(t_container &p_data, const t_size *p_order, t_size p_count)
Definition: sort.h:42
void swap(t_size p_index1, t_size p_index2)
Definition: sort.h:20
reorder_callback_impl_delta(reorder_callback &p_data, t_size p_delta)
Definition: sort.h:31
sort_callback_impl_auto_wrap_t(t_container &p_data)
Definition: sort.h:127
t_permutation const & m_permutation
Definition: sort.h:158
void swap_check(t_size p_index1, t_size p_index2)
Definition: sort.h:84
size_t t_size
Definition: int_types.h:48
reorder_callback_impl_ptr_t(T *p_data)
Definition: sort.h:61
sort_callback & m_chain
Definition: sort.h:94
static void sort_stable_get_permutation_t(const t_container &p_data, t_compare p_compare, t_size p_count, t_permutation const &p_permutation)
Definition: sort.h:183
int compare_t(const hasher_md5_result &p_item1, const hasher_md5_result &p_item2)
Definition: hasher_md5.h:20
void swap(t_size p_index1, t_size p_index2)
Definition: sort.h:32
void swap(t_size p_index1, t_size p_index2)
Definition: sort.h:133
void swap(t_size p_index1, t_size p_index2)
Definition: sort.h:114
static void sort_t(t_container &p_data, t_compare p_compare, t_size p_count)
Definition: sort.h:162
void swap_void(void *item1, void *item2, t_size width)
Definition: sort.cpp:10
void reorder_void(void *data, t_size width, const t_size *order, t_size num, void(*swapfunc)(void *item1, void *item2, t_size width))
Definition: sort.cpp:53
void swap_t(T &p_item1, T &p_item2)
Definition: primitives.h:285
array_t< t_size > m_order
Definition: sort.h:95
static void sort_stable_t(t_container &p_data, t_compare p_compare, t_size p_count)
Definition: sort.h:169
void sort_void(void *base, t_size num, t_size width, int(*comp)(const void *, const void *))
Definition: sort.cpp:231
void sort_void_ex(void *base, t_size num, t_size width, int(*comp)(const void *, const void *), void(*swap)(void *, void *, t_size))
Definition: sort.cpp:116