include/basix/list_sort.hpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : list_sort.hpp
* DESCRIPTION: Merge sort for linked lists
* COPYRIGHT  : (C) 2004  Joris van der Hoeven
*******************************************************************************
* This software falls under the GNU general public license and comes WITHOUT
* ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
* If you don't have this file, write to the Free Software Foundation, Inc.,
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
******************************************************************************/

#ifndef __MMX_SORT_LIST_HPP
#define __MMX_SORT_LIST_HPP
#include <basix/list.hpp>


namespace mmx {
#define TMPL template<typename C>
#define List list<C>

TMPL void
split (const List& l, nat n, List& head, List& tail) {
  if (n == 0) {
    head= List ();
    tail= l;
  }
  else {
    split (cdr (l), n-1, head, tail);
    head= cons (car (l), head);
  }
}

TMPL List
merge (const List& head, const List& tail, int (*cmp) (const C&, const C&)) {
  if (is_nil (head)) return tail;
  if (is_nil (tail)) return head;
  if (cmp (car (head), car (tail)) <= 0)
    return cons (car (head), merge (cdr (head), tail, cmp));
  return cons (car (tail), merge (head, cdr (tail), cmp));
}

TMPL List
sort (const List& l, int (*cmp) (const C&, const C&)) {
  nat n= N(l);
  if (n <= 1) return l;
  List head, tail;
  split (l, n>>1, head, tail);
  head= sort (head, cmp);
  tail= sort (tail, cmp);
  return merge (head, tail, cmp);
}

#undef TMPL
#undef List
} // namespace mmx
#endif // __MMX_LIST_HPP

---