apps/keditbookmarks/kinsertionsort.h

   1 // -*- c-basic-offset: 4; indent-tabs-mode:nil -*-
   2 // vim: set ts=4 sts=4 sw=4 et:
   3 /* This file is part of the KDE project
   4    Copyright (C) 2000 David Faure <faure@kde.org>
   5
   6    This program is free software: you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation, either version 2 of the License, or
   9    (at your option) any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #ifndef __kinsertionsort_h
  21 #define __kinsertionsort_h
  22
  23 /**
  24  * A template-based insertion sort algorithm, but not really 100%
  25  * generic. It is mostly written for lists, not for arrays.
  26  *
  27  * A good reason to use insertion sort over faster algorithms like
  28  * heap sort or quick sort, is that it minimizes the number of
  29  * movements of the items. This is important in applications which support
  30  * undo, because the number of commands is kept to a minimum.
  31  */
  32
  33 // Item must define isNull(), previousSibling(), nextSibling()
  34 // SortHelper must define  moveAfter( const Item &, const Item & )
  35 // Criteria must define  static Key key(const Item &)
  36 template <class Item, class Criteria, class Key, class SortHelper>
  37 inline void kInsertionSort( Item& firstChild, SortHelper& sortHelper )
  38 {
  39     if (firstChild.isNull()) return;
  40     Item j = firstChild.nextSibling();
  41     while ( !j.isNull() )
  42     {
  43         Key key = Criteria::key(j);
  44         // Insert A[j] into the sorted sequence A[1..j-1]
  45         Item i = j.previousSibling();
  46         bool moved = false;
  47         while ( !i.isNull() && Criteria::key(i) > key )
  48         {
  49             i = i.previousSibling();
  50             moved = true;
  51         }
  52         if ( moved )
  53             sortHelper.moveAfter( j, i ); // move j right after i. If i is null, move to first position.
  54         j = j.nextSibling();
  55     }
  56 }
  57
  58 #endif