#ifndef _OTB_TRISKELE_ARRAY_TREE_SORT_TPP
#define _OTB_TRISKELE_ARRAY_TREE_SORT_TPP

// ========================================
template <typename T>
inline vector<T> getRandReduce (vector<T> index, T reduceCount);

template <typename E, typename WeightT, typename DimImg, typename WeightFunct>
inline DimImg mergeSort (E *dst, const vector<E *> &tab, const vector<DimImg> &tabSize, const WeightFunct &weightFunct);

// ========================================
template <typename T>
inline vector<T> getRandReduce (vector<T> index, T reduceCount) {
  T size = index.size ();
  if (reduceCount >= size)
    return index;
  for (T i = 0; i < size; ++i) {
    T j = rand () % size;
    T tmp = index [i];
    index [i] = index [j];
    index [j] = tmp;
  }
  vector<T> result (&index [0], &index[reduceCount]);
  return result;
}

template <typename E, typename WeightT, typename DimImg, typename WeightFunct>
inline DimImg mergeSort (E *dst, const vector<E *> &tab, const vector<DimImg> &tabSize, const WeightFunct &weightFunct) {
  DimImg count = 0;
  vector<DimImg> curIdx (tab.size (), 0);
  for (;;) {
    int minIdx = -1;
    WeightT minLevel = 0;
    for (DimImg i = 0; i < curIdx.size (); ++i) {
      if (curIdx[i] >= tabSize[i])
	continue;
      if (minIdx >= 0 &&
	  !weightFunct.isWeightInf (tab[i][curIdx[i]], minLevel))
	continue;
      minIdx = i;
      minLevel = tab[i][curIdx[i]];
      // LOG ("set minIdx:" << minIdx << " minLevel:" << minLevel);
    }
    if (minIdx < 0)
      break;
    *dst++ = tab[minIdx][curIdx[minIdx]++];
    ++count;
  }
  return count;
}

#endif // _OTB_TRISKELE_ARRAY_TREE_SORT_TPP