Root/monav/gpsgrid/table.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 TABLE_H
21#define TABLE_H
22
23#include <QtGlobal>
24#include <QCache>
25#include <QFile>
26#include <string.h>
27#include <vector>
28#include <QtDebug>
29
30namespace gg {
31
32    template< class T, int size >
33    struct IndexTable {
34        T index[size * size];
35        IndexTable()
36        {
37            for ( int i = 0; i < size * size; i++ )
38                index[i] = -1;
39        }
40        IndexTable( const char* buffer )
41        {
42            Read( buffer );
43        }
44
45        T GetIndex( int x, int y ) const
46        {
47            if ( x < 0 || x >= 32 )
48                return -1;
49            if ( y < 0 || y >= 32 )
50                return -1;
51            return index[x + y * size];
52        }
53
54        void SetIndex( int x, int y, T data )
55        {
56            assert( x >= 0 );
57            assert( x < 32 );
58            assert( y >= 0 );
59            assert( y < 32 );
60            assert( index[x + y *size] == -1 );
61            index[x + y * size] = data;
62        }
63
64        static size_t Size()
65        {
66            return size * size * sizeof( T );
67        }
68
69        void Write( char* buffer ) const
70        {
71            memcpy( buffer, index, size * size * sizeof( T ) );
72        }
73
74        void Read( const char* buffer )
75        {
76            memcpy( index, buffer, size * size * sizeof( T ) );
77        }
78
79        void Debug()
80        {
81            for ( int i = 0; i < size; i++ ) {
82                QString row;
83                for ( int j = 0; j < size; j++)
84                    row += GetIndex( i, j ) == -1 ? "." : "#";
85                qDebug() << row;
86            }
87        }
88    };
89
90    struct GridIndex {
91        qint64 position;
92        int x;
93        int y;
94    };
95
96    class Index {
97
98    public:
99        Index( QString filename ) :
100                file2( filename + "_2" ), file3( filename + "_3" )
101        {
102            QFile file1( filename + "_1" );
103            file1.open( QIODevice::ReadOnly );
104            top.Read( file1.read( top.Size() ).constData() );
105            file2.open( QIODevice::ReadOnly );
106            file3.open( QIODevice::ReadOnly );
107        }
108
109        qint64 GetIndex( int x, int y ) {
110            int topx = x / 32 / 32;
111            int topy = y / 32 / 32;
112            int middle = top.GetIndex( topx, topy );
113            if ( middle == -1 )
114                return -1;
115
116            int middlex = ( x / 32 ) % 32;
117            int middley = ( y / 32 ) % 32;
118            if ( !cache2.contains( middle ) ) {
119                IndexTable< int, 32 >* newEntry;
120                file2.seek( middle * newEntry->Size() );
121                newEntry = new IndexTable< int, 32 >( file2.read( newEntry->Size() ) );
122                cache2.insert( middle, newEntry, newEntry->Size() );
123            }
124            if ( !cache2.contains( middle ) )
125                return -1;
126            IndexTable< int, 32 >* middleTable = cache2.object( middle );
127            int bottom = middleTable->GetIndex( middlex, middley );
128            if ( bottom == -1 )
129                return -1;
130
131            int bottomx = x % 32;
132            int bottomy = y % 32;
133            if ( !cache3.contains( bottom ) ) {
134                IndexTable< qint64, 32 >* newEntry;
135                file3.seek( bottom * newEntry->Size() );
136                newEntry = new IndexTable< qint64, 32 >( file3.read( newEntry->Size() ) );
137                cache3.insert( bottom, newEntry, newEntry->Size() );
138            }
139            if ( !cache3.contains( bottom ) )
140                return -1;
141            IndexTable< qint64, 32 >* bottomTable = cache3.object( bottom );
142            qint64 position = bottomTable->GetIndex( bottomx, bottomy );
143            return position;
144        }
145
146        void SetCacheSize( long long size )
147        {
148            assert( size > 0 );
149            cache2.setMaxCost( size / 4 );
150            cache3.setMaxCost( 3 * size / 4 );
151        }
152
153        static void Create( QString filename, const std::vector< GridIndex >& data )
154        {
155            gg::IndexTable< int, 32 > top;
156            std::vector< gg::IndexTable< int, 32 > > middle;
157            std::vector< gg::IndexTable< qint64, 32 > > bottom;
158
159            for ( std::vector< GridIndex >::const_iterator i = data.begin(), iend = data.end(); i != iend; i++ ) {
160                int topx = i->x / 32 / 32;
161                int topy = i->y / 32 / 32;
162                int middleIndex = top.GetIndex( topx, topy );
163                if ( middleIndex == -1 ) {
164                    middleIndex = middle.size();
165                    top.SetIndex( topx, topy, middleIndex );
166                    middle.push_back( gg::IndexTable< int, 32 >() );
167                }
168
169                int middlex = ( i->x / 32 ) % 32;
170                int middley = ( i->y / 32 ) % 32;
171                int bottomIndex = middle[middleIndex].GetIndex( middlex, middley );
172                if ( bottomIndex == -1 ) {
173                    bottomIndex = bottom.size();
174                    middle[middleIndex].SetIndex( middlex, middley, bottomIndex );
175                    bottom.push_back( IndexTable< qint64, 32 >() );
176                }
177
178                int bottomx = i->x % 32;
179                int bottomy = i->y % 32;
180                bottom[bottomIndex].SetIndex( bottomx, bottomy, i->position );
181            }
182
183            qDebug() << "GPS Grid: top index filled: " << ( double ) middle.size() * 100 / 32 / 32 << "%";
184            qDebug() << "GPS Grid: middle tables: " << middle.size();
185            qDebug() << "GPS Grid: middle index filled: " << ( double ) bottom.size() * 100 / middle.size() / 32 / 32 << "%";
186            qDebug() << "GPS Grid: bottom tables: " << bottom.size();
187            qDebug() << "GPS Grid: bottom index filled: " << ( double ) data.size() * 100 / bottom.size() / 32 / 32 << "%";
188            qDebug() << "GPS Grid: grid cells: " << data.size();
189
190            QFile file1( filename + "_1" );
191            QFile file2( filename + "_2" );
192            QFile file3( filename + "_3" );
193            file1.open( QIODevice::WriteOnly );
194            file2.open( QIODevice::WriteOnly );
195            file3.open( QIODevice::WriteOnly );
196
197            char* buffer = new char[IndexTable< qint64, 32 >::Size()];
198
199            top.Write( buffer );
200            file1.write( buffer, IndexTable< int, 32 >::Size() );
201
202            for ( int i = 0; i < ( int ) middle.size(); i++ ) {
203                middle[i].Write( buffer );
204                file2.write( buffer, IndexTable< int, 32 >::Size() );
205            }
206
207            for ( int i = 0; i < ( int ) bottom.size(); i++ ) {
208                bottom[i].Write( buffer );
209                file3.write( buffer, IndexTable< qint64, 32 >::Size() );
210            }
211
212            delete[] buffer;
213        }
214
215    private:
216        QFile file2;
217        QFile file3;
218        IndexTable< int, 32 > top;
219        QCache< int, IndexTable< int, 32 > > cache2;
220        QCache< int, IndexTable< qint64, 32 > > cache3;
221    };
222}
223
224#endif // TABLE_H
225

Archive Download this file

Branches:
master



interactive