// -*- 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