LRU_Cache.h

Go to the documentation of this file.

/***************************************************************************
            LRU_Cache.h  -  template class for a LRU cache
                             -------------------
    begin                : Thu Jun 18 2009
    copyright            : (C) 2009 by Thomas Eschenbacher
    email                : Thomas.Eschenbacher@gmx.de
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

#ifndef LRU_CACHE_H
#define LRU_CACHE_H

#include "config.h"

#include <QLinkedList>
#include <QMutableLinkedListIterator>
#include <QPair>

namespace Kwave
{

    template<class IDX, class DATA> class LRU_Cache
        :public QLinkedList< QPair<IDX, DATA> >
    {
    private:
        typedef QPair<IDX,DATA> Pair;

    public:
        LRU_Cache()
            :QLinkedList< Pair >()
        {
        }

        virtual ~LRU_Cache()
        {
        }

        bool isEmpty() const {
            return QLinkedList<Pair>::isEmpty();
        }

        const DATA & operator [] (const IDX index) const
        {
            foreach(const Pair &p, *this) {
                if (p.first == index) {
                    return p.second;
                }
            }
            return DATA();
        }

        DATA & operator [] (const IDX index)
        {
            static DATA dummy;

            if (!QLinkedList<Pair>::isEmpty()) {
                QMutableLinkedListIterator<Pair> it(*this);
                while (it.hasNext()) {
                    Pair &p = it.next();
                    if (p.first == index) {
                        if (p.first != QLinkedList<Pair>::first().first) {
                            // found it -> move the entry to the start of the list
                            Pair pair = p;
                            it.remove();
                            insert(pair.first, pair.second);
//                          qDebug("Kwave::MemoryManager[%9d] - reordering",
//                                 pair.first);
                        }

                        // get the newly entered entry again
                        return QLinkedList<Pair>::first().second;
                    }
                }
            }
            return dummy;
        }

        bool contains(const IDX index) const
        {
            foreach(const Pair &p, *this) {
                if (p.first == index)
                    return true;
            }
            return false;
        }

        void remove(const IDX index)
        {
            if (!QLinkedList<Pair>::isEmpty()) {
                QMutableLinkedListIterator<Pair> it(*this);
                while (it.hasNext()) {
                    Pair &p = it.next();
                    if (p.first == index) {
                        it.remove();
                        break;
                    }
                }
            }
        }

        void insert(const IDX index, DATA &value)
        {
            QLinkedList<Pair>::prepend(Pair(index, value));
        }

        QList<IDX> keys() const
        {
            QList<IDX> i;
            foreach(const Pair &p, *this) {
                i << p.first;
            }
            return i;
        }

        QList<DATA> values() const
        {
            QList<DATA> v;
            foreach(const Pair &p, *this) {
                v << p.second;
            }
            return v;
        }

    };

}

#endif /* LRU_CACHE_H */

//***************************************************************************
//***************************************************************************