/*
 * Copyright (C) 2006, 2013.
 *
 * 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.boundary;

import java.awt.Rectangle;
import java.awt.Shape;
import java.awt.geom.Area;
import java.awt.geom.Path2D;
import java.awt.geom.PathIterator;
import java.awt.geom.Rectangle2D;
import java.io.BufferedInputStream;
import java.io.ByteArrayInputStream;
import java.io.DataInputStream;
import java.io.EOFException;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Date;
import java.util.Enumeration;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.regex.Pattern;
import java.util.zip.ZipEntry;
import java.util.zip.ZipFile;

import uk.me.parabola.imgfmt.ExitException;
import uk.me.parabola.imgfmt.FormatException;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.log.Logger;
import uk.me.parabola.mkgmap.reader.osm.Tags;
import uk.me.parabola.mkgmap.reader.osm.Way;
import uk.me.parabola.util.EnhancedProperties;
import uk.me.parabola.util.Java2DConverter;
import uk.me.parabola.util.MultiHashMap;
import uk.me.parabola.util.ShapeSplitter;

public class BoundaryUtil {
	private static final Logger log = Logger.getLogger(BoundaryUtil.class);

	private static final int UNKNOWN_DATA_FORMAT = 0;
	private static final int RAW_DATA_FORMAT_V1 = 2;
	private static final int QUADTREE_DATA_FORMAT_V1 = 3;
	public static final double MIN_DIMENSION = 0.0000001;
	/**
	 * Calculate the polygons that describe the area.
	 * @param area the Area instance
	 * @param id an id that is used to create meaningful messages, typically a boundary Id
	 * @return A list of BoundaryElements (can be empty)
	 */
	public static List<BoundaryElement> splitToElements(Area area, String id) {
		if (area.isEmpty()) {
			return Collections.emptyList();
		}

		Area testArea = area;
		boolean tryAgain = true;
		while (true){
			List<List<Coord>> areaElements = Java2DConverter.areaToShapes(testArea);

			if (areaElements.isEmpty()) {
				// this may happen if a boundary overlaps a raster tile in a very small area
				// so that it is has no dimension
				log.debug("Area has no dimension. Area:",area.getBounds());
				return Collections.emptyList();
			}

			List<BoundaryElement> bElements = new ArrayList<>();
			for (List<Coord> singleElement : areaElements) {
				if (singleElement.size() <= 3) {
					// need at least 4 items to describe a polygon
					continue;
				}
				boolean outer = Way.clockwise(singleElement);
				bElements.add(new BoundaryElement(outer, singleElement));
			}

			if (bElements.isEmpty()) {
				// should not happen because empty polygons should be removed by
				// the Java2DConverter
				log.error("Empty boundary elements list after conversion. Area: "+area.getBounds());
				return Collections.emptyList();
			}


			// reverse the list because it starts with the inner elements first and
			// we need the other way round
			Collections.reverse(bElements);

			if (bElements.get(0).isOuter())
				return bElements;

			// result is not usable if first element is not outer 
			if (tryAgain == false){
				// cannot convert this area
				log.error(" first element is not outer. "+ bElements.get(0));
				
				//createJavaCodeSnippet(area);
				//String fname = "bnd_gpx/first_not_outer" + id ;
				//GpxCreator.createGpx(fname, bElements.get(0).getPoints());
				return Collections.emptyList();
			}
			// try converting the area with rounded float values
			Path2D.Float path = new Path2D.Float(area);
			testArea = new Area(path);
			tryAgain = false;
		}
	}

	/**
	 * Wrapper for {@link #loadQuadTrees(String, List, uk.me.parabola.imgfmt.app.Area, EnhancedProperties)}
	 * @param boundaryDirName a directory name or zip file containing the *.bnd file
	 * @param boundaryFileName the *.bnd file name
	 * @return the quadtree or null in case of errors
	 */
	public static BoundaryQuadTree loadQuadTree (String boundaryDirName, 
			String boundaryFileName){
		Map<String,BoundaryQuadTree> trees = loadQuadTrees (boundaryDirName, Collections.singletonList(boundaryFileName), null, null);
		return trees.get(boundaryFileName);
	}
	
	/**
	 * Create a BoundaryQuadTree for each file listed in boundaryFileNames. 
	 * @param boundaryDirName a directory name or zip file containing the *.bnd file
	 * @param boundaryFileNames the list of *.bnd file names
	 * @param searchBbox null or a bounding box. Data outside of this box is ignored.
	 * @param props null or the properties to be used for the locator
	 * @return a map with quadtrees which can be empty
	 */
	public static Map<String,BoundaryQuadTree> loadQuadTrees (String boundaryDirName, 
			List<String> boundaryFileNames, 
			uk.me.parabola.imgfmt.app.Area searchBbox, EnhancedProperties props){
		Map<String,BoundaryQuadTree>  trees = new HashMap<>();
		File boundaryDir = new File(boundaryDirName);
		BoundaryQuadTree bqt;
		if (boundaryDir.isDirectory()){
			for (String boundaryFileName: boundaryFileNames){
				log.info("loading boundary file:", boundaryFileName);
				// no support for nested directories
				File boundaryFile = new File(boundaryDir, boundaryFileName);
				if (boundaryFile.exists()){
					try(InputStream stream = new FileInputStream(boundaryFile)){
						bqt = BoundaryUtil.loadQuadTreeFromStream(stream, boundaryFileName, searchBbox, props);
						if (bqt != null)
							trees.put(boundaryFileName,bqt);
					} catch (IOException exp) {
						log.error("Cannot load boundary file " +  boundaryFileName + "." + exp);
					}
				}					
			}
		} else if (boundaryDirName.endsWith(".zip")) {
			String  currentFileName = "";
			try(ZipFile zipFile = new ZipFile(boundaryDir)){
				for (String boundaryFileName : boundaryFileNames){
					log.info("loading boundary file:", boundaryFileName);
					currentFileName = boundaryFileName;
					// direct access  
					ZipEntry entry = zipFile.getEntry(boundaryFileName);
					if (entry != null){ 
						try(InputStream stream = zipFile.getInputStream(entry)){
							bqt = BoundaryUtil.loadQuadTreeFromStream(stream, boundaryFileName, searchBbox, props);
							if (bqt != null)
								trees.put(boundaryFileName,bqt);
						}
					}
				}
			} catch (IOException exp) {
				log.error("Cannot load boundary file " + currentFileName + "." + exp);
			}
		} else{ 
			log.error("Cannot read " + boundaryDirName);
		}
		return trees;
	}

	
	/**
	 * read path iterator info from stream and create Area. 
	 * Data is stored with varying length doubles.
	 * @param inpStream the already opened DataInputStream 
	 * @return a new Area object or null if not successful 
	 * @throws IOException
	 */
	public static Area readAreaAsPath(DataInputStream inpStream) throws IOException{
		double[] res = new double[2];
		Path2D.Double path = new Path2D.Double(PathIterator.WIND_NON_ZERO, 1024);
		int windingRule = inpStream.readInt();
		path.setWindingRule(windingRule);
		int type = inpStream.readInt(); 
		double minX = Double.MAX_VALUE,maxX = Double.MIN_VALUE;
		double minY = Double.MAX_VALUE,maxY = Double.MIN_VALUE;
		while (type >= 0) {
			switch (type) {
			case PathIterator.SEG_LINETO:
				int len = inpStream.readInt();
				while(len > 0){
					for (int ii = 0; ii < 2; ii++){
						double delta = readVarDouble(inpStream);
						if (delta == BoundarySaver.RESET_DELTA)
							res[ii] = readVarDouble(inpStream);
						else
							res[ii] = res[ii] + delta;
					}
					if (res[0] < minX)
						minX = res[0];
					if (res[0] > maxX)
						maxX = res[0];
					if (res[1] < minY)
						minY = res[1];
					if (res[1] > maxY)
						maxY = res[1];
					path.lineTo(res[0],res[1]);
					--len;
				}
				break;
			case PathIterator.SEG_MOVETO:
				for (int ii = 0; ii < 2; ii++){
					double delta = readVarDouble(inpStream);
					if (delta == BoundarySaver.RESET_DELTA)
						res[ii] = readVarDouble(inpStream);
					else
						res[ii] = res[ii] + delta;
				}
				if (res[0] < minX)
					minX = res[0];
				if (res[0] > maxX)
					maxX = res[0];
				if (res[1] < minY)
					minY = res[1];
				if (res[1] > maxY)
					maxY = res[1];
				path.moveTo(res[0],res[1]);
				break;
			case PathIterator.SEG_CLOSE:
				path.closePath();
				break;
			default:
				log.error("Unsupported path iterator type " + type
						+ ". This is an mkgmap error.");
				return null;
			}

			type = inpStream.readInt();
		}
		if (type != -1){
			log.error("Final type value != -1: " + type);
		}
		else{
			if (maxX - minX >= MIN_DIMENSION || maxY - minY >= MIN_DIMENSION)
				return new Area(path);
			else {
				// ignore micro area caused by rounding errors in awt area routines
			}
				
		}
		return null;
	}
	
	/**
	 * Read boundary info saved in RAW_DATA_FORMAT 
	 * (written by 1st pass of preparer)
	 * @param inpStream the already opened DataInputStream
	 * @param fname the related file name of the *.bnd file
	 * @param bbox a bounding box. Data outside of this box is ignored.
	 * @return
	 * @throws IOException
	 */
	private static List<Boundary> readStreamRawFormat(
			DataInputStream inpStream, String fname,
			uk.me.parabola.imgfmt.app.Area bbox) throws IOException			{
		List<Boundary> boundaryList = new ArrayList<>();

		try {
			while (true) {
				int minLat = inpStream.readInt();
				int minLong = inpStream.readInt();
				int maxLat = inpStream.readInt();
				int maxLong = inpStream.readInt();
				if (log.isDebugEnabled())
					log.debug("Next boundary. Lat min:",minLat,"max:",maxLat,"Long min:",minLong,"max:",maxLong);
				uk.me.parabola.imgfmt.app.Area rBbox = new uk.me.parabola.imgfmt.app.Area(
						minLat, minLong, maxLat, maxLong);
				int bSize = inpStream.readInt();
				log.debug("Size:",bSize);

				if ( bbox == null || bbox.intersects(rBbox)) {
					log.debug("Bbox intersects. Load the boundary");
					String id = inpStream.readUTF();
					Tags tags = new Tags();
					int noOfTags = inpStream.readInt();
					for (int i = 0; i < noOfTags; i++) {
						String name = inpStream.readUTF();
						String value = inpStream.readUTF();
						tags.put(name, value.intern()); 					
					}
					Area area = readAreaAsPath(inpStream);
					if (area != null) {
						Boundary boundary = new Boundary(area, tags,id);
						boundaryList.add(boundary);
					} else {
						log.warn("Boundary "+tags+" does not contain any valid area in file " + fname);
					}

				} else {
					log.debug("Bbox does not intersect. Skip",bSize);
					inpStream.skipBytes(bSize);
				}
			}
		} catch (EOFException exp) {
			// it's always thrown at the end of the file
			// log.error("Got EOF at the end of the file");
		}  		
		return boundaryList;
	}

	/**
	 * For a given bounding box, calculate the list of file names that have to be read 
	 * @param bbox the bounding box
	 * @return a List with the names
	 */
	public static List<String> getRequiredBoundaryFileNames(uk.me.parabola.imgfmt.app.Area bbox) {
		List<String> names = new ArrayList<>();
		if (!bbox.isEmpty()) {
			for (int latSplit = getSplitBegin(bbox.getMinLat()); latSplit <= BoundaryUtil
					.getSplitBegin(bbox.getMaxLat()); latSplit += RASTER) {
				for (int lonSplit = getSplitBegin(bbox.getMinLong()); lonSplit <= BoundaryUtil
						.getSplitBegin(bbox.getMaxLong()); lonSplit += RASTER) {
					names.add("bounds_"+ getKey(latSplit, lonSplit) + ".bnd");
				}
			}
		}
		return names;
	}

	/** 
	 * Check content of directory or zip file with precompiled boundary data, 
	 * dirName Name has to be a directory or a zip file.
	 * @param dirName : path to a directory or a zip file containing the *.bnd files
	 * @return the available *.bnd files in dirName.
	 */
	public static List<String> getBoundaryDirContent(String dirName) {
		List<String> names = new ArrayList<>();
		File boundaryDir = new File(dirName);
		if (!boundaryDir.exists())
			log.error("boundary directory/zip does not exist: " + dirName);
		else{		
			if (boundaryDir.isDirectory()){
				// boundaryDir.list() is much quicker than boundaryDir.listFiles(FileFilter)
				String[] allNames = boundaryDir.list();
				for (String name: allNames){
					if (name.endsWith(".bnd"))
						names.add(name);
				}
			}
			else if (boundaryDir.getName().endsWith(".zip")){
				try (ZipFile zipFile = new ZipFile(boundaryDir)){
					Enumeration<? extends ZipEntry> entries = zipFile.entries();
					boolean isFlat = true;
					while(entries.hasMoreElements()) {
						ZipEntry entry = entries.nextElement();
						if (entry.isDirectory()){
							isFlat = false;
						}
						if (entry.getName().endsWith(".bnd"))
							names.add(entry.getName());
					}
					if (!isFlat){
						log.error("boundary zip file contains directories. Files in directories will be ignored." + dirName);			
					}
				} catch (IOException ioe) {
					log.error("Cannot read",dirName,ioe);
//					ioe.printStackTrace();
					throw new ExitException("Failed to read required file " + dirName);				}
			}
		}
		return names;
	}
	
	public static final int RASTER = 50000;

	public static int getSplitBegin(int value) {
		int rem = value % RASTER;
		if (rem == 0) {
			return value;
		} else if (value >= 0) {
			return value - rem;
		} else {
			return value - RASTER - rem;
		}
	}

	public static int getSplitEnd(int value) {
		int rem = value % RASTER;
		if (rem == 0) {
			return value;
		} else if (value >= 0) {
			return value + RASTER - rem;
		} else {
			return value - rem;
		}
	}

	public static String getKey(int lat, int lon) {
		return lat + "_" + lon;
	}
	
	/**
	 * Retrieve the bounding box of the given boundary file.
	 * @param boundaryFileName the name of the boundary file
	 * @return the bounding box
	 */
	public static uk.me.parabola.imgfmt.app.Area getBbox(String boundaryFileName) {
		String filename = new String(boundaryFileName);
		// cut off the extension
		filename = filename.substring(0,filename.length()-4);
		String[] fParts = filename.split(Pattern.quote("_"));
		
		int lat = Integer.parseInt(fParts[1]);
		int lon = Integer.parseInt(fParts[2]);
		
		return new uk.me.parabola.imgfmt.app.Area(lat, lon, lat+RASTER, lon+RASTER);
	}

	/**
	 * Create and fill a BoundaryQuadTree. Read the header of the stream to detect
	 * the proper reading routine for the different supported formats.
	 * @param stream an already opened InputStream
	 * @param fname the file name of the corresponding *.bnd file
	 * @param searchBbox a bounding box or null. If not null, area info outside of this
	 * bounding box is ignored. 
	 * @param props properties to be used or null 
	 * @return on success it returns a new BoundaryQuadTree, else null 
	 * @throws IOException
	 */
	private static BoundaryQuadTree loadQuadTreeFromStream(InputStream stream, 
			String fname,
			uk.me.parabola.imgfmt.app.Area searchBbox, 
			EnhancedProperties props)throws IOException{
		BoundaryQuadTree bqt = null;
		uk.me.parabola.imgfmt.app.Area qtBbox = getBbox(fname);
		try (DataInputStream inpStream = new DataInputStream(new BufferedInputStream(stream, 1024 * 1024))){
			try {
				// 1st read the mkgmap release the boundary file is created by
				String mkgmapRel = "?";
				String firstId = inpStream.readUTF();
				if ("BND".equals(firstId) == false){
					throw new FormatException("Unsupported boundary data type "+firstId);
				}

				int format = UNKNOWN_DATA_FORMAT;
				long createTime = inpStream.readLong();
				int headerLength = inpStream.readInt();
				byte[] header = new byte[headerLength];
				int bytesRead = 0;
				while (bytesRead < headerLength) {
					int nBytes = inpStream.read(header, bytesRead, headerLength-bytesRead);
					if (nBytes<0) {
						throw new IOException("Cannot read header with size "+headerLength);
					}
					bytesRead += nBytes;
				}
					
				ByteArrayInputStream rawHeaderStream = new ByteArrayInputStream(header);
				DataInputStream headerStream =new DataInputStream(rawHeaderStream);
				String dataFormat = (rawHeaderStream.available() > 0 ? headerStream.readUTF() : "RAW");
				int recordVersion = (rawHeaderStream.available() > 0 ? headerStream.readInt() : RAW_DATA_FORMAT_V1);
				mkgmapRel = (rawHeaderStream.available() > 0 ? headerStream.readUTF() : "unknown");
				
				if ("RAW".equals(dataFormat) && recordVersion == 1)
					format = RAW_DATA_FORMAT_V1;
				else if ("QUADTREE".equals(dataFormat) && recordVersion == 1)
					format = QUADTREE_DATA_FORMAT_V1;

				if (log.isDebugEnabled()) {
					log.debug("File created by mkgmap release",mkgmapRel,"at",new Date(createTime));
				}
				
				switch (format) {
				case QUADTREE_DATA_FORMAT_V1:
					bqt = new BoundaryQuadTree(inpStream, qtBbox, searchBbox, props);
					break;
				case RAW_DATA_FORMAT_V1:
					List<Boundary> boundaryList = readStreamRawFormat(inpStream, fname,searchBbox);
					if (boundaryList == null || boundaryList.isEmpty())
						return null;
					boundaryList = mergePostalCodes(boundaryList);
					bqt = new BoundaryQuadTree(qtBbox, boundaryList, props);
					break;
				default:
					throw new FormatException("Unsupported boundary file format: "+format);
				}
			} catch (EOFException exp) {
				// it's always thrown at the end of the file
				//				log.error("Got EOF at the end of the file");
			} 
			catch (FormatException exp) {
				log.error("Failed to read boundary file " + fname + " " + exp.getMessage());
			} 
		} 
		return bqt;
	}
	
	/**
	 * Merges boundaries with the same postal code.
	 * @param boundaries a list of boundaries
	 * @return the boundary list with postal code areas merged
	 */
	private static List<Boundary> mergePostalCodes(List<Boundary> boundaries) {
		List<Boundary> mergedList = new ArrayList<>(boundaries.size());
		
		MultiHashMap<String, Boundary> equalPostalCodes = new MultiHashMap<>();
		for (Boundary boundary : boundaries) {
			String postalCode = getPostalCode(boundary.getTags());
			if (postalCode == null) {
				// no postal code boundary
				mergedList.add(boundary);
			} else {
				// postal code boundary => merge it later
				equalPostalCodes.add(postalCode, boundary);
			}
		}

		for (Entry<String, List<Boundary>> postCodeBoundary : equalPostalCodes
				.entrySet()) {
			if (postCodeBoundary.getValue().size() == 1) {
				// nothing to merge
				mergedList.addAll(postCodeBoundary.getValue());
				continue;
			}
			
			// there are more than 2 boundaries with the same post code
			// => merge them
			Area newPostCodeArea = new Area();
			for (Boundary b : postCodeBoundary.getValue()) {
				newPostCodeArea.add(b.getArea());
				
				// remove the post code tags from the original boundary
				if (b.getTags().get("postal_code") != null) {
					b.getTags().remove("postal_code");
				} else if ("postal_code".equals(b.getTags().get("boundary"))) {
					b.getTags().remove("boundary");
					b.getTags().remove("name");
				}
				
				// check if the boundary contains other boundary information
				if (isAdministrativeBoundary(b)) {
					mergedList.add(b);
				} else {
					log.info("Boundary", b.getId(), b.getTags(), "contains no more boundary tags. Skipping it.");
				}
			}
			
			Tags postalCodeTags = new Tags();
			postalCodeTags.put("postal_code", postCodeBoundary.getKey());
			Boundary postalCodeBoundary = new Boundary(newPostCodeArea, postalCodeTags, "p"+postCodeBoundary.getKey());

			log.info("Merged", postCodeBoundary.getValue().size(), "postal code boundaries for postal code", postCodeBoundary.getKey());
			mergedList.add(postalCodeBoundary);
		}
		
		return mergedList;
	}
	
	/**
	 * Checks if the given boundary contains tags for an administrative boundary.
	 * @param b a boundary
	 * @return <code>true</code> administrative boundary or postal code; 
	 * <code>false</code> element cannot be used for precompiled bounds 
	 */
	public static boolean isAdministrativeBoundary(Boundary b) {
		
		if (b.getId().startsWith("r")) {
			String type = b.getTags().get("type");
			
			if ("boundary".equals(type) || "multipolygon".equals(type)) {
				String boundaryVal = b.getTags().get("boundary");
				if ("administrative".equals(boundaryVal) == false) 
					return false;
				// for boundary=administrative the admin_level must be set
				if (b.getTags().get("admin_level") == null) {
					return false;
				}
				// and a name must be set (check only for a tag containing name
				Iterator<Entry<String,String>> tagIterator = b.getTags().entryIterator();
				while (tagIterator.hasNext()) {
					Entry<String,String> tag  = tagIterator.next();
					if (tag.getKey().contains("name")) {
						return true;
					}
				}
				// does not contain a name tag => do not use it
			}
		} else if (b.getId().startsWith("w")) {
			// the boundary tag must be "administrative" or "postal_code"
			String boundaryVal = b.getTags().get("boundary");
			if ("administrative".equals(boundaryVal)) {
				// for boundary=administrative the admin_level must be set
				if (b.getTags().get("admin_level") == null) {
					return false;
				}
				// and a name must be set (check only for a tag containing name)
				Iterator<Entry<String,String>> tagIterator = b.getTags().entryIterator();
				while (tagIterator.hasNext()) {
					Entry<String,String> tag  = tagIterator.next();
					if (tag.getKey().contains("name")) {
						return true;
					}
				}
				// does not contain a name tag => do not use it
			}
		} 
		return false;
	}
	
	
	private static String getPostalCode(Tags tags) {
		String zip = tags.get("postal_code");
		if (zip == null) {
			if ("postal_code".equals(tags.get("boundary"))){
				String name = tags.get("name"); 
				if (name != null) {
					String[] nameParts = name.split(Pattern.quote(" "));
					if (nameParts.length > 0) {
						zip = nameParts[0].trim();
					}
				}
			}
		}
		return zip;
	}
	/**
	 * Helper to ease the reporting of errors. Creates a java code snippet 
	 * that can be compiled to have the same area.
	 * @param area the area for which the code should be produced
	 */
	public static void createJavaCodeSnippet(Area area) {
		double[] res = new double[6];
		PathIterator pit = area.getPathIterator(null);
		System.out.println("Path2D.Double path = new Path2D.Double();");
		System.out.println("path.setWindingRule(" + pit.getWindingRule() + ");");
		while (!pit.isDone()) {
			int type = pit.currentSegment(res);
			switch (type) {
			case PathIterator.SEG_LINETO:
				System.out.println("path.lineTo(" + res[0] + "d, " + res[1] + "d);");
				break;
			case PathIterator.SEG_MOVETO: 
				System.out.println("path.moveTo(" + res[0] + "d, " + res[1] + "d);");
				break;
			case PathIterator.SEG_CLOSE:
				System.out.println("path.closePath();");
				break;
			default:
				log.error("Unsupported path iterator type " + type
						+ ". This is an mkgmap error.");
			}

			pit.next();
		}
		System.out.println("Area area = new Area(path);");
		
	}

	/**
	 * read a varying length double. See BoundarySaver.writeVarDouble().
	 * @param inp the already opened DataInputStream
	 * @return the extracted double value
	 * @throws IOException
	 */
	static double readVarDouble(DataInputStream inp) throws IOException{
		byte b;
		long res = 0;
		long toShift = 64 - 7;
		while (((b = inp.readByte()) & 0x80) != 0){ // more bytes will follow
			res |= (b & 0x7f);
			toShift -= 7;
			if (toShift > 0)
				res <<= 7;
		}
		if (toShift > 0){
			res |= b;
			res <<= toShift;
		}
		else {
			// special case: all 64 bits were written, 64 = 9*7 + 1
			res <<= 1;
			res |= 1;
		}
		return Double.longBitsToDouble(res);
	}

	/**
	 * Raster a given area. This is the non-recursive public method.
	 * @param areaToSplit the area
	 * @return a map with the divided shapes 
	 */
	public static Map<String, Shape> rasterArea(Area areaToSplit) {
		return rasterShape(areaToSplit, new HashMap<String, Shape>());
	}

	/**
	 * Raster a given shape. This method calls itself recursively.
	 * @param shapeToSplit the shape
	 * @param splits a map that will contain the resulting shapes
	 * @return a reference to the map 
	 */
	private static Map<String, Shape> rasterShape(Shape shapeToSplit, Map<String, Shape> splits) {
		double minX = Double.POSITIVE_INFINITY,minY = Double.POSITIVE_INFINITY, 
				maxX = Double.NEGATIVE_INFINITY,maxY = Double.NEGATIVE_INFINITY;
		PathIterator pit = shapeToSplit.getPathIterator(null);
		double[] points = new double[512];
		double[] res = new double[6];
		int num = 0;
		while (!pit.isDone()) {
			int type = pit.currentSegment(res);
			double x = res[0];
			double y = res[1];
			if (x < minX) minX = x;
			if (x > maxX) maxX = x;
			if (y < minY) minY = y;
			if (y > maxY) maxY = y;
			switch (type) {
			case PathIterator.SEG_LINETO:
			case PathIterator.SEG_MOVETO:
				if (num  + 2 >= points.length) {
					points = Arrays.copyOf(points, points.length * 2);
				}
				points[num++] = x;
				points[num++] = y;
				break;
			case PathIterator.SEG_CLOSE:
				int sMinLong = getSplitBegin((int)Math.round(minX));
				int sMinLat = getSplitBegin((int)Math.round(minY));
				int sMaxLong = getSplitEnd((int)Math.round(maxX));
				int sMaxLat = getSplitEnd((int)Math.round(maxY));
	
				int dLon = sMaxLong- sMinLong;
				int dLat = sMaxLat - sMinLat;
				Rectangle2D.Double bbox = new Rectangle2D.Double(minX,minY,maxX-minX,maxY-minY);
				if (dLon > RASTER || dLat > RASTER) {
					// split into two halves
					Rectangle clip1,clip2;
					if (dLon > dLat) {
						int midLon = getSplitEnd(sMinLong+dLon/2);
						clip1 = new Rectangle(sMinLong, sMinLat, midLon-sMinLong, dLat);
						clip2 = new Rectangle(midLon, sMinLat, sMaxLong-midLon, dLat);
					} else {
						int midLat = getSplitEnd(sMinLat+dLat/2);
						clip1 = new Rectangle(sMinLong, sMinLat, dLon, midLat-sMinLat);
						clip2 = new Rectangle(sMinLong, midLat, dLon, sMaxLat-midLat);
					}
	
					// intersect with the both halves
					// and split both halves recursively
					Path2D.Double clippedPath = ShapeSplitter.clipSinglePathWithSutherlandHodgman (points, num, clip1, bbox);
					if (clippedPath != null)
						rasterShape(clippedPath, splits);
					clippedPath = ShapeSplitter.clipSinglePathWithSutherlandHodgman (points, num, clip2, bbox);
					if (clippedPath != null)
						rasterShape(clippedPath, splits);
				} 
				else {
					String key = getKey(sMinLat, sMinLong);
					// no need to split, path fits into one tile
					Path2D.Double segment = ShapeSplitter.pointsToPath2D(points, num);
					if (segment != null){
						Path2D.Double path = (Path2D.Double) splits.get(key);
						if (path == null)
							splits.put(key, segment);
						else 
							path.append(segment, false);
					}
				}
				num = 0;
				minX = minY = Double.POSITIVE_INFINITY; 
				maxX = maxY = Double.NEGATIVE_INFINITY;
				break;
			default:
				log.error("Unsupported path iterator type " + type
						+ ". This is an mkgmap error.");
			}
	
			pit.next();
		}
		return splits;
	}
}
