Root/monav/unicodetournamenttrie/trie.h

1/*
2Copyright 2010 Christian Vetter veaac.fdirct@gmail.com
3
4This file is part of MoNav.
5
6MoNav is free software: you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation, either version 3 of the License, or
9(at your option) any later version.
10
11MoNav is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with MoNav. If not, see <http://www.gnu.org/licenses/>.
18*/
19
20#ifndef TRIE_H
21#define TRIE_H
22
23#include <QString>
24#include <vector>
25#include "utils/coordinates.h"
26#include "utils/bithelpers.h"
27
28namespace utt
29{
30
31struct CityData {
32    UnsignedCoordinate coordinate;
33
34    size_t GetSize() const {
35        return 2 * sizeof( unsigned );
36    }
37
38    void Write( char* buffer ) const {
39        *( ( unsigned* ) buffer ) = coordinate.x;
40        buffer += sizeof( unsigned );
41        *( ( unsigned* ) buffer ) = coordinate.y;
42    }
43
44    void Read( const char* buffer ) {
45        coordinate.x = readUnaligned< unsigned >( buffer );
46        buffer += sizeof( unsigned );
47        coordinate.y = readUnaligned< unsigned >( buffer );
48    }
49};
50
51struct Data {
52    unsigned start;
53    unsigned short length;
54
55    size_t GetSize() const {
56        return sizeof( unsigned ) + sizeof( unsigned short );
57    }
58
59    void Write( char* buffer ) const {
60        *( ( unsigned* ) buffer ) = start;
61        buffer += sizeof( unsigned );
62        *( ( unsigned short* ) buffer ) = length;
63    }
64
65    void Read( const char* buffer ) {
66        start = readUnaligned< unsigned >( buffer );
67        buffer += sizeof( unsigned );
68        length = readUnaligned< unsigned short >( buffer );
69    }
70
71    bool operator==( const Data& right ) const {
72        return start == right.start && length == right.length;
73    }
74};
75
76struct Label {
77    QString string;
78    unsigned index;
79    unsigned importance;
80
81    bool operator<( const Label& right ) const {
82        if ( importance != right.importance )
83            return importance > right.importance;
84        return string < right.string;
85    }
86
87    bool operator==( const Label& right ) const {
88        return string == right.string && importance == right.importance;
89    }
90
91    size_t GetSize() const {
92        size_t result = 0;
93        result += sizeof( unsigned );
94        result += sizeof( unsigned );
95        result += strlen( string.toUtf8().constData() ) + 1;
96        return result;
97    }
98
99    void Write( char* buffer ) const {
100        *( ( unsigned* ) buffer ) = index;
101        buffer += sizeof( unsigned );
102        *( ( unsigned* ) buffer ) = importance;
103        buffer += sizeof( unsigned );
104        strcpy( buffer, string.toUtf8().constData() );
105    }
106
107    void Read( const char* buffer ) {
108        index = readUnaligned< unsigned >( buffer );
109        buffer += sizeof( unsigned );
110        importance = readUnaligned< unsigned >( buffer );
111        buffer += sizeof( unsigned );
112        string = QString::fromUtf8( buffer );
113    }
114};
115
116struct Node {
117    std::vector< Data > dataList;
118    std::vector< Label > labelList;
119
120    size_t GetSize() const {
121        size_t result = 0;
122        result += sizeof( short );
123        if ( dataList.size() != 0 )
124            result += sizeof( unsigned short );
125        for ( int i = 0; i < ( int ) labelList.size(); i++ )
126            result += labelList[i].GetSize();
127        for ( int i = 0; i < ( int ) dataList.size(); i++ )
128            result += dataList[i].GetSize();
129        return result;
130    }
131
132    void Write( char* buffer ) const {
133        assert( ( int ) labelList.size() <= std::numeric_limits< short >::max() );
134        assert( dataList.size() <= std::numeric_limits< unsigned short >::max() );
135        *( ( short* ) buffer ) = labelList.size() * ( dataList.size() > 0 ? -1 : 1 );
136        buffer += sizeof( short );
137        if ( dataList.size() > 0 ) {
138            *( ( unsigned short* ) buffer ) = dataList.size();
139            buffer += sizeof( unsigned short );
140        }
141        for ( int i = 0; i < ( int ) labelList.size(); i++ ) {
142            labelList[i].Write( buffer );
143            buffer += labelList[i].GetSize();
144        }
145        for ( int i = 0; i < ( int ) dataList.size(); i++ ) {
146            dataList[i].Write( buffer );
147            buffer += dataList[i].GetSize();
148        }
149    }
150
151    void Read( const char* buffer ) {
152        short labelSize = readUnaligned< short >( buffer );
153        labelList.resize( labelSize >= 0 ? labelSize : -labelSize );
154        buffer += sizeof( unsigned short );
155        if ( labelSize <= 0 ) {
156            dataList.resize( readUnaligned< unsigned short >( buffer ) );
157            buffer += sizeof( unsigned short );
158        }
159        for( int i = 0; i < ( int ) labelList.size(); i++ ) {
160            labelList[i].Read( buffer );
161            buffer += labelList[i].GetSize();
162        }
163        for( int i = 0; i < ( int ) dataList.size(); i++ ) {
164            dataList[i].Read( buffer );
165            buffer += dataList[i].GetSize();
166        }
167    }
168
169    bool operator== ( const Node& right ) const {
170        if ( dataList.size() != right.dataList.size() )
171            return false;
172        if ( labelList.size() != right.labelList.size() )
173            return false;
174        for ( int i = 0; i < ( int ) dataList.size(); ++i ) {
175            if ( !( dataList[i] == right.dataList[i] ) )
176                return false;
177        }
178        for ( int i = 0; i < ( int ) labelList.size(); ++i ) {
179            if ( !( labelList[i] == right.labelList[i] ) )
180                return false;
181        }
182        return true;
183    }
184};
185
186}
187
188#endif // TRIE_H
189

Archive Download this file

Branches:
master



interactive