1 files changed, 59 insertions, 0 deletions
diff --git a/konqueror/keditbookmarks/kinsertionsort.h b/konqueror/keditbookmarks/kinsertionsort.h
new file mode 100644
index 000000000..5f71184ed
--- /dev/null
+++ b/konqueror/keditbookmarks/kinsertionsort.h
@@ -0,0 +1,59 @@
+// -*- mode:cperl; cperl-indent-level:4; cperl-continued-statement-offset:4; indent-tabs-mode:nil -*-
+// vim: set ts=4 sts=4 sw=4 et:
+/* This file is part of the KDE project
+   Copyright (C) 2000 David Faure <faure@kde.org>
+ 
+   This program is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public
+   License version 2 as published by the Free Software Foundation.
+ 
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    General Public License for more details.
+ 
+   You should have received a copy of the GNU General Public License
+   along with this program; see the file COPYING.  If not, write to
+   the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+   Boston, MA 02110-1301, USA.
+*/
+
+#ifndef __kinsertionsort_h
+#define __kinsertionsort_h
+
+/**
+ * A template-based insertion sort algorithm, but not really 100%
+ * generic. It is mostly written for lists, not for arrays.
+ *
+ * A good reason to use insertion sort over faster algorithms like
+ * heap sort or quick sort, is that it minimizes the number of
+ * movements of the items. This is important in applications which support
+ * undo, because the number of commands is kept to a minimum.
+ */
+
+// Item must define isNull(), previousSibling(), nextSibling()
+// SortHelper must define  moveAfter( const Item &, const Item & )
+// Criteria must define  static Key key(const Item &)
+template <class Item, class Criteria, class Key, class SortHelper>
+inline void kInsertionSort( Item& firstChild, SortHelper& sortHelper )
+{
+    if (firstChild.isNull()) return;
+    Item j = firstChild.nextSibling();
+    while ( !j.isNull() )
+    {
+        Key key = Criteria::key(j);
+        // Insert A[j] into the sorted sequence A[1..j-1]
+        Item i = j.previousSibling();
+        bool moved = false;
+        while ( !i.isNull() && Criteria::key(i) > key )
+        {
+            i = i.previousSibling();
+            moved = true;
+        }
+        if ( moved )
+            sortHelper.moveAfter( j, i ); // move j right after i. If i is null, move to first position.
+        j = j.nextSibling();
+    }
+}
+
+#endif