bdtl-1.0.4/ 0000755 0001750 0001750 00000000000 12364543027 012241 5 ustar melamed melamed bdtl-1.0.4/flags.mk 0000644 0001750 0001750 00000002346 12122405072 013660 0 ustar melamed melamed
#--------------------------------------------------------------------------
# setting variables for compilation
#--------------------------------------------------------------------------
ifdef CONDOR_COMPILE
CONDOR_CMP = condor_compile
USECONDOR = -DUSE_CONDOR
else
CONDOR_CMP =
USECONDOR =
endif
ifdef 32BIT
ARCH_SIZE = 32
ARCH_LIB_SUFX =
else
ARCH_SIZE = 64
ARCH_LIB_SUFX = 64
endif
ARCH_FLAG = -m$(ARCH_SIZE)
ifdef DYNAMIC
STATIC_FLAG =
else
STATIC_FLAG = -static -Bstatic
endif
ifdef VALID
VALIDATION_FLAG = -DVALIDATION
else
VALIDATION_FLAG =
endif
ifdef USE_BOOST_MEM_POOL
MEM_POOL_FLAG = -DBOOST_MEM_POOL -DBOOST_NO_PROPER_STL_DEALLOCATE
else
MEM_POOL_FLAG =
endif
ifdef DBG
OPT_DEBUG_FLAG = -ggdb -O0 -fno-inline
SUFFIX=dbg
LIBSUFFIX = _dbg
endif
ifdef OPT
OPT_DEBUG_FLAG = -O3 -DNDEBUG
SUFFIX = opt
LIBSUFFIX =
else
OPT_DEBUG_FLAG = -O0 -ggdb -fno-inline
SUFFIX = dbg
LIBSUFFIX = _dbg
endif
ifdef OPTDBG
OPT_DEBUG_FLAG = -O3 -ggdb
SUFFIX = optdbg
LIBSUFFIX = _optdbg
endif
ifdef GOOG
GOOG_FLAG = -L/usr/local/lib -lprofiler -ltcmalloc
else
GOOG_FLAG =
endif
ifdef GPROF
USE_GPROF = -pg
SUFFIX := $(SUFFIX)_gprof
LIBSUFFIX := $(LIBSUFFIX)_gprof
else
USE_GRPOF =
endif
bdtl-1.0.4/shared.mk 0000644 0001750 0001750 00000000714 12151020420 014017 0 ustar melamed melamed ########################################################################################
#
# BDTL configuration variables that are unlikely to change,
# but are needed by multiple parts of the installation
#
########################################################################################
include $(BASE_DIR)/flags.mk
# determine the machine architecture
ARCH := $(shell uname -s)
BIN_BASE = $(BASE_DIR)/bin
BIN = $(BIN_BASE)/$(ARCH)/$(SUFFIX)
bdtl-1.0.4/WHAT.this.is 0000644 0001750 0001750 00000002617 12151020420 014272 0 ustar melamed melamed Boosted Decision Trees and Lists (BDTL)
The BDTL software package implements two main boosting algorithms with
many variations. The first one is Turian and Melamed's extension of
confidence-rated boosting (Schapire & Singer, 1999). See Joseph
Turian's thesis (NYU, 2007) for details. The second algorithm is
Galron and Melamed's extension of the first one, to boost decision
lists rather than decision trees. (Every decision tree ensemble is
equivalent to some decision list ensemble, and vice versa.)
Major features of the software include:
* Classification and regression
* tested on 3M+ examples with 1M+ features, but limited only by your
computer's RAM.
* Easily customizable loss functions and regularization methods.
Currently implemented ones are logistic and exponential loss for
classification, and squared loss for regression, each with L1 or L2
regularization.
* Selection of weak learners to directly optimize the regularized
training objective.
* One-shot training following an entire regularization path, which can
save a lot of time during hyperparameter optimization.
* Continuous checkpointing, so that if a long learning cycle crashes,
you can continue training where it left off.
* Warm-start training.
* Both binary and scalar feature types.
To get started, read the file README.1st in the top level directory.
Questions, suggestions, and offers of collaboration are most welcome.
bdtl-1.0.4/scripts/ 0000755 0001750 0001750 00000000000 12364543027 013730 5 ustar melamed melamed bdtl-1.0.4/scripts/sort_scoresets.pl 0000755 0001750 0001750 00000002612 12122405072 017337 0 ustar melamed melamed #!/usr/bin/perl
########################################################################
# Author: I. Dan Melamed
# Computes: sorts lines delimited by and
# Loads: nothing
# Streams: grammar, etc.
# N.B.: sort is numeric on first column and alphabetic on the rest
#######################################################################
$TRUE = 1;
$FALSE = 0;
# 2 statuses -- either within a scoreset or not
$inScoreSet = $FALSE;
while (<>) {
if ($inScoreSet) {
if (/^/) {
die "nested SCORESET?";
} elsif (/^<\/SCORESET>/) {
print "\n";
# sort the indexes from 0 to $#score first by the score and then by the rest
@indexes = sort
{$score[$a] <=> $score[$b] || $rest[$a] cmp $rest[$b]}
(0 .. $#score);
# dump them in order
foreach $ind (@indexes) {
print "$score[$ind]\t$rest[$ind]";
};
print "\n";
# clean up
$inScoreSet = $FALSE;
undef @score; undef @rest;
} else {
# store it
($score, $rest) = split(' ', $_, 2);
$score[$.] = $score;
$rest[$.] = $rest;
}
} else { # not in scoreset
if (/^<\/SCORESET>/) {
die "SCORESET ended before starting?";
} elsif (/^/) {
$inScoreSet = $TRUE;
$. = -1; # reset line counter
} else {
print;
}
}
}
if ($inScoreSet) {
die "scoreset not finished!";
};
bdtl-1.0.4/scripts/SVMLi2f.withDict.pl 0000755 0001750 0001750 00000001642 12215740062 017224 0 ustar melamed melamed #!/usr/bin/perl
########################################################################
# Author: I. Dan Melamed
# Computes: converts integer feature values to reals, for some feature types
# Loads: list of feature types to convert
# Streams: example set in SVMLight format
# N.B.: conversion is done merely by adding .0
#######################################################################
$TRUE = 1;
$FALSE = 0;
$INFINITY = 9999999999;
$TINY = 1 - $INFINITY / ($INFINITY + 1);
$| = 1;
#check for correct usage
if ($#ARGV < 0) {
print "usage: $0 []\n";
exit;
};
print STDERR "$0: Reading feature list... from $ARGV[0]";
open(F, $ARGV[0]) || die "\nCouldn't open $ARGV[0]: $!\n";
while () {
chomp;
push(@float, $_);
};
close(F);
shift;
print STDERR " done.\n";
while (<>) {
foreach $feat (@float) {
s/( $feat:\-?\d+)([^\.])/${1}.0$2/;
}
print;
}
bdtl-1.0.4/scripts/SVMLi2f.pl 0000755 0001750 0001750 00000002365 12215740062 015451 0 ustar melamed melamed #!/usr/bin/perl
########################################################################
# Author: I. Dan Melamed
# Purpose: convert integer feature values to floats, if that feature's
# value ever appears as a float, so that BDT::parameter
# doesn't get confused
# Streams: examples in SMLight format, twice
#######################################################################
#check for correct usage
if ($#ARGV < 0) {
print "usage: $0 \n";
exit;
};
$inFile = shift;
open(F, $inFile) || die "\nCouldn't open $inFile: $!\n";
while () {
chomp;
@tok = split;
$objective = shift @tok;
if ($objective ne "1" && $objective ne "0") {
$scalarObjective = 1;
};
foreach $tok (@tok) {
($name, $val) = split(/:/, $tok);
if ($val =~ /\./) {
$float{$name} = $TRUE;
}
}
}
close F;
open(F, $inFile) || die "\nCouldn't open $inFile: $!\n";
while () {
chomp;
@tok = split;
$objective = shift @tok;
if ($scalarObjective && $objective !~ /\./) {
$objective .= ".";
};
$out = $objective;
foreach $tok (@tok) {
($name, $val) = split(/:/, $tok);
if ($val !~ /\./ && exists $float{$name}) {
$val .= ".0";
}
$out .= " $name:$val";
}
print "$out\n";
}
close F;
bdtl-1.0.4/scripts/SVML2BDT.sh 0000755 0001750 0001750 00000000674 12122405072 015460 0 ustar melamed melamed #!/bin/tcsh
# Original Author: Dan Melamed
# Created on: June 4, 2010
# Purpose: convert examples in SVMLight format into a format more suitable for BDT
# N.B.: use the faster SVM2BDT.withDict.sh instead if you have a file of float feature types
if ($#argv < 1) then
echo "usage: $0 "
exit 0
endif
SVMLi2f.pl $1 > stage1.$$
SVMLInt2Bool.pl stage1.$$ \
| perl -pe 's/^\+1/1/; s/^\-1/0/;' # to stdout
rm *.$$
bdtl-1.0.4/scripts/causality.pl 0000755 0001750 0001750 00000003741 12335422172 016266 0 ustar melamed melamed #!/usr/bin/perl
########################################################################
# Author: I. Dan Melamed
# Purpose: for each feature, determine likelihood of being the cause of the objective
# using Hyvarinen & Smith's Equations 5 and 17
# Streams: entire data set, only once
# Stores: a handful of variables for each feature
# N.B.: assumes data has been standardized to 0 mean and unit variance
#######################################################################
# use autodie qw(:all);
use Math::Trig;
$TRUE = 1;
$FALSE = 0;
# duck compiler warning
$TRUE = 1;
$FALSE = 0;
while (<>) {
chomp;
($obj , @feat) = split;
++$numEx;
$sumObj += $obj;
$sumsqObj += $obj ** 2;
$skewObj = &skew($obj);
foreach $feat (@feat) {
if ($feat =~ /(\d+):([\-\d\.]+)/) { # scalar
$featNum = $1;
$featVal = $2;
++$count{$featNum};
$sum{$featNum} += $featVal;
$sumsq{$featNum} += $featVal ** 2;
$sumObjFeat{$featNum} += $featVal * $obj;
$eq5inner{$featNum} += $obj * tanh($featVal) - tanh($obj) * $featVal;
$eq17inner{$featNum} += $skewObj * $featVal - $obj * &skew($featVal);
} else { # boolean
die "input should be standardized";
}
}
};
@sortedFeats = sort {$a <=> $b} keys %count;
$meanObj = $sumObj / $numEx;
$stdObj = sqrt($sumsqObj / $numEx - $meanObj ** 2);
for ($i = 0; $i <= $#sortedFeats; ++$i) {
$featNum = $sortedFeats[$i];
$count = $count{$featNum};
if ($count < $numEx) {
die "feature $featNum has missing values";
}
$meanFeat = $sum{$featNum} / $numEx;
$stdFeat = sqrt($sumsq{$featNum} / $numEx - $meanFeat ** 2);
$cov = $sumObjFeat{$featNum} / $numEx - $meanObj * $meanFeat;
$rho1 = $cov / $stdObj;
$rho = $rho1/ $stdFeat;
$eq5mean = $eq5inner{$featNum} / $numEx;
$eq5 = $rho * $eq5mean;
$eq17mean = $eq17inner{$featNum} / $numEx;
$eq17 = $rho * $eq17mean;
print "$featNum $eq5 $eq17\n";
}
sub skew {
$val = $_[0];
if ($val < 0.0) {
$ret = log ( cosh ( 0.0));
} else {
$ret = log ( cosh ( $val));
}
return $ret;
}
bdtl-1.0.4/scripts/freqThreshold.pl 0000755 0001750 0001750 00000001703 12332555660 017104 0 ustar melamed melamed #!/usr/bin/perl
########################################################################
# Author: I. Dan Melamed
# Purpose: remove boolean features that occur less than given number of times
# Loads: entire example set in BDT format
#######################################################################
# use autodie qw(:all);
$TRUE = 1;
$FALSE = 0;
# duck compiler warning
$TRUE = 1;
$FALSE = 0;
#check for correct usage
if ($#ARGV < 0) {
print "usage: $0 []\n";
exit;
};
$thresh = shift;
print STDERR "$0: Reading examples... ";
while (<>) {
chomp;
push(@ex, $_);
($objective, @feat) = split;
foreach $feat (@feat) {
if ($feat =~ /:/) { # scalar
next;
}
++$count{$feat};
}
};
print STDERR " done.\n";
foreach $ex (@ex) {
($objective, @feat) = split(' ', $ex);
$out = $objective;
foreach $feat (@feat) {
if ($feat =~ /:/ || ($count{$feat} >= $thresh)) {
$out .= " $feat";
}
}
print "$out\n";
};
bdtl-1.0.4/scripts/prettyBDT.pl 0000755 0001750 0001750 00000004553 12122405072 016145 0 ustar melamed melamed #!/usr/bin/perl
########################################################################
# Author: I. Dan Melamed
# Computes: pretty-prints BDT tree sequences
# Loads: feature vocab
# Streams: tree sequence
#######################################################################
$TRUE = 1;
$FALSE = 0;
$INFINITY = 9999999999;
$TINY = 1 - $INFINITY / ($INFINITY + 1);
$| = 1;
#check for correct usage
if ($#ARGV < 0) {
print "usage: $0 [tree sequence file]\n";
exit;
};
print STDERR "$0: Reading feature vocab ...";
open(F, $ARGV[0]) || die "Couldn't open $ARGV[0]: $!\n";
$delim = ;
chomp($delim);
die "malformed vocab" if ($delim ne "");
my $ind = 1;
while () {
if (/VOCAB>/) {
last;
};
chomp;
$fv{$ind++} = $_;
};
close(F);
shift;
print STDERR " done.\n";
$tree = 0;
while (<>) {
if (! /\S/) {
print;
next;
};
if (/BeginTree/) {
undef %leaf, %pos, %neg, %feat, %sign, %thresh;
++$tree;
} elsif (/EndTree/) {
print "\n";
if (exists $leaf{0}) {
printTree(0, 0);
}
} elsif (/Node# (\d+) \S+ \[ \+ (\d+) , \- (\d+) \] \+child= (\d+) \-child= (\d+) splitOn \( (\d+) (.+) (.+) \) depth= (\d+)/) {
$nn = $1;
$leaf{$nn} = $FALSE;
$poseg{$nn} = $2;
$negeg{$nn} = $3;
$pos{$nn} = $4;
$neg{$nn} = $5;
$feat{$nn} = $6;
$sign{$nn} = $7;
$thresh{$nn} = $8;
$dep = $9;
} elsif (/Node# (\d+) confidence= ([\d\.\+\-e]+) \S+ \[ \+ (\d+) , \- (\d+) \] \+child= (\d+) \-child= (\d+) splitOn \( (\d+) (.+) (.+) \) depth= (\d+)/) {
$nn = $1;
$leaf{$nn} = $FALSE;
$conf{$nn} = $2;
$poseg{$nn} = $3;
$negeg{$nn} = $4;
$pos{$nn} = $5;
$neg{$nn} = $6;
$feat{$nn} = $7;
$sign{$nn} = $8;
$thresh{$nn} = $9;
$dep = $10;
} elsif (/Leaf# (\d+) confidence= ([\d\.\+\-e]+) \S+ \[ \+ (\d+) , \- (\d+) \] weightBiases \[.*\] depth= (\d+)/) {
$nn = $1;
$leaf{$nn} = $TRUE;
$conf{$nn} = $2;
$poseg{$nn} = $3;
$negeg{$nn} = $4;
$dep = $5;
} else {
die "malformed line: $_";
};
};
sub printTree {
my($nn, $depth) = @_;
print " " x $depth;
if ($leaf{$nn}) {
print "+ $poseg{$nn} / - $negeg{$nn} # $conf{$nn}\n";
} else {
print "+ $poseg{$nn} / - $negeg{$nn} # $fv{$feat{$nn}} $sign{$nn} $thresh{$nn} $conf{$nn}\n";
printTree($pos{$nn}, $depth +1);
printTree($neg{$nn}, $depth +1);
};
};
bdtl-1.0.4/scripts/standardize.pl 0000755 0001750 0001750 00000004557 12335422172 016606 0 ustar melamed melamed #!/usr/bin/perl
########################################################################
# Author: I. Dan Melamed
# Purpose: standardize features to 0 mean, 1 variance; discarding those with constant values
# Loads: entire example set in BDT format
# N.B.: representation becomes dense, because all booleans become scalars
# N.B.2: all missing values, including scalars, treated as zeros
#######################################################################
# use autodie qw(:all);
$TRUE = 1;
$FALSE = 0;
# duck compiler warning
$TRUE = 1;
$FALSE = 0;
while (<>) {
chomp;
push(@ex, $_);
($objective, @feat) = split;
$sumObj += $objective;
$sumsqObj += $objective ** 2;
foreach $feat (@feat) {
if ($feat =~ /(\d+):([\-\d\.]+)/) { # scalar
$featNum = $1;
$featVal = $2;
$isScalar{$featNum} = $TRUE;
$sum{$featNum} += $featVal;
$sumsq{$featNum} += $featVal ** 2;
++$count{$featNum};
} else { # boolean
++$count{$feat};
}
}
};
$numEx = scalar @ex;
$meanObj = $sumObj / $numEx;
$stdObj = sqrt($sumsqObj / $numEx - ($sumObj / $numEx) ** 2);
@sortedFeats = sort {$a <=> $b} keys %count;
for ($i = 0; $i <= $#sortedFeats; ++$i) {
$featNum = $sortedFeats[$i];
$count = $count{$featNum};
if (exists $isScalar{$featNum}) {
# this treats missing values as zero
$mean[$i] = $sum{$featNum} / $numEx;
$std[$i] = sqrt($sumsq{$featNum} / $numEx - $mean[$i] ** 2);
} else {
$mean[$i] = $count / $numEx;
# $standardizedOne = 1 - $mean[$i];
# $standardizedZero = 0 - $mean[$i];
# $numZeros = $numEx - $count;
# $sum = $count;
# $sumsq = $count * 1 ** 2;
$std[$i] = sqrt($count / $numEx - ($count / $numEx) ** 2);
}
}
foreach $ex (@ex) {
($objective, @feat) = split(' ', $ex);
$normVal = ($objective - $meanObj) / $stdObj;
$out = $normVal;
%featVal = ();
foreach $feat (@feat) {
if ($feat =~ /(\d+):([\-\d\.]+)/) { # scalar
$featNum = $1;
$featVal{$featNum} = $2;
} else { # boolean
$featVal{$feat} = $TRUE;
}
}
for ($i = 0; $i <= $#sortedFeats; ++$i) {
$featNum = $sortedFeats[$i];
if (not exists $featVal{$featNum}) {
$featVal{$featNum} = 0.0; # works for both scalars and booleans
}
if ($std[$i] <= 0.0) { # can be less due to rounding error
next; # discard features with no variance
} else {
$normVal = ($featVal{$featNum} - $mean[$i]) / $std[$i];
}
$out .= " $featNum:$normVal";
}
print "$out\n";
};
bdtl-1.0.4/scripts/literalizeRegexp.pl 0000755 0001750 0001750 00000000057 12122405072 017576 0 ustar melamed melamed #!/usr/bin/perl -p
s/(\W)/\\$1/g;
s/\\\n/\n/;
bdtl-1.0.4/scripts/rms.pl 0000755 0001750 0001750 00000000556 12171623303 015067 0 ustar melamed melamed #!/usr/bin/perl
########################################################################
# Author: I. Dan Melamed
# Computes: root mean squared of a list of numbers
#######################################################################
$counter = $ssq = 0;
while (<>) {
chomp;
$ssq += $_ * $_;
++$counter;
}
printf "%.15f\n", sqrt($ssq / $counter);
bdtl-1.0.4/scripts/SVMLInt2Bool.pl 0000755 0001750 0001750 00000002566 12122405072 016420 0 ustar melamed melamed #!/usr/bin/perl
########################################################################
# Author: I. Dan Melamed
# Purpose: convert integer feature values to bools, if that feature's
# value appears only as a 0 or 1, where a bool feature name
# either appears or not, but never has a colon or value
# Streams: examples in SMLight format, twice
# N.B.: the result is not strictly in SVMLight format
#######################################################################
#check for correct usage
if ($#ARGV < 0) {
print "usage: $0 \n";
exit;
};
$TRUE = 1;
$inFile = shift;
open(F, $inFile) || die "\nCouldn't open $inFile: $!\n";
while () {
chomp;
@tok = split;
$objective = shift @tok;
foreach $tok (@tok) {
($name, $val) = split(/:/, $tok);
if ($val ne "1" && $val ne "0") {
$nonbool{$name} = $TRUE;
delete $bool{$name};
} else {
if (! exists $nonbool{$name}) {
$bool{$name} = $TRUE;
}
}
}
}
close F;
open(F, $inFile) || die "\nCouldn't open $inFile: $!\n";
while () {
chomp;
@tok = split;
$objective = shift @tok;
$out = $objective;
foreach $tok (@tok) {
($name, $val) = split(/:/, $tok);
if (exists $bool{$name}) {
if ($val eq "1") {
$out .= " $name";
} else {
# skip it
}
} else {
$out .= " $name:$val";
}
}
print "$out\n";
}
close F;
bdtl-1.0.4/scripts/SVML2BDT.withDict.sh 0000755 0001750 0001750 00000001001 12122405072 017217 0 ustar melamed melamed #!/bin/tcsh
# Original Author: Dan Melamed
# Created on: Jan 6, 2011
# Purpose: convert examples in SVMLight format into a format more suitable for BDT
# use the slower SVML2BDT.sh instead if you have no float feature dictionary
if ($#argv < 2) then
echo "usage: $0 [float feat dict] "
exit 0
endif
set floatDict=$1
shift
set inFile=$1
shift
SVMLi2f.withDict.pl $floatDict $inFile > stage1.$$
SVMLInt2Bool.pl stage1.$$ \
| perl -pe 's/^\+1/1/; s/^\-1/0/;' # to stdout
rm *.$$
bdtl-1.0.4/Makefile 0000644 0001750 0001750 00000001621 12337200550 013670 0 ustar melamed melamed # top-level Makefile
# we do not want these to be done in parallel
.NOTPARALLEL:
SUBDIRS = src sandbox # doc/code
.PHONY: $(SUBDIRS) doc
# default rule
valid: $(SUBDIRS)
@echo OK
$(SUBDIRS):
$(MAKE) -rC $@
doc: doc/code/Doxyfile
doxygen doc/code/Doxyfile
clean:
for dir in $(SUBDIRS); do \
$(MAKE) -rC $$dir clean || exit; \
done
spotless:
for dir in $(SUBDIRS); do \
$(MAKE) -rC $$dir spotless || exit; \
done
depend:
$(MAKE) -rC src depend
# use this target to run without validation
run:
for dir in $(SUBDIRS); do \
echo && echo "--> $$dir start at " `date`; \
$(MAKE) -rC $$dir run || exit; \
done
@ echo && echo "--> done at " `date`; \
check:
for dir in sandbox; do \
$(MAKE) -rC $$dir check || exit; \
done
expected:
for dir in sandbox; do \
$(MAKE) -rC $$dir expected || exit; \
done
pretend:
for dir in sandbox; do \
$(MAKE) -rC $$dir pretend || exit; \
done
bdtl-1.0.4/doc/ 0000755 0001750 0001750 00000000000 12364543027 013006 5 ustar melamed melamed bdtl-1.0.4/doc/background/ 0000755 0001750 0001750 00000000000 12364543027 015125 5 ustar melamed melamed bdtl-1.0.4/doc/background/math.tex 0000644 0001750 0001750 00000013426 12151020420 016563 0 ustar melamed melamed \documentclass{article}
\usepackage{fullpage}
%\usepackage{hltnaacl03}
\usepackage{latexsym,amsmath,array,natbib}
% \usepackage{psfig,here}
\usepackage{bibtex-cite-macros}
\usepackage{boxedminipage}
\usepackage{amsmath}
\usepackage{algorithmicx}
\newcommand{\ignore}[1]{}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\hyphenation{Figure Table Equation}
\hyphenation{Section Chapter}
\widowpenalty = 10000
\clubpenalty = 10000
\title{Mathematical Background for the {\tt BDTL} software package}
\author{
I. Dan Melamed
\\ AT\&T Shannon Laboratory
\\ Florham Park, NJ, U.S.A., 07932
\\ {\tt \{lastname\}@research.att.com}
}
\date{}
\begin{document}
\maketitle
\begin{abstract}
Sample abstract.
\end{abstract}
\section{Introduction}
Let the atomic feature set be represented by $A$.
Let the training set be represented by $I = \{(y_i, X_i)\}$, where
$y_i$ are the labels and $X_i$ are the feature value vectors $(x_{i,1},
x_{i,2}, \ldots, x_{i,|A|})$ . Each feature $x_{i,f}$ can be Boolean
(0/1) or scalar (integer or real).
Every node in a decision tree contains a Boolean atomic feature test
$f$. If $f$ involves a Boolean atomic feature $a$, then it will be of
the form $a = true$. If it involves a scalar atomic feature, then it
will be of the form $a \diamond c$ for some constant $c$ and relation
$\diamond$. The possible relations in that case are $<, >, \leq,$ and
$\geq$. Let $F$ be the set of possible atomic feature tests.
The path from the root to a non-leaf node in a decision tree
represents a Boolean conjunction of atomic feature tests, which we
call a compound feature test. Elsewhere in the literature, such
Boolean expressions are called decision lists. We denote them by $q$
and their 0/1 value on a particular example $i$ is $q(i)$. Since the
path from the root to a node in a tree is unique, every non-leaf
decision tree node has a unique compound feature test associated with
it, in addition to a unique atomic feature test. However, since
conjunctions are commutative, a given compound feature test can have
its elements in any order, so multiple nodes can be associated with a
given compound feature test.
Let $Q$ be the set of possible compound feature tests. If all
the atomic features in $A$ are Boolean, then $|Q| = 3^{|A|}$ because
each atomic feature test can be positive, negative, or absent in a
compound feature test. However, when we allow atomic features to be
scalar, the number of possible compound feature tests becomes much
larger, because every scalar feature value can be compared to many
possible values of $c$.
Let the model be represented by $\Theta = (\theta_1, \theta_2, \ldots,
\theta_{|Q|})$ . There is one parameter for every possible compound
feature test, though usually most of their values will be zero.
Let the hypothesis function be represented by
\begin{equation}
h(i) = \Theta \cdot Q(i) = \sum_{k = 1}^{|Q|} \theta_k q_k(i)
\end{equation}
We grow decision trees by splitting their leaves to minimize risk over
some training set, following \cite{TurianThesis}. For each leaf node
$n$, we choose a new feature test $\hat{f}$ to maximize a gain
function $G$ over the examples $I$ in $n$. Let $q$ be the compound
feature test associated with the parent node of $n$. Then
\begin{equation}
\hat{f} = {\arg \max}_{f \in F} [ G(I ; q \wedge f) + G(I ; q \wedge \neg f) ]
\end{equation}
where $\wedge$ is conjunction and $\neg$ is negation. $G(I ; p)$
involves the gradient of the loss function over $I$ with respect to
the model parameter $\theta_p$.
\ignore{
For now we assume a loss function that treats each example
independently:
\begin{equation}
L(I) = \sum_{i \in I} l(i)
\end{equation}
}
\section{Regression}
We use the squared loss
\begin{equation}
L(I) = \sum_{i \in I} l(i) = \sum_{i \in I} \frac{1}{2} (y_i - h(i))^2
\end{equation}
Let $\mu(i) = y_i - h(i)$ so that $l(i) = \frac{1}{2} \mu(i)^2$ . To
find the gradient, we have:
\begin{eqnarray}
\frac{\partial L(I)}{\partial \theta_k} & = & \sum_{i \in I} \frac{\partial l(i)}{\partial \theta_k} \\
& = & \sum_{i \in I} \frac{\partial l(i)}{\partial \mu(i)} \cdot \frac{\partial \mu(i)}{\partial \theta_k} \\
& = & \sum_{i \in I} \mu(i) \cdot -q_k(i) \\
& = & \sum_{i \in I} (h(i) - y_i) q_k(i) \\
\label{eqn:feas} & = & \sum_{i \in I : q_k(i) = 1} h(i) - y_i \\
& = & \left(\sum_{i \in I : q_k(i) = 1, h(i) \geq y_i} h(i) - y_i \right)
- \left(\sum_{i \in I : q_k(i) = 1, h(i) < y_i} y_i - h(i) \right)
\end{eqnarray}
Equation~\ref{eqn:feas} works because $q$ can be only 0 or 1, and it is what
makes this optimization feasible.
\ignore{
\subsection{Training algorithm}
\begin{Listing}[thb]
\caption{Training algorithm.}
\label{alg:training}
\begin{algorithmic}[1]
\Procedure{Find best split point on scalar feature}{f}
\State find $G_\Theta(f)$
\label{alg:training:conf-update-begin}
\State choose \alpha_f to minimize \objective
\label{alg:training:objective-minimization}
\State add \alpha_f to $h(i)$ for all i in this leaf \label{alg:training:confidence-update}
\EndFor
\label{alg:training:conf-update-end}
\EndFor
\EndProcedure
\end{algorithmic}
\end{Listing}
}
\ignore{
\begin{figure}
\centerline{
% (a)
%\raisebox{.2in}{\psfig{figure=parsematrix.eps,width=1.9in}}
\hfill
(b)
%\psfig{figure=venn.eps,width=1.1in}
}
\caption{Generalizations of ordinary parsing.
% $D = $ dimensionality of grammar; $I =$ dimensionality of input.
% (a) Classification with respect to dimensionality; (b) Venn diagram.
\label{venn}
\label{parsematrix}}
\end{figure}
\section{Conclusion}
}
\section*{Acknowledgments}
Thanks to Pannaga Shivaswamy for helpful discussions.
%%%%%%%%%%%%%%%%%% BIBLIOGRAPHY
\bibliographystyle{bibtex-cite-macros}
%\bibliography{mt}
\end{document}
bdtl-1.0.4/doc/background/bibtex-cite-macros.sty 0000644 0001750 0001750 00000022666 12122405072 021350 0 ustar melamed melamed % File acl04.sty
% January 07, 2004
% Contact: rambow@cs.columbia.edu
% This is the LaTeX style file for ACL 2004. It is identical to the
% style files for ACL 2003, ACL 2002, ACL 2001, ACL 2000, EACL 95 and EACL
% 99.
%
% -- Roberto Zamparelli, March 26, 2001
% -- Dekang Lin, October 1, 2001
% This is the LaTeX style file for ACL 2000. It is nearly identical to the
% style files for EACL 95 and EACL 99. Minor changes include editing the
% instructions to reflect use of \documentclass rather than \documentstyle
% and removing the white space before the title on the first page
% -- John Chen, June 29, 2000
% To convert from submissions prepared using the style file aclsub.sty
% prepared for the ACL 2000 conference, proceed as follows:
% 1) Remove submission-specific information: \whichsession, \id,
% \wordcount, \otherconferences, \area, \keywords
% 2) \summary should be removed. The summary material should come
% after \maketitle and should be in the ``abstract'' environment
% 3) Check all citations. This style should handle citations correctly
% and also allows multiple citations separated by semicolons.
% 4) Check figures and examples. Because the final format is double-
% column, some adjustments may have to be made to fit text in the column
% or to choose full-width (\figure*} figures.
% 5) Change the style reference from aclsub to acl2000, and be sure
% this style file is in your TeX search path
% This is the LaTeX style file for EACL-95. It is identical to the
% style file for ANLP '94 except that the margins are adjusted for A4
% paper. -- abney 13 Dec 94
% The ANLP '94 style file is a slightly modified
% version of the style used for AAAI and IJCAI, using some changes
% prepared by Fernando Pereira and others and some minor changes
% by Paul Jacobs.
% Papers prepared using the aclsub.sty file and acl.bst bibtex style
% should be easily converted to final format using this style.
% (1) Submission information (\wordcount, \subject, and \makeidpage)
% should be removed.
% (2) \summary should be removed. The summary material should come
% after \maketitle and should be in the ``abstract'' environment
% (between \begin{abstract} and \end{abstract}).
% (3) Check all citations. This style should handle citations correctly
% and also allows multiple citations separated by semicolons.
% (4) Check figures and examples. Because the final format is double-
% column, some adjustments may have to be made to fit text in the column
% or to choose full-width (\figure*} figures.
% Place this in a file called aclap.sty in the TeX search path.
% (Placing it in the same directory as the paper should also work.)
% Prepared by Peter F. Patel-Schneider, liberally using the ideas of
% other style hackers, including Barbara Beeton.
% This style is NOT guaranteed to work. It is provided in the hope
% that it will make the preparation of papers easier.
%
% There are undoubtably bugs in this style. If you make bug fixes,
% improvements, etc. please let me know. My e-mail address is:
% pfps@research.att.com
% Papers are to be prepared using the ``acl'' bibliography style,
% as follows:
% \documentclass[11pt]{article}
% \usepackage{acl2000}
% \title{Title}
% \author{Author 1 \and Author 2 \\ Address line \\ Address line \And
% Author 3 \\ Address line \\ Address line}
% \begin{document}
% ...
% \bibliography{bibliography-file}
% \bibliographystyle{acl}
% \end{document}
% Author information can be set in various styles:
% For several authors from the same institution:
% \author{Author 1 \and ... \and Author n \\
% Address line \\ ... \\ Address line}
% if the names do not fit well on one line use
% Author 1 \\ {\bf Author 2} \\ ... \\ {\bf Author n} \\
% For authors from different institutions:
% \author{Author 1 \\ Address line \\ ... \\ Address line
% \And ... \And
% Author n \\ Address line \\ ... \\ Address line}
% To start a seperate ``row'' of authors use \AND, as in
% \author{Author 1 \\ Address line \\ ... \\ Address line
% \AND
% Author 2 \\ Address line \\ ... \\ Address line \And
% Author 3 \\ Address line \\ ... \\ Address line}
% If the title and author information does not fit in the area allocated,
% place \setlength\titlebox{} right after
% \usepackage{acl2000}
% where can be something larger than 2.25in
% \typeout{Conference Style for ACL 2000 -- released June 20, 2000}
\typeout{Conference Style for ACL 2002 -- released April 8, 2002}
% NOTE: Some laser printers have a serious problem printing TeX output.
% These printing devices, commonly known as ``write-white'' laser
% printers, tend to make characters too light. To get around this
% problem, a darker set of fonts must be created for these devices.
%
% % Physical page layout - slightly modified from IJCAI by pj
% \setlength\topmargin{0.0in} \setlength\oddsidemargin{-0.0in}
% \setlength\textheight{9.0in} \setlength\textwidth{6.5in}
% \setlength\columnsep{0.2in}
% \newlength\titlebox
% \setlength\titlebox{2.25in}
% \setlength\headheight{0pt} \setlength\headsep{0pt}
% %\setlength\footheight{0pt}
% \setlength\footskip{0pt}
% \thispagestyle{empty} \pagestyle{empty}
% \flushbottom \twocolumn \sloppy
% %% A4 version of page layout
% \setlength\topmargin{-0.45cm} % changed by Rz -1.4
% \setlength\oddsidemargin{.8mm} % was -0cm, changed by Rz
% \setlength\textheight{23.5cm}
% \setlength\textwidth{15.8cm}
% \setlength\columnsep{0.6cm}
% \newlength\titlebox
% \setlength\titlebox{2.00in}
% \setlength\headheight{5pt}
% \setlength\headsep{0pt}
% %\setlength\footheight{0pt}
% \setlength\footskip{0pt}
% \thispagestyle{empty}
% \pagestyle{empty}
% most of cite format is from aclsub.sty by SMS
% don't box citations, separate with ; and a space
% also, make the penalty between citations negative: a good place to break
% changed comma back to semicolon pj 2/1/90
% \def\@citex[#1]#2{\if@filesw\immediate\write\@auxout{\string\citation{#2}}\fi
% \def\@citea{}\@cite{\@for\@citeb:=#2\do
% {\@citea\def\@citea{;\penalty\@citeseppen\ }\@ifundefined
% {b@\@citeb}{{\bf ?}\@warning
% {Citation `\@citeb' on page \thepage \space undefined}}%
% {\csname b@\@citeb\endcsname}}}{#1}}
% don't box citations, separate with ; and a space
% Replaced for multiple citations (pj)
% don't box citations and also add space, semicolon between multiple citations
\def\@citex[#1]#2{\if@filesw\immediate\write\@auxout{\string\citation{#2}}\fi
\def\@citea{}\@cite{\@for\@citeb:=#2\do
{\@citea\def\@citea{; }\@ifundefined
{b@\@citeb}{{\bf ?}\@warning
{Citation `\@citeb' on page \thepage \space undefined}}%
{\csname b@\@citeb\endcsname}}}{#1}}
% Allow short (name-less) citations, when used in
% conjunction with a bibliography style that creates labels like
% \citename{, }
%
\let\@internalcite\cite
\def\cite{\def\citename##1{##1, }\@internalcite}
\def\shortcite{\def\citename##1{}\@internalcite}
\def\newcite{\leavevmode\def\citename##1{{##1} (}\@internalciteb}
% Macros for \newcite, which leaves name in running text, and is
% otherwise like \shortcite.
\def\@citexb[#1]#2{\if@filesw\immediate\write\@auxout{\string\citation{#2}}\fi
\def\@citea{}\@newcite{\@for\@citeb:=#2\do
{\@citea\def\@citea{;\penalty\@m\ }\@ifundefined
{b@\@citeb}{{\bf ?}\@warning
{Citation `\@citeb' on page \thepage \space undefined}}%
\hbox{\csname b@\@citeb\endcsname}}}{#1}}
\def\@internalciteb{\@ifnextchar [{\@tempswatrue\@citexb}{\@tempswafalse\@citexb[]}}
\def\@newcite#1#2{{#1\if@tempswa, #2\fi)}}
\def\@biblabel#1{\def\citename##1{##1}[#1]\hfill}
%%% More changes made by SMS (originals in latex.tex)
% Use parentheses instead of square brackets in the text.
\def\@cite#1#2{({#1\if@tempswa , #2\fi})}
% Don't put a label in the bibliography at all. Just use the unlabeled format
% instead.
\def\thebibliography#1{\vskip\parskip%
\vskip\baselineskip%
\def\baselinestretch{1}%
\ifx\@currsize\normalsize\@normalsize\else\@currsize\fi%
\vskip-\parskip%
\vskip-\baselineskip%
\section*{References\@mkboth
{References}{References}}\list
{}{\setlength{\labelwidth}{0pt}\setlength{\leftmargin}{\parindent}
\setlength{\itemindent}{-\parindent}}
\def\newblock{\hskip .11em plus .33em minus -.07em}
\sloppy\clubpenalty4000\widowpenalty4000
\sfcode`\.=1000\relax}
\let\endthebibliography=\endlist
% Allow for a bibliography of sources of attested examples
\def\thesourcebibliography#1{\vskip\parskip%
\vskip\baselineskip%
\def\baselinestretch{1}%
\ifx\@currsize\normalsize\@normalsize\else\@currsize\fi%
\vskip-\parskip%
\vskip-\baselineskip%
\section*{Sources of Attested Examples\@mkboth
{Sources of Attested Examples}{Sources of Attested Examples}}\list
{}{\setlength{\labelwidth}{0pt}\setlength{\leftmargin}{\parindent}
\setlength{\itemindent}{-\parindent}}
\def\newblock{\hskip .11em plus .33em minus -.07em}
\sloppy\clubpenalty4000\widowpenalty4000
\sfcode`\.=1000\relax}
\let\endthesourcebibliography=\endlist
\def\@lbibitem[#1]#2{\item[]\if@filesw
{ \def\protect##1{\string ##1\space}\immediate
\write\@auxout{\string\bibcite{#2}{#1}}\fi\ignorespaces}}
\def\@bibitem#1{\item\if@filesw \immediate\write\@auxout
{\string\bibcite{#1}{\the\c@enumi}}\fi\ignorespaces}
bdtl-1.0.4/doc/background/Makefile 0000644 0001750 0001750 00000004670 12122405072 016561 0 ustar melamed melamed # $Id: Makefile,v 1.1 2004/09/14 00:30:12 melamed Exp $
# Usage: "make help" or simply "make"
##################################################################
SHELL = /bin/bash
## Disable the standard LaTeX rule.
%.dvi: %.tex
#%.pdf: %.ps
%.pdf: %.tex
SUFF = *.bak *.out *.toc *.log *.aux *.idx *.ind *.ilg \
*.lot *.loc *.lof *.bbl *.blg *.tar *.gz
SUFF1 := $(patsubst *.%,\%.%,$(SUFF))
FIGS := $(patsubst %.fig,%.eps,$(wildcard *.fig))
DIAS := $(patsubst %.dia,%.eps,$(wildcard *.dia))
HTMLDIR = .html
# these targets will not be treated as files.
.PHONY: help clean
# The "make" program will not automatically delete intermediate files with
# the following suffixes.
.PRECIOUS: $(SUFF1) %.eps %.dvi %.ps %.pdf
.IGNORE: %.bbl
## programs
LATEX = latex
BIBTEX = -bibtex --min-crossrefs=100
LATEX2HTML = latex2html
PS2PDF = ps2pdf
PDFLATEX = pdflatex
PDF2PS = pdf2ps
EPS2PDF = epstopdf
FIG2DEV = fig2dev
DVI2PS = dvips
## TARGETS
help:
@echo "LaTeX Makefile v2.0"
@echo "----------------------"
@echo "Targets:"
@echo " help (or nothing) Show this message"
@echo " Make the .dvi file"
@echo " .dvi Make the .dvi file"
@echo " .ps Make the .ps file"
@echo " .pdf Make the .pdf file"
@echo " .html Make the html files in the .html directory"
@echo " .tar Tar the directory"
@echo " .tar.gz Tar and gzip the directory"
@echo " clean Remove all generated files"
@echo
%.tar:
@echo "Generating $@..."
@tar cvf - . > $@
@echo "done"
%.gz: %
@gzip < $< > $@
clean:
@echo "cleaning files..."
rm -rf $(SUFF) $(FIGS) $(DIAS) *.ps *.pdf *.dvi
@if [ -d $(HTMLDIR) ]; then rm -rf $(HTMLDIR); fi
@echo "done."
%.bbl: %.tex $(FIGS) $(DIAS)
echo the figures are $(FIGS) $(DIAS)
$(LATEX) $<
$(BIBTEX) -min-crossrefs=100 $*
%.dvi: %.tex *.tex %.bbl $(FIGS) $(DIAS)
$(LATEX) $<
$(LATEX) $<
%.ps: %.dvi
$(DVI2PS) $< -o $@
#%.ps: %.pdf
# $(PDF2PS) $< $@
%.eps: %.fig
@echo "Generating $@..."
@$(FIG2DEV) -L eps -p portrait $< > $@
%.eps: %.dia
echo "Generating $@..."
dia -e $@ $<
#%.pdf: %.eps
# $(EPS2PDF) $< > $@
#%.pdf: %.ps
# $(PS2PDF) $< $@
%.pdf: %.tex
$(PDFLATEX) $<
%.html: %.dvi
@echo -n "Creating the html files..."
@if [ ! -d "$(HTMLDIR)" ]; then mkdir $(HTMLDIR); fi
@$(LATEX2HTML) -dir $(HTMLDIR) $* >& /dev/null;
@echo "done"
%: %.dvi
bdtl-1.0.4/doc/background/bibtex-cite-macros.bst 0000644 0001750 0001750 00000056103 12122405072 021312 0 ustar melamed melamed % BibTeX `acl' style file for BibTeX version 0.99c, LaTeX version 2.09
% This version was made by modifying `aaai-named' format based on the master
% file by Oren Patashnik (PATASHNIK@SCORE.STANFORD.EDU)
% Copyright (C) 1985, all rights reserved.
% Modifications Copyright 1988, Peter F. Patel-Schneider
% Further modifictions by Stuart Shieber, 1991, and Fernando Pereira, 1992.
% Copying of this file is authorized only if either
% (1) you make absolutely no changes to your copy, including name, or
% (2) if you do make changes, you name it something other than
% btxbst.doc, plain.bst, unsrt.bst, alpha.bst, and abbrv.bst.
% This restriction helps ensure that all standard styles are identical.
% There are undoubtably bugs in this style. If you make bug fixes,
% improvements, etc. please let me know. My e-mail address is:
% pfps@spar.slb.com
% Citation format: [author-last-name, year]
% [author-last-name and author-last-name, year]
% [author-last-name {\em et al.}, year]
%
% Reference list ordering: alphabetical by author or whatever passes
% for author in the absence of one.
%
% This BibTeX style has support for short (year only) citations. This
% is done by having the citations actually look like
% \citename{name-info, }year
% The LaTeX style has to have the following
% \let\@internalcite\cite
% \def\cite{\def\citename##1{##1}\@internalcite}
% \def\shortcite{\def\citename##1{}\@internalcite}
% \def\@biblabel#1{\def\citename##1{##1}[#1]\hfill}
% which makes \shortcite the macro for short citations.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Changes made by SMS for thesis style
% no emphasis on "et al."
% "Ph.D." includes periods (not "PhD")
% moved year to immediately after author's name
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
ENTRY
{ address
author
booktitle
chapter
edition
editor
howpublished
institution
journal
key
month
note
number
organization
pages
publisher
school
series
title
type
volume
year
}
{}
{ label extra.label sort.label }
INTEGERS { output.state before.all mid.sentence after.sentence after.block }
FUNCTION {init.state.consts}
{ #0 'before.all :=
#1 'mid.sentence :=
#2 'after.sentence :=
#3 'after.block :=
}
STRINGS { s t }
FUNCTION {output.nonnull}
{ 's :=
output.state mid.sentence =
{ ", " * write$ }
{ output.state after.block =
{ add.period$ write$
newline$
"\newblock " write$
}
{ output.state before.all =
'write$
{ add.period$ " " * write$ }
if$
}
if$
mid.sentence 'output.state :=
}
if$
s
}
FUNCTION {output}
{ duplicate$ empty$
'pop$
'output.nonnull
if$
}
FUNCTION {output.check}
{ 't :=
duplicate$ empty$
{ pop$ "empty " t * " in " * cite$ * warning$ }
'output.nonnull
if$
}
FUNCTION {output.bibitem}
{ newline$
"\bibitem[" write$
label write$
"]{" write$
cite$ write$
"}" write$
newline$
""
before.all 'output.state :=
}
FUNCTION {fin.entry}
{ add.period$
write$
newline$
}
FUNCTION {new.block}
{ output.state before.all =
'skip$
{ after.block 'output.state := }
if$
}
FUNCTION {new.sentence}
{ output.state after.block =
'skip$
{ output.state before.all =
'skip$
{ after.sentence 'output.state := }
if$
}
if$
}
FUNCTION {not}
{ { #0 }
{ #1 }
if$
}
FUNCTION {and}
{ 'skip$
{ pop$ #0 }
if$
}
FUNCTION {or}
{ { pop$ #1 }
'skip$
if$
}
FUNCTION {new.block.checka}
{ empty$
'skip$
'new.block
if$
}
FUNCTION {new.block.checkb}
{ empty$
swap$ empty$
and
'skip$
'new.block
if$
}
FUNCTION {new.sentence.checka}
{ empty$
'skip$
'new.sentence
if$
}
FUNCTION {new.sentence.checkb}
{ empty$
swap$ empty$
and
'skip$
'new.sentence
if$
}
FUNCTION {field.or.null}
{ duplicate$ empty$
{ pop$ "" }
'skip$
if$
}
FUNCTION {emphasize}
{ duplicate$ empty$
{ pop$ "" }
{ "{\em " swap$ * "}" * }
if$
}
INTEGERS { nameptr namesleft numnames }
FUNCTION {format.names}
{ 's :=
#1 'nameptr :=
s num.names$ 'numnames :=
numnames 'namesleft :=
{ namesleft #0 > }
{ s nameptr "{ff~}{vv~}{ll}{, jj}" format.name$ 't :=
nameptr #1 >
{ namesleft #1 >
{ ", " * t * }
{ numnames #2 >
{ "," * }
'skip$
if$
t "others" =
{ " et~al." * }
{ " and " * t * }
if$
}
if$
}
't
if$
nameptr #1 + 'nameptr :=
namesleft #1 - 'namesleft :=
}
while$
}
FUNCTION {format.authors}
{ author empty$
{ "" }
{ author format.names }
if$
}
FUNCTION {format.editors}
{ editor empty$
{ "" }
{ editor format.names
editor num.names$ #1 >
{ ", editors" * }
{ ", editor" * }
if$
}
if$
}
FUNCTION {format.title}
{ title empty$
{ "" }
{ title "t" change.case$ }
if$
}
FUNCTION {n.dashify}
{ 't :=
""
{ t empty$ not }
{ t #1 #1 substring$ "-" =
{ t #1 #2 substring$ "--" = not
{ "--" *
t #2 global.max$ substring$ 't :=
}
{ { t #1 #1 substring$ "-" = }
{ "-" *
t #2 global.max$ substring$ 't :=
}
while$
}
if$
}
{ t #1 #1 substring$ *
t #2 global.max$ substring$ 't :=
}
if$
}
while$
}
FUNCTION {format.date}
{ year empty$
{ month empty$
{ "" }
{ "there's a month but no year in " cite$ * warning$
month
}
if$
}
{ month empty$
{ "" }
{ month }
if$
}
if$
}
FUNCTION {format.btitle}
{ title emphasize
}
FUNCTION {tie.or.space.connect}
{ duplicate$ text.length$ #3 <
{ "~" }
{ " " }
if$
swap$ * *
}
FUNCTION {either.or.check}
{ empty$
'pop$
{ "can't use both " swap$ * " fields in " * cite$ * warning$ }
if$
}
FUNCTION {format.bvolume}
{ volume empty$
{ "" }
{ "volume" volume tie.or.space.connect
series empty$
'skip$
{ " of " * series emphasize * }
if$
"volume and number" number either.or.check
}
if$
}
FUNCTION {format.number.series}
{ volume empty$
{ number empty$
{ series field.or.null }
{ output.state mid.sentence =
{ "number" }
{ "Number" }
if$
number tie.or.space.connect
series empty$
{ "there's a number but no series in " cite$ * warning$ }
{ " in " * series * }
if$
}
if$
}
{ "" }
if$
}
FUNCTION {format.edition}
{ edition empty$
{ "" }
{ output.state mid.sentence =
{ edition "l" change.case$ " edition" * }
{ edition "t" change.case$ " edition" * }
if$
}
if$
}
INTEGERS { multiresult }
FUNCTION {multi.page.check}
{ 't :=
#0 'multiresult :=
{ multiresult not
t empty$ not
and
}
{ t #1 #1 substring$
duplicate$ "-" =
swap$ duplicate$ "," =
swap$ "+" =
or or
{ #1 'multiresult := }
{ t #2 global.max$ substring$ 't := }
if$
}
while$
multiresult
}
FUNCTION {format.pages}
{ pages empty$
{ "" }
{ pages multi.page.check
{ "pages" pages n.dashify tie.or.space.connect }
{ "page" pages tie.or.space.connect }
if$
}
if$
}
FUNCTION {format.year.label}
{ year extra.label *
}
FUNCTION {format.vol.num.pages}
{ volume field.or.null
number empty$
'skip$
{ "(" number * ")" * *
volume empty$
{ "there's a number but no volume in " cite$ * warning$ }
'skip$
if$
}
if$
pages empty$
'skip$
{ duplicate$ empty$
{ pop$ format.pages }
{ ":" * pages n.dashify * }
if$
}
if$
}
FUNCTION {format.chapter.pages}
{ chapter empty$
'format.pages
{ type empty$
{ "chapter" }
{ type "l" change.case$ }
if$
chapter tie.or.space.connect
pages empty$
'skip$
{ ", " * format.pages * }
if$
}
if$
}
FUNCTION {format.in.ed.booktitle}
{ booktitle empty$
{ "" }
{ editor empty$
{ "In " booktitle emphasize * }
{ "In " format.editors * ", " * booktitle emphasize * }
if$
}
if$
}
FUNCTION {empty.misc.check}
{ author empty$ title empty$ howpublished empty$
month empty$ year empty$ note empty$
and and and and and
key empty$ not and
{ "all relevant fields are empty in " cite$ * warning$ }
'skip$
if$
}
FUNCTION {format.thesis.type}
{ type empty$
'skip$
{ pop$
type "t" change.case$
}
if$
}
FUNCTION {format.tr.number}
{ type empty$
{ "Technical Report" }
'type
if$
number empty$
{ "t" change.case$ }
{ number tie.or.space.connect }
if$
}
FUNCTION {format.article.crossref}
{ key empty$
{ journal empty$
{ "need key or journal for " cite$ * " to crossref " * crossref *
warning$
""
}
{ "In {\em " journal * "\/}" * }
if$
}
{ "In " key * }
if$
" \cite{" * crossref * "}" *
}
FUNCTION {format.crossref.editor}
{ editor #1 "{vv~}{ll}" format.name$
editor num.names$ duplicate$
#2 >
{ pop$ " et~al." * }
{ #2 <
'skip$
{ editor #2 "{ff }{vv }{ll}{ jj}" format.name$ "others" =
{ " et~al." * }
{ " and " * editor #2 "{vv~}{ll}" format.name$ * }
if$
}
if$
}
if$
}
FUNCTION {format.book.crossref}
{ volume empty$
{ "empty volume in " cite$ * "'s crossref of " * crossref * warning$
"In "
}
{ "Volume" volume tie.or.space.connect
" of " *
}
if$
editor empty$
editor field.or.null author field.or.null =
or
{ key empty$
{ series empty$
{ "need editor, key, or series for " cite$ * " to crossref " *
crossref * warning$
"" *
}
{ "{\em " * series * "\/}" * }
if$
}
{ key * }
if$
}
{ format.crossref.editor * }
if$
" \cite{" * crossref * "}" *
}
FUNCTION {format.incoll.inproc.crossref}
{ editor empty$
editor field.or.null author field.or.null =
or
{ key empty$
{ booktitle empty$
{ "need editor, key, or booktitle for " cite$ * " to crossref " *
crossref * warning$
""
}
{ "In {\em " booktitle * "\/}" * }
if$
}
{ "In " key * }
if$
}
{ "In " format.crossref.editor * }
if$
" \cite{" * crossref * "}" *
}
FUNCTION {article}
{ output.bibitem
format.authors "author" output.check
new.block
format.year.label "year" output.check
new.block
format.title "title" output.check
new.block
crossref missing$
{ journal emphasize "journal" output.check
format.vol.num.pages output
format.date output
}
{ format.article.crossref output.nonnull
format.pages output
}
if$
new.block
note output
fin.entry
}
FUNCTION {book}
{ output.bibitem
author empty$
{ format.editors "author and editor" output.check }
{ format.authors output.nonnull
crossref missing$
{ "author and editor" editor either.or.check }
'skip$
if$
}
if$
new.block
format.year.label "year" output.check
new.block
format.btitle "title" output.check
crossref missing$
{ format.bvolume output
new.block
format.number.series output
new.sentence
publisher "publisher" output.check
address output
}
{ new.block
format.book.crossref output.nonnull
}
if$
format.edition output
format.date output
new.block
note output
fin.entry
}
FUNCTION {booklet}
{ output.bibitem
format.authors output
new.block
format.year.label "year" output.check
new.block
format.title "title" output.check
howpublished address new.block.checkb
howpublished output
address output
format.date output
new.block
note output
fin.entry
}
FUNCTION {inbook}
{ output.bibitem
author empty$
{ format.editors "author and editor" output.check }
{ format.authors output.nonnull
crossref missing$
{ "author and editor" editor either.or.check }
'skip$
if$
}
if$
format.year.label "year" output.check
new.block
new.block
format.btitle "title" output.check
crossref missing$
{ format.bvolume output
format.chapter.pages "chapter and pages" output.check
new.block
format.number.series output
new.sentence
publisher "publisher" output.check
address output
}
{ format.chapter.pages "chapter and pages" output.check
new.block
format.book.crossref output.nonnull
}
if$
format.edition output
format.date output
new.block
note output
fin.entry
}
FUNCTION {incollection}
{ output.bibitem
format.authors "author" output.check
new.block
format.year.label "year" output.check
new.block
format.title "title" output.check
new.block
crossref missing$
{ format.in.ed.booktitle "booktitle" output.check
format.bvolume output
format.number.series output
format.chapter.pages output
new.sentence
publisher "publisher" output.check
address output
format.edition output
format.date output
}
{ format.incoll.inproc.crossref output.nonnull
format.chapter.pages output
}
if$
new.block
note output
fin.entry
}
FUNCTION {inproceedings}
{ output.bibitem
format.authors "author" output.check
new.block
format.year.label "year" output.check
new.block
format.title "title" output.check
new.block
crossref missing$
{ format.in.ed.booktitle "booktitle" output.check
format.bvolume output
format.number.series output
format.pages output
address empty$
{ organization publisher new.sentence.checkb
organization output
publisher output
format.date output
}
{ address output.nonnull
format.date output
new.sentence
organization output
publisher output
}
if$
}
{ format.incoll.inproc.crossref output.nonnull
format.pages output
}
if$
new.block
note output
fin.entry
}
FUNCTION {conference} { inproceedings }
FUNCTION {manual}
{ output.bibitem
author empty$
{ organization empty$
'skip$
{ organization output.nonnull
address output
}
if$
}
{ format.authors output.nonnull }
if$
format.year.label "year" output.check
new.block
new.block
format.btitle "title" output.check
author empty$
{ organization empty$
{ address new.block.checka
address output
}
'skip$
if$
}
{ organization address new.block.checkb
organization output
address output
}
if$
format.edition output
format.date output
new.block
note output
fin.entry
}
FUNCTION {mastersthesis}
{ output.bibitem
format.authors "author" output.check
new.block
format.year.label "year" output.check
new.block
format.title "title" output.check
new.block
"Master's thesis" format.thesis.type output.nonnull
school "school" output.check
address output
format.date output
new.block
note output
fin.entry
}
FUNCTION {misc}
{ output.bibitem
format.authors output
new.block
format.year.label output
new.block
title howpublished new.block.checkb
format.title output
howpublished new.block.checka
howpublished output
format.date output
new.block
note output
fin.entry
empty.misc.check
}
FUNCTION {phdthesis}
{ output.bibitem
format.authors "author" output.check
new.block
format.year.label "year" output.check
new.block
format.btitle "title" output.check
new.block
"{Ph.D.} thesis" format.thesis.type output.nonnull
school "school" output.check
address output
format.date output
new.block
note output
fin.entry
}
FUNCTION {proceedings}
{ output.bibitem
editor empty$
{ organization output }
{ format.editors output.nonnull }
if$
new.block
format.year.label "year" output.check
new.block
format.btitle "title" output.check
format.bvolume output
format.number.series output
address empty$
{ editor empty$
{ publisher new.sentence.checka }
{ organization publisher new.sentence.checkb
organization output
}
if$
publisher output
format.date output
}
{ address output.nonnull
format.date output
new.sentence
editor empty$
'skip$
{ organization output }
if$
publisher output
}
if$
new.block
note output
fin.entry
}
FUNCTION {techreport}
{ output.bibitem
format.authors "author" output.check
new.block
format.year.label "year" output.check
new.block
format.title "title" output.check
new.block
format.tr.number output.nonnull
institution "institution" output.check
address output
format.date output
new.block
note output
fin.entry
}
FUNCTION {unpublished}
{ output.bibitem
format.authors "author" output.check
new.block
format.year.label "year" output.check
new.block
format.title "title" output.check
new.block
note "note" output.check
format.date output
fin.entry
}
FUNCTION {default.type} { misc }
MACRO {jan} {"January"}
MACRO {feb} {"February"}
MACRO {mar} {"March"}
MACRO {apr} {"April"}
MACRO {may} {"May"}
MACRO {jun} {"June"}
MACRO {jul} {"July"}
MACRO {aug} {"August"}
MACRO {sep} {"September"}
MACRO {oct} {"October"}
MACRO {nov} {"November"}
MACRO {dec} {"December"}
MACRO {acmcs} {"ACM Computing Surveys"}
MACRO {acta} {"Acta Informatica"}
MACRO {cacm} {"Communications of the ACM"}
MACRO {ibmjrd} {"IBM Journal of Research and Development"}
MACRO {ibmsj} {"IBM Systems Journal"}
MACRO {ieeese} {"IEEE Transactions on Software Engineering"}
MACRO {ieeetc} {"IEEE Transactions on Computers"}
MACRO {ieeetcad}
{"IEEE Transactions on Computer-Aided Design of Integrated Circuits"}
MACRO {ipl} {"Information Processing Letters"}
MACRO {jacm} {"Journal of the ACM"}
MACRO {jcss} {"Journal of Computer and System Sciences"}
MACRO {scp} {"Science of Computer Programming"}
MACRO {sicomp} {"SIAM Journal on Computing"}
MACRO {tocs} {"ACM Transactions on Computer Systems"}
MACRO {tods} {"ACM Transactions on Database Systems"}
MACRO {tog} {"ACM Transactions on Graphics"}
MACRO {toms} {"ACM Transactions on Mathematical Software"}
MACRO {toois} {"ACM Transactions on Office Information Systems"}
MACRO {toplas} {"ACM Transactions on Programming Languages and Systems"}
MACRO {tcs} {"Theoretical Computer Science"}
READ
FUNCTION {sortify}
{ purify$
"l" change.case$
}
INTEGERS { len }
FUNCTION {chop.word}
{ 's :=
'len :=
s #1 len substring$ =
{ s len #1 + global.max$ substring$ }
's
if$
}
INTEGERS { et.al.char.used }
FUNCTION {initialize.et.al.char.used}
{ #0 'et.al.char.used :=
}
EXECUTE {initialize.et.al.char.used}
FUNCTION {format.lab.names}
{ 's :=
s num.names$ 'numnames :=
numnames #1 =
{ s #1 "{vv }{ll}" format.name$ }
{ numnames #2 =
{ s #1 "{vv }{ll }and " format.name$ s #2 "{vv }{ll}" format.name$ *
}
{ s #1 "{vv }{ll }\bgroup et al.\egroup " format.name$ }
if$
}
if$
}
FUNCTION {author.key.label}
{ author empty$
{ key empty$
{ cite$ #1 #3 substring$ }
{ key #3 text.prefix$ }
if$
}
{ author format.lab.names }
if$
}
FUNCTION {author.editor.key.label}
{ author empty$
{ editor empty$
{ key empty$
{ cite$ #1 #3 substring$ }
{ key #3 text.prefix$ }
if$
}
{ editor format.lab.names }
if$
}
{ author format.lab.names }
if$
}
FUNCTION {author.key.organization.label}
{ author empty$
{ key empty$
{ organization empty$
{ cite$ #1 #3 substring$ }
{ "The " #4 organization chop.word #3 text.prefix$ }
if$
}
{ key #3 text.prefix$ }
if$
}
{ author format.lab.names }
if$
}
FUNCTION {editor.key.organization.label}
{ editor empty$
{ key empty$
{ organization empty$
{ cite$ #1 #3 substring$ }
{ "The " #4 organization chop.word #3 text.prefix$ }
if$
}
{ key #3 text.prefix$ }
if$
}
{ editor format.lab.names }
if$
}
FUNCTION {calc.label}
{ type$ "book" =
type$ "inbook" =
or
'author.editor.key.label
{ type$ "proceedings" =
'editor.key.organization.label
{ type$ "manual" =
'author.key.organization.label
'author.key.label
if$
}
if$
}
if$
duplicate$
"\protect\citename{" swap$ * "}" *
year field.or.null purify$ *
'label :=
year field.or.null purify$ *
sortify 'sort.label :=
}
FUNCTION {sort.format.names}
{ 's :=
#1 'nameptr :=
""
s num.names$ 'numnames :=
numnames 'namesleft :=
{ namesleft #0 > }
{ nameptr #1 >
{ " " * }
'skip$
if$
s nameptr "{vv{ } }{ll{ }}{ ff{ }}{ jj{ }}" format.name$ 't :=
nameptr numnames = t "others" = and
{ "et al" * }
{ t sortify * }
if$
nameptr #1 + 'nameptr :=
namesleft #1 - 'namesleft :=
}
while$
}
FUNCTION {sort.format.title}
{ 't :=
"A " #2
"An " #3
"The " #4 t chop.word
chop.word
chop.word
sortify
#1 global.max$ substring$
}
FUNCTION {author.sort}
{ author empty$
{ key empty$
{ "to sort, need author or key in " cite$ * warning$
""
}
{ key sortify }
if$
}
{ author sort.format.names }
if$
}
FUNCTION {author.editor.sort}
{ author empty$
{ editor empty$
{ key empty$
{ "to sort, need author, editor, or key in " cite$ * warning$
""
}
{ key sortify }
if$
}
{ editor sort.format.names }
if$
}
{ author sort.format.names }
if$
}
FUNCTION {author.organization.sort}
{ author empty$
{ organization empty$
{ key empty$
{ "to sort, need author, organization, or key in " cite$ * warning$
""
}
{ key sortify }
if$
}
{ "The " #4 organization chop.word sortify }
if$
}
{ author sort.format.names }
if$
}
FUNCTION {editor.organization.sort}
{ editor empty$
{ organization empty$
{ key empty$
{ "to sort, need editor, organization, or key in " cite$ * warning$
""
}
{ key sortify }
if$
}
{ "The " #4 organization chop.word sortify }
if$
}
{ editor sort.format.names }
if$
}
FUNCTION {presort}
{ calc.label
sort.label
" "
*
type$ "book" =
type$ "inbook" =
or
'author.editor.sort
{ type$ "proceedings" =
'editor.organization.sort
{ type$ "manual" =
'author.organization.sort
'author.sort
if$
}
if$
}
if$
*
" "
*
year field.or.null sortify
*
" "
*
title field.or.null
sort.format.title
*
#1 entry.max$ substring$
'sort.key$ :=
}
ITERATE {presort}
SORT
STRINGS { longest.label last.sort.label next.extra }
INTEGERS { longest.label.width last.extra.num }
FUNCTION {initialize.longest.label}
{ "" 'longest.label :=
#0 int.to.chr$ 'last.sort.label :=
"" 'next.extra :=
#0 'longest.label.width :=
#0 'last.extra.num :=
}
FUNCTION {forward.pass}
{ last.sort.label sort.label =
{ last.extra.num #1 + 'last.extra.num :=
last.extra.num int.to.chr$ 'extra.label :=
}
{ "a" chr.to.int$ 'last.extra.num :=
"" 'extra.label :=
sort.label 'last.sort.label :=
}
if$
}
FUNCTION {reverse.pass}
{ next.extra "b" =
{ "a" 'extra.label := }
'skip$
if$
label extra.label * 'label :=
label width$ longest.label.width >
{ label 'longest.label :=
label width$ 'longest.label.width :=
}
'skip$
if$
extra.label 'next.extra :=
}
EXECUTE {initialize.longest.label}
ITERATE {forward.pass}
REVERSE {reverse.pass}
FUNCTION {begin.bib}
{ et.al.char.used
{ "\newcommand{\etalchar}[1]{$^{#1}$}" write$ newline$ }
'skip$
if$
preamble$ empty$
'skip$
{ preamble$ write$ newline$ }
if$
"\begin{thebibliography}{" "}" * write$ newline$
}
EXECUTE {begin.bib}
EXECUTE {init.state.consts}
ITERATE {call.type$}
FUNCTION {end.bib}
{ newline$
"\end{thebibliography}" write$ newline$
}
EXECUTE {end.bib}
bdtl-1.0.4/doc/background/algorithmicx.sty 0000644 0001750 0001750 00000064176 12122405072 020363 0 ustar melamed melamed % ALGORITHMIC STYLE -- Released 27 APR 2005
% for LaTeX version 2e
%
% Copyright Szasz Janos
% E-mail szaszjanos@users.sourceforge.net
%
%
% *** INITIALISING ***
%
%
\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{algorithmicx}[2005/04/27 v1.2 Algorithmicx]
\RequirePackage{ifthen}
\typeout{Document Style algorithmicx 1.2 - a greatly improved `algorithmic' style}
%
\newcounter{ALG@line}
\newcounter{ALG@rem}
\newcounter{ALG@nested}
\newlength{\ALG@tlm}
\newlength{\ALG@thistlm}
\newcounter{ALG@Lnr}% the number of defined languages
\setcounter{ALG@Lnr}{0}
\newcounter{ALG@blocknr}% the number of defined blocks
\setcounter{ALG@blocknr}{0}
\newcounter{ALG@storecount}% number of stored but not restored algorithmic environments
\setcounter{ALG@storecount}{0}
\newcounter{ALG@tmpcounter}% only to decrement things
\newlength\ALG@tmplength%
%\def\algorithmicnoindent{-\ALG@tlm}
% \def\algbackskipbegin{\hskip\ALG@ctlm}
%\def\algbackskip{\hskip-\ALG@thistlm}
%\def\algbackskipend{\hskip-\ALG@tlm}
\def\ALG@defaultindent{\algorithmicindent}
%
% conditional states
%
\def\ALG@newcondstate#1%
{%
\expandafter\edef\csname ALG@x@#1\endcsname%
{\expandafter\noexpand\csname @@ALG@x@#1\endcsname}%
}%
\ALG@newcondstate{notext}%
\ALG@newcondstate{default}%
%
%
% *** ALGORITHMIC ***
%
%
\newcommand\ALG@beginblock[1]% #1 - indentation
{%
\ALG@thistlm\ALG@tlm%
\addtolength\ALG@tlm{#1}%
\addtocounter{ALG@nested}{1}%
\setlength\ALG@tmplength{#1}%
\expandafter\edef\csname ALG@ind@\theALG@nested\endcsname{\the\ALG@tmplength}%
}%
\newcommand\ALG@endblock%
{%
\addtolength\ALG@tlm{-\csname ALG@ind@\theALG@nested\endcsname}%
\addtocounter{ALG@nested}{-1}%
\ALG@thistlm\ALG@tlm%
}%
%
% algorithmic environment
%
\def\ALG@step%
{%
\addtocounter{ALG@line}{1}%
\addtocounter{ALG@rem}{1}%
\ifthenelse{\equal{\arabic{ALG@rem}}{\ALG@numberfreq}}%
{\setcounter{ALG@rem}{0}\alglinenumber{\arabic{ALG@line}}}%
{}%
}%
\newenvironment{algorithmic}[1][0]%
{%
\edef\ALG@numberfreq{#1}%
\def\@currentlabel{\theALG@line}%
%
\setcounter{ALG@line}{0}%
\setcounter{ALG@rem}{0}%
%
\let\\\algbreak%
%
\expandafter\edef\csname ALG@currentblock@\theALG@nested\endcsname{0}%
\expandafter\let\csname ALG@currentlifetime@\theALG@nested\endcsname\relax%
%
\begin{list}%
{\ALG@step}%
{%
\rightmargin\z@%
\itemsep\z@ \itemindent\z@ \listparindent2em%
\partopsep\z@ \parskip\z@ \parsep\z@%
\labelsep 0.5em \topsep 0.2em%\skip 1.2em
\ifthenelse{\equal{#1}{0}}%
{\labelwidth 0.5em}%
{\labelwidth 1.2em}%
\leftmargin\labelwidth \addtolength{\leftmargin}{\labelsep}% Ok. the perfect leftmargin :-))
\ALG@tlm\z@%
}%
\setcounter{ALG@nested}{0}%
\ALG@beginalgorithmic%
}%
{% end{algorithmic}
% check if all blocks are closed
\ALG@closeloops%
\expandafter\ifnum\csname ALG@currentblock@\theALG@nested\endcsname=0\relax%
\else%
\PackageError{algorithmicx}{Some blocks are not closed!!!}{}%
\fi%
\ALG@endalgorithmic%
\end{list}%
}%
%
%
% *** Functional core ***
%
%
\def\ALG@makeentity#1% execute the entity (#1)
{%
\def\ALG@thisentity{#1}%
\expandafter\ifx\csname ALG@b@\ALG@L @#1@0\endcsname\relax%
\let\ALG@makenobeginrepeat\ALG@makenobegin\ALG@makenobeginrepeat% this entitie ends or continues blocks
\else%
\let\ALG@makebeginrepeat\ALG@makebegin\ALG@makebeginrepeat% this entitie can open blocks
\fi%
\ALG@entitiecommand%
}%
%
\def\ALG@makebegin% executes an entitie that can open blocks
{%
\expandafter\let\expandafter\ALG@thislifetime\csname ALG@currentlifetime@\theALG@nested\endcsname%
\ifx\ALG@thislifetime\relax%
\let\ALG@makebeginrepeat\ALG@doentity% in infinite block I can open my block
\else%
\ifnum\ALG@thislifetime>0\relax%
\ifnum\ALG@thislifetime>65534\else%
\setcounter{ALG@tmpcounter}{\ALG@thislifetime}% the block has 'space' for another included block
\addtocounter{ALG@tmpcounter}{-1}%
\expandafter\edef\csname ALG@currentlifetime@\theALG@nested\endcsname{\arabic{ALG@tmpcounter}}%
\fi%
\let\ALG@makebeginrepeat\ALG@doentity%
\else% the block needs to be closed
\expandafter\ifx\csname ALG@b@\ALG@L @\ALG@thisentity @\csname ALG@currentblock@\theALG@nested\endcsname\endcsname\relax%
\ALG@closebyforce% I can not close this block, continue after it is closed by force
% \ALG@makebegin%
\else%
% the block would be closed automatically, but this entitie can close it, so let's do it with the entity
\let\ALG@makebeginrepeat\ALG@doentity%
\fi%
\fi%
\fi%
\ALG@makebeginrepeat%
}%
%
\def\ALG@makenobegin% executes an entitie that can not open blocks
{%
\expandafter\ifx\csname ALG@currentlifetime@\theALG@nested\endcsname\relax%
\let\ALG@makenobeginrepeat\ALG@doentity% an infinite block must be broken
\else%
\expandafter\ifx\csname ALG@b@\ALG@L @\ALG@thisentity @\csname ALG@currentblock@\theALG@nested\endcsname\endcsname\relax%
\ALG@closebyforce% the block must be ended by force,
\else%
\let\ALG@makenobeginrepeat\ALG@doentity% I can continue / end this block, let's do it
\fi%
\fi%
\ALG@makenobeginrepeat%
}%
%
\def\ALG@dobegin%
{%
\ALG@beginblock{\csname ALG@i@\ALG@L @\ALG@thisentity @\ALG@thisblock\endcsname}%
\expandafter\edef\csname ALG@currentblock@\theALG@nested\endcsname{\csname ALG@b@\ALG@L @\ALG@thisentity @\ALG@thisblock\endcsname}%
\expandafter\ifx\csname ALG@c@\ALG@L @\ALG@thisentity @\ALG@thisblock\endcsname\relax%
\expandafter\let\csname ALG@currentlifetime@\theALG@nested\endcsname\relax%
\else%
\expandafter\edef\csname ALG@currentlifetime@\theALG@nested\endcsname{\csname ALG@c@\ALG@L @\ALG@thisentity @\ALG@thisblock\endcsname}%
\fi%
}%
%
\def\ALG@doend%
{%
\ALG@endblock%
}%
%
\def\ALG@doentity% the number of the closed block, the entitie
{%
\edef\ALG@thisblock{\csname ALG@currentblock@\theALG@nested\endcsname}%
\expandafter\ifx\csname ALG@b@\ALG@L @\ALG@thisentity @\ALG@thisblock\endcsname\relax%
\def\ALG@thisblock{0}%
\fi%
\ALG@getentitytext%
\ifnum\ALG@thisblock=0\else\ALG@doend\fi%
\ifx\ALG@text\ALG@x@notext%
\item[]\nointerlineskip%\vskip-\prevdepth\nointerlineskip% bug: if there are no text and no lines, then this is wrong
\else%
\item%
\fi%
\noindent\hskip\ALG@tlm%
\expandafter\ifnum0=\csname ALG@b@\ALG@L @\ALG@thisentity @\ALG@thisblock\endcsname\else%
\ALG@dobegin%
\fi%
\def\ALG@entitiecommand{\ALG@displayentity}%
}%
%
\def\ALG@getentitytext%
{%
\expandafter\let\expandafter\ALG@text\csname ALG@t@\ALG@L @\ALG@thisentity @\ALG@thisblock\endcsname%
\ifx\ALG@text\ALG@x@default%
% block specific - default
\expandafter\let\expandafter\ALG@text\csname ALG@t@\ALG@L @\ALG@thisentity\endcsname%
\ifx\ALG@text\ALG@x@default%
% block specific - default, language specific - default
\def\ALG@text{\ALG@deftext{\ALG@thisentity}}%
\fi%
\fi%
}%
%
\def\ALG@deftext{\csname ALG@deftext@\ALG@L\endcsname}%
%
\def\ALG@displayentity%
{%
\ifx\ALG@text\ALG@x@notext%
\let\ALG@text\relax%
\fi
\ALG@text%
}%
%
\def\ALG@closebyforce%
{%
\ALG@endblock%
}%
%
\def\ALG@closeloops% closes all finite blocks
{%
\expandafter\ifx\csname ALG@currentlifetime@\theALG@nested\endcsname\relax%
\else% only if it is finite
\ALG@closebyforce% the block must be ended by force,
\ALG@closeloops% the command still runs
\fi%
}%
%
%
% *** Low level block/entitie defining commands ***
%
%
\def\ALG@bl@{0}% the BIG block
\let\ALG@bl@@\ALG@bl@% the BIG block
%
% Create a block
%
\def\ALG@createblock#1% create the block #1, if it does not exists
{%
\@ifundefined{ALG@bl@\ALG@Ld @#1}% needs to be created?
{%
\addtocounter{ALG@blocknr}{1}% increment the block counter
\expandafter\edef\csname ALG@bl@\ALG@Ld @#1\endcsname{\arabic{ALG@blocknr}}% set the block number
}%
{}%
}%
%
% Get the block number
%
\def\ALG@getblocknumber#1{\csname ALG@bl@\ALG@Ld @#1\endcsname}%
%
% Create an entitie
%
\def\ALG@createentitie#1% create the entitie #1, if it does not exists
{%
\expandafter\ALG@edefcmd\csname #1\endcsname{\noexpand\ALG@makeentity{#1}}%
\@ifundefined{ALG@t@\ALG@Ld @#1}% the entity text is defined in this language?
{%
\expandafter\let\csname ALG@t@\ALG@Ld @#1\endcsname\ALG@x@default%
}%
{}%
}%
%
\def\ALG@createtext#1#2% #1 = closed block; #2 = entitie; creates \ALG@t@#2@#1
{%
\expandafter\let\csname ALG@t@\ALG@Ld @#2@#1\endcsname\ALG@x@default%
}%
%
% End and Continue block
%
\def\ALG@endandcontinueblock#1#2#3#4#5% #1 = new block; #2 = old block; #3 = entitie; #4 = credits; #5 = indent
{%
\ifthenelse{\equal{#3}{}}{}% execute only if the entity is not empty
{%
\ALG@createentitie{#3}% create the entitie
\ALG@createblock{#2}% create the old block, if needed
\ifthenelse{\equal{#1}{}}% whe need to open a new block?
{\expandafter\edef\csname ALG@b@\ALG@Ld @#3@\ALG@getblocknumber{#2}\endcsname{0}}% no, just close the old one
{% yes,
\ALG@createblock{#1}% create the block
\expandafter\edef\csname ALG@b@\ALG@Ld @#3@\ALG@getblocknumber{#2}\endcsname{\ALG@getblocknumber{#1}}% ending the old block opens a new one
\ifthenelse{\equal{#4}{}}% infinite or finite credits?
{\expandafter\let\csname ALG@c@\ALG@Ld @#3@\ALG@getblocknumber{#2}\endcsname\relax}% infinite credits
{\expandafter\edef\csname ALG@c@\ALG@Ld @#3@\ALG@getblocknumber{#2}\endcsname{#4}}% finite credits
\ifthenelse{\equal{#5}{}}% default or specified indentation
{\expandafter\let\csname ALG@i@\ALG@Ld @#3@\ALG@getblocknumber{#2}\endcsname\ALG@defaultindent}% default indentation
{\expandafter\edef\csname ALG@i@\ALG@Ld @#3@\ALG@getblocknumber{#2}\endcsname{#5}}% indentation is specified
}%
\ALG@createtext{\ALG@getblocknumber{#2}}{#3}%
}%
}%
%
% macros used in declarations
%
\def\ALG@p@endtext@E{\algrenewtext{\ALG@v@end}}%
\def\ALG@p@endtext@xE{\algrenewtext[\ALG@v@newblock]{\ALG@v@end}}%
\def\ALG@p@endtext@nE{\algnotext{\ALG@v@end}}%
\def\ALG@p@endtext@xnE{\algnotext[\ALG@v@newblock]{\ALG@v@end}}%
\def\ALG@p@endtext@{}%
% starttext defines are more compex -- care must be taken for the optional parameters
\def\ALG@p@starttext@S{\ALG@p@s@process{\algrenewtext}}%
\def\ALG@p@starttext@C{\ALG@p@s@process{\algrenewtext}}%
\def\ALG@p@starttext@xC{\ALG@p@s@process{\algrenewtext[\ALG@v@oldblock]}}%
\def\ALG@p@s@process#1%
{%
\ifthenelse{\equal{\ALG@v@start}{}}%
{\ALG@p@endtext}%
{\@ifnextchar{[}{\ALG@p@s@getparamcount{#1}}{\ALG@p@s@simple{#1}}}%
}%
\def\ALG@p@s@getparamcount#1[#2]%
{%
\@ifnextchar{[}{\ALG@p@s@getdefparam{#1}{#2}}{\ALG@p@s@param{#1}{#2}}%
}%
\def\ALG@p@s@getdefparam#1#2[#3]%
{%
\ALG@p@s@defparam{#1}{#2}{#3}%
}%
\def\ALG@p@s@simple#1#2{#1{\ALG@v@start}{#2}\ALG@p@endtext}%
\def\ALG@p@s@param#1#2#3{#1{\ALG@v@start}[#2]{#3}\ALG@p@endtext}%
\def\ALG@p@s@defparam#1#2#3#4{#1{\ALG@v@start}[#2][#3]{#4}\ALG@p@endtext}%
% the rest of the crew
\def\ALG@p@starttext@nS{\algnotext{\ALG@v@start}\ALG@p@endtext}%
\def\ALG@p@starttext@nC{\algnotext{\ALG@v@start}\ALG@p@endtext}%
\def\ALG@p@starttext@xnC{\algnotext[\ALG@v@oldblock]{\ALG@v@start}\ALG@p@endtext}%
\def\ALG@p@starttext@{\ALG@p@endtext}%
\def\ALG@p@indent@def#1{\def\ALG@v@indent{#1}\ALG@p@setup}%
\def\ALG@p@indent@{\def\ALG@v@indent{}\ALG@p@setup}%
\def\ALG@p@credits@def#1{\def\ALG@v@credits{#1}\ALG@p@indent}%
\def\ALG@p@credits@{\ALG@p@indent}%
\def\ALG@p@end@def#1{\def\ALG@v@end{#1}\ALG@p@credits}%
\def\ALG@p@end@{\def\ALG@v@end{}\ALG@p@credits}%
\def\ALG@p@start@def#1{\def\ALG@v@start{#1}\ALG@p@end}%
\def\ALG@p@start@{\def\ALG@v@start{}\ALG@p@end}%
\def\ALG@p@oldblock@def#1{\def\ALG@v@oldblock{#1}\ALG@p@start}%
\def\ALG@p@oldblock@{\def\ALG@v@oldblock{}\ALG@p@start}%
\newcommand\ALG@p@newblock[1][]{\def\ALG@v@newblock{#1}\ALG@p@oldblock}%
\def\ALG@p@setup%
{%
\ifthenelse{\equal{\ALG@v@newblock}{}}%
{%
\ifthenelse{\equal{\ALG@v@start}{}}%
{%
\PackageError{algorithmicx}{Block or starting entitie must be specified!!!}{}%
}%
{%
\let\ALG@v@newblock\ALG@v@start%
}%
}%
{%
}%
\ALG@endandcontinueblock%
{\ALG@v@newblock}{\ALG@v@oldblock}{\ALG@v@start}%
{\ALG@v@credits}{\ALG@v@indent}%
\ALG@endandcontinueblock%
{}{\ALG@v@newblock}{\ALG@v@end}%
{}{}%
\ALG@p@starttext%
}%
%
% param handling
%
\newcommand\ALG@p@def[2][def]%
{%
\expandafter\let\csname ALG@p@#2\expandafter\endcsname\csname ALG@p@#2@#1\endcsname%
}%
\def\ALG@p@undef{\ALG@p@def[]}%
%
\def\ALG@p@ons{\ALG@p@def{start}}%
\def\ALG@p@onS{\ALG@p@def{start}\ALG@p@def[S]{starttext}}%
\def\ALG@p@onc{\ALG@p@def{oldblock}\ALG@p@def{start}}%
\def\ALG@p@onC{\ALG@p@def{oldblock}\ALG@p@def{start}\ALG@p@def[C]{starttext}}%
\def\ALG@p@one{\ALG@p@def{end}}%
\def\ALG@p@onE{\ALG@p@def{end}\ALG@p@def[E]{endtext}}%
\def\ALG@p@onxC{\ALG@p@def{oldblock}\ALG@p@def{start}\ALG@p@def[xC]{starttext}}%
\def\ALG@p@onxE{\ALG@p@def{end}\ALG@p@def[xE]{endtext}}%
\def\ALG@p@onnS{\ALG@p@def{start}\ALG@p@def[nS]{starttext}}%
\def\ALG@p@onnC{\ALG@p@def{oldblock}\ALG@p@def{start}\ALG@p@def[nC]{starttext}}%
\def\ALG@p@onnE{\ALG@p@def{end}\ALG@p@def[nE]{endtext}}%
\def\ALG@p@onxnC{\ALG@p@def{oldblock}\ALG@p@def{start}\ALG@p@def[xnC]{starttext}}%
\def\ALG@p@onxnE{\ALG@p@def{end}\ALG@p@def[xnE]{endtext}}%
\def\ALG@p@onb{\def\ALG@v@credits{}}%
\def\ALG@p@onl{\def\ALG@v@credits{1}}%
\def\ALG@p@onL{\ALG@p@def{credits}}%
\def\ALG@p@oni{\ALG@p@def{indent}}%
%
\def\ALG@p@main#1%
{%
\@ifundefined{ALG@ps@\ALG@p@state @#1}%
{%
\csname ALG@ps@\ALG@p@state @other\endcsname{#1}%
}%
{%
\csname ALG@ps@\ALG@p@state @#1\endcsname%
}%
\ALG@p@rec%
}%
% STATE : <>
\expandafter\def\csname ALG@ps@@]\endcsname{\let\ALG@p@rec\relax}%
\def\ALG@ps@@s{\ALG@p@ons}%
\def\ALG@ps@@S{\ALG@p@onS}%
\def\ALG@ps@@c{\ALG@p@onc}%
\def\ALG@ps@@C{\ALG@p@onC}%
\def\ALG@ps@@e{\ALG@p@one}%
\def\ALG@ps@@E{\ALG@p@onE}%
\def\ALG@ps@@N{\typeout{algdef: 'N' obsoloted, use 'nE'.}\ALG@p@onnE}%
\def\ALG@ps@@b{\ALG@p@onb}%
\def\ALG@ps@@l{\ALG@p@onl}%
\def\ALG@ps@@L{\ALG@p@onL}%
\def\ALG@ps@@i{\ALG@p@oni}%
\def\ALG@ps@@x{\def\ALG@p@state{x}}%
\def\ALG@ps@@n{\def\ALG@p@state{n}}%
\def\ALG@ps@@other#1{\typeout{algdef: Ignoring unknown token #1}}%
% STATE : x
\def\ALG@ps@x@C{\def\ALG@p@state{}\ALG@p@onxC}%
\def\ALG@ps@x@E{\def\ALG@p@state{}\ALG@p@onxE}%
\def\ALG@ps@x@N{\def\ALG@p@state{}\typeout{algdef: 'xN' obsoloted, use 'xnE'.}\ALG@p@onxnE}%
\def\ALG@ps@x@n{\def\ALG@p@state{xn}}%
\def\ALG@ps@x@other#1%
{%
\typeout{algdef: Ignoring 'x' before '#1'.}%
\def\ALG@p@state{}%
\def\ALG@p@rec{\let\ALG@p@rec\ALG@p@main\ALG@p@rec#1}%
}%
% STATE : n
\def\ALG@ps@n@S{\def\ALG@p@state{}\ALG@p@onnS}%
\def\ALG@ps@n@C{\def\ALG@p@state{}\ALG@p@onnC}%
\def\ALG@ps@n@E{\def\ALG@p@state{}\ALG@p@onnE}%
\def\ALG@ps@n@x{\def\ALG@p@state{nx}}%
\def\ALG@ps@n@other#1%
{%
\typeout{algdef: Ignoring 'n' before '#1'.}%
\def\ALG@p@state{}%
\def\ALG@p@rec{\let\ALG@p@rec\ALG@p@main\ALG@p@rec#1}%
}%
% STATE : xn
\def\ALG@ps@xn@C{\def\ALG@p@state{}\ALG@p@onxnC}%
\def\ALG@ps@xn@E{\def\ALG@p@state{}\ALG@p@onxnE}%
\def\ALG@ps@xn@x{\typeout{algdef: Ignoring 'x' after 'xn'.}}%
\def\ALG@ps@xn@n{\typeout{algdef: Ignoring 'n' after 'xn'.}}%
\def\ALG@ps@xn@other#1%
{%
\typeout{algdef: Ignoring 'xn' before '#1'.}%
\def\ALG@p@state{}%
\def\ALG@p@rec{\let\ALG@p@rec\ALG@p@main\ALG@p@rec#1}%
}%
% STATE : nx
\def\ALG@ps@nx@C{\def\ALG@p@state{}\ALG@p@onxnC}%
\def\ALG@ps@nx@E{\def\ALG@p@state{}\ALG@p@onxnE}%
\def\ALG@ps@nx@x{\typeout{algdef: Ignoring 'x' after 'nx'.}}%
\def\ALG@ps@nx@n{\typeout{algdef: Ignoring 'n' after 'nx'.}}%
\def\ALG@ps@nx@other#1%
{%
\typeout{algdef: Ignoring 'nx' before '#1'.}%
\def\ALG@p@state{}%
\def\ALG@p@rec{\let\ALG@p@rec\ALG@p@main\ALG@p@rec#1}%
}%
%
%
% *** User level block/entitie commands ***
%
%
%
% algdef{switches}... -- the king of all definitions in the algorithmicx package
%
\newcommand\algdef[1]%
{%
\ALG@p@undef{oldblock}%
\ALG@p@undef{start}%
\ALG@p@undef{end}%
\def\ALG@v@credits{}%
\ALG@p@undef{credits}%
\ALG@p@undef{indent}%
\ALG@p@undef{starttext}%
\ALG@p@undef{endtext}%
\def\ALG@p@state{}%
\let\ALG@p@rec\ALG@p@main%
\ALG@p@rec#1]%
\ALG@p@newblock%
}%
%
% a lot of other macros are provided for convenience
%
\def\algblock{\algdef{se}}%
\def\algcblock{\algdef{ce}}%
\def\algloop{\algdef{sl}}%
\def\algcloop{\algdef{cl}}%
\def\algsetblock{\algdef{seLi}}%
\def\algsetcblock{\algdef{ceLi}}%
\def\algblockx{\algdef{SxE}}%
\def\algblockdefx{\algdef{SE}}%
\def\algcblockx{\algdef{CxE}}%
\def\algcblockdefx{\algdef{CE}}%
\def\algsetblockx{\algdef{SxELi}}%
\def\algsetblockdefx{\algdef{SELi}}%
\def\algsetcblockx{\algdef{CxELi}}%
\def\algsetcblockdefx{\algdef{CELi}}%
\def\algloopdefx{\algdef{Sl}}%
\def\algcloopx{\algdef{xCl}}%
\def\algcloopdefx{\algdef{Cl}}%
% algloopx is not correct, use algloopdefx
%
% Text output commands
%
\newcommand\algrenewtext[2][]% [block]{entity}
{%
\ifthenelse{\equal{#2}{}}{}%
{%
\ifthenelse{\equal{#1}{}}%
{%
\expandafter\let\csname ALG@t@\ALG@Ld @#2\endcsname\relax%
\expandafter\newcommand\csname ALG@t@\ALG@Ld @#2\endcsname%
}%
{%
\expandafter\let\csname ALG@t@\ALG@Ld @#2@\ALG@getblocknumber{#1}\endcsname\relax%
\expandafter\newcommand\csname ALG@t@\ALG@Ld @#2@\ALG@getblocknumber{#1}\endcsname%
}%
}%
}%
%
\def\ALG@letentitytext#1#2% [block]{entity}
{%
\ifthenelse{\equal{#2}{}}{}%
{%
\ifthenelse{\equal{#1}{}}%
{%
\expandafter\let\csname ALG@t@\ALG@Ld @#2\endcsname%
}%
{%
\expandafter\let\csname ALG@t@\ALG@Ld @#2@\ALG@getblocknumber{#1}\endcsname%
}%
}%
}%
%
\newcommand\algnotext[2][]% [block]{entity}
{%
\ALG@letentitytext{#1}{#2}\ALG@x@notext%
}%
%
\newcommand\algdefaulttext[2][]% [block]{entity}
{%
\ALG@letentitytext{#1}{#2}\ALG@x@default%
}%
%
\def\ALG@notext*{\algnotext}%
\def\algtext{\@ifnextchar{*}{\ALG@notext}{\algrenewtext}}%
%
%
% *** LANGUAGE SWITCHING ***
%
%
%
\newcommand\algnewlanguage[1]%
{%
\@ifundefined{ALG@L@#1}% needs to be created?
{}%
{%
\PackageError{algorithmicx}{Language '#1' already defined!}{}%
}%
\addtocounter{ALG@Lnr}{1}% increment the language counter
\expandafter\edef\csname ALG@L@#1\endcsname{\arabic{ALG@Lnr}}% set the language number
\edef\ALG@Ld{\csname ALG@L@#1\endcsname}%
\expandafter\let\csname ALG@bl@\ALG@Ld @\endcsname\ALG@bl@% the BIG block
\expandafter\let\csname ALG@bl@\ALG@Ld @@\endcsname\ALG@bl@% the BIG block
\algdef{SL}[STATE]{State}{0}{}%
\expandafter\def\csname ALG@deftext@\ALG@Ld\endcsname{\textbf}%
\algnewcommand\algorithmiccomment[1]{\hfill\(\triangleright\) ##1}%
\algnewcommand\algorithmicindent{1.5em}%
\algnewcommand\alglinenumber[1]{\footnotesize ##1:}%
\algnewcommand\ALG@beginalgorithmic\relax% for user overrides
\algnewcommand\ALG@endalgorithmic\relax% for user overrides
}%
%
\newcommand\algsetlanguage[1]%
{%
\@ifundefined{ALG@L@#1}% needs to be created?
{%
\PackageError{algorithmicx}{Language '#1' is not yet defined!}{}%
}{}%
\edef\ALG@L{\csname ALG@L@#1\endcsname}%
}%
%
\newcommand\algdeflanguage[1]%
{%
\@ifundefined{ALG@L@#1}% needs to be created?
{%
\PackageError{algorithmicx}{Language '#1' is not yet defined!}{}%
}{}%
\edef\ALG@Ld{\csname ALG@L@#1\endcsname}%
}%
%
\newcommand\alglanguage[1]%
{%
\algdeflanguage{#1}%
\algsetlanguage{#1}%
}%
%
%
% *** Defining language dependent stuff ***
%
%
\def\ALG@eatoneparam#1{}%
\def\ALG@defbasecmd#1#2%
{%
\edef\ALG@tmp{\expandafter\ALG@eatoneparam\string #2}%
\@ifundefined\ALG@tmp{\edef #2{\noexpand\csname ALG@cmd@\noexpand\ALG@L @\ALG@tmp\endcsname}}{}%
\expandafter#1\csname ALG@cmd@\ALG@Ld @\ALG@tmp\endcsname%
}%
\newcommand\algnewcommand{\ALG@defbasecmd\newcommand}%
\newcommand\algrenewcommand{\ALG@defbasecmd\renewcommand}%
\def\ALG@letcmd{\ALG@defbasecmd\let}%
\def\ALG@defcmd{\ALG@defbasecmd\def}%
\def\ALG@edefcmd{\ALG@defbasecmd\edef}%
%
%
% *** OTHERS ***
%
%
\def\BState{\State \algbackskip}%
\def\Statex{\item[]}% an empty line
\newcommand\algrenewcomment{\algrenewcommand\algorithmiccomment}%
\def\Comment{\algorithmiccomment}%
\def\algref#1#2{\ref{#1}.\ref{#2}}%
\algnewlanguage{default}%
\algsetlanguage{default}%
%
%
% *** Line breaks ***
%
%
\newcommand\algbreak% for multiline parameters !!! needs fix
{%
\item%
% \hskip\ALG@parindent%!!! not yet implemented
% \hskip-\algorithmicindent%
}%
%
\def\ALG@noputindents%
{%
\hskip\ALG@tlm%
}%
%
%
% *** algorithm store / restore ***
%
%
% store
%
\ALG@newcondstate{mustrestore}%
\def\algstore%
{%
\renewcommand\ALG@beginblock%
{%
\PackageError{algorithmicx}{The environment must be closed after store!}{}%
}%
\@ifstar{\ALG@starstore}{\ALG@nostarstore}%
}%
\def\ALG@nostarstore#1% save all infos into #1 and terminate the algorithmic block
{%
\addtocounter{ALG@storecount}{1}%
\expandafter\global\expandafter\let\csname ALG@save@mustrestore@#1\endcsname\ALG@x@mustrestore%
\ALG@starstore{#1}%
}%
\def\ALG@starstore#1%
{%
\@ifundefined{ALG@save@line@#1}{}%
{\PackageError{algorithmicx}{This save name '#1' is already used!}{}}%
\def\ALG@savename{#1}%
\expandafter\xdef\csname ALG@save@totalnr@\ALG@savename\endcsname{\theALG@nested}%
\expandafter\xdef\csname ALG@save@line@\ALG@savename\endcsname{\theALG@line}%
\expandafter\xdef\csname ALG@save@numberfreq@\ALG@savename\endcsname{\ALG@numberfreq}%
\expandafter\xdef\csname ALG@save@rem@\ALG@savename\endcsname{\theALG@rem}%
\let\ALG@storerepeat\ALG@store%
\ALG@storerepeat%
}%
\def\ALG@store% simply terminate all open blocks
{%
\ifnum\theALG@nested=0\let\ALG@storerepeat\relax%
\else%
\expandafter\xdef\csname ALG@save@currentblock@\ALG@savename @\theALG@nested\endcsname%
{\csname ALG@currentblock@\theALG@nested\endcsname}%
\expandafter\ifx\csname ALG@currentlifetime@\theALG@nested\endcsname\relax%
\else%
\expandafter\xdef\csname ALG@save@currentlifetime@\ALG@savename @\theALG@nested\endcsname%
{\csname ALG@currentlifetime@\theALG@nested\endcsname}%
\fi%
\expandafter\xdef\csname ALG@save@ind@\ALG@savename @\theALG@nested\endcsname%
{\csname ALG@ind@\theALG@nested\endcsname}%
\ALG@closebyforce%
\fi%
\ALG@storerepeat%
}%
%
% restore
%
\def\algrestore%
{%
\@ifstar{\ALG@starrestore}{\ALG@nostarrestore}%
}%
\def\ALG@starrestore%
{%
\let\ALG@restorerem\relax%
\let\ALG@restorereprem\relax%
\ALG@restoremain%
}%
\def\ALG@nostarrestore%
{%
\let\ALG@restorerem\ALG@restoreremovesave%
\let\ALG@restorereprem\ALG@restorerepremovesave%
\ALG@restoremain%
}%
\def\ALG@restoreremovesave%
{%
\expandafter\global\expandafter\let\csname ALG@save@totalnr@\ALG@savename\endcsname\relax%
\expandafter\global\expandafter\let\csname ALG@save@line@\ALG@savename\endcsname\relax%
\expandafter\global\expandafter\let\csname ALG@save@rem@\ALG@savename\endcsname\relax%
\expandafter\global\expandafter\let\csname ALG@save@totalnr@\ALG@savename\endcsname\relax%
\expandafter\global\expandafter\let\csname ALG@save@numberfreq@\ALG@savename\endcsname\relax%
}%
\def\ALG@restorerepremovesave%
{%
\expandafter\global\expandafter\let\csname ALG@save@currentblock@\ALG@savename @\theALG@tmpcounter\endcsname\relax%
\expandafter\global\expandafter\let\csname ALG@save@currentlifetime@\ALG@savename @\theALG@tmpcounter\endcsname\relax%
\expandafter\global\expandafter\let\csname ALG@save@currentlifetime@\ALG@savename @\theALG@tmpcounter\endcsname\relax%
\expandafter\global\expandafter\let\csname ALG@save@ind@\ALG@savename @\theALG@tmpcounter\endcsname\relax%
}%
\def\ALG@restoremain#1% restore all infos from #1 in an open algorithmic block
{%
\ifnum\theALG@line=0%
\else\PackageError{algorithmicx}{Restore might be used only at the beginning of the environment!}{}%
\fi%
\def\ALG@savename{#1}%
\expandafter\ifx\csname ALG@save@totalnr@\ALG@savename\endcsname\relax%
\PackageError{algorithmicx}{Save '\ALG@savename'\space not defined!!!}{}%
\fi%
\@ifundefined{ALG@save@mustrestore@\ALG@savename}{}%
{%
\addtocounter{ALG@storecount}{-1}%
\expandafter\global\expandafter\let\csname ALG@save@mustrestore@\ALG@savename\endcsname\relax%
}%
\setcounter{ALG@line}{\csname ALG@save@line@\ALG@savename\endcsname}%
\edef\ALG@numberfreq{\csname ALG@save@numberfreq@\ALG@savename\endcsname}%
\setcounter{ALG@rem}{\csname ALG@save@rem@\ALG@savename\endcsname}%
\setcounter{ALG@tmpcounter}{\csname ALG@save@totalnr@\ALG@savename\endcsname}%
\setcounter{ALG@nested}{0}%
\ALG@restorerem%
\let\ALG@restorerepeat\ALG@restore%
\ALG@restorerepeat%
}%
\def\ALG@restore%
{%
\ifnum\theALG@tmpcounter>0%
\expandafter\edef\csname ALG@currentblock@\theALG@tmpcounter\endcsname%
{\csname ALG@save@currentblock@\ALG@savename @\theALG@tmpcounter\endcsname}%
\expandafter\ifx\csname ALG@save@currentlifetime@\ALG@savename @\theALG@tmpcounter\endcsname\relax%
\expandafter\let\csname ALG@currentlifetime@\theALG@tmpcounter\endcsname\relax%
\else%
\expandafter\edef\csname ALG@currentlifetime@\theALG@tmpcounter\endcsname%
{\csname ALG@save@currentlifetime@\ALG@savename @\theALG@tmpcounter\endcsname}%
\fi%
%
\ALG@beginblock{\csname ALG@save@ind@\ALG@savename @\theALG@tmpcounter\endcsname}%
\ALG@restorereprem%
\addtocounter{ALG@tmpcounter}{-1}%
\else\let\ALG@restorerepeat\relax%
\fi%
\ALG@restorerepeat%
}%
\AtEndDocument%
{%
\ifnum\theALG@storecount>0\relax%
\PackageError{algorithmicx}{Some stored algorithms are not restored!}{}%
\fi%
}%
bdtl-1.0.4/doc/HOWTO.build 0000777 0001750 0001750 00000000000 12364543027 017647 2../src/HOWTO.build ustar melamed melamed bdtl-1.0.4/doc/HOWTO.use 0000777 0001750 0001750 00000000000 12364543027 017143 2usage/HOWTO.use ustar melamed melamed bdtl-1.0.4/doc/usage/ 0000755 0001750 0001750 00000000000 12364543027 014112 5 ustar melamed melamed bdtl-1.0.4/doc/usage/HOWTO.use 0000644 0001750 0001750 00000035330 12364537635 015544 0 ustar melamed melamed How to Use the Boosted Decision Trees and Lists (BDTL) Software (after it's built)
BDTL currently provides 3 binary executables and several utility
scripts. The binary executables are trainOne, testOne, and
compileEnsemble. trainOne and testOne do training and testing.
compileEnsemble is a utility for converting BDTL's models into a more
compact format. trainOne and testOne can work with models in either
format. The default output format of trainOne is less compact to
facilitate continuous checkpointing. The utility scripts include a
pretty-printer for BDTL's model format and scripts for converting
examples from SVMLight format to BDTL's more informative and more
compact format.
BDTL comes with a "sandbox", which serves multiple purposes. One of its
purposes is to show typical usage to new users. Users who want a
quick start can proceed as follows:
1. Set the environment variable BDTL_BASE to the top directory of your
installation. OTHERWISE NOTHING WILL WORK!
2. Follow the instructions in src/HOWTO.build to build the
executables.
3. Change to the sandbox/ directory and type `make`.
The sub-Makefiles in the sandbox can serve as templates that users
can modify for various purposes. For other uses of the sandbox, refer
to sandbox/HOWTO.play .
BDTL has more configuration parameters than most people expect in this
kind of software. However, users can ignore them, and just use the
defaults in the configuration files provided in the sandbox. More
info about the configuration parameters is provided below, for those
who want more control.
BDTL reads examples one per line, in the format