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/ocompletion.cpp') 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 );*/ } -- cgit v0.9.0.2