Subversion Repositories mkgmap

/*
 * Copyright (C) 2008 - 2012.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 3 or
 * version 2 as published by the Free Software Foundation.
 *
 * 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.
 */

package uk.me.parabola.mkgmap.reader.osm;

import java.util.AbstractMap;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;

/**
 * Store the tags that belong to an Element.
 *
 * Used to use a HashMap for this.  We used to have a requirement to be able
 * to add to the map during iteration over it but now the main reason
 * to keep this class is that it is more memory efficient than a regular
 * HashMap (hash maps are the main use of memory in the
 * application), as it doesn't allocate a Map.Entry object for every tag.
 * Performance of the whole application is unchanged compared with when
 * a regular HashMap was used.
 *
 * It doesn't fully behave the same way that a map would.
 *
 * @author Steve Ratcliffe
 */
public class Tags implements Iterable<String> {
        private static final int INIT_SIZE = 8;

        private short keySize;
        private short capacity;
       
        private short size;

        private String[] keys;
        private String[] values;

        public Tags() {
                keys = new String[INIT_SIZE];
                values = new String[INIT_SIZE];
                capacity = INIT_SIZE;
        }

        public String get(String key) {
                int ind = keyPos(key);
                if (ind < 0)
                        return null;

                return values[ind];
        }
       
        /**
         * Retrieves the number of tags.
         * @return number of tags
         */
        public int size() {
                return size;
        }

        public String put(String key, String value) {
                assert key != null : "key is null";
                assert value != null : "value is null";
                ensureSpace();
                int ind = keyPos(key);
                if (ind < 0)
                        assert false : "keyPos(" + key + ") returns null - size = " + keySize + ", capacity = " + capacity;
                keys[ind] = key;

                String old = values[ind];
                if (old == null) {
                        keySize++;
                        size++;
                }
                values[ind] = value;

                return old;
        }

        public String remove(String key) {
                int k = keyPos(key);

                if (k >= 0 && values[k] != null) {
                        // because of the way this works, you can never remove keys
                        // except when resizing.
                        String old = values[k];
                        values[k] = null;
                        size--;
                        return old;
                }
                return null;
        }
       
        /**
         * Make a deep copy of this object.
         * @return A copy of this object.
         */
        public Tags copy() {
                Tags cp = new Tags();
                cp.keySize = keySize;
                cp.size = size;
                cp.capacity = capacity;

                cp.keys = Arrays.copyOf(keys, keys.length);
                cp.values = Arrays.copyOf(values, values.length);
                return cp;
        }

        private void ensureSpace() {
                while (keySize + 1 >= capacity) {
                        short ncap = (short) (capacity*2);
                        String[] okey = keys;
                        String[] oval = values;
                        keys = new String[ncap];
                        values = new String[ncap];
                        capacity = ncap;
                        keySize = 0;
                        size = 0;
                        for (int i = 0; i < okey.length; i++) {
                                String k = okey[i];
                                String v = oval[i]; // null if tag has been removed
                                if (k != null && v != null)
                                        put(k, v);
                        }
                }
                assert keySize < capacity;
        }

        private int keyPos(String key) {
                int h = key.hashCode();
                int k = h & (capacity - 1);

                int i = k;
                do {
                        String fk = keys[i];
                        if (fk == null || fk.equals(key))
                                return i;
                        i++;
                        if (i >= capacity)
                                i = 0;
                } while (i != k);
                return -1;
        }

        /**
         * Iterates over the tags in a special way that is used to look up in
         * the rules.
         *
         * If you have the tags a=b, c=d then you will get the following strings
         * returned: "a=b", "a=*", "c=d", "c=*".
         *
         * If you add a tag during the iteration, then it is guaranteed to
         * appear later in the iteration.
         */
        public Iterator<String> iterator() {
                return new Iterator<String>() {
                        private int pos;

                        public boolean hasNext() {
                                // After every normal entry there is a wild card entry.
                                //if (doWild)
                                //      return true;

                                // Normal entries in the map
                                for (int i = pos; i < capacity; i++) {
                                        if (values[i] != null) {
                                                pos = i;
                                                return true;
                                        }
                                }

                                return false;
                        }

                        /**
                         * Get the next tag as a single string.  Also returns wild card
                         * entries.
                         */
                        public String next() {
                                /*if (doWild) {
                                        doWild = false;
                                        return wild + "=*";
                                } else*/ if (pos < capacity) {
                                        for (int i = pos; i < capacity; i++) {
                                                if (values[i] != null) {
                                                        pos = i+1;
                                                        return (keys[i] + "=" + values[i]);
                                                }
                                        }
                                        pos = capacity;
                                }

                                return null;
                        }

                        public void remove() {
                                throw new UnsupportedOperationException();
                        }
                };
        }

        public Iterator<Map.Entry<String, String>> entryIterator() {
                return new Iterator<Map.Entry<String, String>>() {
                        private int pos;
                       
                        public boolean hasNext() {
                                for (int i = pos; i < capacity; i++) {
                                        if (values[i] != null) {
                                                pos = i;
                                                return true;
                                        }
                                }
                                return false;
                        }

                        public Map.Entry<String, String> next() {
                                Map.Entry<String, String> entry = new AbstractMap.SimpleEntry<String, String>(keys[pos], values[pos]);

                                pos++;
                                return entry;
                        }

                        public void remove() {
                                throw new UnsupportedOperationException();
                        }
                };
        }

        public Map<String, String> getTagsWithPrefix(String prefix, boolean removePrefix) {
                Map<String, String> map = new HashMap<String, String>();

                int prefixLen = prefix.length();
                for(int i = 0; i < capacity; ++i) {
                        if(keys[i] != null && keys[i].startsWith(prefix)) {
                                if(removePrefix)
                                        map.put(keys[i].substring(prefixLen), values[i]);
                                else
                                        map.put(keys[i], values[i]);
                        }
                }

                return map;
        }
       
        public void removeAll() {
                for (int i = 0; i < capacity; i++){
                        keys[i] = null;
                        values[i] = null;
                }
                keySize = 0;
                size = 0;
        }
       
        public String toString() {
                StringBuilder s =new StringBuilder();
                s.append("[");
                Iterator<Entry<String,String>> tagIter = entryIterator();
                while (tagIter.hasNext()) {
                        Entry<String,String> tag = tagIter.next();
                        if (s.length() > 1) {
                                s.append("; ");
                        }
                        s.append(tag.getKey());
                        s.append("=");
                        s.append(tag.getValue());
                }
                s.append("]");
                return s.toString();
        }
}