Fix:Core:Renamed src to navit for cleanup of includes

git-svn-id: http://svn.code.sf.net/p/navit/code/trunk/navit@1059 ffa7fe5e-494d-0410-b361-a75ebd5db220

17 files changed, 2592 insertions, 0 deletions

diff --git a/navit/fib-1.1/Makefile.am b/navit/fib-1.1/Makefile.am
new file mode 100644
index 00000000..7c7b2a13
--- /dev/null
+++ b/navit/fib-1.1/Makefile.am
@@ -0,0 +1,3 @@
+noinst_LTLIBRARIES = libfib.la
+libfib_la_SOURCES = fib.c fib.h fibpriv.h
+EXTRA_DIST=README configure.in fh_extractmin.3 fh_makeheap.3 fh_makekeyheap.3 fibtest.c fibtest2.c tt.c use.c
diff --git a/navit/fib-1.1/README b/navit/fib-1.1/README
new file mode 100644
index 00000000..eabcd5f8
--- /dev/null
+++ b/navit/fib-1.1/README
@@ -0,0 +1,26 @@
+Version 1.1 now supports increasing the key using the fh_replace*
+functions.  Previously it would simply return NULL when you tried to
+increase the key.  It also improves performance slightly by only calling
+checkcons when we are about to use it, at extract, instead of calling it
+on every insert.
+
+I have now fixed fh_union and it properly updates the minimum.
+
+Thanks to Ryan Earl for pointing out that in fh_consolidate, it is VERY
+time consuming to constantly malloc/free an array of pointers.  The array
+is small enough that simply reallocating when more pointers are needed
+is ok.
+
+Thanks to Thomas Eschbach and Wolfgang Guenther who have pointed out bugs
+with my code.  Wolfgang Guenther provided a fix which put in on the correct
+track for where the bug was.  They have also provided a few test programs
+that exhibited other bugs which I have now integrated into my source so
+that you can easily regress test the library.
+
+I have reciently completed a review of the code.  I have made a number
+of improvements with a few minor interface changes.  There is another
+improvement to the rh_replace* family of functions to help eliminate
+redundant code.
+
+I'm still planning on writing a type safe memory allocator for use with
+the code instead of using malloc to hopefully improve performance slightly.
diff --git a/navit/fib-1.1/configure b/navit/fib-1.1/configure
new file mode 100755
index 00000000..62eaa3d0
--- /dev/null
+++ b/navit/fib-1.1/configure
@@ -0,0 +1,1045 @@
+#! /bin/sh
+
+# Guess values for system-dependent variables and create Makefiles.
+# Generated automatically using autoconf version 2.13 
+# Copyright (C) 1992, 93, 94, 95, 96 Free Software Foundation, Inc.
+#
+# This configure script is free software; the Free Software Foundation
+# gives unlimited permission to copy, distribute and modify it.
+
+# Defaults:
+ac_help=
+ac_default_prefix=/usr/local
+# Any additions from configure.in:
+
+# Initialize some variables set by options.
+# The variables have the same names as the options, with
+# dashes changed to underlines.
+build=NONE
+cache_file=./config.cache
+exec_prefix=NONE
+host=NONE
+no_create=
+nonopt=NONE
+no_recursion=
+prefix=NONE
+program_prefix=NONE
+program_suffix=NONE
+program_transform_name=s,x,x,
+silent=
+site=
+srcdir=
+target=NONE
+verbose=
+x_includes=NONE
+x_libraries=NONE
+bindir='${exec_prefix}/bin'
+sbindir='${exec_prefix}/sbin'
+libexecdir='${exec_prefix}/libexec'
+datadir='${prefix}/share'
+sysconfdir='${prefix}/etc'
+sharedstatedir='${prefix}/com'
+localstatedir='${prefix}/var'
+libdir='${exec_prefix}/lib'
+includedir='${prefix}/include'
+oldincludedir='/usr/include'
+infodir='${prefix}/info'
+mandir='${prefix}/man'
+
+# Initialize some other variables.
+subdirs=
+MFLAGS= MAKEFLAGS=
+SHELL=${CONFIG_SHELL-/bin/sh}
+# Maximum number of lines to put in a shell here document.
+ac_max_here_lines=12
+
+ac_prev=
+for ac_option
+do
+
+  # If the previous option needs an argument, assign it.
+  if test -n "$ac_prev"; then
+    eval "$ac_prev=\$ac_option"
+    ac_prev=
+    continue
+  fi
+
+  case "$ac_option" in
+  -*=*) ac_optarg=`echo "$ac_option" | sed 's/[-_a-zA-Z0-9]*=//'` ;;
+  *) ac_optarg= ;;
+  esac
+
+  # Accept the important Cygnus configure options, so we can diagnose typos.
+
+  case "$ac_option" in
+
+  -bindir | --bindir | --bindi | --bind | --bin | --bi)
+    ac_prev=bindir ;;
+  -bindir=* | --bindir=* | --bindi=* | --bind=* | --bin=* | --bi=*)
+    bindir="$ac_optarg" ;;
+
+  -build | --build | --buil | --bui | --bu)
+    ac_prev=build ;;
+  -build=* | --build=* | --buil=* | --bui=* | --bu=*)
+    build="$ac_optarg" ;;
+
+  -cache-file | --cache-file | --cache-fil | --cache-fi \
+  | --cache-f | --cache- | --cache | --cach | --cac | --ca | --c)
+    ac_prev=cache_file ;;
+  -cache-file=* | --cache-file=* | --cache-fil=* | --cache-fi=* \
+  | --cache-f=* | --cache-=* | --cache=* | --cach=* | --cac=* | --ca=* | --c=*)
+    cache_file="$ac_optarg" ;;
+
+  -datadir | --datadir | --datadi | --datad | --data | --dat | --da)
+    ac_prev=datadir ;;
+  -datadir=* | --datadir=* | --datadi=* | --datad=* | --data=* | --dat=* \
+  | --da=*)
+    datadir="$ac_optarg" ;;
+
+  -disable-* | --disable-*)
+    ac_feature=`echo $ac_option|sed -e 's/-*disable-//'`
+    # Reject names that are not valid shell variable names.
+    if test -n "`echo $ac_feature| sed 's/[-a-zA-Z0-9_]//g'`"; then
+      { echo "configure: error: $ac_feature: invalid feature name" 1>&2; exit 1; }
+    fi
+    ac_feature=`echo $ac_feature| sed 's/-/_/g'`
+    eval "enable_${ac_feature}=no" ;;
+
+  -enable-* | --enable-*)
+    ac_feature=`echo $ac_option|sed -e 's/-*enable-//' -e 's/=.*//'`
+    # Reject names that are not valid shell variable names.
+    if test -n "`echo $ac_feature| sed 's/[-_a-zA-Z0-9]//g'`"; then
+      { echo "configure: error: $ac_feature: invalid feature name" 1>&2; exit 1; }
+    fi
+    ac_feature=`echo $ac_feature| sed 's/-/_/g'`
+    case "$ac_option" in
+      *=*) ;;
+      *) ac_optarg=yes ;;
+    esac
+    eval "enable_${ac_feature}='$ac_optarg'" ;;
+
+  -exec-prefix | --exec_prefix | --exec-prefix | --exec-prefi \
+  | --exec-pref | --exec-pre | --exec-pr | --exec-p | --exec- \
+  | --exec | --exe | --ex)
+    ac_prev=exec_prefix ;;
+  -exec-prefix=* | --exec_prefix=* | --exec-prefix=* | --exec-prefi=* \
+  | --exec-pref=* | --exec-pre=* | --exec-pr=* | --exec-p=* | --exec-=* \
+  | --exec=* | --exe=* | --ex=*)
+    exec_prefix="$ac_optarg" ;;
+
+  -gas | --gas | --ga | --g)
+    # Obsolete; use --with-gas.
+    with_gas=yes ;;
+
+  -help | --help | --hel | --he)
+    # Omit some internal or obsolete options to make the list less imposing.
+    # This message is too long to be a string in the A/UX 3.1 sh.
+    cat << EOF
+Usage: configure [options] [host]
+Options: [defaults in brackets after descriptions]
+Configuration:
+  --cache-file=FILE       cache test results in FILE
+  --help                  print this message
+  --no-create             do not create output files
+  --quiet, --silent       do not print \`checking...' messages
+  --version               print the version of autoconf that created configure
+Directory and file names:
+  --prefix=PREFIX         install architecture-independent files in PREFIX
+                          [$ac_default_prefix]
+  --exec-prefix=EPREFIX   install architecture-dependent files in EPREFIX
+                          [same as prefix]
+  --bindir=DIR            user executables in DIR [EPREFIX/bin]
+  --sbindir=DIR           system admin executables in DIR [EPREFIX/sbin]
+  --libexecdir=DIR        program executables in DIR [EPREFIX/libexec]
+  --datadir=DIR           read-only architecture-independent data in DIR
+                          [PREFIX/share]
+  --sysconfdir=DIR        read-only single-machine data in DIR [PREFIX/etc]
+  --sharedstatedir=DIR    modifiable architecture-independent data in DIR
+                          [PREFIX/com]
+  --localstatedir=DIR     modifiable single-machine data in DIR [PREFIX/var]
+  --libdir=DIR            object code libraries in DIR [EPREFIX/lib]
+  --includedir=DIR        C header files in DIR [PREFIX/include]
+  --oldincludedir=DIR     C header files for non-gcc in DIR [/usr/include]
+  --infodir=DIR           info documentation in DIR [PREFIX/info]
+  --mandir=DIR            man documentation in DIR [PREFIX/man]
+  --srcdir=DIR            find the sources in DIR [configure dir or ..]
+  --program-prefix=PREFIX prepend PREFIX to installed program names
+  --program-suffix=SUFFIX append SUFFIX to installed program names
+  --program-transform-name=PROGRAM
+                          run sed PROGRAM on installed program names
+EOF
+    cat << EOF
+Host type:
+  --build=BUILD           configure for building on BUILD [BUILD=HOST]
+  --host=HOST             configure for HOST [guessed]
+  --target=TARGET         configure for TARGET [TARGET=HOST]
+Features and packages:
+  --disable-FEATURE       do not include FEATURE (same as --enable-FEATURE=no)
+  --enable-FEATURE[=ARG]  include FEATURE [ARG=yes]
+  --with-PACKAGE[=ARG]    use PACKAGE [ARG=yes]
+  --without-PACKAGE       do not use PACKAGE (same as --with-PACKAGE=no)
+  --x-includes=DIR        X include files are in DIR
+  --x-libraries=DIR       X library files are in DIR
+EOF
+    if test -n "$ac_help"; then
+      echo "--enable and --with options recognized:$ac_help"
+    fi
+    exit 0 ;;
+
+  -host | --host | --hos | --ho)
+    ac_prev=host ;;
+  -host=* | --host=* | --hos=* | --ho=*)
+    host="$ac_optarg" ;;
+
+  -includedir | --includedir | --includedi | --included | --include \
+  | --includ | --inclu | --incl | --inc)
+    ac_prev=includedir ;;
+  -includedir=* | --includedir=* | --includedi=* | --included=* | --include=* \
+  | --includ=* | --inclu=* | --incl=* | --inc=*)
+    includedir="$ac_optarg" ;;
+
+  -infodir | --infodir | --infodi | --infod | --info | --inf)
+    ac_prev=infodir ;;
+  -infodir=* | --infodir=* | --infodi=* | --infod=* | --info=* | --inf=*)
+    infodir="$ac_optarg" ;;
+
+  -libdir | --libdir | --libdi | --libd)
+    ac_prev=libdir ;;
+  -libdir=* | --libdir=* | --libdi=* | --libd=*)
+    libdir="$ac_optarg" ;;
+
+  -libexecdir | --libexecdir | --libexecdi | --libexecd | --libexec \
+  | --libexe | --libex | --libe)
+    ac_prev=libexecdir ;;
+  -libexecdir=* | --libexecdir=* | --libexecdi=* | --libexecd=* | --libexec=* \
+  | --libexe=* | --libex=* | --libe=*)
+    libexecdir="$ac_optarg" ;;
+
+  -localstatedir | --localstatedir | --localstatedi | --localstated \
+  | --localstate | --localstat | --localsta | --localst \
+  | --locals | --local | --loca | --loc | --lo)
+    ac_prev=localstatedir ;;
+  -localstatedir=* | --localstatedir=* | --localstatedi=* | --localstated=* \
+  | --localstate=* | --localstat=* | --localsta=* | --localst=* \
+  | --locals=* | --local=* | --loca=* | --loc=* | --lo=*)
+    localstatedir="$ac_optarg" ;;
+
+  -mandir | --mandir | --mandi | --mand | --man | --ma | --m)
+    ac_prev=mandir ;;
+  -mandir=* | --mandir=* | --mandi=* | --mand=* | --man=* | --ma=* | --m=*)
+    mandir="$ac_optarg" ;;
+
+  -nfp | --nfp | --nf)
+    # Obsolete; use --without-fp.
+    with_fp=no ;;
+
+  -no-create | --no-create | --no-creat | --no-crea | --no-cre \
+  | --no-cr | --no-c)
+    no_create=yes ;;
+
+  -no-recursion | --no-recursion | --no-recursio | --no-recursi \
+  | --no-recurs | --no-recur | --no-recu | --no-rec | --no-re | --no-r)
+    no_recursion=yes ;;
+
+  -oldincludedir | --oldincludedir | --oldincludedi | --oldincluded \
+  | --oldinclude | --oldinclud | --oldinclu | --oldincl | --oldinc \
+  | --oldin | --oldi | --old | --ol | --o)
+    ac_prev=oldincludedir ;;
+  -oldincludedir=* | --oldincludedir=* | --oldincludedi=* | --oldincluded=* \
+  | --oldinclude=* | --oldinclud=* | --oldinclu=* | --oldincl=* | --oldinc=* \
+  | --oldin=* | --oldi=* | --old=* | --ol=* | --o=*)
+    oldincludedir="$ac_optarg" ;;
+
+  -prefix | --prefix | --prefi | --pref | --pre | --pr | --p)
+    ac_prev=prefix ;;
+  -prefix=* | --prefix=* | --prefi=* | --pref=* | --pre=* | --pr=* | --p=*)
+    prefix="$ac_optarg" ;;
+
+  -program-prefix | --program-prefix | --program-prefi | --program-pref \
+  | --program-pre | --program-pr | --program-p)
+    ac_prev=program_prefix ;;
+  -program-prefix=* | --program-prefix=* | --program-prefi=* \
+  | --program-pref=* | --program-pre=* | --program-pr=* | --program-p=*)
+    program_prefix="$ac_optarg" ;;
+
+  -program-suffix | --program-suffix | --program-suffi | --program-suff \
+  | --program-suf | --program-su | --program-s)
+    ac_prev=program_suffix ;;
+  -program-suffix=* | --program-suffix=* | --program-suffi=* \
+  | --program-suff=* | --program-suf=* | --program-su=* | --program-s=*)
+    program_suffix="$ac_optarg" ;;
+
+  -program-transform-name | --program-transform-name \
+  | --program-transform-nam | --program-transform-na \
+  | --program-transform-n | --program-transform- \
+  | --program-transform | --program-transfor \
+  | --program-transfo | --program-transf \
+  | --program-trans | --program-tran \
+  | --progr-tra | --program-tr | --program-t)
+    ac_prev=program_transform_name ;;
+  -program-transform-name=* | --program-transform-name=* \
+  | --program-transform-nam=* | --program-transform-na=* \
+  | --program-transform-n=* | --program-transform-=* \
+  | --program-transform=* | --program-transfor=* \
+  | --program-transfo=* | --program-transf=* \
+  | --program-trans=* | --program-tran=* \
+  | --progr-tra=* | --program-tr=* | --program-t=*)
+    program_transform_name="$ac_optarg" ;;
+
+  -q | -quiet | --quiet | --quie | --qui | --qu | --q \
+  | -silent | --silent | --silen | --sile | --sil)
+    silent=yes ;;
+
+  -sbindir | --sbindir | --sbindi | --sbind | --sbin | --sbi | --sb)
+    ac_prev=sbindir ;;
+  -sbindir=* | --sbindir=* | --sbindi=* | --sbind=* | --sbin=* \
+  | --sbi=* | --sb=*)
+    sbindir="$ac_optarg" ;;
+
+  -sharedstatedir | --sharedstatedir | --sharedstatedi \
+  | --sharedstated | --sharedstate | --sharedstat | --sharedsta \
+  | --sharedst | --shareds | --shared | --share | --shar \
+  | --sha | --sh)
+    ac_prev=sharedstatedir ;;
+  -sharedstatedir=* | --sharedstatedir=* | --sharedstatedi=* \
+  | --sharedstated=* | --sharedstate=* | --sharedstat=* | --sharedsta=* \
+  | --sharedst=* | --shareds=* | --shared=* | --share=* | --shar=* \
+  | --sha=* | --sh=*)
+    sharedstatedir="$ac_optarg" ;;
+
+  -site | --site | --sit)
+    ac_prev=site ;;
+  -site=* | --site=* | --sit=*)
+    site="$ac_optarg" ;;
+
+  -srcdir | --srcdir | --srcdi | --srcd | --src | --sr)
+    ac_prev=srcdir ;;
+  -srcdir=* | --srcdir=* | --srcdi=* | --srcd=* | --src=* | --sr=*)
+    srcdir="$ac_optarg" ;;
+
+  -sysconfdir | --sysconfdir | --sysconfdi | --sysconfd | --sysconf \
+  | --syscon | --sysco | --sysc | --sys | --sy)
+    ac_prev=sysconfdir ;;
+  -sysconfdir=* | --sysconfdir=* | --sysconfdi=* | --sysconfd=* | --sysconf=* \
+  | --syscon=* | --sysco=* | --sysc=* | --sys=* | --sy=*)
+    sysconfdir="$ac_optarg" ;;
+
+  -target | --target | --targe | --targ | --tar | --ta | --t)
+    ac_prev=target ;;
+  -target=* | --target=* | --targe=* | --targ=* | --tar=* | --ta=* | --t=*)
+    target="$ac_optarg" ;;
+
+  -v | -verbose | --verbose | --verbos | --verbo | --verb)
+    verbose=yes ;;
+
+  -version | --version | --versio | --versi | --vers)
+    echo "configure generated by autoconf version 2.13"
+    exit 0 ;;
+
+  -with-* | --with-*)
+    ac_package=`echo $ac_option|sed -e 's/-*with-//' -e 's/=.*//'`
+    # Reject names that are not valid shell variable names.
+    if test -n "`echo $ac_package| sed 's/[-_a-zA-Z0-9]//g'`"; then
+      { echo "configure: error: $ac_package: invalid package name" 1>&2; exit 1; }
+    fi
+    ac_package=`echo $ac_package| sed 's/-/_/g'`
+    case "$ac_option" in
+      *=*) ;;
+      *) ac_optarg=yes ;;
+    esac
+    eval "with_${ac_package}='$ac_optarg'" ;;
+
+  -without-* | --without-*)
+    ac_package=`echo $ac_option|sed -e 's/-*without-//'`
+    # Reject names that are not valid shell variable names.
+    if test -n "`echo $ac_package| sed 's/[-a-zA-Z0-9_]//g'`"; then
+      { echo "configure: error: $ac_package: invalid package name" 1>&2; exit 1; }
+    fi
+    ac_package=`echo $ac_package| sed 's/-/_/g'`
+    eval "with_${ac_package}=no" ;;
+
+  --x)
+    # Obsolete; use --with-x.
+    with_x=yes ;;
+
+  -x-includes | --x-includes | --x-include | --x-includ | --x-inclu \
+  | --x-incl | --x-inc | --x-in | --x-i)
+    ac_prev=x_includes ;;
+  -x-includes=* | --x-includes=* | --x-include=* | --x-includ=* | --x-inclu=* \
+  | --x-incl=* | --x-inc=* | --x-in=* | --x-i=*)
+    x_includes="$ac_optarg" ;;
+
+  -x-libraries | --x-libraries | --x-librarie | --x-librari \
+  | --x-librar | --x-libra | --x-libr | --x-lib | --x-li | --x-l)
+    ac_prev=x_libraries ;;
+  -x-libraries=* | --x-libraries=* | --x-librarie=* | --x-librari=* \
+  | --x-librar=* | --x-libra=* | --x-libr=* | --x-lib=* | --x-li=* | --x-l=*)
+    x_libraries="$ac_optarg" ;;
+
+  -*) { echo "configure: error: $ac_option: invalid option; use --help to show usage" 1>&2; exit 1; }
+    ;;
+
+  *)
+    if test -n "`echo $ac_option| sed 's/[-a-z0-9.]//g'`"; then
+      echo "configure: warning: $ac_option: invalid host type" 1>&2
+    fi
+    if test "x$nonopt" != xNONE; then
+      { echo "configure: error: can only configure for one host and one target at a time" 1>&2; exit 1; }
+    fi
+    nonopt="$ac_option"
+    ;;
+
+  esac
+done
+
+if test -n "$ac_prev"; then
+  { echo "configure: error: missing argument to --`echo $ac_prev | sed 's/_/-/g'`" 1>&2; exit 1; }
+fi
+
+trap 'rm -fr conftest* confdefs* core core.* *.core $ac_clean_files; exit 1' 1 2 15
+
+# File descriptor usage:
+# 0 standard input
+# 1 file creation
+# 2 errors and warnings
+# 3 some systems may open it to /dev/tty
+# 4 used on the Kubota Titan
+# 6 checking for... messages and results
+# 5 compiler messages saved in config.log
+if test "$silent" = yes; then
+  exec 6>/dev/null
+else
+  exec 6>&1
+fi
+exec 5>./config.log
+
+echo "\
+This file contains any messages produced by compilers while
+running configure, to aid debugging if configure makes a mistake.
+" 1>&5
+
+# Strip out --no-create and --no-recursion so they do not pile up.
+# Also quote any args containing shell metacharacters.
+ac_configure_args=
+for ac_arg
+do
+  case "$ac_arg" in
+  -no-create | --no-create | --no-creat | --no-crea | --no-cre \
+  | --no-cr | --no-c) ;;
+  -no-recursion | --no-recursion | --no-recursio | --no-recursi \
+  | --no-recurs | --no-recur | --no-recu | --no-rec | --no-re | --no-r) ;;
+  *" "*|*"	"*|*[\[\]\~\#\$\^\&\*\(\)\{\}\\\|\;\<\>\?]*)
+  ac_configure_args="$ac_configure_args '$ac_arg'" ;;
+  *) ac_configure_args="$ac_configure_args $ac_arg" ;;
+  esac
+done
+
+# NLS nuisances.
+# Only set these to C if already set.  These must not be set unconditionally
+# because not all systems understand e.g. LANG=C (notably SCO).
+# Fixing LC_MESSAGES prevents Solaris sh from translating var values in `set'!
+# Non-C LC_CTYPE values break the ctype check.
+if test "${LANG+set}"   = set; then LANG=C;   export LANG;   fi
+if test "${LC_ALL+set}" = set; then LC_ALL=C; export LC_ALL; fi
+if test "${LC_MESSAGES+set}" = set; then LC_MESSAGES=C; export LC_MESSAGES; fi
+if test "${LC_CTYPE+set}"    = set; then LC_CTYPE=C;    export LC_CTYPE;    fi
+
+# confdefs.h avoids OS command line length limits that DEFS can exceed.
+rm -rf conftest* confdefs.h
+# AIX cpp loses on an empty file, so make sure it contains at least a newline.
+echo > confdefs.h
+
+# A filename unique to this package, relative to the directory that
+# configure is in, which we can look for to find out if srcdir is correct.
+ac_unique_file=fib.c
+
+# Find the source files, if location was not specified.
+if test -z "$srcdir"; then
+  ac_srcdir_defaulted=yes
+  # Try the directory containing this script, then its parent.
+  ac_prog=$0
+  ac_confdir=`echo $ac_prog|sed 's%/[^/][^/]*$%%'`
+  test "x$ac_confdir" = "x$ac_prog" && ac_confdir=.
+  srcdir=$ac_confdir
+  if test ! -r $srcdir/$ac_unique_file; then
+    srcdir=..
+  fi
+else
+  ac_srcdir_defaulted=no
+fi
+if test ! -r $srcdir/$ac_unique_file; then
+  if test "$ac_srcdir_defaulted" = yes; then
+    { echo "configure: error: can not find sources in $ac_confdir or .." 1>&2; exit 1; }
+  else
+    { echo "configure: error: can not find sources in $srcdir" 1>&2; exit 1; }
+  fi
+fi
+srcdir=`echo "${srcdir}" | sed 's%\([^/]\)/*$%\1%'`
+
+# Prefer explicitly selected file to automatically selected ones.
+if test -z "$CONFIG_SITE"; then
+  if test "x$prefix" != xNONE; then
+    CONFIG_SITE="$prefix/share/config.site $prefix/etc/config.site"
+  else
+    CONFIG_SITE="$ac_default_prefix/share/config.site $ac_default_prefix/etc/config.site"
+  fi
+fi
+for ac_site_file in $CONFIG_SITE; do
+  if test -r "$ac_site_file"; then
+    echo "loading site script $ac_site_file"
+    . "$ac_site_file"
+  fi
+done
+
+if test -r "$cache_file"; then
+  echo "loading cache $cache_file"
+  . $cache_file
+else
+  echo "creating cache $cache_file"
+  > $cache_file
+fi
+
+ac_ext=c
+# CFLAGS is not in ac_cpp because -g, -O, etc. are not valid cpp options.
+ac_cpp='$CPP $CPPFLAGS'
+ac_compile='${CC-cc} -c $CFLAGS $CPPFLAGS conftest.$ac_ext 1>&5'
+ac_link='${CC-cc} -o conftest${ac_exeext} $CFLAGS $CPPFLAGS $LDFLAGS conftest.$ac_ext $LIBS 1>&5'
+cross_compiling=$ac_cv_prog_cc_cross
+
+ac_exeext=
+ac_objext=o
+if (echo "testing\c"; echo 1,2,3) | grep c >/dev/null; then
+  # Stardent Vistra SVR4 grep lacks -e, says ghazi@caip.rutgers.edu.
+  if (echo -n testing; echo 1,2,3) | sed s/-n/xn/ | grep xn >/dev/null; then
+    ac_n= ac_c='
+' ac_t='	'
+  else
+    ac_n=-n ac_c= ac_t=
+  fi
+else
+  ac_n= ac_c='\c' ac_t=
+fi
+
+
+
+
+
+echo $ac_n "checking how to run the C preprocessor""... $ac_c" 1>&6
+echo "configure:529: checking how to run the C preprocessor" >&5
+# On Suns, sometimes $CPP names a directory.
+if test -n "$CPP" && test -d "$CPP"; then
+  CPP=
+fi
+if test -z "$CPP"; then
+if eval "test \"`echo '$''{'ac_cv_prog_CPP'+set}'`\" = set"; then
+  echo $ac_n "(cached) $ac_c" 1>&6
+else
+    # This must be in double quotes, not single quotes, because CPP may get
+  # substituted into the Makefile and "${CC-cc}" will confuse make.
+  CPP="${CC-cc} -E"
+  # On the NeXT, cc -E runs the code through the compiler's parser,
+  # not just through cpp.
+  cat > conftest.$ac_ext <<EOF
+#line 544 "configure"
+#include "confdefs.h"
+#include <assert.h>
+Syntax Error
+EOF
+ac_try="$ac_cpp conftest.$ac_ext >/dev/null 2>conftest.out"
+{ (eval echo configure:550: \"$ac_try\") 1>&5; (eval $ac_try) 2>&5; }
+ac_err=`grep -v '^ *+' conftest.out | grep -v "^conftest.${ac_ext}\$"`
+if test -z "$ac_err"; then
+  :
+else
+  echo "$ac_err" >&5
+  echo "configure: failed program was:" >&5
+  cat conftest.$ac_ext >&5
+  rm -rf conftest*
+  CPP="${CC-cc} -E -traditional-cpp"
+  cat > conftest.$ac_ext <<EOF
+#line 561 "configure"
+#include "confdefs.h"
+#include <assert.h>
+Syntax Error
+EOF
+ac_try="$ac_cpp conftest.$ac_ext >/dev/null 2>conftest.out"
+{ (eval echo configure:567: \"$ac_try\") 1>&5; (eval $ac_try) 2>&5; }
+ac_err=`grep -v '^ *+' conftest.out | grep -v "^conftest.${ac_ext}\$"`
+if test -z "$ac_err"; then
+  :
+else
+  echo "$ac_err" >&5
+  echo "configure: failed program was:" >&5
+  cat conftest.$ac_ext >&5
+  rm -rf conftest*
+  CPP="${CC-cc} -nologo -E"
+  cat > conftest.$ac_ext <<EOF
+#line 578 "configure"
+#include "confdefs.h"
+#include <assert.h>
+Syntax Error
+EOF
+ac_try="$ac_cpp conftest.$ac_ext >/dev/null 2>conftest.out"
+{ (eval echo configure:584: \"$ac_try\") 1>&5; (eval $ac_try) 2>&5; }
+ac_err=`grep -v '^ *+' conftest.out | grep -v "^conftest.${ac_ext}\$"`
+if test -z "$ac_err"; then
+  :
+else
+  echo "$ac_err" >&5
+  echo "configure: failed program was:" >&5
+  cat conftest.$ac_ext >&5
+  rm -rf conftest*
+  CPP=/lib/cpp
+fi
+rm -f conftest*
+fi
+rm -f conftest*
+fi
+rm -f conftest*
+  ac_cv_prog_CPP="$CPP"
+fi
+  CPP="$ac_cv_prog_CPP"
+else
+  ac_cv_prog_CPP="$CPP"
+fi
+echo "$ac_t""$CPP" 1>&6
+
+echo $ac_n "checking for ANSI C header files""... $ac_c" 1>&6
+echo "configure:609: checking for ANSI C header files" >&5
+if eval "test \"`echo '$''{'ac_cv_header_stdc'+set}'`\" = set"; then
+  echo $ac_n "(cached) $ac_c" 1>&6
+else
+  cat > conftest.$ac_ext <<EOF
+#line 614 "configure"
+#include "confdefs.h"
+#include <stdlib.h>
+#include <stdarg.h>
+#include <string.h>
+#include <float.h>
+EOF
+ac_try="$ac_cpp conftest.$ac_ext >/dev/null 2>conftest.out"
+{ (eval echo configure:622: \"$ac_try\") 1>&5; (eval $ac_try) 2>&5; }
+ac_err=`grep -v '^ *+' conftest.out | grep -v "^conftest.${ac_ext}\$"`
+if test -z "$ac_err"; then
+  rm -rf conftest*
+  ac_cv_header_stdc=yes
+else
+  echo "$ac_err" >&5
+  echo "configure: failed program was:" >&5
+  cat conftest.$ac_ext >&5
+  rm -rf conftest*
+  ac_cv_header_stdc=no
+fi
+rm -f conftest*
+
+if test $ac_cv_header_stdc = yes; then
+  # SunOS 4.x string.h does not declare mem*, contrary to ANSI.
+cat > conftest.$ac_ext <<EOF
+#line 639 "configure"
+#include "confdefs.h"
+#include <string.h>
+EOF
+if (eval "$ac_cpp conftest.$ac_ext") 2>&5 |
+  egrep "memchr" >/dev/null 2>&1; then
+  :
+else
+  rm -rf conftest*
+  ac_cv_header_stdc=no
+fi
+rm -f conftest*
+
+fi
+
+if test $ac_cv_header_stdc = yes; then
+  # ISC 2.0.2 stdlib.h does not declare free, contrary to ANSI.
+cat > conftest.$ac_ext <<EOF
+#line 657 "configure"
+#include "confdefs.h"
+#include <stdlib.h>
+EOF
+if (eval "$ac_cpp conftest.$ac_ext") 2>&5 |
+  egrep "free" >/dev/null 2>&1; then
+  :
+else
+  rm -rf conftest*
+  ac_cv_header_stdc=no
+fi
+rm -f conftest*
+
+fi
+
+if test $ac_cv_header_stdc = yes; then
+  # /bin/cc in Irix-4.0.5 gets non-ANSI ctype macros unless using -ansi.
+if test "$cross_compiling" = yes; then
+  :
+else
+  cat > conftest.$ac_ext <<EOF
+#line 678 "configure"
+#include "confdefs.h"
+#include <ctype.h>
+#define ISLOWER(c) ('a' <= (c) && (c) <= 'z')
+#define TOUPPER(c) (ISLOWER(c) ? 'A' + ((c) - 'a') : (c))
+#define XOR(e, f) (((e) && !(f)) || (!(e) && (f)))
+int main () { int i; for (i = 0; i < 256; i++)
+if (XOR (islower (i), ISLOWER (i)) || toupper (i) != TOUPPER (i)) exit(2);
+exit (0); }
+
+EOF
+if { (eval echo configure:689: \"$ac_link\") 1>&5; (eval $ac_link) 2>&5; } && test -s conftest${ac_exeext} && (./conftest; exit) 2>/dev/null
+then
+  :
+else
+  echo "configure: failed program was:" >&5
+  cat conftest.$ac_ext >&5
+  rm -fr conftest*
+  ac_cv_header_stdc=no
+fi
+rm -fr conftest*
+fi
+
+fi
+fi
+
+echo "$ac_t""$ac_cv_header_stdc" 1>&6
+if test $ac_cv_header_stdc = yes; then
+  cat >> confdefs.h <<\EOF
+#define STDC_HEADERS 1
+EOF
+
+fi
+
+for ac_hdr in limits.h
+do
+ac_safe=`echo "$ac_hdr" | sed 'y%./+-%__p_%'`
+echo $ac_n "checking for $ac_hdr""... $ac_c" 1>&6
+echo "configure:716: checking for $ac_hdr" >&5
+if eval "test \"`echo '$''{'ac_cv_header_$ac_safe'+set}'`\" = set"; then
+  echo $ac_n "(cached) $ac_c" 1>&6
+else
+  cat > conftest.$ac_ext <<EOF
+#line 721 "configure"
+#include "confdefs.h"
+#include <$ac_hdr>
+EOF
+ac_try="$ac_cpp conftest.$ac_ext >/dev/null 2>conftest.out"
+{ (eval echo configure:726: \"$ac_try\") 1>&5; (eval $ac_try) 2>&5; }
+ac_err=`grep -v '^ *+' conftest.out | grep -v "^conftest.${ac_ext}\$"`
+if test -z "$ac_err"; then
+  rm -rf conftest*
+  eval "ac_cv_header_$ac_safe=yes"
+else
+  echo "$ac_err" >&5
+  echo "configure: failed program was:" >&5
+  cat conftest.$ac_ext >&5
+  rm -rf conftest*
+  eval "ac_cv_header_$ac_safe=no"
+fi
+rm -f conftest*
+fi
+if eval "test \"`echo '$ac_cv_header_'$ac_safe`\" = yes"; then
+  echo "$ac_t""yes" 1>&6
+    ac_tr_hdr=HAVE_`echo $ac_hdr | sed 'y%abcdefghijklmnopqrstuvwxyz./-%ABCDEFGHIJKLMNOPQRSTUVWXYZ___%'`
+  cat >> confdefs.h <<EOF
+#define $ac_tr_hdr 1
+EOF
+ 
+else
+  echo "$ac_t""no" 1>&6
+fi
+done
+
+
+echo $ac_n "checking for inline""... $ac_c" 1>&6
+echo "configure:754: checking for inline" >&5
+if eval "test \"`echo '$''{'ac_cv_c_inline'+set}'`\" = set"; then
+  echo $ac_n "(cached) $ac_c" 1>&6
+else
+  ac_cv_c_inline=no
+for ac_kw in inline __inline__ __inline; do
+  cat > conftest.$ac_ext <<EOF
+#line 761 "configure"
+#include "confdefs.h"
+
+int main() {
+} $ac_kw foo() {
+; return 0; }
+EOF
+if { (eval echo configure:768: \"$ac_compile\") 1>&5; (eval $ac_compile) 2>&5; }; then
+  rm -rf conftest*
+  ac_cv_c_inline=$ac_kw; break
+else
+  echo "configure: failed program was:" >&5
+  cat conftest.$ac_ext >&5
+fi
+rm -f conftest*
+done
+
+fi
+
+echo "$ac_t""$ac_cv_c_inline" 1>&6
+case "$ac_cv_c_inline" in
+  inline | yes) ;;
+  no) cat >> confdefs.h <<\EOF
+#define inline 
+EOF
+ ;;
+  *)  cat >> confdefs.h <<EOF
+#define inline $ac_cv_c_inline
+EOF
+ ;;
+esac
+
+
+
+trap '' 1 2 15
+cat > confcache <<\EOF
+# This file is a shell script that caches the results of configure
+# tests run on this system so they can be shared between configure
+# scripts and configure runs.  It is not useful on other systems.
+# If it contains results you don't want to keep, you may remove or edit it.
+#
+# By default, configure uses ./config.cache as the cache file,
+# creating it if it does not exist already.  You can give configure
+# the --cache-file=FILE option to use a different cache file; that is
+# what configure does when it calls configure scripts in
+# subdirectories, so they share the cache.
+# Giving --cache-file=/dev/null disables caching, for debugging configure.
+# config.status only pays attention to the cache file if you give it the
+# --recheck option to rerun configure.
+#
+EOF
+# The following way of writing the cache mishandles newlines in values,
+# but we know of no workaround that is simple, portable, and efficient.
+# So, don't put newlines in cache variables' values.
+# Ultrix sh set writes to stderr and can't be redirected directly,
+# and sets the high bit in the cache file unless we assign to the vars.
+(set) 2>&1 |
+  case `(ac_space=' '; set | grep ac_space) 2>&1` in
+  *ac_space=\ *)
+    # `set' does not quote correctly, so add quotes (double-quote substitution
+    # turns \\\\ into \\, and sed turns \\ into \).
+    sed -n \
+      -e "s/'/'\\\\''/g" \
+      -e "s/^\\([a-zA-Z0-9_]*_cv_[a-zA-Z0-9_]*\\)=\\(.*\\)/\\1=\${\\1='\\2'}/p"
+    ;;
+  *)
+    # `set' quotes correctly as required by POSIX, so do not add quotes.
+    sed -n -e 's/^\([a-zA-Z0-9_]*_cv_[a-zA-Z0-9_]*\)=\(.*\)/\1=${\1=\2}/p'
+    ;;
+  esac >> confcache
+if cmp -s $cache_file confcache; then
+  :
+else
+  if test -w $cache_file; then
+    echo "updating cache $cache_file"
+    cat confcache > $cache_file
+  else
+    echo "not updating unwritable cache $cache_file"
+  fi
+fi
+rm -f confcache
+
+trap 'rm -fr conftest* confdefs* core core.* *.core $ac_clean_files; exit 1' 1 2 15
+
+test "x$prefix" = xNONE && prefix=$ac_default_prefix
+# Let make expand exec_prefix.
+test "x$exec_prefix" = xNONE && exec_prefix='${prefix}'
+
+# Any assignment to VPATH causes Sun make to only execute
+# the first set of double-colon rules, so remove it if not needed.
+# If there is a colon in the path, we need to keep it.
+if test "x$srcdir" = x.; then
+  ac_vpsub='/^[ 	]*VPATH[ 	]*=[^:]*$/d'
+fi
+
+trap 'rm -f $CONFIG_STATUS conftest*; exit 1' 1 2 15
+
+# Transform confdefs.h into DEFS.
+# Protect against shell expansion while executing Makefile rules.
+# Protect against Makefile macro expansion.
+cat > conftest.defs <<\EOF
+s%#define \([A-Za-z_][A-Za-z0-9_]*\) *\(.*\)%-D\1=\2%g
+s%[ 	`~#$^&*(){}\\|;'"<>?]%\\&%g
+s%\[%\\&%g
+s%\]%\\&%g
+s%\$%$$%g
+EOF
+DEFS=`sed -f conftest.defs confdefs.h | tr '\012' ' '`
+rm -f conftest.defs
+
+
+# Without the "./", some shells look in PATH for config.status.
+: ${CONFIG_STATUS=./config.status}
+
+echo creating $CONFIG_STATUS
+rm -f $CONFIG_STATUS
+cat > $CONFIG_STATUS <<EOF
+#! /bin/sh
+# Generated automatically by configure.
+# Run this file to recreate the current configuration.
+# This directory was configured as follows,
+# on host `(hostname || uname -n) 2>/dev/null | sed 1q`:
+#
+# $0 $ac_configure_args
+#
+# Compiler output produced by configure, useful for debugging
+# configure, is in ./config.log if it exists.
+
+ac_cs_usage="Usage: $CONFIG_STATUS [--recheck] [--version] [--help]"
+for ac_option
+do
+  case "\$ac_option" in
+  -recheck | --recheck | --rechec | --reche | --rech | --rec | --re | --r)
+    echo "running \${CONFIG_SHELL-/bin/sh} $0 $ac_configure_args --no-create --no-recursion"
+    exec \${CONFIG_SHELL-/bin/sh} $0 $ac_configure_args --no-create --no-recursion ;;
+  -version | --version | --versio | --versi | --vers | --ver | --ve | --v)
+    echo "$CONFIG_STATUS generated by autoconf version 2.13"
+    exit 0 ;;
+  -help | --help | --hel | --he | --h)
+    echo "\$ac_cs_usage"; exit 0 ;;
+  *) echo "\$ac_cs_usage"; exit 1 ;;
+  esac
+done
+
+ac_given_srcdir=$srcdir
+
+trap 'rm -fr `echo "Makefile" | sed "s/:[^ ]*//g"` conftest*; exit 1' 1 2 15
+EOF
+cat >> $CONFIG_STATUS <<EOF
+
+# Protect against being on the right side of a sed subst in config.status.
+sed 's/%@/@@/; s/@%/@@/; s/%g\$/@g/; /@g\$/s/[\\\\&%]/\\\\&/g;
+ s/@@/%@/; s/@@/@%/; s/@g\$/%g/' > conftest.subs <<\\CEOF
+$ac_vpsub
+$extrasub
+s%@SHELL@%$SHELL%g
+s%@CFLAGS@%$CFLAGS%g
+s%@CPPFLAGS@%$CPPFLAGS%g
+s%@CXXFLAGS@%$CXXFLAGS%g
+s%@FFLAGS@%$FFLAGS%g
+s%@DEFS@%$DEFS%g
+s%@LDFLAGS@%$LDFLAGS%g
+s%@LIBS@%$LIBS%g
+s%@exec_prefix@%$exec_prefix%g
+s%@prefix@%$prefix%g
+s%@program_transform_name@%$program_transform_name%g
+s%@bindir@%$bindir%g
+s%@sbindir@%$sbindir%g
+s%@libexecdir@%$libexecdir%g
+s%@datadir@%$datadir%g
+s%@sysconfdir@%$sysconfdir%g
+s%@sharedstatedir@%$sharedstatedir%g
+s%@localstatedir@%$localstatedir%g
+s%@libdir@%$libdir%g
+s%@includedir@%$includedir%g
+s%@oldincludedir@%$oldincludedir%g
+s%@infodir@%$infodir%g
+s%@mandir@%$mandir%g
+s%@CPP@%$CPP%g
+
+CEOF
+EOF
+
+cat >> $CONFIG_STATUS <<\EOF
+
+# Split the substitutions into bite-sized pieces for seds with
+# small command number limits, like on Digital OSF/1 and HP-UX.
+ac_max_sed_cmds=90 # Maximum number of lines to put in a sed script.
+ac_file=1 # Number of current file.
+ac_beg=1 # First line for current file.
+ac_end=$ac_max_sed_cmds # Line after last line for current file.
+ac_more_lines=:
+ac_sed_cmds=""
+while $ac_more_lines; do
+  if test $ac_beg -gt 1; then
+    sed "1,${ac_beg}d; ${ac_end}q" conftest.subs > conftest.s$ac_file
+  else
+    sed "${ac_end}q" conftest.subs > conftest.s$ac_file
+  fi
+  if test ! -s conftest.s$ac_file; then
+    ac_more_lines=false
+    rm -f conftest.s$ac_file
+  else
+    if test -z "$ac_sed_cmds"; then
+      ac_sed_cmds="sed -f conftest.s$ac_file"
+    else
+      ac_sed_cmds="$ac_sed_cmds | sed -f conftest.s$ac_file"
+    fi
+    ac_file=`expr $ac_file + 1`
+    ac_beg=$ac_end
+    ac_end=`expr $ac_end + $ac_max_sed_cmds`
+  fi
+done
+if test -z "$ac_sed_cmds"; then
+  ac_sed_cmds=cat
+fi
+EOF
+
+cat >> $CONFIG_STATUS <<EOF
+
+CONFIG_FILES=\${CONFIG_FILES-"Makefile"}
+EOF
+cat >> $CONFIG_STATUS <<\EOF
+for ac_file in .. $CONFIG_FILES; do if test "x$ac_file" != x..; then
+  # Support "outfile[:infile[:infile...]]", defaulting infile="outfile.in".
+  case "$ac_file" in
+  *:*) ac_file_in=`echo "$ac_file"|sed 's%[^:]*:%%'`
+       ac_file=`echo "$ac_file"|sed 's%:.*%%'` ;;
+  *) ac_file_in="${ac_file}.in" ;;
+  esac
+
+  # Adjust a relative srcdir, top_srcdir, and INSTALL for subdirectories.
+
+  # Remove last slash and all that follows it.  Not all systems have dirname.
+  ac_dir=`echo $ac_file|sed 's%/[^/][^/]*$%%'`
+  if test "$ac_dir" != "$ac_file" && test "$ac_dir" != .; then
+    # The file is in a subdirectory.
+    test ! -d "$ac_dir" && mkdir "$ac_dir"
+    ac_dir_suffix="/`echo $ac_dir|sed 's%^\./%%'`"
+    # A "../" for each directory in $ac_dir_suffix.
+    ac_dots=`echo $ac_dir_suffix|sed 's%/[^/]*%../%g'`
+  else
+    ac_dir_suffix= ac_dots=
+  fi
+
+  case "$ac_given_srcdir" in
+  .)  srcdir=.
+      if test -z "$ac_dots"; then top_srcdir=.
+      else top_srcdir=`echo $ac_dots|sed 's%/$%%'`; fi ;;
+  /*) srcdir="$ac_given_srcdir$ac_dir_suffix"; top_srcdir="$ac_given_srcdir" ;;
+  *) # Relative path.
+    srcdir="$ac_dots$ac_given_srcdir$ac_dir_suffix"
+    top_srcdir="$ac_dots$ac_given_srcdir" ;;
+  esac
+
+
+  echo creating "$ac_file"
+  rm -f "$ac_file"
+  configure_input="Generated automatically from `echo $ac_file_in|sed 's%.*/%%'` by configure."
+  case "$ac_file" in
+  *Makefile*) ac_comsub="1i\\
+# $configure_input" ;;
+  *) ac_comsub= ;;
+  esac
+
+  ac_file_inputs=`echo $ac_file_in|sed -e "s%^%$ac_given_srcdir/%" -e "s%:% $ac_given_srcdir/%g"`
+  sed -e "$ac_comsub
+s%@configure_input@%$configure_input%g
+s%@srcdir@%$srcdir%g
+s%@top_srcdir@%$top_srcdir%g
+" $ac_file_inputs | (eval "$ac_sed_cmds") > $ac_file
+fi; done
+rm -f conftest.s*
+
+EOF
+cat >> $CONFIG_STATUS <<EOF
+
+EOF
+cat >> $CONFIG_STATUS <<\EOF
+
+exit 0
+EOF
+chmod +x $CONFIG_STATUS
+rm -fr confdefs* $ac_clean_files
+test "$no_create" = yes || ${CONFIG_SHELL-/bin/sh} $CONFIG_STATUS || exit 1
+
diff --git a/navit/fib-1.1/configure.in b/navit/fib-1.1/configure.in
new file mode 100644
index 00000000..82701527
--- /dev/null
+++ b/navit/fib-1.1/configure.in
@@ -0,0 +1,17 @@
+dnl Process this file with autoconf to produce a configure script.
+AC_INIT(fib.c)
+
+dnl Checks for programs.
+
+dnl Checks for libraries.
+
+dnl Checks for header files.
+AC_HEADER_STDC
+AC_CHECK_HEADERS(limits.h)
+
+dnl Checks for typedefs, structures, and compiler characteristics.
+AC_C_INLINE
+
+dnl Checks for library functions.
+
+AC_OUTPUT(Makefile)
diff --git a/navit/fib-1.1/fh_extractmin.3 b/navit/fib-1.1/fh_extractmin.3
new file mode 100644
index 00000000..e1492b40
--- /dev/null
+++ b/navit/fib-1.1/fh_extractmin.3
@@ -0,0 +1,97 @@
+.TH FH_EXTRACTMIN 3 "29 Mar 2000" "libfib"
+.SH NAME
+fh_extractmin \- extract minimum element from a Fibonacci Heap
+.SH SYNOPSIS
+#include <fib.h>
+.PP
+void *
+.PD 0
+.HP 8
+.BR fh_extractmin "(struct fibheap *heap)"
+.PD
+.PP
+void *
+.PD 0
+.HP 8
+.BR fh_min "(struct fibheap *heap)"
+.PD
+.PP
+void *
+.PD 0
+.HP 8
+.BR fh_replacedata "(struct fibheap *heap, struct fibheap_el *elem, void *data)"
+.PD
+.PP
+void *
+.PD 0
+.HP 8
+.BR fh_delete "(struct fibheap *heap, struct fibheap_el *elem)"
+.PD
+.PP
+void
+.PD 0
+.HP 8
+.BR fh_deleteheap "(struct fibheap *heap)"
+.PD
+.PP
+struct fibheap *
+.PD 0
+.HP 8
+.BR fh_union "(struct fibheap *heapa, struct fibheap *heapb)"
+.PD
+.SH DESCRIPTION
+These functions are shared between both key heaps and normal heaps.
+.PP
+Once a
+.B elem
+pointer has been passed to
+.BR fh_delete (3)
+that
+.B elem
+pointer may be reused to store another datum.
+You should make sure that you destroy any copies of the pointer.
+.SH RETURN VALUES
+The
+.B fh_extractmin
+function returns the value of
+.B data
+that is the minimum element and removes it from the heap.
+.PP
+The
+.B fh_min
+function returns the current minimum element but does
+.I not
+remove it from the heap.
+.PP
+The
+.B fh_replacedata
+replaces the data in
+.B elem
+and returns the old data.
+.PP
+The
+.B fh_delete
+function removes
+.B elem
+from the heap, and returns the
+.B data
+that was stored in the element.
+.PP
+The
+.B fh_deleteheap
+complete destroys the heap.  It does not free any user supplied
+.B data
+elements stored in the heap.
+.PP
+The
+.B fh_union
+function returns the union of the two heaps
+.B heapa
+and
+.BR heapb .
+.SH SEE ALSO
+.BR fh_makeheap (3),
+.BR fh_makekeyheap (3)
+.SH AUTHORS
+This library and man page was writen by John-Mark Gurney <gurney_j@efn.org>.
+.SH BUGS
diff --git a/navit/fib-1.1/fh_makeheap.3 b/navit/fib-1.1/fh_makeheap.3
new file mode 100644
index 00000000..bd867cd0
--- /dev/null
+++ b/navit/fib-1.1/fh_makeheap.3
@@ -0,0 +1,17 @@
+.TH FH_MAKEHEAP 3 "29 Mar 2000" "libfib"
+.SH NAME
+fh_makeheap \- make a Fibonacci Heap
+.SH SYNOPSIS
+.nf
+#include <fib.h>
+.PP
+struct fibheap *
+.BR fh_makeheap (void)
+.fi
+.SH DESCRIPTION
+.SH RETURN VALUES
+.SH FILES
+.SH SEE ALSO
+.SH AUTHORS
+This library and man page was writen by John-Mark Gurney <gurney_j@efn.org>.
+.SH BUGS
diff --git a/navit/fib-1.1/fh_makekeyheap.3 b/navit/fib-1.1/fh_makekeyheap.3
new file mode 100644
index 00000000..f55d4307
--- /dev/null
+++ b/navit/fib-1.1/fh_makekeyheap.3
@@ -0,0 +1,84 @@
+.TH FH_MAKEKEYHEAP 3 "29 Mar 2000" "libfib"
+.SH NAME
+fh_makekeyheap \- make a Fibonacci key Heap
+.SH SYNOPSIS
+#include <fib.h>
+.PP
+struct fibheap *
+.PD 0
+.HP 8
+.BR fh_makekeyheap (void)
+.PD
+.PP
+struct fibheap_el *
+.PD 0
+.HP 8
+.BR fh_insertkey "(struct fibheap *heap, int key, void *data)"
+.PD
+.PP
+int
+.PD 0
+.HP 8
+.BR fh_minkey "(struct fibheap *heap)"
+.PD
+.PP
+void *
+.PD 0
+.HP 8
+.BR fh_replacekey "(struct fibheap *heap, struct fibheap_el *elem, int key)"
+.PD
+.PP
+void *
+.PD 0
+.HP 8
+.BR fh_replacekeydata "(struct fibheap *heap, struct fibheap_el *elem, int key, void *data)"
+.PD
+.SH DESCRIPTION
+The
+.B fh_makekeyheap
+function makes a Fibonacci heap which does ordering based on an
+integer key that is given in addition to the data.
+This menthod is useful so that you can eliminate the need to call
+a comparision function to order the data in the heap.
+.PP
+The pointer to the structure
+.B fibheap
+returned by
+.B fh_makekeyheap
+is an opaque structure.  The the pointer can only be passed to other
+functions in the
+.B libfib
+library.
+.PP
+The
+.B fh_insertkey
+function inserts the
+.B data
+element into the heap with a value of
+.BR key .
+The pointer returned can be used in calls to functions like
+.BR fh_delete (3)
+to delete the key from the heap before it gets extracted via
+.BR fh_extractmin (3).
+.SH RETURN VALUES
+The
+.B fh_makekeyheap
+function returns a pointer to a heap structure used to insert and extract
+data elements.
+.PP
+The
+.B fh_insertkey
+functions returns a pointer to a heap element structure which can be used
+to manimulate that data element in the heap.
+.PP
+The
+.B fh_minkey
+function returns the integer key of the data at the top of the heap.  If you would like to view the data, see
+.BR fh_min (3).
+.SH SEE ALSO
+.BR fh_extractmin (3)
+.SH AUTHORS
+This library and man page was writen by John-Mark Gurney <gurney_j@efn.org>.
+.SH BUGS
+A key heap does not provide a way for handling key collitions and deffering
+decission to a user provided function to resolve colissions.
diff --git a/navit/fib-1.1/fib.c b/navit/fib-1.1/fib.c
new file mode 100644
index 00000000..276b6bd3
--- /dev/null
+++ b/navit/fib-1.1/fib.c
@@ -0,0 +1,699 @@
+/*-
+ * Copyright 1997-2003 John-Mark Gurney.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ *	$Id: fib.c,v 1.2 2007-07-04 22:44:39 martin-s Exp $
+ *
+ */
+
+#include <fib.h>
+#include <fibpriv.h>
+
+#include <limits.h>
+#include <stdlib.h>
+
+#define swap(type, a, b)		\
+		do {			\
+			type c;		\
+			c = a;		\
+			a = b;		\
+			b = c;		\
+		} while (0)		\
+
+#define INT_BITS        (sizeof(int) * 8)
+static inline int
+ceillog2(unsigned int a)
+{
+	int oa;
+	int i;
+	int b;
+
+	oa = a;
+	b = INT_BITS / 2;
+	i = 0;
+	while (b) {
+		i = (i << 1);
+		if (a >= (1 << b)) {
+			a /= (1 << b);
+			i = i | 1;
+		} else
+			a &= (1 << b) - 1;
+		b /= 2;
+	}
+	if ((1 << i) == oa)
+		return i;
+	else
+		return i + 1;
+}
+
+/*
+ * Private Heap Functions
+ */
+static void
+fh_deleteel(struct fibheap *h, struct fibheap_el *x)
+{
+	void *data;
+	int key;
+
+	data = x->fhe_data;
+	key = x->fhe_key;
+
+	if (!h->fh_keys)
+		fh_replacedata(h, x, h->fh_neginf);
+	else
+		fh_replacekey(h, x, INT_MIN);
+	if (fh_extractminel(h) != x) {
+		/*
+		 * XXX - This should never happen as fh_replace should set it
+		 * to min.
+		 */
+		abort();
+	}
+
+	x->fhe_data = data;
+	x->fhe_key = key;
+}
+
+static void
+fh_initheap(struct fibheap *new)
+{
+	new->fh_cmp_fnct = NULL;
+	new->fh_neginf = NULL;
+	new->fh_n = 0;
+	new->fh_Dl = -1;
+	new->fh_cons = NULL;
+	new->fh_min = NULL;
+	new->fh_root = NULL;
+	new->fh_keys = 0;
+#ifdef FH_STATS
+	new->fh_maxn = 0;
+	new->fh_ninserts = 0;
+	new->fh_nextracts = 0;
+#endif
+}
+
+static void
+fh_destroyheap(struct fibheap *h)
+{
+	h->fh_cmp_fnct = NULL;
+	h->fh_neginf = NULL;
+	if (h->fh_cons != NULL)
+		free(h->fh_cons);
+	h->fh_cons = NULL;
+	free(h);
+}
+
+/*
+ * Public Heap Functions
+ */
+struct fibheap *
+fh_makekeyheap()
+{
+	struct fibheap *n;
+
+	if ((n = malloc(sizeof *n)) == NULL)
+		return NULL;
+
+	fh_initheap(n);
+	n->fh_keys = 1;
+
+	return n;
+}
+
+struct fibheap *
+fh_makeheap()
+{
+	struct fibheap *n;
+
+	if ((n = malloc(sizeof *n)) == NULL)
+		return NULL;
+
+	fh_initheap(n);
+
+	return n;
+}
+
+voidcmp
+fh_setcmp(struct fibheap *h, voidcmp fnct)
+{
+	voidcmp oldfnct;
+	
+	oldfnct = h->fh_cmp_fnct;
+	h->fh_cmp_fnct = fnct;
+
+	return oldfnct;
+}
+
+void *
+fh_setneginf(struct fibheap *h, void *data)
+{
+	void *old;
+
+	old = h->fh_neginf;
+	h->fh_neginf = data;
+
+	return old;
+}
+
+struct fibheap *
+fh_union(struct fibheap *ha, struct fibheap *hb)
+{
+	struct fibheap_el *x;
+
+	if (ha->fh_root == NULL || hb->fh_root == NULL) {
+		/* either one or both are empty */
+		if (ha->fh_root == NULL) {
+			fh_destroyheap(ha);
+			return hb;
+		} else {
+			fh_destroyheap(hb);
+			return ha;
+		}
+	}
+	ha->fh_root->fhe_left->fhe_right = hb->fh_root;
+	hb->fh_root->fhe_left->fhe_right = ha->fh_root;
+	x = ha->fh_root->fhe_left;
+	ha->fh_root->fhe_left = hb->fh_root->fhe_left;
+	hb->fh_root->fhe_left = x;
+	ha->fh_n += hb->fh_n;
+	/*
+	 * we probably should also keep stats on number of unions
+	 */
+
+	/* set fh_min if necessary */
+	if (fh_compare(ha, hb->fh_min, ha->fh_min) < 0)
+		ha->fh_min = hb->fh_min;
+
+	fh_destroyheap(hb);
+	return ha;
+}
+
+void
+fh_deleteheap(struct fibheap *h)
+{
+	/*
+	 * We could do this even faster by walking each binomial tree, but
+	 * this is simpler to code.
+	 */
+	while (h->fh_min != NULL)
+		fhe_destroy(fh_extractminel(h));
+
+	fh_destroyheap(h);
+}
+
+/*
+ * Public Key Heap Functions
+ */
+struct fibheap_el *
+fh_insertkey(struct fibheap *h, int key, void *data)
+{
+	struct fibheap_el *x;
+
+	if ((x = fhe_newelem()) == NULL)
+		return NULL;
+
+	/* just insert on root list, and make sure it's not the new min */
+	x->fhe_data = data;
+	x->fhe_key = key;
+
+	fh_insertel(h, x);
+
+	return x;
+}
+
+int
+fh_minkey(struct fibheap *h)
+{
+	if (h->fh_min == NULL)
+		return INT_MIN;
+	return h->fh_min->fhe_key;
+}
+
+int
+fh_replacekey(struct fibheap *h, struct fibheap_el *x, int key)
+{
+	int ret;
+
+	ret = x->fhe_key;
+	(void)fh_replacekeydata(h, x, key, x->fhe_data);
+
+	return ret;
+}
+
+#include <stdio.h>
+
+void *
+fh_replacekeydata(struct fibheap *h, struct fibheap_el *x, int key, void *data)
+{
+	void *odata;
+	int okey;
+	struct fibheap_el *y;
+	int r;
+
+	odata = x->fhe_data;
+	okey = x->fhe_key;
+
+	/*
+	 * we can increase a key by deleting and reinserting, that
+	 * requires O(lgn) time.
+	 */
+	if ((r = fh_comparedata(h, key, data, x)) > 0) {
+		printf("fh_comparedata r=%d key=%d data=%p\n", r, key, data);
+		/* XXX - bad code! */
+		abort();
+		fh_deleteel(h, x);
+
+		x->fhe_data = data;
+		x->fhe_key = key;
+
+		fh_insertel(h, x);
+
+		return odata;
+	}
+
+	x->fhe_data = data;
+	x->fhe_key = key;
+
+	/* because they are equal, we don't have to do anything */
+	if (r == 0)
+		return odata;
+
+	y = x->fhe_p;
+
+	if (h->fh_keys && okey == key)
+		return odata;
+
+	if (y != NULL && fh_compare(h, x, y) <= 0) {
+		fh_cut(h, x, y);
+		fh_cascading_cut(h, y);
+	}
+
+	/*
+	 * the = is so that the call from fh_delete will delete the proper
+	 * element.
+	 */
+	if (fh_compare(h, x, h->fh_min) <= 0)
+		h->fh_min = x;
+
+	return odata;
+}
+
+/*
+ * Public void * Heap Functions
+ */
+/*
+ * this will return these values:
+ *	NULL	failed for some reason
+ *	ptr	token to use for manipulation of data
+ */
+struct fibheap_el *
+fh_insert(struct fibheap *h, void *data)
+{
+	struct fibheap_el *x;
+
+	if ((x = fhe_newelem()) == NULL)
+		return NULL;
+
+	/* just insert on root list, and make sure it's not the new min */
+	x->fhe_data = data;
+
+	fh_insertel(h, x);
+
+	return x;
+}
+
+void *
+fh_min(struct fibheap *h)
+{
+	if (h->fh_min == NULL)
+		return NULL;
+	return h->fh_min->fhe_data;
+}
+
+void *
+fh_extractmin(struct fibheap *h)
+{
+	struct fibheap_el *z;
+	void *ret;
+
+	ret = NULL;
+
+	if (h->fh_min != NULL) {
+		z = fh_extractminel(h);
+		ret = z->fhe_data;
+#ifndef NO_FREE
+		fhe_destroy(z);
+#endif
+
+	}
+
+	return ret;
+}
+
+void *
+fh_replacedata(struct fibheap *h, struct fibheap_el *x, void *data)
+{
+	return fh_replacekeydata(h, x, x->fhe_key, data);
+}
+
+void *
+fh_delete(struct fibheap *h, struct fibheap_el *x)
+{
+	void *k;
+
+	k = x->fhe_data;
+	if (!h->fh_keys)
+		fh_replacedata(h, x, h->fh_neginf);
+	else
+		fh_replacekey(h, x, INT_MIN);
+	fh_extractmin(h);
+
+	return k;
+}
+
+/*
+ * Statistics Functions
+ */
+#ifdef FH_STATS
+int
+fh_maxn(struct fibheap *h)
+{
+	return h->fh_maxn;
+}
+
+int
+fh_ninserts(struct fibheap *h)
+{
+	return h->fh_ninserts;
+}
+
+int
+fh_nextracts(struct fibheap *h)
+{
+	return h->fh_nextracts;
+}
+#endif
+
+/*
+ * begin of private element fuctions
+ */
+static struct fibheap_el *
+fh_extractminel(struct fibheap *h)
+{
+	struct fibheap_el *ret;
+	struct fibheap_el *x, *y, *orig;
+
+	ret = h->fh_min;
+
+	orig = NULL;
+	/* put all the children on the root list */
+	/* for true consistancy, we should use fhe_remove */
+	for(x = ret->fhe_child; x != orig && x != NULL;) {
+		if (orig == NULL)
+			orig = x;
+		y = x->fhe_right;
+		x->fhe_p = NULL;
+		fh_insertrootlist(h, x);
+		x = y;
+	}
+	/* remove minimum from root list */
+	fh_removerootlist(h, ret);
+	h->fh_n--;
+
+	/* if we aren't empty, consolidate the heap */
+	if (h->fh_n == 0)
+		h->fh_min = NULL;
+	else {
+		h->fh_min = ret->fhe_right;
+		fh_consolidate(h);
+	}
+
+#ifdef FH_STATS
+	h->fh_nextracts++;
+#endif
+
+	return ret;
+}
+
+static void
+fh_insertrootlist(struct fibheap *h, struct fibheap_el *x)
+{
+	if (h->fh_root == NULL) {
+		h->fh_root = x;
+		x->fhe_left = x;
+		x->fhe_right = x;
+		return;
+	}
+
+	fhe_insertafter(h->fh_root, x);
+}
+
+static void
+fh_removerootlist(struct fibheap *h, struct fibheap_el *x)
+{
+	if (x->fhe_left == x)
+		h->fh_root = NULL;
+	else
+		h->fh_root = fhe_remove(x);
+}
+
+static void
+fh_consolidate(struct fibheap *h)
+{
+	struct fibheap_el **a;
+	struct fibheap_el *w;
+	struct fibheap_el *y;
+	struct fibheap_el *x;
+	int i;
+	int d;
+	int D;
+
+	fh_checkcons(h);
+
+	/* assign a the value of h->fh_cons so I don't have to rewrite code */
+	D = h->fh_Dl + 1;
+	a = h->fh_cons;
+
+	for (i = 0; i < D; i++)
+		a[i] = NULL;
+
+	while ((w = h->fh_root) != NULL) {
+		x = w;
+		fh_removerootlist(h, w);
+		d = x->fhe_degree;
+		/* XXX - assert that d < D */
+		while(a[d] != NULL) {
+			y = a[d];
+			if (fh_compare(h, x, y) > 0)
+				swap(struct fibheap_el *, x, y);
+			fh_heaplink(h, y, x);
+			a[d] = NULL;
+			d++;
+		}
+		a[d] = x;
+	}
+	h->fh_min = NULL;
+	for (i = 0; i < D; i++)
+		if (a[i] != NULL) {
+			fh_insertrootlist(h, a[i]);
+			if (h->fh_min == NULL || fh_compare(h, a[i],
+			    h->fh_min) < 0)
+				h->fh_min = a[i];
+		}
+}
+
+static void
+fh_heaplink(struct fibheap *h, struct fibheap_el *y, struct fibheap_el *x)
+{
+	/* make y a child of x */
+	if (x->fhe_child == NULL)
+		x->fhe_child = y;
+	else
+		fhe_insertbefore(x->fhe_child, y);
+	y->fhe_p = x;
+	x->fhe_degree++;
+	y->fhe_mark = 0;
+}
+
+static void
+fh_cut(struct fibheap *h, struct fibheap_el *x, struct fibheap_el *y)
+{
+	fhe_remove(x);
+	y->fhe_degree--;
+	fh_insertrootlist(h, x);
+	x->fhe_p = NULL;
+	x->fhe_mark = 0;
+}
+
+static void
+fh_cascading_cut(struct fibheap *h, struct fibheap_el *y)
+{
+	struct fibheap_el *z;
+
+	while ((z = y->fhe_p) != NULL) {
+		if (y->fhe_mark == 0) {
+			y->fhe_mark = 1;
+			return;
+		} else {
+			fh_cut(h, y, z);
+			y = z;
+		}
+	}
+}
+
+/*
+ * begining of handling elements of fibheap
+ */
+static struct fibheap_el *
+fhe_newelem()
+{
+	struct fibheap_el *e;
+
+	if ((e = malloc(sizeof *e)) == NULL)
+		return NULL;
+
+	fhe_initelem(e);
+
+	return e;
+}
+
+static void
+fhe_initelem(struct fibheap_el *e)
+{
+	e->fhe_degree = 0;
+	e->fhe_mark = 0;
+	e->fhe_p = NULL;
+	e->fhe_child = NULL;
+	e->fhe_left = e;
+	e->fhe_right = e;
+	e->fhe_data = NULL;
+}
+
+static void
+fhe_insertafter(struct fibheap_el *a, struct fibheap_el *b)
+{
+	if (a == a->fhe_right) {
+		a->fhe_right = b;
+		a->fhe_left = b;
+		b->fhe_right = a;
+		b->fhe_left = a;
+	} else {
+		b->fhe_right = a->fhe_right;
+		a->fhe_right->fhe_left = b;
+		a->fhe_right = b;
+		b->fhe_left = a;
+	}
+}
+
+static inline void
+fhe_insertbefore(struct fibheap_el *a, struct fibheap_el *b)
+{
+	fhe_insertafter(a->fhe_left, b);
+}
+
+static struct fibheap_el *
+fhe_remove(struct fibheap_el *x)
+{
+	struct fibheap_el *ret;
+
+	if (x == x->fhe_left)
+		ret = NULL;
+	else
+		ret = x->fhe_left;
+
+	/* fix the parent pointer */
+	if (x->fhe_p != NULL && x->fhe_p->fhe_child == x)
+		x->fhe_p->fhe_child = ret;
+
+	x->fhe_right->fhe_left = x->fhe_left;
+	x->fhe_left->fhe_right = x->fhe_right;
+
+	/* clear out hanging pointers */
+	x->fhe_p = NULL;
+	x->fhe_left = x;
+	x->fhe_right = x;
+
+	return ret;
+}
+
+static void
+fh_checkcons(struct fibheap *h)
+{
+	int oDl;
+
+	/* make sure we have enough memory allocated to "reorganize" */
+	if (h->fh_Dl == -1 || h->fh_n > (1 << h->fh_Dl)) {
+		oDl = h->fh_Dl;
+		if ((h->fh_Dl = ceillog2(h->fh_n) + 1) < 8)
+			h->fh_Dl = 8;
+		if (oDl != h->fh_Dl)
+			h->fh_cons = (struct fibheap_el **)realloc(h->fh_cons,
+			    sizeof *h->fh_cons * (h->fh_Dl + 1));
+		if (h->fh_cons == NULL)
+			abort();
+	}
+}
+
+static int
+fh_compare(struct fibheap *h, struct fibheap_el *a, struct fibheap_el *b)
+{
+	if (h->fh_keys) {
+		if (a->fhe_key < b->fhe_key)
+			return -1;
+		if (a->fhe_key == b->fhe_key)
+			return 0;
+		return 1;
+	} else
+		return h->fh_cmp_fnct(a->fhe_data, b->fhe_data);
+}
+
+static int
+fh_comparedata(struct fibheap *h, int key, void *data, struct fibheap_el *b)
+{
+	struct fibheap_el a;
+
+	a.fhe_key = key;
+	a.fhe_data = data;
+
+	return fh_compare(h, &a, b);
+}
+
+static void
+fh_insertel(struct fibheap *h, struct fibheap_el *x)
+{
+	fh_insertrootlist(h, x);
+
+	if (h->fh_min == NULL || (h->fh_keys ? x->fhe_key < h->fh_min->fhe_key
+	    : h->fh_cmp_fnct(x->fhe_data, h->fh_min->fhe_data) < 0))
+		h->fh_min = x;
+
+	h->fh_n++;
+
+#ifdef FH_STATS
+	if (h->fh_n > h->fh_maxn)
+		h->fh_maxn = h->fh_n;
+	h->fh_ninserts++;
+#endif
+
+}
diff --git a/navit/fib-1.1/fib.h b/navit/fib-1.1/fib.h
new file mode 100644
index 00000000..d8564d3c
--- /dev/null
+++ b/navit/fib-1.1/fib.h
@@ -0,0 +1,64 @@
+/*-
+ * Copyright 1997, 1998-2003 John-Mark Gurney.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ *	$Id: fib.h,v 1.1 2005-12-02 10:41:56 martin-s Exp $
+ *
+ */
+
+#ifndef _FIB_H_
+#define _FIB_H_
+
+struct fibheap;
+struct fibheap_el;
+typedef int (*voidcmp)(void *, void *);
+
+/* functions for key heaps */
+struct fibheap *fh_makekeyheap(void);
+struct fibheap_el *fh_insertkey(struct fibheap *, int, void *);
+int fh_minkey(struct fibheap *);
+int fh_replacekey(struct fibheap *, struct fibheap_el *, int);
+void *fh_replacekeydata(struct fibheap *, struct fibheap_el *, int, void *);
+
+/* functions for void * heaps */
+struct fibheap *fh_makeheap(void);
+voidcmp fh_setcmp(struct fibheap *, voidcmp);
+void *fh_setneginf(struct fibheap *, void *);
+struct fibheap_el *fh_insert(struct fibheap *, void *);
+
+/* shared functions */
+void *fh_extractmin(struct fibheap *);
+void *fh_min(struct fibheap *);
+void *fh_replacedata(struct fibheap *, struct fibheap_el *, void *);
+void *fh_delete(struct fibheap *, struct fibheap_el *);
+void fh_deleteheap(struct fibheap *);
+struct fibheap *fh_union(struct fibheap *, struct fibheap *);
+
+#ifdef FH_STATS
+int fh_maxn(struct fibheap *);
+int fh_ninserts(struct fibheap *);
+int fh_nextracts(struct fibheap *);
+#endif
+
+#endif /* _FIB_H_ */
diff --git a/navit/fib-1.1/fibpriv.h b/navit/fib-1.1/fibpriv.h
new file mode 100644
index 00000000..3984b261
--- /dev/null
+++ b/navit/fib-1.1/fibpriv.h
@@ -0,0 +1,98 @@
+/*-
+ * Copyright 1997, 1999-2003 John-Mark Gurney.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ *	$Id: fibpriv.h,v 1.1 2005-12-02 10:41:56 martin-s Exp $
+ *
+ */
+
+#ifndef _FIBPRIV_H_
+#define _FIBPRIV_H_
+
+struct fibheap_el;
+
+/*
+ * global heap operations
+ */
+struct fibheap {
+	int	(*fh_cmp_fnct)(void *, void *);
+	int	fh_n;
+	int	fh_Dl;
+	struct	fibheap_el **fh_cons;
+	struct	fibheap_el *fh_min;
+	struct	fibheap_el *fh_root;
+	void	*fh_neginf;
+	int	fh_keys		: 1;
+#ifdef FH_STATS
+	int	fh_maxn;
+	int	fh_ninserts;
+	int	fh_nextracts;
+#endif
+};
+
+static void fh_initheap(struct fibheap *);
+static void fh_insertrootlist(struct fibheap *, struct fibheap_el *);
+static void fh_removerootlist(struct fibheap *, struct fibheap_el *);
+static void fh_consolidate(struct fibheap *);
+static void fh_heaplink(struct fibheap *h, struct fibheap_el *y,
+			struct fibheap_el *x);
+static void fh_cut(struct fibheap *, struct fibheap_el *, struct fibheap_el *);
+static void fh_cascading_cut(struct fibheap *, struct fibheap_el *);
+static struct fibheap_el *fh_extractminel(struct fibheap *);
+static void fh_checkcons(struct fibheap *h);
+static void fh_destroyheap(struct fibheap *h);
+static int fh_compare(struct fibheap *h, struct fibheap_el *a,
+			struct fibheap_el *b);
+static int fh_comparedata(struct fibheap *h, int key, void *data,
+			struct fibheap_el *b);
+static void fh_insertel(struct fibheap *h, struct fibheap_el *x);
+static void fh_deleteel(struct fibheap *h, struct fibheap_el *x);
+
+/*
+ * specific node operations
+ */
+struct fibheap_el {
+	int	fhe_degree;
+	int	fhe_mark;
+	struct	fibheap_el *fhe_p;
+	struct	fibheap_el *fhe_child;
+	struct	fibheap_el *fhe_left;
+	struct	fibheap_el *fhe_right;
+	int	fhe_key;
+	void	*fhe_data;
+};
+
+static struct fibheap_el *fhe_newelem(void);
+static void fhe_initelem(struct fibheap_el *);
+static void fhe_insertafter(struct fibheap_el *a, struct fibheap_el *b);
+static inline void fhe_insertbefore(struct fibheap_el *a, struct fibheap_el *b);
+static struct fibheap_el *fhe_remove(struct fibheap_el *a);
+#define	fhe_destroy(x)	free((x))
+
+/*
+ * general functions
+ */
+static inline int ceillog2(unsigned int a);
+
+#endif /* _FIBPRIV_H_ */
diff --git a/navit/fib-1.1/fibtest.c b/navit/fib-1.1/fibtest.c
new file mode 100644
index 00000000..c7be1e9c
--- /dev/null
+++ b/navit/fib-1.1/fibtest.c
@@ -0,0 +1,80 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include "fib.h"
+
+int main(void)
+{
+	struct fibheap *a;
+	void *arr[10];
+	int i;
+
+	a = fh_makekeyheap();
+	
+	for (i=1 ; i < 10 ; i++)
+	  {
+              arr[i]= fh_insertkey(a,0,(void *)i);
+	      printf("adding: 0 %d \n",i);
+	  }
+     
+	printf(" \n");
+	 fh_replacekey(a, arr[1],-1);
+         fh_replacekey(a, arr[6],-1);
+	 fh_replacekey(a, arr[4],-1);
+         fh_replacekey(a, arr[2],-1); 
+         fh_replacekey(a, arr[8],-1); 
+	  
+        printf("value(minkey) %d\n",fh_minkey(a));
+	printf("id: %d\n\n", (int)fh_extractmin(a));          
+     
+	 fh_replacekey(a, arr[7],-33);
+/* -> node 7 becomes root node, but is still pointed to by node 6 */
+         fh_replacekey(a, arr[4],-36);
+	 fh_replacekey(a, arr[3],-1);
+         fh_replacekey(a, arr[9],-81); 	
+	
+        printf("value(minkey) %d\n",fh_minkey(a));
+        printf("id: %d\n\n", (int)fh_extractmin(a));
+	
+	 fh_replacekey(a, arr[6],-68);
+         fh_replacekey(a, arr[2],-69);
+
+        printf("value(minkey) %d\n",fh_minkey(a));
+        printf("id: %d\n\n", (int)fh_extractmin(a));
+
+	 fh_replacekey(a, arr[1],-52);
+         fh_replacekey(a, arr[3],-2);
+	 fh_replacekey(a, arr[4],-120);
+         fh_replacekey(a, arr[5],-48); 	
+
+        printf("value(minkey) %d\n",fh_minkey(a));
+	printf("id: %d\n\n", (int)fh_extractmin(a));
+
+	 fh_replacekey(a, arr[3],-3);
+         fh_replacekey(a, arr[5],-63);
+
+        printf("value(minkey) %d\n",fh_minkey(a));
+	printf("id: %d\n\n", (int)fh_extractmin(a));
+
+	 fh_replacekey(a, arr[5],-110);
+         fh_replacekey(a, arr[7],-115);
+
+        printf("value(minkey) %d\n",fh_minkey(a));
+	printf("id: %d\n\n", (int)fh_extractmin(a));
+
+         fh_replacekey(a, arr[5],-188);
+
+        printf("value(minkey) %d\n",fh_minkey(a));
+	printf("id: %d\n\n", (int)fh_extractmin(a));
+
+         fh_replacekey(a, arr[3],-4);
+
+        printf("value(minkey) %d\n",fh_minkey(a));
+	printf("id: %d\n\n", (int)fh_extractmin(a));
+	
+        printf("value(minkey) %d\n",fh_minkey(a));
+        printf("id: %d\n\n", (int)fh_extractmin(a));
+
+	fh_deleteheap(a);
+
+	return 0;
+}
diff --git a/navit/fib-1.1/fibtest.out b/navit/fib-1.1/fibtest.out
new file mode 100644
index 00000000..285bd26b
--- /dev/null
+++ b/navit/fib-1.1/fibtest.out
@@ -0,0 +1,37 @@
+adding: 0 1 
+adding: 0 2 
+adding: 0 3 
+adding: 0 4 
+adding: 0 5 
+adding: 0 6 
+adding: 0 7 
+adding: 0 8 
+adding: 0 9 
+ 
+value(minkey) -1
+id: 8
+
+value(minkey) -81
+id: 9
+
+value(minkey) -69
+id: 2
+
+value(minkey) -120
+id: 4
+
+value(minkey) -68
+id: 6
+
+value(minkey) -115
+id: 7
+
+value(minkey) -188
+id: 5
+
+value(minkey) -52
+id: 1
+
+value(minkey) -4
+id: 3
+
diff --git a/navit/fib-1.1/fibtest2.c b/navit/fib-1.1/fibtest2.c
new file mode 100644
index 00000000..8a623b63
--- /dev/null
+++ b/navit/fib-1.1/fibtest2.c
@@ -0,0 +1,69 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include "fib.h"
+
+int
+main(void) {
+	struct fibheap *a;
+	void *arr[10];
+	int i;
+	a = fh_makekeyheap();
+	
+	for (i=1 ; i < 10 ; i++)
+	  {
+              arr[i]= fh_insertkey(a,0,(void *)i);
+	      printf("adding: 0 %d \n",i);
+	  }
+     
+	printf(" \n");
+	 fh_replacekey(a, arr[1],-38);
+         fh_replacekey(a, arr[7],-34);
+  
+        printf("wert(minkey) %d\n",fh_minkey(a));
+	printf("Knoten: %d\n\n", (int)fh_extractmin(a));
+	 fh_replacekey(a, arr[2],-55);
+         fh_replacekey(a, arr[5],-56);
+        printf("Wert(minkey) %d\n",fh_minkey(a));
+        printf("Knoten: %d\n\n", (int)fh_extractmin(a));
+	
+	 fh_replacekey(a, arr[4],-1);
+         fh_replacekey(a, arr[2],-102);
+	 fh_replacekey(a, arr[6],-1);
+         fh_replacekey(a, arr[9],-1);
+	 fh_replacekey(a, arr[8],-4);
+        printf("Wert(minkey) %d\n",fh_minkey(a));
+        printf("Knoten: %d\n\n", (int)fh_extractmin(a));
+	 fh_replacekey(a, arr[3],-74);
+         fh_replacekey(a, arr[8],-55);
+	 fh_replacekey(a, arr[4],-2);
+        	
+        printf("Wert(minkey) %d\n",fh_minkey(a));
+	printf("Knoten: %d\n\n", (int)fh_extractmin(a));
+	 fh_replacekey(a, arr[4],-3);
+         fh_replacekey(a, arr[6],-2);
+         fh_replacekey(a, arr[7],-99);
+        printf("Wert(minkey) %d\n",fh_minkey(a));
+	printf("Knoten: %d\n\n", (int)fh_extractmin(a));
+	 fh_replacekey(a, arr[6],-3);
+         fh_replacekey(a, arr[4],-4);
+	 fh_replacekey(a, arr[8],-94);
+         fh_replacekey(a, arr[9],-2);
+        printf("Wert(minkey) %d\n",fh_minkey(a));
+	printf("Knoten: %d\n\n", (int)fh_extractmin(a));
+        fh_replacekey(a, arr[6],-4);
+	
+        printf("Wert(minkey) %d\n",fh_minkey(a));
+	printf("Knoten: %d\n\n", (int)fh_extractmin(a));
+	
+        printf("Wert(minkey) %d\n",fh_minkey(a));
+        printf("Knoten: %d\n\n", (int)fh_extractmin(a));
+	/*fh_replacekey(a, arr[9],-3);*/
+        printf("Wert(minkey) %d\n",fh_minkey(a));
+	printf("Knoten: %d\n\n", (int)fh_extractmin(a));
+     
+        /*fh_replacekey(a, arr[9],-49);*/
+ 
+	fh_deleteheap(a);
+
+	return 0;
+}
diff --git a/navit/fib-1.1/fibtest2.out b/navit/fib-1.1/fibtest2.out
new file mode 100644
index 00000000..e9d1704f
--- /dev/null
+++ b/navit/fib-1.1/fibtest2.out
@@ -0,0 +1,37 @@
+adding: 0 1 
+adding: 0 2 
+adding: 0 3 
+adding: 0 4 
+adding: 0 5 
+adding: 0 6 
+adding: 0 7 
+adding: 0 8 
+adding: 0 9 
+ 
+wert(minkey) -38
+Knoten: 1
+
+Wert(minkey) -56
+Knoten: 5
+
+Wert(minkey) -102
+Knoten: 2
+
+Wert(minkey) -74
+Knoten: 3
+
+Wert(minkey) -99
+Knoten: 7
+
+Wert(minkey) -94
+Knoten: 8
+
+Wert(minkey) -4
+Knoten: 6
+
+Wert(minkey) -4
+Knoten: 4
+
+Wert(minkey) -2
+Knoten: 9
+
diff --git a/navit/fib-1.1/tt.c b/navit/fib-1.1/tt.c
new file mode 100644
index 00000000..26db1d2c
--- /dev/null
+++ b/navit/fib-1.1/tt.c
@@ -0,0 +1,64 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include "fib.h"
+
+int main(void)
+{
+  
+    struct fibheap *a;
+    void *arr[10];
+    int i;
+
+    a = fh_makekeyheap();
+	
+    for (i=1 ; i < 8 ; i++)
+     {
+      arr[i]= fh_insertkey(a,0,(void *)i);
+      printf("adding: 0 %d \n",i);
+     }
+     
+     printf(" \n");
+
+     fh_replacekey(a, arr[1],-2);
+     fh_replacekey(a, arr[4],-3);
+     fh_replacekey(a, arr[7],-5);
+	  
+     printf("Wert(minkey) %d\n",fh_minkey(a));
+     printf("Knoten: %d\n\n", (int)fh_extractmin(a)); 
+        
+     fh_replacekey(a, arr[3],-2);
+     fh_replacekey(a, arr[6],-1);
+	
+     printf("Wert(minkey) %d\n",fh_minkey(a));
+     printf("Knoten: %d\n\n", (int)fh_extractmin(a));
+	
+     fh_replacekey(a, arr[1],-9);
+     fh_replacekey(a, arr[5],-3);
+
+     printf("Wert(minkey) %d\n",fh_minkey(a));
+     printf("Knoten: %d\n\n", (int)fh_extractmin(a));
+
+     fh_replacekey(a, arr[2],-4);
+     fh_replacekey(a, arr[5],-5);
+     fh_replacekey(a, arr[6],-3);
+        	
+     printf("Wert(minkey) %d\n",fh_minkey(a));
+     printf("Knoten: %d\n\n", (int)fh_extractmin(a));
+
+     fh_replacekey(a, arr[2],-6);
+     fh_replacekey(a, arr[6],-6);
+
+     printf("Wert(minkey) %d\n",fh_minkey(a));
+     printf("Knoten: %d\n\n", (int)fh_extractmin(a));
+
+     printf("Wert(minkey) %d\n",fh_minkey(a));
+     printf("Knoten: %d\n\n", (int)fh_extractmin(a));
+
+     printf("Wert(minkey) %d\n",fh_minkey(a));
+     printf("Knoten: %d\n\n", (int)fh_extractmin(a));
+       	
+     fh_deleteheap(a);
+
+	return 0;
+}
+
diff --git a/navit/fib-1.1/tt.out b/navit/fib-1.1/tt.out
new file mode 100644
index 00000000..37a8a47c
--- /dev/null
+++ b/navit/fib-1.1/tt.out
@@ -0,0 +1,29 @@
+adding: 0 1 
+adding: 0 2 
+adding: 0 3 
+adding: 0 4 
+adding: 0 5 
+adding: 0 6 
+adding: 0 7 
+ 
+Wert(minkey) -5
+Knoten: 7
+
+Wert(minkey) -3
+Knoten: 4
+
+Wert(minkey) -9
+Knoten: 1
+
+Wert(minkey) -5
+Knoten: 5
+
+Wert(minkey) -6
+Knoten: 6
+
+Wert(minkey) -6
+Knoten: 2
+
+Wert(minkey) -2
+Knoten: 3
+
diff --git a/navit/fib-1.1/use.c b/navit/fib-1.1/use.c
new file mode 100644
index 00000000..e8db3279
--- /dev/null
+++ b/navit/fib-1.1/use.c
@@ -0,0 +1,126 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#include "fib.h"
+
+#define TESTCASE	1
+
+#define COUNT	100000
+#define DIF	1000
+#define MAXEXT	10
+#define VERBOSE	1
+
+int cmp(void *, void *);
+
+int
+cmp(void *x, void *y)
+{
+	int a, b;
+	a = (int)x;
+	b = (int)y;
+
+	if (a < b)
+		return -1;
+	if (a == b)
+		return 0;
+	return 1;
+}
+
+int
+main(void)
+{
+#if !TESTCASE
+	struct fibheap_el *w;
+#else
+	int e, j, k;
+#endif
+	struct fibheap *a;
+	int i, x;
+
+	a = fh_makeheap();
+	fh_setcmp(a, cmp);
+
+	srandom(time(NULL));
+#if TESTCASE
+#if VERBOSE
+	printf("inserting: ");
+#endif
+	e = 0;
+	for (i = 0; i < COUNT; i++) {
+#if VERBOSE
+		if (i)
+			printf(", ");
+#endif
+		fh_insert(a, (void *)(x = random()/10));
+#if VERBOSE
+		printf("%d", x);
+#endif
+		if (i - e > DIF) {
+			k = random() % MAXEXT;
+			for (j = 0; j < k; j++, e++)
+				printf("throwing: %d\n", (int)fh_extractmin(a));
+		}
+	}
+
+#if VERBOSE
+	printf("\nremaining: %d\n", COUNT - e);
+	printf("extracting: ");
+#endif
+	for (i = 0; i < COUNT - e; i++) {
+#if VERBOSE
+		if (i)
+			printf(", ");
+		printf("%d", (int)fh_extractmin(a));
+#else
+		fh_extractmin(a);
+#endif
+	}
+#if VERBOSE
+	printf("\n");
+#endif
+	if ((int)fh_extractmin(a) == 0)
+		printf("heap empty!\n");
+	else {
+		printf("heap not empty! ERROR!\n");
+		exit(1);
+	}
+#else
+	w = fh_insert(a, (void *)6);
+	printf("adding: %d\n", 6);
+	fh_insert(a, (void *)9);
+	printf("adding: %d\n", 9);
+	fh_insert(a, (void *)1);
+	printf("adding: %d\n", 1);
+	for(i = 0; i < 5; i++) {
+		x = random()/10000;
+		printf("adding: %d\n", x);
+		fh_insert(a, (void *)x);
+	}
+	fh_insert(a, (void *)4);
+	printf("adding: %d\n", 4);
+	fh_insert(a, (void *)8);
+	printf("adding: %d\n", 8);
+	printf("first: %d\n", (int)fh_extractmin(a));
+	printf("deleting: %d\n", (int)fh_delete(a, w));
+	printf("first: %d\n", (int)fh_extractmin(a));
+	printf("first: %d\n", (int)fh_extractmin(a));
+	printf("first: %d\n", (int)fh_extractmin(a));
+	printf("first: %d\n", (int)fh_extractmin(a));
+	printf("first: %d\n", (int)fh_extractmin(a));
+	for(i = 0; i < 5; i++) {
+		x = random()/10000;
+		printf("adding: %d\n", x);
+		fh_insert(a, (void *)x);
+	}
+	printf("first: %d\n", (int)fh_extractmin(a));
+	printf("first: %d\n", (int)fh_extractmin(a));
+	printf("first: %d\n", (int)fh_extractmin(a));
+	printf("first: %d\n", (int)fh_extractmin(a));
+	printf("first: %d\n", (int)fh_extractmin(a));
+#endif
+
+	fh_deleteheap(a);
+
+	return 0;
+}