diff options
Diffstat (limited to 'konqueror/keditbookmarks/kinsertionsort.h')
-rw-r--r-- | konqueror/keditbookmarks/kinsertionsort.h | 59 |
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 |