Index

Symbols

&

int_set, If one knows minimum and maximum in advance (class int_set)

()

random_source, The integer mode
string, Tips for the use of the class string

+

date, Dates (class date)
string, Further operations on strings

++

date, Dates (class date)

+=

string, Strings (class string)

-

date, Dates (class date)

--

date, Dates (class date)

-MDd

compiler option, Compiling, linking, and starting

-Tp

compiler option, Compiling, linking, and starting

<

set, Union, intersection, and difference of sets

=, Simple-structured types and their copy concept

(see also type and copy concept)
list, Copying of objects of an item-based type
string, Further operations on strings
with simple-structured types, Simple-structured types and their copy concept

==, Comparisons of LEDA objects

(see also equality predicate)
list, Comparisons of LEDA objects
string, Strings (class string)

>>

random_source, The integer mode, The bit mode

[]

array, Defining arrays and access to elements
list, Lists and the item-container-concept
string, Strings (class string)

|

int_set, If one knows minimum and maximum in advance (class int_set)

~

int_set, If one knows minimum and maximum in advance (class int_set)

Θ(f(n)), The O-notation

A

Algorithmic Solutions, Purchasing LEDA

amortized analysis, Amortized analysis

anagram, An example: Lists of string pairs in the computation of anagrams

anti-symmetry, Linear orders

append

to queue, Queues

append()

list, Appending and deleting of elements at the end of a list
queue, Queues with an unbounded number of elements (class queue)

apply()

list, Further list modifying operations

array, Arrays

and set, Sets (class set)

as opposed to lists, Linear lists (class list)

constructor, Defining arrays and access to elements

doubling strategy, Exercises

dynamical enlarging, Enlarging arrays dynamically

of arrays, Two-dimensional arrays (class array2)

rotating elements, Exercises

two-dimensional, Two-dimensional arrays (class array2)

(see also array2)

array2, Two-dimensional arrays (class array2)

constructor, Two-dimensional arrays (class array2)

assign()

list, Lists and the item-container-concept

assignment operator

and LEDA objects, Copying of objects of an item-based type

(see also type and copy concept)

asymptotical, The O-notation

attribute

of an item, Lists and the item-container-concept

automaton

cellular, Two-dimensional arrays (class array2)

B

b_queue, Queues, Queues with a bounded number of elements (class b_queue)

constructor, Queues with a bounded number of elements (class b_queue)

b_stack, Stacks, Stacks with a bounded number of elements (class b_stack)

constructor, Stacks with a bounded number of elements (class b_stack)

back()

list, Changing lists and searching in lists

bag

implementation by associative container types, array, list, stack, queue, set and d_int_set compared

beast of burden, What for shall we use a stack at all?

big marriage bureau, Union, intersection, and difference of sets

binary search, Useful methods of the class array, Exercises

binary_locate()

array, Useful methods of the class array

binary_search()

array, Useful methods of the class array

binomial coefficient, Enlarging arrays dynamically

Binomial distribution, The bit mode

binomial distribution, Queues with an unbounded number of elements (class queue)

bound

asymptotically lower, The O-notation
asymptotically upper, The O-notation

boxing club

creating pairs, Exercises

bucket_sort()

list, Sorting lists

C

chance, Random numbers (class random_source)

chess tournament

creating pairings, Exercises

choose()

set, Inserting elements and membership test

Christian Uhrig , What we did not cover

clear()

int_set, If one knows minimum and maximum in advance (class int_set)
queue, Queues with an unbounded number of elements (class queue)
set, Union, intersection, and difference of sets
stack, Stacks with an unbounded number of elements (class stack)

compare(), Sorting lists, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

and linear order, Linearly ordered types
and namespace leda, Making a type of our own linearly ordered
by means of polar coordinates, Exercises
defining several linear orders on a type, Several linear orders on a type

compare-equivalent, Linearly ordered types

complexity

quadratic, Time complexity
space, Space complexity
time, Time complexity

compound type, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

conc()

list, Further list modifying operations

constant

time complexity, The O-notation

constructor

with specification of the linear order, Several linear orders on a type

container

and items, Lists and the item-container-concept

container type, Defining arrays and access to elements, Filling and emptying lists

simple, Simple data types and simple container types

comparison of LEDA's types, array, list, stack, queue, set and d_int_set compared

contents()

list, Lists and the item-container-concept

Conway's game of life, Two-dimensional arrays (class array2)

cyclic_pred()

list, Lists and the item-container-concept

cyclic_succ()

list, Lists and the item-container-concept

D

d_int_set, Sets of integer numbers, If minimum or maximum are unknown (class d_int_set)

constructor, If minimum or maximum are unknown (class d_int_set)

data type

simple, Simple data types and simple container types

date, Dates (class date) (see date)

constructor, Dates (class date)

default initialization, Strings (class string)

default order, An example: Lists of string pairs in the computation of anagrams, Linearly ordered types

DEFINE_LINEAR_ORDER, Several linear orders on a type

del()

int_set, If one knows minimum and maximum in advance (class int_set)
set, Inserting elements and membership test
string, Further operations on strings

del_item()

list, Changing lists and searching in lists

delete, Efficient memory management for self-defined types

dice

fair, The integer mode
loaded, Static random variables (class random_variate)

diff()

set, Union, intersection, and difference of sets

difference

of sets, Union, intersection, and difference of sets
symmetric, Union, intersection, and difference of sets

directory

traversing, Dealing with directories and files

doubling strategy

and arrays, Exercises

download area

of the tutorial, Additional materials

dynamic_random_variate, Random variables , Dynamic random variables (class dynamic_random_variate)

constructor, Dynamic random variables (class dynamic_random_variate)

dynamic_trees, What we did not cover

E

eight-queen-problem, Exercises

element

of a container type, Defining arrays and access to elements
of a list, Lists and the item-container-concept

empty string, Strings (class string)

empty()

list, Filling and emptying lists
queue, Queues with an unbounded number of elements (class queue)
set, Union, intersection, and difference of sets
stack, Stacks with an unbounded number of elements (class stack)

equal (see equality of objects)

equality of objects, Comparisons of LEDA objects

equality predicate

and LEDA objects, Comparisons of LEDA objects

equivalence

and linear orders, Linear orders

equivalent (see compare-equivalent)

error handler, Error handling

error handling, Error handling

exception, Error handling

expression

arithmetic

evaluation on stack, Stacks with an unbounded number of elements (class stack)
fully parenthesized, Exercises
partially parenthesized, Exercises

F

f(n)=O(g(n))), The O-notation

FIFO principle, Queues

(see also queue)

file

obtaining information about, Dealing with directories and files

file.h, Dealing with directories and files

file_istream, What we did not cover

file_ostream, What we did not cover

first()

list, Lists and the item-container-concept
two_tuple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

first-in-first-out (see FIFO principle)

forall

over list, Iterating with the forall macros
over set, Inserting elements and membership test
realization by macro expansion, A closer look at the forall macros

forall_items

over list, Lists and the item-container-concept
realization by macro expansion, A closer look at the forall macros

forall_rev

over list, Iterating with the forall macros

forall_rev_items

over list, Lists and the item-container-concept

four_tuple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

fourth()

four_tuple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

front()

list, Changing lists and searching in lists

G

Galton board, The bit mode

generate()

random_variate, Static random variables (class random_variate)

get_day()

date, Dates (class date)

get_day_of_week()

date, Dates (class date)

get_directories(), Dealing with directories and files

get_files, Dealing with directories and files

get_msg()

leda_exception, Error handling

get_num()

leda_exception, Error handling

grammar

context free, Exercises

H

handle scheme, Handle types and handle-like types

handle technique, Queues with an unbounded number of elements (class queue)

handle type, Handle types and handle-like types

head

of a queue, Queues

head()

list, Appending and deleting of elements at the end of a list
string, Further operations on strings

header files, The header files of LEDA

Hello world!, Hello LEDA world! - The very first program

Hewlett-Packard (see pocket calculator with RPN)

high()

array, Useful methods of the class array

high1()

array2, Two-dimensional arrays (class array2)

high2()

array2, Two-dimensional arrays (class array2)

I

identical (see identity of objects)

identical(), Comparisons of LEDA objects

identity of objects, Comparisons of LEDA objects

identity predicate (see identical())

infix notation, Stacks with an unbounded number of elements (class stack)

init()

array, Useful methods of the class array

insert()

int_set, If one knows minimum and maximum in advance (class int_set)
list, Lists and the item-container-concept
set, Inserting elements and membership test
string, Further operations on strings

int_set, Sets of integer numbers

constructor, If one knows minimum and maximum in advance (class int_set)

intersect()

set, Union, intersection, and difference of sets

intersection

of sets, Union, intersection, and difference of sets

invariant, Defining arrays and access to elements

IP-address, Inserting elements and membership test

item, Lists and the item-container-concept

item type

dependent, Lists and the item-container-concept, Comparisons of LEDA objects
independent, Lists and the item-container-concept, Comparisons of LEDA objects

item-container-concept, Lists and the item-container-concept

J

join()

set, Union, intersection, and difference of sets

Josephus problem, Changing lists and searching in lists

generalized version, Exercises

Jumping Jack Flash, Filling and emptying lists

K

Kruskal' algorithm, What we did not cover

L

Landau's symbol, The O-notation

last()

list, Lists and the item-container-concept

last-in-first-out (see LIFO principle)

LD_LIBRARY_PATH, Starting

LEDA, What is LEDA?

categorization of data types, Categorization of the LEDA data types

compendium, Whom does this tutorial address?

compiling programs, Compiling, linking, and starting LEDA programs

discussion list, Where do we get help?

error handler, Error handling

getting help, Preparations

Guide, Whom does this tutorial address?

guide, Where do we get help?

header files, The header files of LEDA

installing, Preparations

integrated development environment, The MS-Windows world

libraries, Linking

linking programs, Compiling, linking, and starting LEDA programs

memory manager, Efficient memory management for self-defined types

news list, Where do we get help?

online manual, Whom does this tutorial address?

Online-Manual, Where do we get help?

purchasing, Preparations

set of rules, The LEDA set of rules, The golden LEDA rules

(see also LEDA rule)
overview, The golden LEDA rules

starting programs, Compiling, linking, and starting LEDA programs

type and copy concept, Simple-structured types and their copy concept

under MS-Windows, The MS-Windows world

under Unix, The Unix world

leda

namespace, The namespace leda, Making a type of our own linearly ordered

LEDA rule

copy of a value, Simple-structured types and their copy concept, Copying of objects of an item-based type
definition with initialization by copying, The LEDA set of rules
equality and identity, Comparisons of LEDA objects
illegal access via an item, Changing lists and searching in lists
Modification of objects of an item-based container type while iterating over them, A closer look at the forall macros
Requirements for linearly ordered types, Linearly ordered types
requirements for type parameters, User-defined type parameters
specification of the structure to be traversed in forall-macros, A closer look at the forall macros

leda::after, Lists and the item-container-concept, Further list modifying operations

leda::before, Lists and the item-container-concept, Further list modifying operations

LEDA_CHECKING_OFF, Automatic range checking

leda_exception, Error handling

leda_mdd.dll, The MS-Windows world

leda_mdd.lib, The MS-Windows world

LEDA_MEMORY(T), Efficient memory management for self-defined types

LEDAROOT, Compiling

lib3D, Linking

libG, Linking

libG2, Linking

libGeoWin, Linking

libL, Linking

libm, Linking

libP, Linking

libW, Linking

LIFO principle, Stacks

list, Linear lists (class list)

(see also list)
(see also slist)
accessing elements, Lists and the item-container-concept
and set, Sets (class set)
concatenating, Changing lists and searching in lists
delete from, Lists and the item-container-concept
deleting an element, Changing lists and searching in lists
doubly linked, Appending and deleting of elements at the end of a list, Lists and the item-container-concept
element, Lists and the item-container-concept
insert into, Lists and the item-container-concept
linear, Linear lists (class list)
permuting, Changing lists and searching in lists
reversing, Changing lists and searching in lists
searching in, Changing lists and searching in lists
singly linked, Singly linked lists (class slist)
sorting, Sorting lists
splitting, Changing lists and searching in lists
vs. array, Linear lists (class list)

logarithmic

time complexity, The O-notation

lottery

creating variations, An application: creating variations

low()

array, Useful methods of the class array

low1()

array2, Two-dimensional arrays (class array2)

low2()

array2, Two-dimensional arrays (class array2)

M

macro expansion

of the forall macros, A closer look at the forall macros

Makefile

generic, Linking

mathematicians' problem, Exercises

max()

int_set, If one knows minimum and maximum in advance (class int_set)
list, Further information about the class list

Max-Planck-Institut für Informatik, What is LEDA?

MAXNONREPMIRP number, Exercises

member()

int_set, If one knows minimum and maximum in advance (class int_set)
set, Inserting elements and membership test

memory manager, Efficient memory management for self-defined types

merge()

list, Sorting lists

merge_sort()

list, Sorting lists

Mergesort, Exercises

min()

int_set, If one knows minimum and maximum in advance (class int_set)
list, Further information about the class list

misc.h, Defining arrays and access to elements, Some useful functions

Monopoly, Exercises

MPII (see Max-Planck-Institut für Informatik)

multiset, Sets (class set)

N

namespace

leda, The namespace leda

new, Efficient memory management for self-defined types

O

O(log(n)), The O-notation

O(n), The O-notation

O(n2), The O-notation

O-notation, The O-notation

Θ, The O-notation

order

linear, Linear orders, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

realized by a compare-function, Linear orders
several on a type, Several linear orders on a type

user-defined, An example: Lists of string pairs in the computation of anagrams

order of magnitude

of a method, The O-notation

P

p_queue, Queues with an unbounded number of elements (class queue)

pair, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

(see also two_tuple)

pairing, Exercises

palindrome, Strings (class string)

partition, What we did not cover

Pascal's triangle, Enlarging arrays dynamically

permute()

array, Useful methods of the class array
list, Further list modifying operations

pocket calculator

with RPN, Stacks with an unbounded number of elements (class stack)

pointer

as elements of a container type, Queues with an unbounded number of elements (class queue)

polar coordinates

and compare(), Exercises

pop()

list, Filling and emptying lists
queue, Queues with an unbounded number of elements (class queue)
stack, Stacks, Stacks with an unbounded number of elements (class stack)

pop_back()

list, Appending and deleting of elements at the end of a list

pos()

string, Further operations on strings

postfix notation, Stacks with an unbounded number of elements (class stack)

precondition, Preconditions, Error handling

pred()

list, Lists and the item-container-concept

print()

array, Useful methods of the class array
list, Sorting lists

print_statistics(), Efficient memory management for self-defined types

profiling, Useful little somethings

push

into queue, Queues

push down automaton, Stacks with an unbounded number of elements (class stack)

push()

list, Filling and emptying lists
stack, Stacks, Stacks with an unbounded number of elements (class stack)

Q

quadruple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

(see also four_tuple)

queue, Queues

and deque, Exercises
simulation, Queues with an unbounded number of elements (class queue)
with unbounded number of elements (see b_queue)

Quicksort, The O-notation

R

rand_int, The seed

random number, Random numbers (class random_source)

random variable, Random variables

non-uniformly distributed, Random variables
uniformly distributed, The integer mode, Random variables

random walk, Dynamic random variables (class dynamic_random_variate)

random_source, Random numbers (class random_source)

bit mode, The bit mode
constructor, The integer mode, The bit mode
creating double values, An example: Creating fractal sets
instead of random_variate, Queues with an unbounded number of elements (class queue)
integer mode, The integer mode
precision, The bit mode

random_variate, Random variables , Static random variables (class random_variate), Queues with an unbounded number of elements (class queue)

constructor, Static random variables (class random_variate)

range checking, Automatic range checking

automatic, The integer mode

read()

list, Further information about the class list
string, Filling and emptying lists

read_line()

string, Strings (class string), Built-in sorting methods

read_string(), Defining arrays and access to elements

reference counting, Handle types and handle-like types

reflexivity, Linear orders

replace()

string, Further operations on strings

replace_all()

string, Further operations on strings

resize()

array, Arbitrary intervals as index sets, Useful methods of the class array, Enlarging arrays dynamically, Basic operations on lists
doubling strategy with array, Dynamic random variables (class dynamic_random_variate)

reverse Polish notation (see postfix notation)

reverse()

list, Further list modifying operations

reverse_items()

list, Further list modifying operations

reversing standard input (see tac)

RPN (see postfix notation)

rule (see LEDA rule)

S

Saarbrücken Central Station, Queues with an unbounded number of elements (class queue)

search tree, Balanced search trees

search()

list, Further list modifying operations

second()

two_tuple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

seed, The seed

sentinel, Two-dimensional arrays (class array2)

set, Sets (class set)

(see also set)
fractal, An example: Creating fractal sets
of integer numbers, Sets of integer numbers

set, Sets (class set)

set_directory(), Dealing with directories and files

set_error_handler(), Error handling

set_precision()

random_source, The bit mode

set_range()

random_source, The integer mode

set_seed()

random_source, The seed

set_to_current_date()

date, Dates (class date)

set_weight()

dynamic_random_variate, Dynamic random variables (class dynamic_random_variate)

signature, An example: Lists of string pairs in the computation of anagrams

size()

array, Useful methods of the class array
list, Appending and deleting of elements at the end of a list
queue, Queues with an unbounded number of elements (class queue)
set, Union, intersection, and difference of sets
stack, Stacks with an unbounded number of elements (class stack)

size_of_file(), Dealing with directories and files

slist, Singly linked lists (class slist)

sort()

array, Built-in sorting methods, The O-notation
list, Sorting lists

sorting

by minimum search, Defining arrays and access to elements, Time complexity, space complexity, and the O-notation
of unequal integer numbers, If one knows minimum and maximum in advance (class int_set)

sorting algorithm

stable, Sorting lists

sortseq, Queues with an unbounded number of elements (class queue)

space complexity, Space complexity

split()

list, Further list modifying operations

stack, Stacks, Stacks with an unbounded number of elements (class stack)

(see also stack)
top of, Stacks

std

namespace, The namespace leda

string, Strings (class string)

(see also string)
constructor, Handle types and handle-like types
empty string, Strings (class string)

string.h, The header files of LEDA

string_istream, What we did not cover

string_ostream, What we did not cover

subscript operator (see [])

succ()

list, Lists and the item-container-concept

symdiff()

set, Union, intersection, and difference of sets

T

tac, Basic operations on lists

tail()

list, Appending and deleting of elements at the end of a list
string, Further operations on strings

third()

three_tuple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

three_tuple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

tic-tac-toe, Exercises

time

amortized, Amortized analysis
constant, The O-notation
expected, The O-notation
linear, The O-notation
logarithmic, The O-notation

time complexity, Time complexity

time-space-tradeoff, Space complexity

top

of queue, Queues

top of stack, Stacks

top()

queue, Queues with an unbounded number of elements (class queue)
stack, Stacks with an unbounded number of elements (class stack)

TORWAT algorithm, An example: Creating fractal sets

tradeoff

time vs. space, Space complexity

transitivity, Linear orders

Traveller, Queues with an unbounded number of elements (class queue)

tree_collection, What we did not cover

triple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

(see also three_tuple)

try-catch, Error handling

two_tuple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

type

compound type, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)
dependent item type , Comparisons of LEDA objects
handle type, Handle types and handle-like types
handle-like, Handle types and handle-like types
independent item type, Comparisons of LEDA objects
item-based structured, Lists and the item-container-concept
linearly ordered, An example: Lists of string pairs in the computation of anagrams, Linear orders
non-item-based, Simple-structured types and their copy concept
non-primitive (see structured)
primitive, Simple-structured types and their copy concept
simple-structured, Simple-structured types and their copy concept
structured, Simple-structured types and their copy concept

type and copy concept, Copying of objects of an item-based type

type parameter, Defining arrays and access to elements, User-defined type parameters

U

unification problem, Sorting lists

and sets, Inserting elements and membership test

union

of sets, Union, intersection, and difference of sets

unique()

array, Useful methods of the class array
list, Sorting lists

used_time(), Some useful functions

using declaration, The namespace leda

using directive, The namespace leda

V

variation

creating by permuting a list, An application: creating variations

VCVARS32.BAT, Setting the environment variables for Visual C++

vector (see array)

Visual C++, Setting the environment variables for Visual C++

Visual Studio, The MS-Windows world

W

weight

of a random variable, Static random variables (class random_variate)


Bibliography