summaryrefslogtreecommitdiff
path: root/navit/fib-1.1
diff options
context:
space:
mode:
Diffstat (limited to 'navit/fib-1.1')
-rw-r--r--navit/fib-1.1/CMakeLists.txt2
-rw-r--r--navit/fib-1.1/README26
-rwxr-xr-xnavit/fib-1.1/configure1045
-rw-r--r--navit/fib-1.1/configure.in17
-rw-r--r--navit/fib-1.1/fh_extractmin.397
-rw-r--r--navit/fib-1.1/fh_makeheap.317
-rw-r--r--navit/fib-1.1/fh_makekeyheap.384
-rw-r--r--navit/fib-1.1/fib.c699
-rw-r--r--navit/fib-1.1/fib.h64
-rw-r--r--navit/fib-1.1/fibpriv.h98
-rw-r--r--navit/fib-1.1/fibtest.c108
-rw-r--r--navit/fib-1.1/fibtest.out37
-rw-r--r--navit/fib-1.1/fibtest2.c96
-rw-r--r--navit/fib-1.1/fibtest2.out37
-rw-r--r--navit/fib-1.1/tt.c91
-rw-r--r--navit/fib-1.1/tt.out29
-rw-r--r--navit/fib-1.1/use.c153
17 files changed, 0 insertions, 2700 deletions
diff --git a/navit/fib-1.1/CMakeLists.txt b/navit/fib-1.1/CMakeLists.txt
deleted file mode 100644
index 1c86263c4..000000000
--- a/navit/fib-1.1/CMakeLists.txt
+++ /dev/null
@@ -1,2 +0,0 @@
-supportlib_add_library(fib fib.c)
-
diff --git a/navit/fib-1.1/README b/navit/fib-1.1/README
deleted file mode 100644
index eabcd5f86..000000000
--- a/navit/fib-1.1/README
+++ /dev/null
@@ -1,26 +0,0 @@
-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
deleted file mode 100755
index 62eaa3d01..000000000
--- a/navit/fib-1.1/configure
+++ /dev/null
@@ -1,1045 +0,0 @@
-#! /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
deleted file mode 100644
index 827015270..000000000
--- a/navit/fib-1.1/configure.in
+++ /dev/null
@@ -1,17 +0,0 @@
-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
deleted file mode 100644
index e1492b400..000000000
--- a/navit/fib-1.1/fh_extractmin.3
+++ /dev/null
@@ -1,97 +0,0 @@
-.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
deleted file mode 100644
index bd867cd09..000000000
--- a/navit/fib-1.1/fh_makeheap.3
+++ /dev/null
@@ -1,17 +0,0 @@
-.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
deleted file mode 100644
index f55d43072..000000000
--- a/navit/fib-1.1/fh_makekeyheap.3
+++ /dev/null
@@ -1,84 +0,0 @@
-.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
deleted file mode 100644
index cf7451467..000000000
--- a/navit/fib-1.1/fib.c
+++ /dev/null
@@ -1,699 +0,0 @@
-/*-
- * 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 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 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
deleted file mode 100644
index d8564d3c7..000000000
--- a/navit/fib-1.1/fib.h
+++ /dev/null
@@ -1,64 +0,0 @@
-/*-
- * 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
deleted file mode 100644
index a1f173557..000000000
--- a/navit/fib-1.1/fibpriv.h
+++ /dev/null
@@ -1,98 +0,0 @@
-/*-
- * 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 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 int ceillog2(unsigned int a);
-
-#endif /* _FIBPRIV_H_ */
diff --git a/navit/fib-1.1/fibtest.c b/navit/fib-1.1/fibtest.c
deleted file mode 100644
index 36510087c..000000000
--- a/navit/fib-1.1/fibtest.c
+++ /dev/null
@@ -1,108 +0,0 @@
-/*-
- * 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.
-
-*/
-
-
-#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
deleted file mode 100644
index 285bd26bb..000000000
--- a/navit/fib-1.1/fibtest.out
+++ /dev/null
@@ -1,37 +0,0 @@
-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
deleted file mode 100644
index 2ce1f6a06..000000000
--- a/navit/fib-1.1/fibtest2.c
+++ /dev/null
@@ -1,96 +0,0 @@
-/*-
- * 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.
-
-*/
-
-#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
deleted file mode 100644
index e9d1704f8..000000000
--- a/navit/fib-1.1/fibtest2.out
+++ /dev/null
@@ -1,37 +0,0 @@
-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
deleted file mode 100644
index 0bf580357..000000000
--- a/navit/fib-1.1/tt.c
+++ /dev/null
@@ -1,91 +0,0 @@
-/*-
- * 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.
-
-*/
-
-#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
deleted file mode 100644
index 37a8a47c1..000000000
--- a/navit/fib-1.1/tt.out
+++ /dev/null
@@ -1,29 +0,0 @@
-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
deleted file mode 100644
index 309d85c44..000000000
--- a/navit/fib-1.1/use.c
+++ /dev/null
@@ -1,153 +0,0 @@
-/*-
- * 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.
-
-*/
-
-#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;
-}
View Lorry Controller Status