Subversion Repositories mkgmap

Rev

Rev 2501 | Blame | Compare with Previous | Last modification | View Log | RSS feed

/*
 * Copyright (C) 2008 Steve Ratcliffe
 *
 * 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.imgfmt.app.net;

import java.util.Iterator;
import java.util.List;

import uk.me.parabola.imgfmt.app.BitWriter;

import static uk.me.parabola.imgfmt.app.net.NumberStyle.*;

/**
 * Class to prepare the bit stream of the house numbering information.
 *
 * There are multiple ways to encode the same numbers, the trick is to find a way that is reasonably
 * small. We recognise a few common cases to reduce the size of the bit stream, but mostly just concentrating
 * on clarity and correctness. Optimisations only made a few percent difference at most.
 *
 * @author Steve Ratcliffe
 */

public class NumberPreparer {

        private final List<Numbers> numbers;
        private boolean valid;

        // The minimum values of the start and end bit widths.
        private static final int START_WIDTH_MIN = 5;
        private static final int END_WIDTH_MIN = 2;

        private BitWriter bw;
        private boolean swappedDefaultStyle;

        public NumberPreparer(List<Numbers> numbers) {
                this.numbers = numbers;
        }

        /**
         * Make the bit stream and return it. This is only done once, if you call this several times
         * the same bit writer is returned every time.
         * @return A bit writer containing the computed house number stream.
         */

        public BitWriter fetchBitStream() {
                if (bw != null)
                        return bw;

                int initialValue = setup();

                // Write the bitstream
                bw = new BitWriter();

                try {

                        // Look at the numbers and calculate some optimal values for the bit field widths etc.
                        State state = new GatheringState(initialValue);
                        process(new BitWriter(), state);

                        // Write the initial values.
                        writeWidths(state);
                        writeInitialValue(state);

                        state = new WritingState(state);
                        process(bw, state);

                        // If we get this far and there is something there, the stream might be valid!
                        if (bw.getLength() > 1)
                                valid = true;
                } catch (Abandon e) {
                        System.out.println(e.getMessage());
                        valid = false;
                }

                return bw;
        }

        /**
         * Do some initial calculation and sanity checking of the numbers that we are to
         * write.
         * @return The initial base value that all other values are derived from.
         */

        private int setup() {
                // Should we use the swapped default numbering style EVEN/ODD rather than
                // ODD/EVEN and the initialValue.
                for (Iterator<Numbers> iterator = numbers.listIterator(); iterator.hasNext(); ) {
                        Numbers n = iterator.next();
                        if (n.getLeftNumberStyle() == NONE && n.getRightNumberStyle() == NONE)
                                iterator.remove();
                }
                if (numbers.isEmpty())
                        throw new Abandon("no numbers");

                Numbers first = numbers.get(0);
                if (first.getLeftNumberStyle() == EVEN && first.getRightNumberStyle() == ODD)
                        swappedDefaultStyle = true;

                // Calculate the initial value we want to use
                int initial = 0;
                if (first.getLeftNumberStyle() != NONE)
                        initial = first.getLeftStart();

                int rightStart = 0;
                if (first.getRightNumberStyle() != NONE)
                        rightStart = first.getRightStart();

                if (initial == 0)
                        initial = rightStart;

                if (first.getLeftStart() > first.getLeftEnd() || first.getRightStart() > first.getRightEnd())
                        initial = Math.max(initial, rightStart);
                else if (rightStart > 0)
                        initial = Math.min(initial, rightStart);
                return initial;
        }

        /**
         * Process the list of number ranges and compile them into a bit stream.
         *
         * This is done twice, once to calculate the sizes of the bit fields needed, and again
         * to do the actual writing.
         *
         * @param bw The bit stream to write to.
         * @param state Use to keep track of state during the construction process.
         */

        private void process(BitWriter bw, State state) {
                if (swappedDefaultStyle)
                        state.swapDefaults();

                int lastNode = -1;
                for (Numbers n : numbers) {
                        if (!n.hasRnodNumber())
                                throw new Abandon("no r node set");

                        // See if we need to skip some nodes
                        if (n.getRnodNumber() != lastNode + 1)
                                state.writeSkip(bw, n.getRnodNumber() - lastNode - 2);

                        // Normal case write out the next node.
                        state.setTarget(n);

                        state.writeNumberingStyle(bw);
                        state.calcNumbers();
                        state.writeBitWidths(bw);
                        state.writeNumbers(bw);
                        state.restoreWriters();

                        lastNode = n.getRnodNumber();
                }
        }

        /**
         * The initial base value is written out separately before anything else.
         * All numbers are derived from differences from this value.
         * @param state Holds the initial value to write.
         */

        private void writeInitialValue(State state) {
                assert state.initialValue >= 0 : "initial value is not positive: " + state.initialValue;
                int width = 32 - Integer.numberOfLeadingZeros(state.initialValue);
                if (width > 20)
                        throw new Abandon("Initial value too large: " + state.initialValue);

                if (width > 5) {
                        bw.put1(false);
                        bw.putn(width - 5, 4);
                } else {
                        bw.put1(true);
                        width = 5;
                }
                bw.putn(state.initialValue, width);
        }

        /**
         * Write out a block that describes the number of bits to use. Numbers can be
         * either all positive or all negative, or they can be signed and each bit field
         * also has an extra sign bit. This is like how lines are encoded. See the LinePreparer
         * class.
         * @param state Holds the width information.
         */

        private void writeWidths(State state) {
                state.getStartWriter().writeFormat();
                state.getEndWriter().writeFormat();
        }

        /**
         * Returns true if the bit stream was calculated on the basis that the initial even/odd defaults
         * should be swapped.
         * @return True to signify swapped default, ie bit 0x20 in the net flags should be set.
         */

        public boolean getSwapped() {
                return swappedDefaultStyle;
        }

        /**
         * During development, any case that cannot be written correctly is marked invalid so it can
         * be skipped on output.
         *
         * This will probably go away when complete.
         *
         * @return True if the preparer believes that the output is valid.
         */

        public boolean isValid() {
                return valid;
        }

        /**
         * The current state of the writing process.
         */

        static abstract class State {

                protected final Side left = new Side(true);
                protected final Side right = new Side(false);
                private int initialValue;

                State() {
                        left.style = ODD;
                        right.style = EVEN;
                }

                /**
                 * Set the initial value. All numbers are derived from this by adding differences.
                 */

                public void setInitialValue(int val) {
                        initialValue = val;
                        left.base = val;
                        right.base = val;
                }

                /**
                 * Set the next number to output. Once the target is set, we then output commands to
                 * transform the current state into the target state.
                 * @param numbers The target numbers.
                 */

                public void setTarget(Numbers numbers) {
                        left.setTargets(numbers.getLeftNumberStyle(), numbers.getLeftStart(), numbers.getLeftEnd());
                        right.setTargets(numbers.getRightNumberStyle(), numbers.getRightStart(), numbers.getRightEnd());
                }

                /**
                 * If the target numbering style is different to the current one, then write out
                 * the command to change it.
                 */

                public void writeNumberingStyle(BitWriter bw) {
                }

                /**
                 * If we need a larger bit width for this node, then write out a command to
                 * change it. Changes are temporary and it reverts to the default after the
                 * next number output command.
                 */

                public void writeBitWidths(BitWriter bw) {
                }

                public void writeSkip(BitWriter bw, int n) {
                }

                /**
                 * Calculate the number difference to represent the current number range.
                 */

                public void calcNumbers() {
                        if (left.style == NONE)
                                left.base = right.base;

                        equalizeBases();

                        left.calc(right);
                        right.calc(left);
                }

                /**
                 * See if we can set the bases of both sides of the road to be equal. Doesn't seem to be
                 * that useful, but does not cost any bits, as long as doing so doesn't cause you to write
                 * a difference when you wouldn't without.
                 * @return True if the bases have been set equal.  There are two cases, the left can be set equal to
                 * the right, or visa versa. The flags on the left/right objects will say which.
                 */

                private boolean equalizeBases() {
                        left.equalized = right.equalized = false;

                        // Don't if runs are in different directions
                        if (left.direction != right.direction) {
                                return false;
                        }

                        int diff = left.targetStart - left.base;

                        // Do not lose the benefit of a 0 start.
                        if (left.tryStart(left.base))
                                diff = 0;

                        if (right.tryStart(left.base + diff)) {
                                left.equalized = true;
                                right.base = left.base;
                                left.startDiff = right.startDiff = diff;
                                return true;
                        }

                        diff = right.targetStart - right.base;
                        if (left.tryStart(right.base + diff)) {
                                right.equalized = true;
                                left.base = right.base;
                                left.startDiff = right.startDiff = diff;
                                return true;
                        }

                        return false;
                }

                /**
                 * Write the bit stream to the given bit writer.
                 *
                 * When this is called, all the calculations as to what is to be done have been made and
                 * it is just a case of translating those into the correct format.
                 *
                 * @param bw Bit writer to use. In the gathering phase this must be a throw away one.
                 */

                public void writeNumbers(BitWriter bw) {
                        boolean doSingleSide = left.style == NONE || right.style == NONE;

                        // Output the command that a number follows.
                        bw.put1(true);

                        boolean equalized = false;
                        if (!doSingleSide) {
                                equalized = left.equalized || right.equalized;
                                bw.put1(equalized);
                                if (equalized)
                                        bw.put1(left.equalized);
                        }

                        if (!doSingleSide) {
                                bw.put1(!right.needOverride(left));
                        }

                        Side firstSide = left;
                        if (doSingleSide && left.style == NONE)
                                firstSide = right;

                        boolean doStart = firstSide.startDiff != 0;
                        boolean doEnd = firstSide.endDiff != 0;
                        bw.put1(!doStart);
                        bw.put1(!doEnd);

                        if (doStart)
                                writeStart(firstSide.startDiff);
                        if (doEnd)
                                writeEnd(firstSide.endDiff);

                        firstSide.finish();

                        if (doSingleSide) {
                                left.base = right.base = firstSide.base;
                                left.lastEndDiff = right.lastEndDiff = firstSide.lastEndDiff;
                                return;
                        }

                        doStart = right.startDiff != 0;
                        doEnd = right.endDiff != 0;

                        if (!equalized)
                                bw.put1(!doStart);
                        if (right.needOverride(left))
                                bw.put1(!doEnd);

                        if (doStart && !equalized)
                                writeStart(right.startDiff);
                        if (doEnd)
                                writeEnd(right.endDiff);

                        right.finish();
                }

                protected void restoreWriters() {
                }

                /** Write a start difference */
                public abstract void writeStart(int diff);
                /** Write an end difference */
                public abstract void writeEnd(int diff);

                public abstract VarBitWriter getStartWriter();
                public abstract VarBitWriter getEndWriter();

                /**
                 * By default the left side of the road is odd numbered and the right even.
                 * Calling this swaps that around. If NONE or BOTH is needed then an explicit set of
                 * the numbering styles must be made.
                 */

                public void swapDefaults() {
                        left.style = EVEN;
                        right.style = ODD;
                }
        }

        /**
         * Represents one side of the road.
         */

        static class Side {
                private final boolean left;

                private NumberStyle style;
                private int base;

                // The calculated end number for the node. Might be different to the actual number
                // that are wanted that are in targetEnd.
                private int end;

                // These are the target start and end numbers for the node. The real numbers are different as there
                // is an adjustment applied.
                private NumberStyle targetStyle;
                private int targetStart;
                private int targetEnd;

                // Everything is represented as a difference from a previous value.
                private int startDiff;
                private int endDiff;
                private int lastEndDiff;

                // This is +1 if the numbers are ascending, and -1 if descending.
                private int direction;

                // Bases equalised to this side.
                private boolean equalized;

                Side(boolean left) {
                        this.left = left;
                }

                /**
                 * Set the wanted values for start and end for this side of the road.
                 */

                public void setTargets(NumberStyle style, int start, int end) {
                        this.targetStyle = style;
                        this.targetStart = start;
                        this.targetEnd = end;

                        // In reality should use the calculated start and end values, not the targets. Real start and end
                        // values are not ever the same (in this implementation) so that is why the case where start==end
                        // is given the value +1.
                        if (targetStart < targetEnd)
                                direction = 1;
                        else if (targetEnd < targetStart)
                                direction = -1;
                        else
                                direction = 1;
                }

                /**
                 * Try a start value to see if it will work.  Obviously a value equal to the target will work
                 * but so will a value that equals it after rounding for odd/even.
                 * @param value The value to test.
                 * @return True if this value would result in the targetStart.
                 */

                private boolean tryStart(int value) {
                        return value == targetStart || style.round(value, direction) == targetStart;
                }

                /**
                 *  For the right hand side, read and end value, or use the last end value as default.
                 *
                 * Otherwise, the same end diff is used for the right side as the left.
                 * @param left Reference to the left hand side.
                 */

                public boolean needOverride(Side left) {
                        return endDiff != 0 || left.endDiff == 0;
                }

                /**
                 * There is more than one way to represent the same range of numbers. The idea is to pick one of
                 * the shorter ways. We don't make any effort to find the shortest, but just pick a reasonable
                 * strategy for some common cases, and making use of defaults where we can.
                 *
                 * @param other The details of the other side of the road.
                 *
                 */

                private void calc(Side other) {
                        if (style == NONE)
                                return;

                        boolean equalized = this.equalized || other.equalized;

                        if (!equalized)
                                startDiff = tryStart(base)? 0: targetStart - base;

                        endDiff = targetEnd - (base+startDiff) + direction;

                        // Special for start == end, we can often do without an end diff.
                        if (targetStart == targetEnd && base == targetStart && lastEndDiff == 0 && !equalized) {
                                if (left || (other.endDiff == 0))
                                        endDiff = 0;
                        }

                        // Now that end is calculated we fix it and see if we can obtain it by default instead.
                        end = base+startDiff+endDiff;

                        if (left) {
                                if (endDiff == lastEndDiff) endDiff = 0; // default is our last diff.

                        } else if (other.style != NONE) {
                                // right side (and left not NONE)
                                if (other.endDiff == 0 && endDiff == lastEndDiff) endDiff = 0;   // No left diff, default is our last
                                if (other.endDiff != 0 && other.endDiff == endDiff) endDiff = 0; // Left diff set, that's our default
                        }
                }

                /**
                 * Called at the end of processing a number range. Sets up the fields for the next one.
                 */

                public void finish() {
                        lastEndDiff = end - (base + startDiff);
                        base = end;
                }
        }

        /**
         * The calculations are run on this class first, which keeps track of the sizes required to
         * write the values without actually writing them anywhere.
         *
         * When passing a BitWriter to any method on this class, it must be a throw away one, as it
         * will actually be written to by some of the common methods.
         */

        private class GatheringState extends State {
                class BitSizes {
                        private boolean positive;
                        private boolean negative;
                        private int diff;

                        private boolean isSigned() {
                                return positive && negative;
                        }

                        private int calcWidth() {
                                int n = diff;
                                if (isSigned())
                                        n++;
                                return 32 - Integer.numberOfLeadingZeros(n);
                        }
                }

                private final BitSizes start = new BitSizes();
                private final BitSizes end = new BitSizes();

                public GatheringState(int initialValue) {
                        setInitialValue(initialValue);
                }

                public void writeNumberingStyle(BitWriter bw) {
                        left.style = left.targetStyle;
                        right.style = right.targetStyle;
                }

                /**
                 * Calculate the size required for this write and keeps the maximum values.
                 * @param diff The value to examine.
                 */

                public void writeStart(int diff) {
                        int val = testSign(start, diff);
                        if (val > start.diff)
                                start.diff = val;
                }

                /**
                 * Calculate the size required to hold this write and keeps the maximum.
                 * @param diff The value to be examined.
                 */

                public void writeEnd(int diff) {
                        int val = testSign(end, diff);
                        if (val > end.diff)
                                end.diff = val;
                }

                /**
                 * Checks the sign properties required for the write.
                 */

                private int testSign(BitSizes bs, int val) {
                        if (val > 0) {
                                bs.positive = true;
                        } else if (val < 0) {
                                bs.negative = true;
                                return -val;
                        }
                        return val;
                }

                /**
                 * Construct a writer that uses a bit width and sign properties that are sufficient to write
                 * all of the values found in the gathering phase. This is for start differences.
                 */

                public VarBitWriter getStartWriter() {
                        return getVarBitWriter(start, START_WIDTH_MIN);
                }
                /**
                 * Construct a writer that uses a bit width and sign properties that are sufficient to write
                 * all of the values found in the gathering phase. This is for end differences.
                 */

                public VarBitWriter getEndWriter() {
                        return getVarBitWriter(end, END_WIDTH_MIN);
                }

                /**
                 * Common code to create the bit writer.
                 * @see #getStartWriter()
                 * @see #getEndWriter()
                 */

                private VarBitWriter getVarBitWriter(BitSizes bs, int minWidth) {
                        VarBitWriter writer = new VarBitWriter(bw, minWidth);
                        if (bs.isSigned())
                                writer.signed = true;
                        else if (bs.negative)
                                writer.negative = true;
                        int width = bs.calcWidth();
                        if (width > minWidth)
                                writer.bitWidth = width - minWidth;
                        if (writer.bitWidth > 15)
                                throw new Abandon("Difference too large");
                        return writer;
                }
        }

        /**
         * This is used to actually write the bit stream.
         * @see GatheringState
         */

        static class WritingState extends State {

                private VarBitWriter startWriter;
                private VarBitWriter endWriter;
                private boolean restoreBitWriters;
                private final VarBitWriter savedStartWriter;
                private final VarBitWriter savedEndWriter;

                public WritingState(State state) {
                        setInitialValue(state.initialValue);
                        left.base = state.initialValue;
                        right.base = state.initialValue;

                        startWriter = state.getStartWriter();
                        endWriter = state.getEndWriter();
                        this.savedStartWriter = startWriter;
                        this.savedEndWriter = endWriter;
                }

                public void writeStart(int diff) {
                        startWriter.write(diff);
                }

                public void writeEnd(int diff) {
                        endWriter.write(diff);
                }

                public void writeNumberingStyle(BitWriter bw) {
                        if (left.targetStyle != left.style || right.targetStyle != right.style) {
                                bw.putn(0, 2);
                                bw.putn(left.targetStyle.getVal(), 2);
                                bw.putn(right.targetStyle.getVal(), 2);
                                left.style = left.targetStyle;
                                right.style = right.targetStyle;
                        }
                }

                /**
                 * You can change the number of bits and the sign properties of the writers before writing a nodes
                 * numbers.  We don't try and work out the optimum sequence, but use this for tricky cases where
                 * we fail to work out the correct sizes in advance.
                 *
                 * This routine means that we will always be using writers that will deal with the next node numbers.
                 *
                 * @param bw The output stream writer.
                 */

                public void writeBitWidths(BitWriter bw) {
                        newWriter(bw, startWriter, left.startDiff, right.startDiff, true);
                        newWriter(bw, endWriter, left.endDiff, right.endDiff, false);
                }

                /**
                 * Common code for writeBitWidths. Calculate the width and the sign properties required to
                 * represent the two numbers.
                 * @param leftDiff One of the numbers to be represented.
                 * @param rightDiff The other number to be represented.
                 * @param start Set to true if this is the start writer, else it is for the end writer.
                 */

                private void newWriter(BitWriter bw, VarBitWriter writer, int leftDiff, int rightDiff, boolean start) {
                        if (!writer.checkFit(leftDiff) || !writer.checkFit(rightDiff)) {
                                int min = Math.min(leftDiff, rightDiff);
                                int max = Math.max(leftDiff, rightDiff);
                                boolean signed = false;
                                boolean negative = false;
                                if (max < 0)
                                        negative = true;
                                else if (min < 0)
                                        signed = true;

                                int val = Math.max(Math.abs(min), Math.abs(max));
                                int width = 32 - Integer.numberOfLeadingZeros(val);
                                if (signed) width++;

                                restoreBitWriters = true;
                                VarBitWriter nw;
                                if (start) {
                                        startWriter = nw = new VarBitWriter(bw, START_WIDTH_MIN, negative, signed, width);
                                        bw.putn(2, 4); // change width start
                                } else {
                                        endWriter = nw = new VarBitWriter(bw, END_WIDTH_MIN, negative, signed, width);
                                        bw.putn(0xa, 4); // change width end (0x8 | 0x2)
                                }
                                nw.writeFormat();
                        }
                }

                public void writeSkip(BitWriter bw, int n) {
                        if (n < 0)
                                throw new Abandon("bad skip value:" + n);

                        bw.putn(6, 3);

                        int width = 32 - Integer.numberOfLeadingZeros(n);
                        if (width > 5) {
                                bw.put1(true);
                                width = 10;
                        } else {
                                bw.put1(false);
                                width = 5;
                        }
                        bw.putn(n, width);
                }

                public VarBitWriter getStartWriter() {
                        return startWriter;
                }

                public VarBitWriter getEndWriter() {
                        return endWriter;
                }

                /**
                 * If we used an alternate writer for a node's numbers then we restore the default
                 * writers afterwards.
                 */

                protected void restoreWriters() {
                        if (restoreBitWriters) {
                                startWriter = savedStartWriter;
                                endWriter = savedEndWriter;
                                restoreBitWriters = false;
                        }
                }
        }
}

/**
 * A bit writer that can be configured with different bit width and sign properties.
 *
 * The sign choices are:
 * negative: all numbers are negative and so can be represented without a sign bit. (or all positive
 * if this is false).
 * signed: numbers are positive and negative, and so have sign bit.
 *
 * The bit width is composed of two parts since it is represented as a difference between
 * a well known minimum value and the actual value.
 */

class VarBitWriter {
        private final BitWriter bw;
        private final int minWidth;
        int bitWidth;
        boolean negative;
        boolean signed;

        VarBitWriter(BitWriter bw, int minWidth) {
                this.bw = bw;
                this.minWidth = minWidth;
        }

        public VarBitWriter(BitWriter bw, int minWidth, boolean negative, boolean signed, int width) {
                this(bw, minWidth);
                this.negative = negative;
                this.signed = signed;
                if (width > minWidth)
                        this.bitWidth = width - minWidth;
        }

        /**
         * Write the number to the bit stream. If the number cannot be written
         * correctly with this bit writer then an exception is thrown. This shouldn't
         * happen since we check before hand and create a new writer if the numbers are not
         * going to fit.
         *
         * @param n The number to be written.
         */

        public void write(int n) {
                if (!checkFit(n))
                        throw new Abandon("number does not fit bit space available");

                if (n < 0 && negative)
                        n = -n;

                if (signed) {
                        int mask = (1 << (minWidth + bitWidth+2)) - 1;
                        n &= mask;
                }

                bw.putn(n, minWidth+bitWidth + ((signed)?1:0));
        }

        /**
         * Checks to see if the number that we want to write can be written by this writer.
         * @param n The number we would like to write.
         * @return True if all is OK for writing it.
         */

        boolean checkFit(int n) {
                if (negative) {
                        if (n > 0)
                                return false;
                        else
                                n = -n;
                } else if (signed && n < 0)
                        n = -1 - n;

                int mask = (1 << minWidth + bitWidth) - 1;

                return n == (n & mask);
        }

        /**
         * Write the format of this bit writer to the output stream. Used at the beginning and
         * when changing the bit widths.
         */

        public void writeFormat() {
                bw.put1(negative);
                bw.put1(signed);
                bw.putn(bitWidth, 4);
        }
}

/**
 * Exception to throw when we detect that we do not know how to encode a particular case.
 * This should not be thrown any more, when the preparers is called correctly.
 *
 * If it is, then the number preparer is marked as invalid and the data is not written to the
 * output file.
 */

class Abandon extends RuntimeException {
        Abandon(String message) {
                super("HOUSE NUMBER RANGE: " + message);
        }
}