File indexing completed on 2022-11-29 15:26:22

0001 /* This file is part of the KDE project
0002    Copyright (C) 2000 David Faure <faure@kde.org>
0003 
0004    This program is free software: you can redistribute it and/or modify
0005    it under the terms of the GNU General Public License as published by
0006    the Free Software Foundation, either version 2 of the License, or
0007    (at your option) any later version.
0008 
0009    This program is distributed in the hope that it will be useful,
0010    but WITHOUT ANY WARRANTY; without even the implied warranty of
0011    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
0012    GNU General Public License for more details.
0013 
0014    You should have received a copy of the GNU General Public License
0015    along with this program.  If not, see <http://www.gnu.org/licenses/>.
0016 */
0017 
0018 #ifndef KINSERTIONSORT_P_H
0019 #define KINSERTIONSORT_P_H
0020 
0021 /**
0022  * A template-based insertion sort algorithm, but not really 100%
0023  * generic. It is mostly written for lists, not for arrays.
0024  *
0025  * A good reason to use insertion sort over faster algorithms like
0026  * heap sort or quick sort, is that it minimizes the number of
0027  * movements of the items. This is important in applications which support
0028  * undo, because the number of commands is kept to a minimum.
0029  */
0030 
0031 // Item must define isNull(), previousSibling(), nextSibling()
0032 // SortHelper must define  moveAfter( const Item &, const Item & )
0033 // Criteria must define  static Key key(const Item &)
0034 template<class Item, class Criteria, class Key, class SortHelper>
0035 inline void kInsertionSort(Item &firstChild, SortHelper &sortHelper)
0036 {
0037     if (firstChild.isNull())
0038         return;
0039     Item j = firstChild.nextSibling();
0040     while (!j.isNull()) {
0041         Key key = Criteria::key(j);
0042         // qCDebug(KEDITBOOKMARKS_LOG) << "Looking at j=" << key;
0043         // Insert A[j] into the sorted sequence A[1..j-1]
0044         Item i = j.previousSibling();
0045         Item next = j.nextSibling();
0046         bool moved = false;
0047         while (!i.isNull() && Criteria::key(i) > key) {
0048             i = i.previousSibling();
0049             moved = true;
0050         }
0051         if (moved) {
0052             // qCDebug(KEDITBOOKMARKS_LOG) << "moveAfter(" << Criteria::key(j) << "," << (i.isNull() ? "null" : Criteria::key(i)) << ")";
0053             sortHelper.moveAfter(j, i); // move j right after i. If i is null, move to first position.
0054         }
0055         j = next;
0056         // qCDebug(KEDITBOOKMARKS_LOG) << "Now j is" << Criteria::key(next);
0057     }
0058 }
0059 
0060 #endif