#line 5915 "smat.w"
#ifndef _TILED_H_
#define _TILED_H_

#ifndef TILED_SMALL_CHUNK
#define TILED_SMALL_CHUNK 16
#endif

using namespace std;

enum { small_elem = TILED_SMALL_CHUNK };


#line 5937 "smat.w"
template <typename Iter>
static void
chunk_mergesort(Iter first, Iter last,
  typename std::iterator_traits<Iter>::pointer tmpbuf,
  typename std::iterator_traits<Iter>::difference_type chunk_elem)
{
  while (first + chunk_elem <= last)
    {
      tiled_mergesort_internal(first, first + chunk_elem, tmpbuf, small_elem);
      first += chunk_elem;
    }

  if (first < last)
    tiled_mergesort_internal(first, last, tmpbuf, small_elem);
}
#line 5926 "smat.w"


#line 5954 "smat.w"
template <typename Iter>
static void
tiled_mergesort_internal(Iter first, Iter last,
  typename std::iterator_traits<Iter>::pointer tmpbuf,
  typename std::iterator_traits<Iter>::difference_type chunk_elem)
{
  typedef typename std::iterator_traits<Iter>::difference_type _Distance;
  typedef typename std::iterator_traits<Iter>::pointer _Pointer;

  _Distance nelement = last - first;
  _Pointer tmpbuf_last = tmpbuf + nelement;
  
  if (small_elem < chunk_elem)
    chunk_mergesort(first, last, tmpbuf, chunk_elem);
  else
    __chunk_insertion_sort(first, last, chunk_elem);

  _Distance nchunk = (nelement + chunk_elem - 1) / chunk_elem;

  while (nchunk > 1)
    {
      __merge_sort_loop(first, last, tmpbuf, chunk_elem);
      chunk_elem *= 2;
      __merge_sort_loop(tmpbuf, tmpbuf_last, first, chunk_elem);
      chunk_elem *= 2;
      nchunk = (nchunk + 3) / 4;
    }
}
#line 5927 "smat.w"


#line 5984 "smat.w"
template <typename Iter>
inline bool
tiled_mergesort(Iter first, Iter last,
  typename iterator_traits<Iter>::difference_type tile_size)
{
  typedef typename iterator_traits<Iter>::value_type _Value;
  
  _Temporary_buffer<Iter, _Value> buf(first, last);
  if (buf.size() != buf.requested_size())
    return false;

  tiled_mergesort_internal(first, last, buf.begin(), tile_size / sizeof(_Value));

  return true;
}
#line 5928 "smat.w"


#endif // _TILED_H_