From 11304d02942e9fa493e4e80943a828f9c65f6772 Mon Sep 17 00:00:00 2001 From: mickeyl Date: Fri, 28 Mar 2003 15:11:52 +0000 Subject: skeleton and the start of libopie2, please read README, ROADMAP and STATUS and comment... --- (limited to 'libopie2/qt3/opiecore') diff --git a/libopie2/qt3/opiecore/ocompletion.cpp b/libopie2/qt3/opiecore/ocompletion.cpp new file mode 100644 index 0000000..7b263ab --- a/dev/null +++ b/libopie2/qt3/opiecore/ocompletion.cpp @@ -0,0 +1,1061 @@ +/* +                 This file is part of the Opie Project + Originally part of the KDE Project + Copyright (C) 1999,2000,2001 Carsten Pfeiffer + =. + .=l. +           .>+-= + _;:,     .>    :=|. This program is free software; you can +.> <`_,   >  .   <= redistribute it and/or modify it under +:`=1 )Y*s>-.--   : the terms of the GNU Library General Public +.="- .-=="i,     .._ License as published by the Free Software + - .   .-<_>     .<> Foundation; either version 2 of the License, +     ._= =}       : or (at your option) any later version. +    .%`+i>       _;_. +    .i_,=:_.      -`: PARTICULAR PURPOSE. See the GNU +..}^=.=       =       ; Library General Public License for more +++=   -.     .`     .: details. + :     =  ...= . :.=- + -.   .:....=;==+<; You should have received a copy of the GNU +  -_. . .   )=.  = Library General Public License along with +    --        :-=` this library; see the file COPYING.LIB. + If not, write to the Free Software Foundation, + Inc., 59 Temple Place - Suite 330, + Boston, MA 02111-1307, USA. +*/ + +#include + +class OCompTreeNode; + +/**************************************************************************************************/ +/* OCompTreeNodeList +/**************************************************************************************************/ + +class OCompTreeNodeList +{ +public: + OCompTreeNodeList() : first(0), last(0), m_count(0) {} + OCompTreeNode *begin() const { return first; } + OCompTreeNode *end() const { return last; } + + OCompTreeNode *at(uint index) const; + void append(OCompTreeNode *item); + void prepend(OCompTreeNode *item); + void insert(OCompTreeNode *after, OCompTreeNode *item); + OCompTreeNode *remove(OCompTreeNode *item); + uint count() const { return m_count; } + +private: + OCompTreeNode *first, *last; + uint m_count; +}; + +typedef OCompTreeNodeList OCompTreeChildren; +typedef OSortableValueList OCompletionMatchesList; + +/** + * A helper class for OCompletion. Implements a tree of QChar. + * + * The tree looks like this (containing the items "kde", "kde-ui", + * "kde-core" and "pfeiffer". Every item is delimited with QChar( 0x0 ) + * + * some_root_node + * / \ + * k p + * | | + * d f + * | | + * e e + * /| | + * 0x0 - i + * / \ | + * u c f + * | | | + * i o f + * | | | + * 0x0 r e + * | | + * e r + * | | + * 0x0 0x0 + * + * @author Carsten Pfeiffer + * @internal + */ + +/**************************************************************************************************/ +/* OCompTreeNode +/**************************************************************************************************/ + +class OCompTreeNode : public QChar +{ +public: + OCompTreeNode():QChar(), myWeight(0) {} + OCompTreeNode( const QChar& ch, uint weight = 0 ):QChar( ch ), myWeight( weight ) {} + ~OCompTreeNode(); + + // FIXME: Do we need this for Opie? [see also the static ZoneAllocater below] + //void * operator new( size_t s ) { + // return alloc.allocate( s ); + //} + //void operator delete( void * s ) { + // alloc.deallocate( s ); + //} + + // Returns a child of this node matching ch, if available. + // Otherwise, returns 0L + inline OCompTreeNode * find( const QChar& ch ) const { + OCompTreeNode * cur = myChildren.begin(); + while (cur && (*cur != ch)) cur = cur->next; + return cur; + } + + OCompTreeNode * insert( const QChar&, bool sorted ); + void remove( const QString& ); + + inline int childrenCount() const { return myChildren.count(); }; + + // weighting + inline void confirm() { myWeight++; }; + inline void confirm(uint w) { myWeight += w; }; + inline void decline() { myWeight--; }; + inline uint weight() const { return myWeight; }; + + inline const OCompTreeChildren * children() const { return &myChildren; }; + inline const OCompTreeNode * childAt(int index) const { return myChildren.at(index); }; + inline const OCompTreeNode * firstChild() const { return myChildren.begin(); }; + inline const OCompTreeNode * lastChild() const { return myChildren.end(); }; + + /* We want to handle a list of OCompTreeNodes on our own, to not + need to use QValueList<>. And to make it even more fast we don't + use an accessor, but just a public member. */ + OCompTreeNode *next; + +private: + uint myWeight; + OCompTreeNodeList myChildren; + //static OZoneAllocator alloc; // FIXME: Do we need this for Opie? +}; + +/**************************************************************************************************/ +/* OCompletionMatchesWrapper +/**************************************************************************************************/ + +class OCompletionMatchesWrapper +{ +public: + OCompletionMatchesWrapper( bool sort = false ) + : sortedList( sort ? new OCompletionMatchesList : 0L ), + dirty( false ) + {} + ~OCompletionMatchesWrapper() { + delete sortedList; + } + + void setSorting( bool sort ) { + if ( sort && !sortedList ) + sortedList = new OCompletionMatchesList; + else if ( !sort ) { + delete sortedList; + sortedList = 0L; + } + stringList.clear(); + dirty = false; + } + + bool sorting() const { + return sortedList != 0L; + } + + void append( int i, const QString& string ) { + if ( sortedList ) + sortedList->insert( i, string ); + else + stringList.append( string ); + dirty = true; + } + + void clear() { + if ( sortedList ) + sortedList->clear(); + stringList.clear(); + dirty = false; + } + + uint count() const { + if ( sortedList ) + return sortedList->count(); + return stringList.count(); + } + + bool isEmpty() const { + return count() == 0; + } + + QString first() const { + return list().first(); + } + + QString last() const { + return list().last(); + } + + QStringList list() const; + + mutable QStringList stringList; + OCompletionMatchesList *sortedList; + mutable bool dirty; +}; + +/**************************************************************************************************/ +/* OCompletionPrivate +/**************************************************************************************************/ + +class OCompletionPrivate +{ +public: + // not a member to avoid #including kcompletion_private.h from kcompletion.h + // list used for nextMatch() and previousMatch() + OCompletionMatchesWrapper matches; +}; + +/**************************************************************************************************/ +/* OCompletion +/**************************************************************************************************/ + +OCompletion::OCompletion() +{ + d = new OCompletionPrivate; + + myCompletionMode = OGlobalSettings::completionMode(); + myTreeRoot = new OCompTreeNode; + myBeep = true; + myIgnoreCase = false; + myHasMultipleMatches = false; + myRotationIndex = 0; + setOrder( Insertion ); +} + + +OCompletion::~OCompletion() +{ + delete d; + delete myTreeRoot; +} + + +void OCompletion::setOrder( CompOrder order ) +{ + myOrder = order; + d->matches.setSorting( order == Weighted ); +} + + +void OCompletion::setIgnoreCase( bool ignoreCase ) +{ + myIgnoreCase = ignoreCase; +} + + +void OCompletion::setItems( const QStringList& items ) +{ + clear(); + insertItems( items ); +} + + +void OCompletion::insertItems( const QStringList& items ) +{ + bool weighted = (myOrder == Weighted); + QStringList::ConstIterator it; + if ( weighted ) { // determine weight + for ( it = items.begin(); it != items.end(); ++it ) addWeightedItem( *it ); + } + else { + for ( it = items.begin(); it != items.end(); ++it ) addItem( *it, 0 ); + } +} + + +QStringList OCompletion::items() const +{ + OCompletionMatchesWrapper list; // unsorted + bool addWeight = (myOrder == Weighted); + extractStringsFromNode( myTreeRoot, QString::null, &list, addWeight ); + + return list.list(); +} + + +void OCompletion::addItem( const QString& item ) +{ + d->matches.clear(); + myRotationIndex = 0; + myLastString = QString::null; + + addItem( item, 0 ); +} + + +void OCompletion::addItem( const QString& item, uint weight ) +{ + if ( item.isEmpty() ) return; + + OCompTreeNode *node = myTreeRoot; + uint len = item.length(); + + bool sorted = (myOrder == Sorted); + bool weighted = ((myOrder == Weighted) && weight > 1); + + // knowing the weight of an item, we simply add this weight to all of its + // nodes. + + for ( uint i = 0; i < len; i++ ) { + node = node->insert( item.at(i), sorted ); + if ( weighted ) node->confirm( weight -1 ); // node->insert() sets weighting to 1 + } + + // add 0x0-item as delimiter with evtl. weight + node = node->insert( 0x0, true ); + if ( weighted ) + node->confirm( weight -1 ); + //qDebug( "OCompletion: added: %s (%i)", item.latin1(), node->weight()); +} + + +void OCompletion::addWeightedItem( const QString& item ) +{ + if ( myOrder != Weighted ) { + addItem( item, 0 ); + return; + } + + uint len = item.length(); + uint weight = 0; + + // find out the weighting of this item (appended to the string as ":num") + int index = item.findRev(':'); + if ( index > 0 ) { + bool ok; + weight = item.mid( index + 1 ).toUInt( &ok ); + if ( !ok ) + weight = 0; + + len = index; // only insert until the ':' + } + + addItem( item.left( len ), weight ); + return; +} + + +void OCompletion::removeItem( const QString& item ) +{ + d->matches.clear(); + myRotationIndex = 0; + myLastString = QString::null; + + myTreeRoot->remove( item ); +} + + +void OCompletion::clear() +{ + d->matches.clear(); + myRotationIndex = 0; + myLastString = QString::null; + + delete myTreeRoot; + myTreeRoot = new OCompTreeNode; +} + + +QString OCompletion::makeCompletion( const QString& string ) +{ + if ( myCompletionMode == OGlobalSettings::CompletionNone ) + return QString::null; + + //qDebug( "OCompletion: completing: %s", string ); + + d->matches.clear(); + myRotationIndex = 0; + myHasMultipleMatches = false; + myLastMatch = myCurrentMatch; + + // in Shell-completion-mode, emit all matches when we get the same + // complete-string twice + if ( myCompletionMode == OGlobalSettings::CompletionShell && + string == myLastString ) { + // Don't use d->matches since calling postProcessMatches() + // on d->matches here would interfere with call to + // postProcessMatch() during rotation + + findAllCompletions( string, &d->matches, myHasMultipleMatches ); + QStringList l = d->matches.list(); + postProcessMatches( &l ); + emit matches( l ); + + if ( l.isEmpty() ) + doBeep( NoMatch ); + + return QString::null; + } + + QString completion; + // in case-insensitive popup mode, we search all completions at once + if ( myCompletionMode == OGlobalSettings::CompletionPopup || + myCompletionMode == OGlobalSettings::CompletionPopupAuto ) { + findAllCompletions( string, &d->matches, myHasMultipleMatches ); + if ( !d->matches.isEmpty() ) + completion = d->matches.first(); + } + else + completion = findCompletion( string ); + + if ( myHasMultipleMatches ) + emit multipleMatches(); + + myLastString = string; + myCurrentMatch = completion; + + postProcessMatch( &completion ); + + if ( !string.isEmpty() ) { // only emit match when string != "" + //qDebug( "OCompletion: Match: %s", completion ); + emit match( completion ); + } + + if ( completion.isNull() ) + doBeep( NoMatch ); + + return completion; +} + +QStringList OCompletion::substringCompletion( const QString& string ) const +{ + // get all items in the tree, eventually in sorted order + bool sorted = (myOrder == Weighted); + OCompletionMatchesWrapper allItems( sorted ); + extractStringsFromNode( myTreeRoot, QString::null, &allItems, false ); + + QStringList list = allItems.list(); + + // subStringMatches is invoked manually, via a shortcut, so we should + // beep here, if necessary. + if ( list.isEmpty() ) { + doBeep( NoMatch ); + return list; + } + + if ( string.isEmpty() ) { // shortcut + postProcessMatches( &list ); + return list; + } + + QStringList matches; + QStringList::ConstIterator it = list.begin(); + + for( ; it != list.end(); ++it ) { + QString item = *it; + if ( item.find( string, 0, false ) != -1 ) { // always case insensitive + postProcessMatch( &item ); + matches.append( item ); + } + } + + if ( matches.isEmpty() ) + doBeep( NoMatch ); + + return matches; +} + + +void OCompletion::setCompletionMode( OGlobalSettings::Completion mode ) +{ + myCompletionMode = mode; +} + + +QStringList OCompletion::allMatches() +{ + // Don't use d->matches since calling postProcessMatches() + // on d->matches here would interfere with call to + // postProcessMatch() during rotation + OCompletionMatchesWrapper matches( myOrder == Weighted ); + bool dummy; + findAllCompletions( myLastString, &matches, dummy ); + QStringList l = matches.list(); + postProcessMatches( &l ); + return l; +} + + +OCompletionMatches OCompletion::allWeightedMatches() +{ + // Don't use d->matches since calling postProcessMatches() + // on d->matches here would interfere with call to + // postProcessMatch() during rotation + OCompletionMatchesWrapper matches( myOrder == Weighted ); + bool dummy; + findAllCompletions( myLastString, &matches, dummy ); + OCompletionMatches ret( matches ); + postProcessMatches( &ret ); + return ret; +} + +QStringList OCompletion::allMatches( const QString &string ) +{ + OCompletionMatchesWrapper matches( myOrder == Weighted ); + bool dummy; + findAllCompletions( string, &matches, dummy ); + QStringList l = matches.list(); + postProcessMatches( &l ); + return l; +} + +OCompletionMatches OCompletion::allWeightedMatches( const QString &string ) +{ + OCompletionMatchesWrapper matches( myOrder == Weighted ); + bool dummy; + findAllCompletions( string, &matches, dummy ); + OCompletionMatches ret( matches ); + postProcessMatches( &ret ); + return ret; +} + +///////////////////////////////////////////////////// +///////////////// tree operations /////////////////// + + +QString OCompletion::nextMatch() +{ + QString completion; + myLastMatch = myCurrentMatch; + + if ( d->matches.isEmpty() ) { + findAllCompletions( myLastString, &d->matches, myHasMultipleMatches ); + completion = d->matches.first(); + myCurrentMatch = completion; + myRotationIndex = 0; + postProcessMatch( &completion ); + emit match( completion ); + return completion; + } + + QStringList matches = d->matches.list(); + myLastMatch = matches[ myRotationIndex++ ]; + + if ( myRotationIndex == matches.count() -1 ) + doBeep( Rotation ); // indicate last matching item -> rotating + + else if ( myRotationIndex == matches.count() ) + myRotationIndex = 0; + + completion = matches[ myRotationIndex ]; + myCurrentMatch = completion; + postProcessMatch( &completion ); + emit match( completion ); + return completion; +} + + + +QString OCompletion::previousMatch() +{ + QString completion; + myLastMatch = myCurrentMatch; + + if ( d->matches.isEmpty() ) { + findAllCompletions( myLastString, &d->matches, myHasMultipleMatches ); + completion = d->matches.last(); + myCurrentMatch = completion; + myRotationIndex = 0; + postProcessMatch( &completion ); + emit match( completion ); + return completion; + } + + QStringList matches = d->matches.list(); + myLastMatch = matches[ myRotationIndex ]; + if ( myRotationIndex == 1 ) + doBeep( Rotation ); // indicate first item -> rotating + + else if ( myRotationIndex == 0 ) + myRotationIndex = matches.count(); + + myRotationIndex--; + + completion = matches[ myRotationIndex ]; + myCurrentMatch = completion; + postProcessMatch( &completion ); + emit match( completion ); + return completion; +} + + + +// tries to complete "string" from the tree-root +QString OCompletion::findCompletion( const QString& string ) +{ + QChar ch; + QString completion; + const OCompTreeNode *node = myTreeRoot; + + // start at the tree-root and try to find the search-string + for( uint i = 0; i < string.length(); i++ ) { + ch = string.at( i ); + node = node->find( ch ); + + if ( node ) + completion += ch; + else + return QString::null; // no completion + } + + // Now we have the last node of the to be completed string. + // Follow it as long as it has exactly one child (= longest possible + // completion) + + while ( node->childrenCount() == 1 ) { + node = node->firstChild(); + if ( !node->isNull() ) + completion += *node; + } + // if multiple matches and auto-completion mode + // -> find the first complete match + if ( node && node->childrenCount() > 1 ) { + myHasMultipleMatches = true; + + if ( myCompletionMode == OGlobalSettings::CompletionAuto ) { + myRotationIndex = 1; + if (myOrder != Weighted) { + while ( (node = node->firstChild()) ) { + if ( !node->isNull() ) + completion += *node; + else + break; + } + } + else { + // don't just find the "first" match, but the one with the + // highest priority + + const OCompTreeNode* temp_node = 0L; + while(1) { + int count = node->childrenCount(); + temp_node = node->firstChild(); + uint weight = temp_node->weight(); + const OCompTreeNode* hit = temp_node; + for( int i = 1; i < count; i++ ) { + temp_node = node->childAt(i); + if( temp_node->weight() > weight ) { + hit = temp_node; + weight = hit->weight(); + } + } + // 0x0 has the highest priority -> we have the best match + if ( hit->isNull() ) + break; + + node = hit; + completion += *node; + } + } + } + + else + doBeep( PartialMatch ); // partial match -> beep + } + + return completion; +} + + +void OCompletion::findAllCompletions(const QString& string, + OCompletionMatchesWrapper *matches, + bool& hasMultipleMatches) const +{ + //qDebug( "OCompletion: finding all completions for %s", (const char*) string ); + + if ( string.isEmpty() ) + return; + + if ( myIgnoreCase ) { // case insensitive completion + extractStringsFromNodeCI( myTreeRoot, QString::null, string, matches ); + hasMultipleMatches = (matches->count() > 1); + return; + } + + QChar ch; + QString completion; + const OCompTreeNode *node = myTreeRoot; + + // start at the tree-root and try to find the search-string + for( uint i = 0; i < string.length(); i++ ) { + ch = string.at( i ); + node = node->find( ch ); + + if ( node ) + completion += ch; + else + return; // no completion -> return empty list + } + + // Now we have the last node of the to be completed string. + // Follow it as long as it has exactly one child (= longest possible + // completion) + + while ( node->childrenCount() == 1 ) { + node = node->firstChild(); + if ( !node->isNull() ) + completion += *node; + // kdDebug() << completion << node->latin1(); + } + + + // there is just one single match) + if ( node->childrenCount() == 0 ) + matches->append( node->weight(), completion ); + + else { + // node has more than one child + // -> recursively find all remaining completions + hasMultipleMatches = true; + extractStringsFromNode( node, completion, matches ); + } +} + + +void OCompletion::extractStringsFromNode( const OCompTreeNode *node, + const QString& beginning, + OCompletionMatchesWrapper *matches, + bool addWeight ) const +{ + if ( !node || !matches ) return; + + // kDebug() << "Beginning: " << beginning << endl; + const OCompTreeChildren *list = node->children(); + QString string; + QString w; + + // loop thru all children + for ( OCompTreeNode *cur = list->begin(); cur ; cur = cur->next) { + string = beginning; + node = cur; + if ( !node->isNull() ) + string += *node; + + while ( node && node->childrenCount() == 1 ) { + node = node->firstChild(); + if ( node->isNull() ) break; + string += *node; + } + + if ( node && node->isNull() ) { // we found a leaf + if ( addWeight ) { + // add ":num" to the string to store the weighting + string += ':'; + w.setNum( node->weight() ); + string.append( w ); + } + matches->append( node->weight(), string ); + } + + // recursively find all other strings. + if ( node && node->childrenCount() > 1 ) + extractStringsFromNode( node, string, matches, addWeight ); + } +} + +void OCompletion::extractStringsFromNodeCI( const OCompTreeNode *node, + const QString& beginning, + const QString& restString, + OCompletionMatchesWrapper *matches ) const +{ + if ( restString.isEmpty() ) { + extractStringsFromNode( node, beginning, matches, false /*noweight*/ ); + return; + } + + QChar ch1 = restString.at(0); + QString newRest = restString.mid(1); + OCompTreeNode *child1, *child2; + + child1 = node->find( ch1 ); // the correct match + if ( child1 ) + extractStringsFromNodeCI( child1, beginning + *child1, newRest, + matches ); + + // append the case insensitive matches, if available + if ( ch1.isLetter() ) { + // find out if we have to lower or upper it. Is there a better way? + QChar ch2 = ch1.lower(); + if ( ch1 == ch2 ) + ch2 = ch1.upper(); + if ( ch1 != ch2 ) { + child2 = node->find( ch2 ); + if ( child2 ) + extractStringsFromNodeCI( child2, beginning + *child2, newRest, + matches ); + } + } +} + +// FIXME: Revise this for Opie? + +void OCompletion::doBeep( BeepMode mode ) const +{ + if ( !myBeep ) return; + + QString text, event; + + switch ( mode ) { + case Rotation: + event = QString::fromLatin1("Textcompletion: rotation"); + text = tr("You reached the end of the list\nof matching items.\n"); + break; + case PartialMatch: + if ( myCompletionMode == OGlobalSettings::CompletionShell || + myCompletionMode == OGlobalSettings::CompletionMan ) { + event = QString::fromLatin1("Textcompletion: partial match"); + text = tr("The completion is ambiguous, more than one\nmatch is available.\n"); + } + break; + case NoMatch: + if ( myCompletionMode == OGlobalSettings::CompletionShell ) { + event = QString::fromLatin1("Textcompletion: no match"); + text = tr("There is no matching item available.\n"); + } + break; + } + + //if ( !text.isEmpty() ) + //ONotifyClient::event( event, text ); // FIXME: Revise for Opie? +} + +// Implements the tree. Every node is a QChar and has a list of children, which +// are Nodes as well. +// QChar( 0x0 ) is used as the delimiter of a string; the last child of each +// inserted string is 0x0. + +OCompTreeNode::~OCompTreeNode() +{ + // delete all children + OCompTreeNode *cur = myChildren.begin(); + while (cur) { + OCompTreeNode * next = cur->next; + delete myChildren.remove(cur); + cur = next; + } +} + + +// Adds a child-node "ch" to this node. If such a node is already existant, +// it will not be created. Returns the new/existing node. +OCompTreeNode * OCompTreeNode::insert( const QChar& ch, bool sorted ) +{ + OCompTreeNode *child = find( ch ); + if ( !child ) { + child = new OCompTreeNode( ch ); + + // FIXME, first (slow) sorted insertion implementation + if ( sorted ) { + OCompTreeNode * prev = 0; + OCompTreeNode * cur = myChildren.begin(); + while ( cur ) { + if ( ch > *cur ) { + prev = cur; + cur = cur->next; + } else + break; + } + if (prev) + myChildren.insert( prev, child ); + else + myChildren.prepend(child); + } + + else + myChildren.append( child ); + } + + // implicit weighting: the more often an item is inserted, the higher + // priority it gets. + child->confirm(); + + return child; +} + + +// Recursively removes a string from the tree (untested :-) +void OCompTreeNode::remove( const QString& string ) +{ + OCompTreeNode *child = 0L; + + if ( string.isEmpty() ) { + child = find( 0x0 ); + delete myChildren.remove( child ); + return; + } + + QChar ch = string.at(0); + child = find( ch ); + if ( child ) { + child->remove( string.right( string.length() -1 ) ); + if ( child->myChildren.count() == 0 ) { + delete myChildren.remove( child ); + } + } +} + +QStringList OCompletionMatchesWrapper::list() const { + if ( sortedList && dirty ) { + sortedList->sort(); + dirty = false; + + stringList.clear(); + + // high weight == sorted last -> reverse the sorting here + QValueListConstIterator > it; + for ( it = sortedList->begin(); it != sortedList->end(); ++it ) + stringList.prepend( (*it).value() ); + } + + return stringList; +} + +OCompletionMatches::OCompletionMatches( bool sort_P ) + : _sorting( sort_P ) +{ +} + +OCompletionMatches::OCompletionMatches( const OCompletionMatchesWrapper& matches ) + : _sorting( matches.sorting()) +{ + if( matches.sortedList != 0L ) + OCompletionMatchesList::operator=( *matches.sortedList ); + else { + QStringList l = matches.list(); + for( QStringList::ConstIterator it = l.begin(); + it != l.end(); + ++it ) + prepend( OSortableItem( 1, *it ) ); + } +} + +OCompletionMatches::~OCompletionMatches() +{ +} + +QStringList OCompletionMatches::list( bool sort_P ) const +{ + if( _sorting && sort_P ) + const_cast< OCompletionMatches* >( this )->sort(); + QStringList stringList; + // high weight == sorted last -> reverse the sorting here + for ( ConstIterator it = begin(); it != end(); ++it ) + stringList.prepend( (*it).value() ); + return stringList; +} + +void OCompletionMatches::removeDuplicates() +{ + Iterator it1, it2; + for ( it1 = begin(); it1 != end(); ++it1 ) { + for ( (it2 = it1), ++it2; it2 != end();) { + if( (*it1).value() == (*it2).value()) { + // use the max height + //(*it1).first = kMax( (*it1).index(), (*it2).index()); + (*it1).first = (*it2).index() < (*it1).index() ? (*it1).index() : (*it2).index(); + it2 = remove( it2 ); + continue; + } + ++it2; + } + } +} + +void OCompTreeNodeList::append(OCompTreeNode *item) +{ + m_count++; + if (!last) { + last = item; + last->next = 0; + first = item; + return; + } + last->next = item; + item->next = 0; + last = item; +} + +void OCompTreeNodeList::prepend(OCompTreeNode *item) +{ + m_count++; + if (!last) { + last = item; + last->next = 0; + first = item; + return; + } + item->next = first; + first = item; +} + +void OCompTreeNodeList::insert(OCompTreeNode *after, OCompTreeNode *item) +{ + if (!after) { + append(item); + return; + } + + m_count++; + + item->next = after->next; + after->next = item; + + if (after == last) + last = item; +} + +OCompTreeNode *OCompTreeNodeList::remove(OCompTreeNode *item) +{ + if (!first || !item) + return 0; + OCompTreeNode *cur = 0; + + if (item == first) + first = first->next; + else { + cur = first; + while (cur && cur->next != item) cur = cur->next; + if (!cur) + return 0; + cur->next = item->next; + } + if (item == last) + last = cur; + m_count--; + return item; +} + +OCompTreeNode *OCompTreeNodeList::at(uint index) const +{ + OCompTreeNode *cur = first; + while (index-- && cur) cur = cur->next; + return cur; +} + +// FIXME: Revise for Opie? +//OZoneAllocator OCompTreeNode::alloc(8192); + +//void OCompletion::virtual_hook( int, void* ) +//{ /*BASE::virtual_hook( id, data );*/ } + +//void OCompletionBase::virtual_hook( int, void* ) +//{ /*BASE::virtual_hook( id, data );*/ } diff --git a/libopie2/qt3/opiecore/ocompletion.h b/libopie2/qt3/opiecore/ocompletion.h new file mode 100644 index 0000000..0317c1b --- a/dev/null +++ b/libopie2/qt3/opiecore/ocompletion.h @@ -0,0 +1,603 @@ +/* +                 This file is part of the Opie Project + Originally part of the KDE Project + Copyright (C) 1999,2000 Carsten Pfeiffer + =. + .=l. +           .>+-= + _;:,     .>    :=|. This program is free software; you can +.> <`_,   >  .   <= redistribute it and/or modify it under +:`=1 )Y*s>-.--   : the terms of the GNU Library General Public +.="- .-=="i,     .._ License as published by the Free Software + - .   .-<_>     .<> Foundation; either version 2 of the License, +     ._= =}       : or (at your option) any later version. +    .%`+i>       _;_. +    .i_,=:_.      -`: PARTICULAR PURPOSE. See the GNU +..}^=.=       =       ; Library General Public License for more +++=   -.     .`     .: details. + :     =  ...= . :.=- + -.   .:....=;==+<; You should have received a copy of the GNU +  -_. . .   )=.  = Library General Public License along with +    --        :-=` this library; see the file COPYING.LIB. + If not, write to the Free Software Foundation, + Inc., 59 Temple Place - Suite 330, + Boston, MA 02111-1307, USA. +*/ + +#ifndef OCOMPLETION_H +#define OCOMPLETION_H + +/* QT */ + +#include +#include +#include +#include +#include +#include + +/* OPIE */ + +#include +#include + +/* FORWARDS */ + +class OCompTreeNode; +class OCompletionPrivate; +class OCompletionBasePrivate; +class OCompletionMatchesWrapper; +class OCompletionMatches; +class QPopupMenu; + +// FIXME: Do we need special ShortCut handling in Opie? If so, revise this. +class OShortcut +{ +public: + bool isNull() const { return true; }; + bool operator == ( const OShortcut& bla ) const { return false; }; +}; + + +/** + * This class offers easy use of "auto-completion", "manual-completion" or + * "shell completion" on QString objects. A common use is completing filenames + * or URLs (see @ref OURLCompletion()). + * But it is not limited to URL-completion -- everything should be completable! + * The user should be able to complete email-addresses, telephone-numbers, + * commands, SQL queries, ... + * Every time your program knows what the user can type into an edit-field, you + * should offer completion. With OCompletion, this is very easy, and if you are + * using a line edit widget (@ref OLineEdit), it is even more easy. + * Basically, you tell a OCompletion object what strings should be completable + * and whenever completion should be invoked, you call @ref makeCompletion(). + * OLineEdit and (an editable) OComboBox even do this automatically for you. + * + * OCompletion offers the completed string via the signal @ref match() and + * all matching strings (when the result is ambiguous) via the method + * @ref allMatches(). + * + * Notice: auto-completion, shell completion and manual completion work + * slightly differently: + * + * @li auto-completion always returns a complete item as match. + * When more than one matching items are available, it will deliver just + * the first (depending on sorting order) item. Iterating over all matches + * is possible via @ref nextMatch() and @ref previousMatch(). + * + * @li popup-completion works in the same way, the only difference being that + * the completed items are not put into the edit-widget, but into a + * separate popup-box. + * + * @li manual completion works the same way as auto-completion, the + * subtle difference is, that it isn't invoked automatically while the user + * is typing, but only when the user presses a special key. The difference + * of manual and auto-completion is therefore only visible in UI classes, + * OCompletion needs to know whether to deliver partial matches + * (shell completion) or whole matches (auto/manual completion), therefore + * @ref OGlobalSettings::CompletionMan and + * @ref OGlobalSettings::CompletionAuto have the exact same effect in + * OCompletion. + * + * @li shell completion works like how shells complete filenames: + * when multiple matches are available, the longest possible string of all + * matches is returned (i.e. only a partial item). + * Iterating over all matching items (complete, not partial) is possible + * via @ref nextMatch() and @ref previousMatch(). + * + * You don't have to worry much about that though, OCompletion handles + * that for you, according to the setting @ref setCompletionMode(). + * The default setting is globally configured by the user and read + * from @ref OGlobalSettings::completionMode(). + * + * A short example: + * 
+ * OCompletion completion;
+ * completion.setOrder( OCompletion::Sorted );
+ * completion.addItem( "pfeiffer@kde.org" );
+ * completion.addItem( "coolo@kde.org" );
+ * completion.addItem( "carpdjih@sp.zrz.tu-berlin.de" );
+ * completion.addItem( "carp@cs.tu-berlin.de" );
+ *
+ * cout << completion.makeCompletion( "ca" ).latin1() << endl;
+ *
+ * In shell-completion-mode, this will be "carp"; in auto-completion- + * mode it will be "carp@cs.tu-berlin.de", as that is alphabetically + * smaller. + * If setOrder was set to Insertion, "carpdjih@sp.zrz.tu-berlin.de" + * would be completed in auto-completion-mode, as that was inserted before + * "carp@cs.tu-berlin.de". + * + * You can dynamically update the completable items by removing and adding them + * whenever you want. + * For advanced usage, you could even use multiple OCompletion objects. E.g. + * imagine an editor like kwrite with multiple open files. You could store + * items of each file in a different OCompletion object, so that you know (and + * tell the user) where a completion comes from. + * + * Note: OCompletion does not work with strings that contain 0x0 characters + * (unicode nul), as this is used internally as a delimiter. + * + * You may inherit from OCompletion and override @ref makeCompletion() in + * special cases (like reading directories/urls and then supplying the + * contents to OCompletion, as OURLCompletion does), but generally, this is + * not necessary. + * + * + * @short A generic class for completing QStrings + * @author Carsten Pfeiffer + * @version $Id$ + */ + +class OCompletion : public QObject +{ + Q_ENUMS( CompOrder ) + Q_PROPERTY( CompOrder order READ order WRITE setOrder ) + Q_PROPERTY( bool ignoreCase READ ignoreCase WRITE setIgnoreCase ) + Q_PROPERTY( QStringList items READ items WRITE setItems ) + Q_OBJECT + + public: + /** + * Constants that represent the order in which OCompletion performs + * completion-lookups. + */ + enum CompOrder { Sorted, Insertion, Weighted }; + + /** + * Constructor, nothing special here :) + */ + OCompletion(); + + // FIXME: copy constructor, assignment constructor... + + /** + * Destructor, nothing special here, either. + */ + virtual ~OCompletion(); + + /** + * Attempts to find an item in the list of available completions, + * that begins with @p string. Will either return the first matching item + * (if there is more than one match) or QString::null, if no match was + * found. + * + * In the latter case, a sound will be issued, depending on + * @ref isSoundsEnabled(). + * If a match was found, it will also be emitted via the signal + * @ref match(). + * + * If this is called twice or more often with the same string while no + * items were added or removed in the meantime, all available completions + * will be emitted via the signal @ref matches(). + * This happens only in shell-completion-mode. + * + * @returns the matching item, or QString::null if there is no matching + * item. + * @see #slotMakeCompletion + * @see #substringCompletion + */ + virtual QString makeCompletion( const QString& string ); + + /** + * @returns a list of items which all contain @p text as a substring, + * i.e. not necessarily at the beginning. + * + * @see #makeCompletion + */ + QStringList substringCompletion( const QString& string ) const; + + /** + * @returns the next item from the matching-items-list. + * When reaching the beginning, the list is rotated so it will return the + * last match and a sound is issued (depending on @ref isSoundsEnabled()). + * When there is no match, QString::null is returned and + * a sound is be issued. + * @see #slotPreviousMatch + */ + QString previousMatch(); + + /** + * @returns the previous item from the matching-items-list + * When reaching the last item, the list is rotated, so it will return + * the first match and a sound is issued (depending on + * @ref isSoundsEnabled()). When there is no match, QString::null is + * returned and a sound is issued. + * @see #slotNextMatch + */ + QString nextMatch(); + + /** + * @returns the last match. Might be useful if you need to check whether + * a completion is different from the last one. + * QString::null is returned when there is no last match. + */ + virtual const QString& lastMatch() const { return myLastMatch; } + + /** + * Returns a list of all items inserted into OCompletion. This is useful + * if you need to save the state of a OCompletion object and restore it + * later. + * + * Important note: when @ref order() == Weighted, then every item in the + * stringlist has its weight appended, delimited by a colon. E.g. an item + * "www.kde.org" might look like "www.kde.org:4", where 4 is the weight. + * + * This is necessary so that you can save the items along with its + * weighting on disk and load them back with @ref setItems(), restoring its + * weight as well. If you really don't want the appended weightings, call + * @ref setOrder( OCompletion::Insertion ) + * before calling items(). + * + * @returns a list of all items + * @see #setItems + */ + QStringList items() const; + + /** + * Sets the completion mode to Auto/Manual, Shell or None. + * If you don't set the mode explicitly, the global default value + * OGlobalSettings::completionMode() is used. + * @ref OGlobalSettings::CompletionNone disables completion. + * @see #completionMode + * @see #OGlobalSettings::completionMode + */ + virtual void setCompletionMode( OGlobalSettings::Completion mode ); + + /** + * @returns the current completion mode. + * May be different from @ref OGlobalSettings::completionMode(), if you + * explicitly called @ref setCompletionMode(). + * @see #setCompletionMode + */ + OGlobalSettings::Completion completionMode() const { return myCompletionMode; }; + + /** + * OCompletion offers three different ways in which it offers its items: + * @li in the order of insertion + * @li sorted alphabetically + * @li weighted + * + * Choosing weighted makes OCompletion perform an implicit weighting based + * on how often an item is inserted. Imagine a web browser with a location + * bar, where the user enters URLs. The more often a URL is entered, the + * higher priority it gets. + * + * Note: Setting the order to sorted only affects new inserted items, + * already existing items will stay in the current order. So you probably + * want to call setOrder( Sorted ) before inserting items, when you want + * everything sorted. + * + * Default is insertion order + * @see #order + */ + virtual void setOrder( CompOrder order ); + + /** + * @returns the current completion order. + * @see #setOrder + */ + CompOrder order() const { return myOrder; } + + /** + * Setting this to true makes OCompletion behave case insensitively. + * E.g. makeCompletion( "CA" ); might return "carp@cs.tu-berlin.de". + * Default is false (case sensitive). + * @see #ignoreCase + */ + virtual void setIgnoreCase( bool ignoreCase ); + + /** + * @returns whether OCompletion acts case insensitively or not. + * Default is false (case sensitive). + * @see #setIgnoreCase + */ + bool ignoreCase() const { return myIgnoreCase; }; + + /** + * @returns a list of all items matching the last completed string. + * Might take some time, when you have LOTS of items. + * + * @see #substringCompletion + */ + QStringList allMatches(); + + /** + * @returns a list of all items matching @p string. + */ + QStringList allMatches( const QString& string ); + + /** + * @returns a list of all items matching the last completed string. + * Might take some time, when you have LOTS of items. + * The matches are returned as OCompletionMatches, which also + * keeps the weight of the matches, allowing + * you to modify some matches or merge them with matches + * from another call to allWeightedMatches(), and sort the matches + * after that in order to have the matches ordered correctly + * + * @see #substringCompletion + */ + OCompletionMatches allWeightedMatches(); + + /** + * @returns a list of all items matching @p string. + */ + OCompletionMatches allWeightedMatches( const QString& string ); + + /** + * Enables/disables playing a sound when + * @li @ref makeCompletion() can't find a match + * @li there is a partial completion (= multiple matches in + * Shell-completion mode) + * @li @ref nextMatch() or @ref previousMatch() hit the last possible + * match -> rotation + * + * For playing the sounds, @ref ONotifyClient() is used. // FIXME: Revise this for Opie + * + * @see #isSoundsEnabled + */ + virtual void setEnableSounds( bool enable ) { myBeep = enable; } + + /** + * Tells you whether OCompletion will play sounds on certain occasions. + * Default is enabled + * @see #enableSounds + * @see #disableSounds + */ + bool isSoundsEnabled() const { return myBeep; }; + + /** + * @returns true when more than one match is found + * @see #multipleMatches + */ + bool hasMultipleMatches() const { return myHasMultipleMatches; }; + + public slots: + /** + * Attempts to complete "string" and emits the completion via @ref match(). + * Same as @ref makeCompletion() (just as a slot). + * @see #makeCompletion + */ + void slotMakeCompletion( const QString& string ) { (void) makeCompletion( string ); }; + + /** + * Searches the previous matching item and emits it via @ref match() + * Same as @ref previousMatch() (just as a slot). + * @see #previousMatch + */ + void slotPreviousMatch() { (void) previousMatch(); }; + + /** + * Searches the next matching item and emits it via @ref match() + * Same as @ref nextMatch() (just as a slot). + * @see #nextMatch + */ + void slotNextMatch() { (void) nextMatch(); }; + + /** + * Inserts @p items into the list of possible completions. + * Does the same as @ref setItems(), but does not call @ref clear() before. + */ + void insertItems( const QStringList& items ); + + /** + * Sets the list of items available for completion. Removes all previous + * items. + * + * Notice: when order() == Weighted, then the weighting is looked up for + * every item in the stringlist. Every item should have ":number" appended, + * where number is an unsigned integer, specifying the weighting. + * + * If you don't like this, call + * setOrder( OCompletion::Insertion ) + * before calling setItems(). + * + * @see #items + */ + virtual void setItems( const QStringList& ); + + /** + * Adds an item to the list of available completions. + * Resets the current item-state (@ref previousMatch() and @ref nextMatch() + * won't work anymore). + */ + void addItem( const QString& ); + + /** + * Adds an item to the list of available completions. + * Resets the current item-state (@ref previousMatch() and @ref nextMatch() + * won't work anymore). + * + * Sets the weighting of the item to @p weight or adds it to the current + * weighting if the item is already available. The weight has to be greater + * than 1 to take effect (default weight is 1). + */ + void addItem( const QString&, uint weight ); + + /** + * Removes an item from the list of available completions. + * Resets the current item-state (@ref previousMatch() and @ref nextMatch() + * won't work anymore). + */ + void removeItem( const QString& ); + + /** + * Removes all inserted items. + */ + virtual void clear(); + + signals: + /** + * The matching item. Will be emitted by @ref makeCompletion(), + * @ref previousMatch() or @ref nextMatch(). May be QString::null if there + * is no matching item. + */ + void match( const QString& ); + + /** + * All matching items. Will be emitted by @ref makeCompletion() in shell- + * completion-mode, when the same string is passed to makeCompletion twice + * or more often. + */ + void matches( const QStringList& ); + + /** + * This signal is emitted, when calling @ref makeCompletion() and more than + * one matching item is found. + * @see #hasMultipleMatches + */ + void multipleMatches(); + + protected: + /** + * This method is called after a completion is found and before the + * matching string is emitted. You can override this method to modify the + * string that will be emitted. + * This is necessary e.g. in @ref OURLCompletion(), where files with spaces + * in their names are shown escaped ("filename\ with\ spaces"), but stored + * unescaped inside OCompletion. + * Never delete that pointer! + * + * Default implementation does nothing. + * @see #postProcessMatches + */ + virtual void postProcessMatch( QString * /*match*/ ) const {} + + /** + * This method is called before a list of all available completions is + * emitted via @ref matches. You can override this method to modify the + * found items before @ref match() or @ref matches() are emitted. + * Never delete that pointer! + * + * Default implementation does nothing. + * @see #postProcessMatch + */ + virtual void postProcessMatches( QStringList * /*matches*/ ) const {} + + /** + * This method is called before a list of all available completions is + * emitted via @ref matches. You can override this method to modify the + * found items before @ref match() or @ref matches() are emitted. + * Never delete that pointer! + * + * Default implementation does nothing. + * @see #postProcessMatch + */ + virtual void postProcessMatches( OCompletionMatches * /*matches*/ ) const {} + +private: + void addWeightedItem( const QString& ); + QString findCompletion( const QString& string ); + void findAllCompletions( const QString&, OCompletionMatchesWrapper *matches, bool& hasMultipleMatches ) const; + + void extractStringsFromNode( const OCompTreeNode *, + const QString& beginning, + OCompletionMatchesWrapper *matches, + bool addWeight = false ) const; + void extractStringsFromNodeCI( const OCompTreeNode *, + const QString& beginning, + const QString& restString, + OCompletionMatchesWrapper *matches) const; + + enum BeepMode { NoMatch, PartialMatch, Rotation }; + void doBeep( BeepMode ) const; + + OGlobalSettings::Completion myCompletionMode; + + CompOrder myOrder; + QString myLastString; + QString myLastMatch; + QString myCurrentMatch; + OCompTreeNode * myTreeRoot; + QStringList myRotations; + bool myBeep; + bool myIgnoreCase; + bool myHasMultipleMatches; + uint myRotationIndex; + + private: + OCompletionPrivate *d; +}; + +// some more helper stuff +typedef OSortableValueList OCompletionMatchesList; +class OCompletionMatchesPrivate; + +/** + * This structure is returned by @ref OCompletion::allWeightedMatches . + * It also keeps the weight of the matches, allowing + * you to modify some matches or merge them with matches + * from another call to allWeightedMatches(), and sort the matches + * after that in order to have the matches ordered correctly + * + * Example (a simplified example of what Oonqueror's completion does): + * 
+ * OCompletionMatches matches = completion->allWeightedMatches( location );
+ * if( !location.startsWith( "www." ))
+       matches += completion->allWeightedmatches( "www." + location" );
+ * matches.removeDuplicates();
+ * QStringList list = matches.list();
+ *
+ * + * @short List for keeping matches returned from OCompletion + */ + +class OCompletionMatches + : public OCompletionMatchesList +{ + public: + OCompletionMatches( bool sort ); + /** + * @internal + */ + OCompletionMatches( const OCompletionMatchesWrapper& matches ); + ~OCompletionMatches(); + /** + * Removes duplicate matches. Needed only when you merged several matches + * results and there's a possibility of duplicates. + */ + void removeDuplicates(); + /** + * Returns the matches as a QStringList. + * @param sort if false, the matches won't be sorted before the conversion, + * use only if you're sure the sorting is not needed + */ + QStringList list( bool sort = true ) const; + /** + * If sorting() returns false, the matches aren't sorted by their weight, + * even if true is passed to list(). + */ + bool sorting() const { + return _sorting; + } +private: + bool _sorting; + OCompletionMatchesPrivate* d; +}; + +#endif // OCOMPLETION_H diff --git a/libopie2/qt3/opiecore/ocompletionbase.cpp b/libopie2/qt3/opiecore/ocompletionbase.cpp new file mode 100644 index 0000000..6ff129a --- a/dev/null +++ b/libopie2/qt3/opiecore/ocompletionbase.cpp @@ -0,0 +1,171 @@ +/* +                 This file is part of the Opie Project + +              Copyright (C) 2003 Michael Lauer + Inspired by the KDE completion classes which are + Copyright (C) 2000 Dawit Alemayehu + =. + .=l. +           .>+-= + _;:,     .>    :=|. This program is free software; you can +.> <`_,   >  .   <= redistribute it and/or modify it under +:`=1 )Y*s>-.--   : the terms of the GNU Library General Public +.="- .-=="i,     .._ License as published by the Free Software + - .   .-<_>     .<> Foundation; either version 2 of the License, +     ._= =}       : or (at your option) any later version. +    .%`+i>       _;_. +    .i_,=:_.      -`: PARTICULAR PURPOSE. See the GNU +..}^=.=       =       ; Library General Public License for more +++=   -.     .`     .: details. + :     =  ...= . :.=- + -.   .:....=;==+<; You should have received a copy of the GNU +  -_. . .   )=.  = Library General Public License along with +    --        :-=` this library; see the file COPYING.LIB. + If not, write to the Free Software Foundation, + Inc., 59 Temple Place - Suite 330, + Boston, MA 02111-1307, USA. +*/ + +#include +#include + +OCompletionBase::OCompletionBase() +{ + m_delegate = 0L; + // Assign the default completion type to use. + m_iCompletionMode = OGlobalSettings::completionMode(); + + // Initialize all key-bindings to 0 by default so that + // the event filter will use the global settings. + useGlobalKeyBindings(); + + // By default we initialize everything to false. + // All the variables would be setup properly when + // the appropriate member functions are called. + setup( false, false, false ); +} + +OCompletionBase::~OCompletionBase() +{ + if( m_bAutoDelCompObj && m_pCompObj ) + { + delete m_pCompObj; + } +} + +void OCompletionBase::setDelegate( OCompletionBase *delegate ) +{ + m_delegate = delegate; + + if ( m_delegate ) { + m_delegate->m_bAutoDelCompObj = m_bAutoDelCompObj; + m_delegate->m_bHandleSignals = m_bHandleSignals; + m_delegate->m_bEmitSignals = m_bEmitSignals; + m_delegate->m_iCompletionMode = m_iCompletionMode; + m_delegate->m_keyMap = m_keyMap; + } +} + +OCompletion* OCompletionBase::completionObject( bool hsig ) +{ + if ( m_delegate ) + return m_delegate->completionObject( hsig ); + + if ( !m_pCompObj ) + { + setCompletionObject( new OCompletion(), hsig ); + m_bAutoDelCompObj = true; + } + return m_pCompObj; +} + +void OCompletionBase::setCompletionObject( OCompletion* compObj, bool hsig ) +{ + if ( m_delegate ) { + m_delegate->setCompletionObject( compObj, hsig ); + return; + } + + if ( m_bAutoDelCompObj && compObj != m_pCompObj ) + delete m_pCompObj; + + m_pCompObj = compObj; + + // We emit rotation and completion signals + // if completion object is not NULL. + setup( false, hsig, !m_pCompObj.isNull() ); +} + +// BC: Inline this function and possibly rename it to setHandleEvents??? (DA) +void OCompletionBase::setHandleSignals( bool handle ) +{ + if ( m_delegate ) + m_delegate->setHandleSignals( handle ); + else + m_bHandleSignals = handle; +} + +void OCompletionBase::setCompletionMode( OGlobalSettings::Completion mode ) +{ + if ( m_delegate ) { + m_delegate->setCompletionMode( mode ); + return; + } + + m_iCompletionMode = mode; + // Always sync up OCompletion mode with ours as long as we + // are performing completions. + if( m_pCompObj && m_iCompletionMode != OGlobalSettings::CompletionNone ) + m_pCompObj->setCompletionMode( m_iCompletionMode ); +} + +bool OCompletionBase::setKeyBinding( KeyBindingType item, const OShortcut& cut ) +{ + if ( m_delegate ) + return m_delegate->setKeyBinding( item, cut ); + + + if( !cut.isNull() ) + { + for( KeyBindingMap::Iterator it = m_keyMap.begin(); it != m_keyMap.end(); ++it ) + if( it.data() == cut ) return false; + } + m_keyMap.replace( item, cut ); + return true; +} + +void OCompletionBase::useGlobalKeyBindings() +{ + +/* + + if ( m_delegate ) { + m_delegate->useGlobalKeyBindings(); + return; + } + + m_keyMap.clear(); + m_keyMap.insert( TextCompletion, 0 ); + m_keyMap.insert( PrevCompletionMatch, 0 ); + m_keyMap.insert( NextCompletionMatch, 0 ); + m_keyMap.insert( SubstringCompletion, 0 ); + +*/ + +} + +void OCompletionBase::setup( bool autodel, bool hsig, bool esig ) +{ + if ( m_delegate ) { + m_delegate->setup( autodel, hsig, esig ); + return; + } + + m_bAutoDelCompObj = autodel; + m_bHandleSignals = hsig; + m_bEmitSignals = esig; +} diff --git a/libopie2/qt3/opiecore/ocompletionbase.h b/libopie2/qt3/opiecore/ocompletionbase.h new file mode 100644 index 0000000..517667e --- a/dev/null +++ b/libopie2/qt3/opiecore/ocompletionbase.h @@ -0,0 +1,403 @@ +/* +                 This file is part of the Opie Project + +              Copyright (C) 2003 Michael Lauer + Inspired by the KDE completion classes which are + Copyright (C) 2000 Dawit Alemayehu + =. + .=l. +           .>+-= + _;:,     .>    :=|. This program is free software; you can +.> <`_,   >  .   <= redistribute it and/or modify it under +:`=1 )Y*s>-.--   : the terms of the GNU Library General Public +.="- .-=="i,     .._ License as published by the Free Software + - .   .-<_>     .<> Foundation; either version 2 of the License, +     ._= =}       : or (at your option) any later version. +    .%`+i>       _;_. +    .i_,=:_.      -`: PARTICULAR PURPOSE. See the GNU +..}^=.=       =       ; Library General Public License for more +++=   -.     .`     .: details. + :     =  ...= . :.=- + -.   .:....=;==+<; You should have received a copy of the GNU +  -_. . .   )=.  = Library General Public License along with +    --        :-=` this library; see the file COPYING.LIB. + If not, write to the Free Software Foundation, + Inc., 59 Temple Place - Suite 330, + Boston, MA 02111-1307, USA. +*/ + +#ifndef OCOMPLETIONBASE_H +#define OCOMPLETIONBASE_H + +/** + * An abstract base class for adding a completion feature + * into widgets. + * + * This is a convenience class that provides the basic functions + * needed to add text completion support into widgets. All that + * is required is an implementation for the pure virtual function + * @ref setCompletedText. Refer to @ref OLineEdit or @ref OComboBox + * to see how easily such support can be added using this as a base + * class. + * + * @short An abstract class for adding text completion support to widgets. + * @author Dawit Alemayehu + */ + +class OCompletionBase +{ + + public: + + /** + * Constants that represent the items whose short-cut + * key-binding is programmable. The default key-bindings + * for these items are defined in @ref OStdAccel. + */ + enum KeyBindingType { + /** + * Text completion (by default Ctrl-E). + */ + TextCompletion, + /** + * Switch to previous completion (by default Ctrl-Up). + */ + PrevCompletionMatch, + /** + * Switch to next completion (by default Ctrl-Down). + */ + NextCompletionMatch, + /** + * Substring completion (by default Ctrl-T). + */ + SubstringCompletion + }; + + + // Map for the key binding types mentioned above. + typedef QMap KeyBindingMap; + + /** + * Default constructor. + */ + OCompletionBase(); + + /** + * Destructor. + */ + virtual ~OCompletionBase(); + + /** + * Returns a pointer to the current completion object. + * + * If the object does not exist, it is automatically + * created. Note that the completion object created + * here is used by default to handle the signals + * internally. It is also deleted when this object's + * destructor is invoked. If you do not want these + * default settings, use @ref setAutoDeleteCompletionObject + * and @ref setHandleSignals to change the behavior. + * Alternatively, you can set the boolean parameter to + * false to disable the automatic handling of the signals + * by this object. Note that the boolean argument will be + * ignored if there already exists a completion object since + * no new object needs to be created. You need to use either + * @ref setHandleSignals or @ref setCompletionObject for + * such cases depending on your requirement. + * + * @param hsig if true, handles signals internally. + * @return a pointer the completion object. + */ + OCompletion* completionObject( bool hsig = true ); + + /** + * Sets up the completion object to be used. + * + * This method assigns the completion object and sets it + * up to automatically handle the completion and rotation + * signals internally. You should use this function if + * you want to share one completion object among you widgets + * or need to use a customized completion object. + * + * The object assigned through this method is not deleted + * when this object's destructor is invoked unless you + * explicitly call @ref setAutoDeleteCompletionObject after + * calling this method. Also if you do not want the signals + * to be handled by an internal implementation, be sure to + * set the bool argument to false. + * + * This method is also called when a completion-object is created + * automatically, when completionObject() is called the first time. + * + * @param compObj a @ref OCompletion() or a derived child object. + * @param hsig if true, handles signals internally. + */ + virtual void setCompletionObject( OCompletion* /*compObj*/, bool hsig = true ); + + /** + * Enables this object to handle completion and rotation + * events internally. + * + * This function simply assigns a boolean value that + * indicates whether it should handle rotation and + * completion events or not. Note that this does not + * stop the object from emitting signals when these + * events occur. + * + * @param handle if true, handle completion & rotation internally. + */ + virtual void setHandleSignals( bool /*handle*/ ); + + /** + * Returns true if the completion object is deleted + * upon this widget's destruction. + * + * See @ref setCompletionObject() and @ref enableCompletion() + * for details. + * + * @return true if the completion object + */ + bool isCompletionObjectAutoDeleted() const { + return m_delegate ? m_delegate->isCompletionObjectAutoDeleted() : m_bAutoDelCompObj; + } + + /** + * Sets the completion object when this widget's destructor + * is called. + * + * If the argument is set to true, the completion object + * is deleted when this widget's destructor is called. + * + * @param autoDelete if true, delete completion object on destruction. + */ + void setAutoDeleteCompletionObject( bool autoDelete ) { + if ( m_delegate ) + m_delegate->setAutoDeleteCompletionObject( autoDelete ); + else + m_bAutoDelCompObj = autoDelete; + } + + /** + * Sets the widget's ability to emit text completion and + * rotation signals. + * + * Invoking this function with @p enable set to @p false will + * cause the completion & rotation signals not to be emitted. + * However, unlike setting the completion object to @p NULL + * using @ref setCompletionObject, disabling the emition of + * the signals through this method does not affect the current + * completion object. + * + * There is no need to invoke this function by default. When a + * completion object is created through @ref completionObject or + * @ref setCompletionObject, these signals are set to emit + * automatically. Also note that disabling this signals will not + * necessarily interfere with the objects ability to handle these + * events internally. See @ref setHandleSignals. + * + * @param enable if false, disables the emition of completion & rotation signals. + */ + void setEnableSignals( bool enable ) { + if ( m_delegate ) + m_delegate->setEnableSignals( enable ); + else + m_bEmitSignals = enable; + } + + /** + * Returns true if the object handles the signals + * + * @return true if this signals are handled internally. + */ + bool handleSignals() const { return m_delegate ? m_delegate->handleSignals() : m_bHandleSignals; } + + /** + * Returns true if the object emits the signals + * + * @return true if signals are emitted + */ + bool emitSignals() const { return m_delegate ? m_delegate->emitSignals() : m_bEmitSignals; } + + /** + * Sets the type of completion to be used. + * + * The completion modes supported are those defined in + * @ref OGlobalSettings(). See below. + * + * @param mode Completion type: + * @li CompletionNone: Disables completion feature. + * @li CompletionAuto: Attempts to find a match & + * fills-in the remaining text. + * @li CompletionMan: Acts the same as the above + * except the action has to be + * manually triggered through + * pre-defined completion key. + * @li CompletionShell: Mimics the completion feature + * found in typical *nix shell + * environments. + * @li CompletionPopup: Shows all available completions at once, + * in a listbox popping up. + */ + virtual void setCompletionMode( OGlobalSettings::Completion mode ); + + /** + * Returns the current completion mode. + * + * The return values are of type @ref OGlobalSettings::Completion. + * See @ref setCompletionMode() for details. + * + * @return the completion mode. + */ + OGlobalSettings::Completion completionMode() const { + return m_delegate ? m_delegate->completionMode() : m_iCompletionMode; + } + + /** + * Sets the key-binding to be used for manual text + * completion, text rotation in a history list as + * well as a completion list. + * + * + * When the keys set by this function are pressed, a + * signal defined by the inheriting widget will be activated. + * If the default value or 0 is specified by the second + * parameter, then the key-binding as defined in the global + * setting should be used. This method returns false value + * for @p key is negative or the supplied key-binding conflicts + * with the ones set for one of the other features. + * + * NOTE: To use a modifier key (Shift, Ctrl, Alt) as part of + * the key-binding simply simply @p sum up the values of the + * modifier and the actual key. For example, to use CTRL+E as + * a key binding for one of the items, you would simply supply + * @p "Qt::CtrlButton + Qt::Key_E" as the second argument to this + * function. + * + * @param item the feature whose key-binding needs to be set: + * + * @li TextCompletion the manual completion key-binding. + * @li PrevCompletionMatch the previous match key for multiple completion. + * @li NextCompletionMatch the next match key for for multiple completion. + * @li SubstringCompletion the key for substring completion + * + * @param key key-binding used to rotate down in a list. + * + * @return true if key-binding can successfully be set. + * @see #getKeyBinding + */ + bool setKeyBinding( KeyBindingType /*item*/ , const OShortcut& cut ); + + /** + * Returns the key-binding used for the specified item. + * + * This methods returns the key-binding used to activate + * the feature feature given by @p item. If the binding + * contains modifier key(s), the SUM of the modifier key + * and the actual key code are returned. + * + * @return the key-binding used for the feature given by @p item. + * @see #setKeyBinding + */ + const OShortcut& getKeyBinding( KeyBindingType item ) const { + return m_delegate ? m_delegate->getKeyBinding( item ) : m_keyMap[ item ]; + } + + /** + * Sets this object to use global values for key-bindings. + * + * This method changes the values of the key bindings for + * rotation and completion features to the default values + * provided in OGlobalSettings. + * + * NOTE: By default inheriting widgets should uses the + * global key-bindings so that there will be no need to + * call this method. + */ + void useGlobalKeyBindings(); + + /** + * A pure virtual function that must be implemented by + * all inheriting classes. + * + * This function is intended to allow external completion + * implementations to set completed text appropriately. It + * is mostly relevant when the completion mode is set to + * CompletionAuto and CompletionManual modes. See + * @ref OCompletionBase::setCompletedText. + * Does nothing in CompletionPopup mode, as all available + * matches will be shown in the popup. + * + * @param text the completed text to be set in the widget. + */ + virtual void setCompletedText( const QString& text ) = 0; + + /** + * A pure virtual function that must be implemented by + * all inheriting classes. + * + */ + virtual void setCompletedItems( const QStringList& items ) = 0; + + /** + * Returns a pointer to the completion object. + * + * This method is only different from @ref completionObject() + * in that it does not create a new OCompletion object even if + * the internal pointer is @p NULL. Use this method to get the + * pointer to a completion object when inheriting so that you + * won't inadvertently create it!! + * + * @returns the completion object or NULL if one does not exist. + */ + OCompletion* compObj() const { return m_delegate ? m_delegate->compObj() : (OCompletion*) m_pCompObj; } + +protected: + /** + * Returns a key-binding map + * + * This method is the same as @ref getKeyBinding() except it + * returns the whole keymap containing the key-bindings. + * + * @return the key-binding used for the feature given by @p item. + */ + KeyBindingMap getKeyBindings() const { return m_delegate ? m_delegate->getKeyBindings() : m_keyMap; } + + void setDelegate( OCompletionBase *delegate ); + OCompletionBase *delegate() const { return m_delegate; } + +private: + // This method simply sets the autodelete boolean for + // the completion object, the emit signals and handle + // signals internally flags to the provided values. + void setup( bool, bool, bool ); + + // Flag that determined whether the completion object + // should be deleted when this object is destroyed. + bool m_bAutoDelCompObj; + // Determines whether this widget handles completion signals + // internally or not + bool m_bHandleSignals; + // Determines whether this widget fires rotation signals + bool m_bEmitSignals; + // Stores the completion mode locally. + OGlobalSettings::Completion m_iCompletionMode; + // Pointer to Completion object. + QGuardedPtr m_pCompObj; + // Keybindings + KeyBindingMap m_keyMap; + // we may act as a proxy to another OCompletionBase object + OCompletionBase *m_delegate; + + // FIXME: Revise this for Opie? + //protected: + // virtual void virtual_hook( int id, void* data ); + private: + OCompletionBasePrivate *d; +}; + +#endif // OCOMPLETIONBASE_H + diff --git a/libopie2/qt3/opiecore/opair.h b/libopie2/qt3/opiecore/opair.h new file mode 100644 index 0000000..26f617d --- a/dev/null +++ b/libopie2/qt3/opiecore/opair.h @@ -0,0 +1,99 @@ +// QPair minus QT_INLINE_TEMPLATE (instead directly using 'inline' directive) +//FIXME: remove and use qpair.h as soon as we're on Qt3 + +/**************************************************************************** +** +** Definition of QPair class +** +** +** Copyright (C) 1992-2001 Trolltech AS. All rights reserved. +** +** This file is part of the tools module of the Qt GUI Toolkit. +** +** This file may be distributed under the terms of the Q Public License +** as defined by Trolltech AS of Norway and appearing in the file +** LICENSE.QPL included in the packaging of this file. +** +** This file may be distributed and/or modified under the terms of the +** GNU General Public License version 2 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. +** +** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition +** licenses may use this file in accordance with the Qt Commercial License +** Agreement provided with the Software. +** +** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +** +** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for +** information about Qt Commercial License Agreements. +** See http://www.trolltech.com/qpl/ for QPL licensing information. +** See http://www.trolltech.com/gpl/ for GPL licensing information. +** +** Contact info@trolltech.com if any conditions of this licensing are +** not clear to you. +** +**********************************************************************/ + +#ifndef QPAIR_H +#define QPAIR_H + +#ifndef QT_H +#include "qglobal.h" +#include "qdatastream.h" +#endif // QT_H + +template +struct QPair +{ + typedef T1 first_type; + typedef T2 second_type; + + QPair() + : first( T1() ), second( T2() ) + {} + QPair( const T1& t1, const T2& t2 ) + : first( t1 ), second( t2 ) + {} + + T1 first; + T2 second; +}; + +template +inline bool operator==( const QPair& x, const QPair& y ) +{ + return x.first == y.first && x.second == y.second; +} + +template +inline bool operator<( const QPair& x, const QPair& y ) +{ + return x.first < y.first || + ( !( y.first < x.first ) && x.second < y.second ); +} + +template +inline QPair qMakePair( const T1& x, const T2& y ) +{ + return QPair( x, y ); +} + +#ifndef QT_NO_DATASTREAM +template +inline QDataStream& operator>>( QDataStream& s, QPair& p ) +{ + s >> p.first >> p.second; + return s; +} + +template +inline QDataStream& operator<<( QDataStream& s, const QPair& p ) +{ + s << p.first << p.second; + return s; +} +#endif + +#endif diff --git a/libopie2/qt3/opiecore/osortablevaluelist.h b/libopie2/qt3/opiecore/osortablevaluelist.h new file mode 100644 index 0000000..f66cf25 --- a/dev/null +++ b/libopie2/qt3/opiecore/osortablevaluelist.h @@ -0,0 +1,117 @@ +/* +                 This file is part of the Opie Project + Originally a part of the KDE Project + (C) 2001 Carsten Pfeiffer + =. + .=l. +           .>+-= + _;:,     .>    :=|. This program is free software; you can +.> <`_,   >  .   <= redistribute it and/or modify it under +:`=1 )Y*s>-.--   : the terms of the GNU Library General Public +.="- .-=="i,     .._ License as published by the Free Software + - .   .-<_>     .<> Foundation; either version 2 of the License, +     ._= =}       : or (at your option) any later version. +    .%`+i>       _;_. +    .i_,=:_.      -`: PARTICULAR PURPOSE. See the GNU +..}^=.=       =       ; Library General Public License for more +++=   -.     .`     .: details. + :     =  ...= . :.=- + -.   .:....=;==+<; You should have received a copy of the GNU +  -_. . .   )=.  = Library General Public License along with +    --        :-=` this library; see the file COPYING.LIB. + If not, write to the Free Software Foundation, + Inc., 59 Temple Place - Suite 330, + Boston, MA 02111-1307, USA. +*/ + +#ifndef OSORTABLEVALUELIST_H +#define OSORTABLEVALUELIST_H + +#if QT_VERSION > 290 +#include +#include +#else +#include +#include +#endif +#include + +template class OSortableItem : public QPair +{ +public: + OSortableItem( Key i, const T& t ) : QPair( i, t ) {} + OSortableItem( const OSortableItem &rhs ) + : QPair( rhs.first, rhs.second ) {} + + OSortableItem() {} + + OSortableItem &operator=( const OSortableItem& i ) { + first = i.first; + second = i.second; + return *this; + } + + // operators for sorting + bool operator> ( const OSortableItem& i2 ) const { + return (i2.first < first); + } + bool operator< ( const OSortableItem& i2 ) const { + return (first < i2.first); + } + bool operator>= ( const OSortableItem& i2 ) const { + return (first >= i2.first); + } + bool operator<= ( const OSortableItem& i2 ) const { + return !(i2.first < first); + } + bool operator== ( const OSortableItem& i2 ) const { + return (first == i2.first); + } + bool operator!= ( const OSortableItem& i2 ) const { + return (first != i2.first); + } + + T& value() { + return second; + } + const T& value() const { + return second; + } + + Key index() const { + return first; + } +}; + + +// convenience +template +class OSortableValueList : public QValueList > +{ +public: + void insert( Key i, const T& t ) { + QValueList >::append( OSortableItem( i, t ) ); + } + // add more as you please... + + T& operator[]( Key i ) { + return QValueList >::operator[]( i ).value(); + } + const T& operator[]( Key i ) const { + return QValueList >::operator[]( i ).value(); + } + + void sort() { + qHeapSort( *this ); + } +}; + +// template class OSortableValueListIterator : public QValueListIterator > +// { +// }; + +#endif // OSORTABLEVALUELIST_H diff --git a/libopie2/qt3/opiecore/otl.h b/libopie2/qt3/opiecore/otl.h new file mode 100644 index 0000000..ee2a28e --- a/dev/null +++ b/libopie2/qt3/opiecore/otl.h @@ -0,0 +1,325 @@ +// qtl minus QT_INLINE_TEMPLATE and QT_EXPLICIT (instead directly using 'inline' directive) +//FIXME: remove and use qtl.h as soon as we're on Qt3 + +/**************************************************************************** +** $Id$ +** +** Definition of Qt template library classes +** +** Created : 990128 +** +** Copyright (C) 1992-2000 Trolltech AS. All rights reserved. +** +** This file is part of the tools module of the Qt GUI Toolkit. +** +** This file may be distributed under the terms of the Q Public License +** as defined by Trolltech AS of Norway and appearing in the file +** LICENSE.QPL included in the packaging of this file. +** +** This file may be distributed and/or modified under the terms of the +** GNU General Public License version 2 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. +** +** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition +** licenses may use this file in accordance with the Qt Commercial License +** Agreement provided with the Software. +** +** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +** +** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for +** information about Qt Commercial License Agreements. +** See http://www.trolltech.com/qpl/ for QPL licensing information. +** See http://www.trolltech.com/gpl/ for GPL licensing information. +** +** Contact info@trolltech.com if any conditions of this licensing are +** not clear to you. +** +**********************************************************************/ + +#ifndef QTL_H +#define QTL_H + +#ifndef QT_H +#include "qglobal.h" +#include "qtextstream.h" +#include "qstring.h" +#endif // QT_H + +#ifndef QT_NO_TEXTSTREAM +template +class QTextOStreamIterator +{ +protected: + QTextOStream& stream; + QString separator; + +public: + QTextOStreamIterator( QTextOStream& s) : stream( s ) {} + QTextOStreamIterator( QTextOStream& s, const QString& sep ) + : stream( s ), separator( sep ) {} + QTextOStreamIterator& operator= ( const T& x ) { + stream << x; + if ( !separator.isEmpty() ) + stream << separator; + return *this; + } + QTextOStreamIterator& operator*() { return *this; } + QTextOStreamIterator& operator++() { return *this; } + QTextOStreamIterator& operator++(int) { return *this; } +}; +#endif //QT_NO_TEXTSTREAM + +template +inline OutputIterator qCopy( InputIterator _begin, InputIterator _end, + OutputIterator _dest ) +{ + while( _begin != _end ) + *_dest++ = *_begin++; + return _dest; +} + +template +inline BiOutputIterator qCopyBackward( BiIterator _begin, BiIterator _end, + BiOutputIterator _dest ) +{ + while ( _begin != _end ) + *--_dest = *--_end; + return _dest; +} + +template +inline bool qEqual( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 ) +{ + // ### compare using !(*first1 == *first2) in Qt 4.0 + for ( ; first1 != last1; ++first1, ++first2 ) + if ( *first1 != *first2 ) + return FALSE; + return TRUE; +} + +template +inline void qFill( ForwardIterator first, ForwardIterator last, const T& val ) +{ + for ( ; first != last; ++first ) + *first = val; +} + +#if 0 +template +inline OutputIterator qReverseCopy( BiIterator _begin, BiIterator _end, + OutputIterator _dest ) +{ + while ( _begin != _end ) { + --_end; + *_dest = *_end; + ++_dest; + } + return _dest; +} +#endif + + +template +inline InputIterator qFind( InputIterator first, InputIterator last, + const T& val ) +{ + while ( first != last && *first != val ) + ++first; + return first; +} + +template +inline void qCount( InputIterator first, InputIterator last, const T& value, + Size& n ) +{ + for ( ; first != last; ++first ) + if ( *first == value ) + ++n; +} + +template +inline void qSwap( T& _value1, T& _value2 ) +{ + T tmp = _value1; + _value1 = _value2; + _value2 = tmp; +} + + +template +inline void qBubbleSort( InputIterator b, InputIterator e ) +{ + // Goto last element; + InputIterator last = e; + --last; + // only one element or no elements ? + if ( last == b ) + return; + + // So we have at least two elements in here + while( b != last ) { + bool swapped = FALSE; + InputIterator swap_pos = b; + InputIterator x = e; + InputIterator y = x; + y--; + do { + --x; + --y; + if ( *x < *y ) { + swapped = TRUE; + qSwap( *x, *y ); + swap_pos = y; + } + } while( y != b ); + if ( !swapped ) + return; + b = swap_pos; + b++; + } +} + + +template +inline void qBubbleSort( Container &c ) +{ + qBubbleSort( c.begin(), c.end() ); +} + + +template +inline void qHeapSortPushDown( Value* heap, int first, int last ) +{ + int r = first; + while ( r <= last / 2 ) { + if ( last == 2 * r ) { + // node r has only one child + if ( heap[2 * r] < heap[r] ) + qSwap( heap[r], heap[2 * r] ); + r = last; + } else { + // node r has two children + if ( heap[2 * r] < heap[r] && !(heap[2 * r + 1] < heap[2 * r]) ) { + // swap with left child + qSwap( heap[r], heap[2 * r] ); + r *= 2; + } else if ( heap[2 * r + 1] < heap[r] + && heap[2 * r + 1] < heap[2 * r] ) { + // swap with right child + qSwap( heap[r], heap[2 * r + 1] ); + r = 2 * r + 1; + } else { + r = last; + } + } + } +} + + +template +inline void qHeapSortHelper( InputIterator b, InputIterator e, Value, uint n ) +{ + // Create the heap + InputIterator insert = b; + Value* realheap = new Value[n]; + // Wow, what a fake. But I want the heap to be indexed as 1...n + Value* heap = realheap - 1; + int size = 0; + for( ; insert != e; ++insert ) { + heap[++size] = *insert; + int i = size; + while( i > 1 && heap[i] < heap[i / 2] ) { + qSwap( heap[i], heap[i / 2] ); + i /= 2; + } + } + + // Now do the sorting + for( uint i = n; i > 0; i-- ) { + *b++ = heap[1]; + if ( i > 1 ) { + heap[1] = heap[i]; + qHeapSortPushDown( heap, 1, (int)i - 1 ); + } + } + + delete[] realheap; +} + + +template +inline void qHeapSort( InputIterator b, InputIterator e ) +{ + // Empty ? + if ( b == e ) + return; + + // How many entries have to be sorted ? + InputIterator it = b; + uint n = 0; + while ( it != e ) { + ++n; + ++it; + } + + // The second last parameter is a hack to retrieve the value type + // Do the real sorting here + qHeapSortHelper( b, e, *b, n ); +} + + +template +inline void qHeapSort( Container &c ) +{ + if ( c.begin() == c.end() ) + return; + + // The second last parameter is a hack to retrieve the value type + // Do the real sorting here + qHeapSortHelper( c.begin(), c.end(), *(c.begin()), (uint)c.count() ); +} + +template +class QBackInsertIterator +{ +public: + QBackInsertIterator( Container &c ) + : container( &c ) + { + } + + QBackInsertIterator& + operator=( const typename Container::value_type &value ) + { + container->push_back( value ); + return *this; + } + + QBackInsertIterator& operator*() + { + return *this; + } + + QBackInsertIterator& operator++() + { + return *this; + } + + QBackInsertIterator& operator++(int) + { + return *this; + } + +protected: + Container *container; +}; + +template +inline QBackInsertIterator qBackInserter( Container &c ) +{ + return QBackInsertIterator( c ); +} + +#endif -- cgit v0.9.0.2