You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
58 lines
2.1 KiB
58 lines
2.1 KiB
/* 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
|