qdawg.cpp

Trolltech公司发布的图形界面操作系统。可在qt-embedded-2.3.10平台上编译为嵌入式图形界面操作系统。

/**********************************************************************
** Copyright (C) 2000-2005 Trolltech AS.  All rights reserved.
**
** This file is part of the Qtopia Environment.
** 
** This program is free software; you can redistribute it and/or modify it
** under the terms of the GNU General Public License as published by the
** Free Software Foundation; either version 2 of the License, or (at your
** option) any later version.
** 
** A copy of the GNU GPL license version 2 is included in this package as 
** LICENSE.GPL.
**
** This program is distributed in the hope that it will be useful, but
** WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 
** See the GNU General Public License for more details.
**
** In addition, as a special exception Trolltech gives permission to link
** the code of this program with Qtopia applications copyrighted, developed
** and distributed by Trolltech under the terms of the Qtopia Personal Use
** License Agreement. You must comply with the GNU General Public License
** in all respects for all of the code used other than the applications
** licensed under the Qtopia Personal Use License Agreement. If you modify
** this file, you may extend this exception to your version of the file,
** but you are not obligated to do so. If you do not wish to do so, delete
** this exception statement from your version.
** 
** See http://www.trolltech.com/gpl/ for GPL licensing information.
**
** Contact [e-mail] if any conditions of this licensing are
** not clear to you.
**
**********************************************************************/
#include "qdawg.h"
#include <qintdict.h>
#include <qvaluelist.h>
#include <qtextstream.h>
#include <qfile.h>
#include <qtl.h>

#include <limits.h>
#include <stdio.h>

#include "qmemoryfile_p.h"

class QDawgPrivate;
class QTrie;

typedef QValueList<QTrie*> TrieClub;
typedef QIntDict<TrieClub> TrieClubDirectory;

class TriePtr {
public:
    QChar letter;
    QTrie* p;
    int operator <(const TriePtr& o) const;
    int operator >(const TriePtr& o) const;
    int operator <=(const TriePtr& o) const;
};

class TrieList : public QValueList<TriePtr> {
    bool sorted;
public:
    TrieList()
    {
	sorted=TRUE;
    }

    QTrie* findAdd(QChar c);
    bool equal(TrieList& l);

    void sort()
    {
	if ( !sorted ) {
	    qHeapSort(*this);
	    sorted = TRUE;
	}
    }
};

// A fast but memory-wasting temporary class.  The Dawg is the goal.
class QTrie {
public:
    QTrie();
    ~QTrie();

    void insertWord(const QString& s, uint index=0);
    bool equal(QTrie* o);
    void dump(int indent=0);

private:
    TrieList children;
    bool isword;

    friend class QDawgPrivate;
    int maxdepth;
    int decendants;
    int key;
    void distributeKeys(TrieClubDirectory& directory);
    QTrie* clubLeader(TrieClubDirectory& directory);
    int collectKeys();
    friend class TriePtr;
    friend class TrieList;
};

QTrie::QTrie()
{
    key = 0;
    isword = FALSE;
}

QTrie::~QTrie()
{
    // NOTE: we do not delete the children - after conversion to DAWG
    // it's too difficult.  The QTrie's are deleted via the directory.
}

void QTrie::insertWord(const QString& s, uint index)
{
    if ( index == s.length() ) {
	isword = TRUE;
    } else {
	QTrie* t = children.findAdd(s[(int)index]);
	t->insertWord(s,index+1);
    }
}

bool QTrie::equal(QTrie* o)
{
    if ( o == this ) return TRUE;
    if ( isword != o->isword )
	return FALSE;
    return children.equal(o->children);
}

void QTrie::dump(int indent)
{
    for (TrieList::Iterator it=children.begin(); it!=children.end(); ++it) {
	QTrie* s = (*it).p;
	for (int in=0; in<indent; in++)
	    fputc(' ',stderr);
	fprintf(stderr," %c %d %s %p\n",(*it).letter.unicode(),
	    s->key,s->isword?"word":"",s); // No tr
	s->dump(indent+2);
    }
}

void QTrie::distributeKeys(TrieClubDirectory& directory)
{
    maxdepth = INT_MIN;
    decendants = children.count();
    key = 0;
    for (TrieList::Iterator it=children.begin(); it!=children.end(); ++it) {
	QTrie* s = (*it).p;
	QChar l = (*it).letter;
	s->distributeKeys(directory);
	key = key*64+l.unicode()+s->key*5;
	decendants += s->decendants;
	if ( s->maxdepth+1 > maxdepth )
	    maxdepth = s->maxdepth+1;
    }
    if ( decendants ) {
	key += decendants + maxdepth*256 + children.count() * 65536;
	if ( !key ) key++; // unlikely
    }
    TrieClub* c = directory[key];
    if ( !c ) directory.insert(key, (c = new TrieClub) );
    c->prepend(this);
}

QTrie* QTrie::clubLeader(TrieClubDirectory& directory)
{
    if ( !key ) return directory[0]->first();
    for (TrieList::Iterator itList=children.begin(); 
	 itList!=children.end(); ++itList) {
	QTrie* t= (*itList).p->clubLeader(directory);
	(*itList).p = t;
    }
    TrieClub *club = directory[key];
    for (TrieClub::Iterator itClub = club->begin(); 
	 itClub != club->end(); ++itClub) {
	QTrie* o = *itClub;
	if ( o->equal(this) )
	    return o;
    }
    return this;
}

int QTrie::collectKeys()
{
    int n=0;
    if ( key ) key=0,n+=children.count();
    for (TrieList::Iterator it=children.begin(); it!=children.end(); ++it)
	n += (*it).p->collectKeys();
    return n;
}

int TriePtr::operator <(const TriePtr& o) const
    { return letter < o.letter; }
int TriePtr::operator >(const TriePtr& o) const
    { return letter > o.letter; }
int TriePtr::operator <=(const TriePtr& o) const
    { return letter <= o.letter; }

bool TrieList::equal(TrieList& l)
{
    if ( count() != l.count() )
	return FALSE;
    sort(); l.sort();
    ConstIterator it2 = begin();
    ConstIterator it = l.begin();
    for( ; it != l.end(); ++it, ++it2 )
	if ( (*it).letter != (*it2).letter || ! (*it).p->equal((*it2).p) )
	    return FALSE;
    return TRUE;
}
QTrie* TrieList::findAdd(QChar c)
{
    for (Iterator it=begin(); it!=end(); ++it) {
	if ( (*it).letter == c )
	    return (*it).p;
    }
    TriePtr p;
    p.p = new QTrie;
    p.letter = c;
    prepend(p);
    sorted=FALSE;
    sort();
    return p.p;
}

static const char* dawg_sig32 = "QDAWG100"; //32 bit Node
static const char* dawg_sig64 = "QDAWG200"; //64 bit Node

class Node32 { //old QDawg Node (32 bit size) - for compatibility only 
	friend class QDawgPrivate;
	uint let:12;
	uint isword:1;
	uint islast:1;
	int offset:18;
	Node32() { }
    public:
	QChar letter() const { return QChar((ushort)let); }
	bool isWord() const { return isword; }
	bool isLast() const { return islast; }
	const Node32* next() const { return islast ? 0 : this+1; }
	const Node32* jump() const { return offset ? this+offset : 0; }
};

class QDawgPrivate {
public:
    QDawgPrivate(QIODevice* dev)
    {
	memoryFile = 0;
	QDataStream ds(dev);
	char sig[8];
	ds.readRawBytes(sig,8);
        if ( !strncmp(dawg_sig32,sig,8) ) { 
            qDebug("QDawg: Reading old dawg file format");
            uint n;
            char * nn;
            ds.readBytes(nn,n);

            Node32* node32 = (Node32*)nn;
            nodes = n / sizeof(Node32);
            //convert to QDawg::Node
            node = new QDawg::Node[nodes];
            for (int index = 0; index<nodes; index++) {
                QDawg::Node* node40 = &(node[index]);
                node40->let = node32[index].let;
                node40->isword = node32[index].isword;
                node40->islast = node32[index].islast;
                node40->offset = node32[index].offset;
            }
            delete[] node32;
            
        } else if ( !strncmp(dawg_sig64,sig,8) ) {
            qDebug("QDawg: Reading new dawg file format");
	    uint n;
	    char* nn;
	    ds.readBytes(nn,n);
            
	    // #### endianness problem ignored.
	    node = (QDawg::Node*)nn;
	    nodes = n / sizeof(QDawg::Node);
	} else {
	    node = 0;
	}
    }

    bool ok() const { return node; }

    QDawgPrivate::~QDawgPrivate()
    {
	delete memoryFile;
    }

private:
    QMemoryFile *memoryFile;

public:

    QDawgPrivate(const QString &fileName)
    {
	node = 0;
	nodes = 0;
	uchar* mem = 0;
	memoryFile = new QMemoryFile(fileName);
	if (memoryFile)
	    mem = (uchar*)memoryFile->data();
        
        if (mem) {
            if (!strncmp(dawg_sig32, (char*)mem,8)) {
                qDebug("QDawg: Reading old dawg file format");
                mem += 8;
                
    	        //int n = ((mem[0]*256+mem[1])*256+mem[2])*256+mem[3];
                int n = memoryFile->size() - 12; // 8 bytes signature, 4 bytes file size
    	        mem += 4;
                Node32* node32 = (Node32*)((char*)mem);
                nodes = n / sizeof(Node32);
                //convert to QDawg::Node
                node = new QDawg::Node[nodes];
                for (int index = 0; index<nodes; index++) {
                    QDawg::Node* node40 = &(node[index]);
                    node40->let = node32[index].let;
                    node40->isword = node32[index].isword;
                    node40->islast = node32[index].islast;
                    node40->offset = node32[index].offset;
                }
            } else if (!strncmp(dawg_sig64, (char*)mem, 8)) {
                qDebug("QDawg: Reading new dawg file format");
                mem += 8;
                int n = memoryFile->size() - 12;
    	        mem += 4;
                /*char * a = (char*)mem;
                for (int i = 0; i < memoryFile->size()-12; i++) {
                    if ((i % 8) == 0)
                        printf("\n");
                    printf(" %x ", (unsigned char)*a);
                    a++;
                }
                printf("\n");*/

	        // #### endianness problem ignored.
	        node = (QDawg::Node*)((char*)mem);
	        nodes = n / sizeof(QDawg::Node);
            }
        }
    }

    QDawgPrivate(QTrie* t) // destroys the QTrie.
    {
	memoryFile = 0;
	TrieClubDirectory directory(9973);
	t->distributeKeys(directory);
	QTrie* l = t->clubLeader(directory);
	ASSERT(l==t);
	generateArray(t);

	TrieClub *club;
	for (QIntDictIterator<TrieClub> dit(directory); (club=dit); ++dit)
	{
	    for (TrieClub::Iterator it = club->begin(); it != club->end(); ++it) {
		delete *it;
	    }