← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/mkgmap/oneiric

« back to all changes in this revision

Viewing changes to src/uk/me/parabola/mkgmap/reader/osm/Tags.java

  • Committer: Bazaar Package Importer
  • Author(s): Francesco Paolo Lovergine, Andreas Putzo, Francesco Paolo Lovergine
  • Date: 2009-07-16 11:10:16 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20090716111016-yycxqya1f26xmti7
Tags: 0.0.0+svn1067-1
[ Andreas Putzo ]
* New upstream snapshot.
* Added ${misc:Depends} among dependencies to fix a lintian warning.
* Bumped debhelper compatibility level to 7.
* Updated long description.
* Updated Homepage in debian/control, debian/copyright, debian/watch.
* Added numerous files from /doc to debian/docs.
* Mentioned Bernhard Heibler in debian/copyright and updated copyright
  year of software and packaging.
* Bumped policy to 3.8.2, without changes.
* Added DM-Upload-Allowed to debian/control.

[ Francesco Paolo Lovergine ]
* Added me as Uploader to avoid possible inappropriate NMU notices.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/uk/me/parabola/mkgmap/reader/osm/Tags.java
 
1
/*
 
2
 * Copyright (C) 2008 Steve Ratcliffe
 
3
 * 
 
4
 *  This program is free software; you can redistribute it and/or modify
 
5
 *  it under the terms of the GNU General Public License version 2 as
 
6
 *  published by the Free Software Foundation.
 
7
 * 
 
8
 *  This program is distributed in the hope that it will be useful,
 
9
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
 *  GNU General Public License for more details.
 
12
 * 
 
13
 * 
 
14
 * Author: Steve Ratcliffe
 
15
 * Create date: 08-Dec-2008
 
16
 */
 
17
package uk.me.parabola.mkgmap.reader.osm;
 
18
 
 
19
import java.util.Iterator;
 
20
 
 
21
/**
 
22
 * Store the tags that belong to an Element.
 
23
 *
 
24
 * Used to use a HashMap for this.  We have a requirement to be able
 
25
 * to add to the map during iteration over it so this class was written
 
26
 * instead.
 
27
 *
 
28
 * It should also uses less memory (hash maps are the main use of memory in the
 
29
 * application), as it doesn't allocate a Map.Entry object for every tag.
 
30
 * Performance of the whole application is unchanged compared with when
 
31
 * a regular HashMap was used.
 
32
 *
 
33
 * It doesn't fully behave the same way that a map would.
 
34
 *
 
35
 * @author Steve Ratcliffe
 
36
 */
 
37
public class Tags implements Iterable<String> {
 
38
        private static final int INIT_SIZE = 8;
 
39
 
 
40
        private short size;
 
41
        private short capacity;
 
42
 
 
43
        private String[] keys;
 
44
        private String[] values;
 
45
 
 
46
        // This is a flag that iteration is taking place and a place to store
 
47
        // tags that are added during iteration.
 
48
        private ExtraEntry extra;
 
49
 
 
50
        /**
 
51
         * Used for tags that are added during iteration.
 
52
         */
 
53
        static class ExtraEntry {
 
54
                private String key;
 
55
                private String value;
 
56
                private ExtraEntry next;
 
57
        }
 
58
 
 
59
        public Tags() {
 
60
                keys = new String[INIT_SIZE];
 
61
                values = new String[INIT_SIZE];
 
62
                capacity = INIT_SIZE;
 
63
        }
 
64
 
 
65
        public String get(Object key) {
 
66
                Integer ind = keyPos((String) key);
 
67
                if (ind == null)
 
68
                        return null;
 
69
                return values[ind];
 
70
        }
 
71
 
 
72
        public String put(String key, String value) {
 
73
                if (extra != null) {
 
74
                        // Deal with the case where we are adding a tag during iteration
 
75
                        // of the tags.  This is flagged by extra being non null.
 
76
                        ExtraEntry emptyEntry = extra;
 
77
                        while (emptyEntry.next != null)
 
78
                                emptyEntry = emptyEntry.next;
 
79
                        emptyEntry.key = key;
 
80
                        emptyEntry.value = value;
 
81
                        emptyEntry.next = new ExtraEntry();
 
82
                        return null;
 
83
                }
 
84
 
 
85
                ensureSpace();
 
86
                Integer ind = keyPos(key);
 
87
                if (ind == null)
 
88
                        assert false;
 
89
                keys[ind] = key;
 
90
 
 
91
                String old = values[ind];
 
92
                if (old == null)
 
93
                        size++;
 
94
                values[ind] = value;
 
95
 
 
96
                return old;
 
97
        }
 
98
 
 
99
        public String remove(Object key) {
 
100
                Integer k = keyPos((String) key);
 
101
 
 
102
                if (k != null) {
 
103
                        // because of the way this works, you can never remove keys
 
104
                        // except when resizing.
 
105
                        String old = values[k];
 
106
                        values[k] = null;
 
107
                        if (old != null)
 
108
                                size--;
 
109
                        return old;
 
110
                }
 
111
                return null;
 
112
        }
 
113
 
 
114
        /**
 
115
         * Make a deep copy of this object.
 
116
         * @return A copy of this object.
 
117
         */
 
118
        Tags copy() {
 
119
                addExtraItems();
 
120
                
 
121
                Tags cp = new Tags();
 
122
                cp.size = size;
 
123
                cp.capacity = capacity;
 
124
 
 
125
                // Copy the arrays.  (For java 1.6 we can use Arrays.copyOf().)
 
126
                cp.keys = new String[keys.length];
 
127
                System.arraycopy(keys, 0, cp.keys, 0, keys.length);
 
128
                cp.values = new String[values.length];
 
129
                System.arraycopy(values, 0, cp.values, 0, values.length);
 
130
                return cp;
 
131
        }
 
132
 
 
133
        private void ensureSpace() {
 
134
                while (size + 1 >= capacity) {
 
135
                        short ncap = (short) (capacity*2);
 
136
                        String[] okey = keys;
 
137
                        String[] oval = values;
 
138
                        keys = new String[ncap];
 
139
                        values = new String[ncap];
 
140
                        capacity = ncap;
 
141
                        for (int i = 0; i < okey.length; i++) {
 
142
                                String k = okey[i];
 
143
                                if (k != null)
 
144
                                        put(k, oval[i]);
 
145
                        }
 
146
                }
 
147
                assert size < capacity;
 
148
        }
 
149
 
 
150
        private Integer keyPos(String key) {
 
151
                int h = key.hashCode();
 
152
                int k = h & (capacity - 1);
 
153
 
 
154
                int i = k;
 
155
                do {
 
156
                        String fk = keys[i];
 
157
                        if (fk == null || fk.equals(key))
 
158
                                return i;
 
159
                        i++;
 
160
                        if (i >= capacity)
 
161
                                i = 0;
 
162
                } while (i != k);
 
163
                return null;
 
164
        }
 
165
 
 
166
        /**
 
167
         * Iterates over the tags in a special way that is used to look up in
 
168
         * the rules.
 
169
         *
 
170
         * If you have the tags a=b, c=d then you will get the following strings
 
171
         * returned: "a=b", "a=*", "c=d", "c=*".
 
172
         *
 
173
         * If you add a tag during the iteration, then it is guaranteed to
 
174
         * appear later in the iteration.
 
175
         */
 
176
        public Iterator<String> iterator() {
 
177
                return new Iterator<String>() {
 
178
                        private int pos;
 
179
                        private String wild;
 
180
                        private boolean doWild;
 
181
                        private ExtraEntry nextEntry;
 
182
 
 
183
                        // Set the extra field in the containing class.
 
184
                        {
 
185
                                addExtraItems();
 
186
                                extra = new ExtraEntry();
 
187
                                nextEntry = extra;
 
188
                        }
 
189
 
 
190
                        public boolean hasNext() {
 
191
                                // After every normal entry there is a wild card entry.
 
192
                                if (doWild)
 
193
                                        return true;
 
194
 
 
195
                                // Normal entries in the map
 
196
                                for (int i = pos; i < capacity; i++) {
 
197
                                        if (values[i] != null) {
 
198
                                                pos = i;
 
199
                                                return true;
 
200
                                        }
 
201
                                }
 
202
 
 
203
                                // Entries that were added during iteration
 
204
                                if (nextEntry != null && nextEntry.value != null)
 
205
                                        return true;
 
206
 
 
207
                                // Add everything from extra and clean up, there is no guarantee
 
208
                                // that this gets called here (because you may stop the
 
209
                                // iteration early) but in the normal case it will be called
 
210
                                // and will remove all the ExtraEntry objects, thus keeping
 
211
                                // the memory usage to a minimum.
 
212
                                addExtraItems();
 
213
                                return false;
 
214
                        }
 
215
 
 
216
                        /**
 
217
                         * Get the next tag as a single string.  Also returns wild card
 
218
                         * entries.
 
219
                         */
 
220
                        public String next() {
 
221
                                if (doWild) {
 
222
                                        doWild = false;
 
223
                                        return wild + "=*";
 
224
                                } else if (pos < capacity) {
 
225
                                        for (int i = pos; i < capacity; i++) {
 
226
                                                if (values[i] != null) {
 
227
                                                        doWild = true;
 
228
                                                        wild = keys[i];
 
229
                                                        pos = i+1;
 
230
                                                        return (keys[i] + "=" + values[i]);
 
231
                                                }
 
232
                                        }
 
233
                                        pos = capacity;
 
234
                                }
 
235
 
 
236
                                ExtraEntry ex = nextEntry;
 
237
                                if (nextEntry != null && nextEntry.value != null) {
 
238
                                        nextEntry = ex.next;
 
239
                                        doWild = true;
 
240
                                        wild = ex.key;
 
241
                                        return ex.key + '=' + ex.value;
 
242
                                }
 
243
                                return null;
 
244
                        }
 
245
 
 
246
                        public void remove() {
 
247
                                throw new UnsupportedOperationException();
 
248
                        }
 
249
                };
 
250
        }
 
251
 
 
252
        /**
 
253
         * Add the items that are in 'extra' to the map proper.
 
254
         */
 
255
        private void addExtraItems() {
 
256
                if (extra != null) {
 
257
                        ExtraEntry e = extra;
 
258
                        extra = null;
 
259
                        for (; e != null; e = e.next)
 
260
                                if (e.value != null)
 
261
                                        put(e.key, e.value);
 
262
                }
 
263
        }
 
264
}