#ifndef AG_HEAP_SORT_H
#define AG_HEAP_SORT_H

/*
 * The AGCLIB1 Class Library, Version 1.0
 * Copyright (c) Parsifal Software, 2001. All Rights Reserved.
 * http://www.parsifalsoft.com
*/

#include "agarray.h"
#include "agcntnr.h"

template <class Container>
AgArray<int> agSort(const Container &c, int ascending) {
  if (ascending) ascending = 1;
  int n = c.size();
  AgArray<int> permutationArray(n);        // create return array
  int *perm = (int *)permutationArray;     // For efficient access
  int i;
  // Loop to create heap
  for (i = 0; i < n; i++) {
    int j = i;
    int k = j/2;
    while (j && (c[perm[k]] < c[i]) == ascending) {
      perm[j] = perm[k];
      j = k;
      k = j/2;
    }
    perm[j] = i;
  }
  // Extract maximum value, move to end of array, readjust heap
  while (n--) {
    int x = perm[n];
    perm[n] = perm[0];
    int j = 0;
    int k = 1;
    while (1) {
      if (k+1 < n && (c[perm[k]] < c[perm[k+1]]) == ascending) k++;
      if (k >= n || (c[perm[k]] < c[x]) == ascending) break;
      perm[j] = perm[k];
      j = k;
      k = 2*j;
    }
    perm[j] = x;
  }
  return permutationArray;
}

template <class Container>
AgArray<int> agSort(const Container &c) {
  return agSort(c, 1);
}

template <class Container, class Object>
AgArray<int> agSort(const Container &c, int (*compare)(const Object &, const Object &), int ascending) {
  if (ascending) ascending = 1;
  int n = c.size();
  AgArray<int> permutationArray(n);        // create return array
  int *perm = (int *)permutationArray;     // For efficient access
  int i;
  // Loop to create heap
  for (i = 0; i < n; i++) {
    int j = i;
    int k = j/2;
    while (j && (compare(c[perm[k]],c[i]) < 0) == ascending) {
      perm[j] = perm[k];
      j = k;
      k = j/2;
    }
    perm[j] = i;
  }
  // Extract maximum value, move to end of array, readjust heap
  while (n--) {
    int x = perm[n];
    perm[n] = perm[0];
    int j = 0;
    int k = 1;
    while (1) {
      if (k+1 < n && (compare(c[perm[k]], c[perm[k+1]]) < 0) == ascending) k++;
      if (k >= n || (compare(c[perm[k]], c[x]) < 0) == ascending) break;
      perm[j] = perm[k];
      j = k;
      k = 2*j;
    }
    perm[j] = x;
  }
  return permutationArray;
}

template <class Container, class Object>
AgArray<int> agSort(const Container &c, int (*compare)(const Object &, const Object &)) {
  return agSort(c, compare, 1);
}

template <class Object>
struct AgSortCompare {
  virtual int operator () (const Object &, const Object &) const = 0;
};

template <class Container, class Object>
AgArray<int> agSort(const Container &c, const AgSortCompare<Object> &compare, int ascending) {
  if (ascending) ascending = 1;
  int n = c.size();
  AgArray<int> permutationArray(n);        // create return array
  int *perm = (int *)permutationArray;     // For efficient access
  int i;
  // Loop to create heap
  for (i = 0; i < n; i++) {
    int j = i;
    int k = j/2;
    while (j && (compare(c[perm[k]],c[i]) < 0) == ascending) {
      perm[j] = perm[k];
      j = k;
      k = j/2;
    }
    perm[j] = i;
  }
  // Extract maximum value, move to end of array, readjust heap
  while (n--) {
    int x = perm[n];
    perm[n] = perm[0];
    int j = 0;
    int k = 1;
    while (1) {
      if (k+1 < n && (compare(c[perm[k]], c[perm[k+1]]) < 0) == ascending) k++;
      if (k >= n || (compare(c[perm[k]], c[x]) < 0) == ascending) break;
      perm[j] = perm[k];
      j = k;
      k = 2*j;
    }
    perm[j] = x;
  }
  return permutationArray;
}

template <class Container, class Object>
AgArray<int> agSort(const Container &c, const AgSortCompare<Object> &compare) {
  return agSort(c, compare, 1);
}

template <class Container, class Object, class SortKey>
AgArray<int> agSort(const Container &c, const SortKey &(Object::*sortKey)() const, int ascending) {
  if (ascending) ascending = 1;
  int n = c.size();
  AgArray<int> permutationArray(n);        // create return array
  int *perm = (int *)permutationArray;     // For efficient access
  int i;
  // Loop to create heap
  for (i = 0; i < n; i++) {
    int j = i;
    int k = j/2;
    while (j && ((c[perm[k]].*sortKey)() < (c[i].*sortKey)()) == ascending) {
      perm[j] = perm[k];
      j = k;
      k = j/2;
    }
    perm[j] = i;
  }
  // Extract maximum value, move to end of array, readjust heap
  while (n--) {
    int x = perm[n];
    perm[n] = perm[0];
    int j = 0;
    int k = 1;
    while (1) {
      if (k+1 < n && (((c[perm[k]].*sortKey)() < (c[perm[k+1]].*sortKey)()) == ascending)) k++;
      if (k >= n || ((c[perm[k]].*sortKey)() < (c[x].*sortKey)()) == ascending) break;
      perm[j] = perm[k];
      j = k;
      k = 2*j;
    }
    perm[j] = x;
  }
  return permutationArray;
}

template <class Container, class Object, class SortKey>
AgArray<int> agSort(const Container &c, const SortKey &(Object::*sortKey)() const) {
  return agSort(c, sortKey, 1);
}

#endif