数值算法/人工智能

开发平台：
MultiPlatform

Implement.tex：源码内容
							
chapter{Implementations}
label{Implementations}
section{List of data structures}
label{List of data structures}
This section lists the data structures for dictionaries, dictionary
arrays, priority queues, and geometric data types currently contained in LEDA. 
For each of the data structures its name and type, the list of LEDA data types 
it can implement, and a literature reference are given.
Before using a data structures $xyz$ the corresponding header file
<LEDA/impl/$xyz$.h> has to be included (cf. section ref{Specifications} for an example).
subsection{Dictionaries}
label{Implementations Dictionaries}
begin{tabular}{llll}
$ab_tree$    &a-b tree     &dictionary, d_array, {bf sortseq}&cite{BC72}\
$avl_tree$   &AVL tree     &dictionary, d_array   &cite{AVL62}\
$bb_tree$    &BB[$alpha$] tree&dictionary, d_array, sortseq&cite{BM80}\
$ch_hashing$ &hashing with chaining&dictionary, d_array&cite{M84}\
$dp_hashing$ &dyn. perf. hashing&{bf h_array}    &cite{DKMMRT88}, cite{We92}\
$pers_tree$  &persistent   tree&{bf p_dictionary}&cite{DSST89}\
$rb_tree$    &red-black tree&dictionary, d_array, sortseq&cite{GS78}\
$rs_tree$    &rand. search tree&{bf dictionary}, {bf d_array}, sortseq&cite{AS89}\
$skiplist$    &skip lists   &dictionary, d_array, sortseq&cite{Pu90}
end{tabular}
subsection{Priority Queues}
label{Implementations Priority Queues}
begin{tabular}{llll}
$f_heap$  &Fibonnacci heap    &{bf priority_queue} &cite{FT87}\
$p_heap$  &pairing heap       &priority_queue       &cite{SV87}\
$k_heap$  &k-nary heap        &priority_queue       &cite{M84}\
$m_heap$  &monotonic heap     &priority_queue       &cite{M84}\
$eb_tree$ &Emde-Boas tree     &priority_queue       &cite{EKZ77}, cite{We92}
end{tabular}
subsection{Geometry}
begin{tabular}{llll}
$range_tree$ &range tree     &{bf d2_dictionary}, {bf point_set}&cite{Wi85}, cite{Lu78}\
$seg_tree$   &segment tree         &{bf seg_set}      &cite{B79}, cite{Ed82}\
$ps_tree$    &priority search tree &---             &cite{MC81}\
$iv_tree$    &interval tree        &{bf interval_set} &cite{MC80}, cite{Ed82}\
$delaunay_tree$ &delaunay tree     &{bf point_set}    &cite{De92}
end{tabular}
newpage
section{User Implementations}
label{User Implementations}
In addition to the data structures listed in the previous section user-defined 
data structures can also be used as actual implementation parameters provided 
they fulfill certain requirements.
subsection{Dictionaries}
label{User Implementations Dictionaries}
Any class $dic_impl$ that provides the following operations can be used as 
actual implementation parameter for the $_dictionary<K,I,dic_impl>$ 
and the $_d_array<I,E,dic_impl>$ data types (cf. sections ref{Dictionaries} and ref{Dictionary Arrays}).
typedef ... dic_impl_item;
class dic_impl ${$
hspace*{.5cm}virtual int  cmp(GenPtr, GenPtr) const = 0;\
hspace*{.5cm}virtual int  int_type()hspace*{2.3cm}const = 0;\
hspace*{.5cm}virtual void clear_key(GenPtr&)hspace*{.35cm}const = 0;\
hspace*{.5cm}virtual void clear_inf(GenPtr&)hspace*{.45cm}const = 0;\
hspace*{.5cm}virtual void copy_key(GenPtr&)hspace*{.35cm}const = 0;\
hspace*{.5cm}virtual void copy_inf(GenPtr&)hspace*{.5cm}const = 0;
public:
hspace*{.5cm}dic_impl();\
hspace*{.5cm}dic_impl(const dic_impl&);\
hspace*{.5cm}virtual ~dic_impl();
hspace*{.5cm}dic_impl& operator=(const dic_impl&);
hspace*{.5cm}GenPtr key(dic_impl_item)  const;\
hspace*{.5cm}GenPtr inf(dic_impl_item)   const;
hspace*{.5cm}dic_impl_item insert(GenPtr,GenPtr);\
hspace*{.5cm}dic_impl_item lookup(GenPtr)  const;\
hspace*{.5cm}dic_impl_item first_item()hspace*{1cm}const;\
hspace*{.5cm}dic_impl_item next_item(dic_impl_item) const;
hspace*{.5cm}dic_impl_item item(void$*$ $p$) const ${$ return dic_impl_item($p$); $}$
hspace*{.5cm}void change_inf(dic_impl_item,GenPtr);\
hspace*{.5cm}void del_item(dic_impl_item);\
hspace*{.5cm}void del(GenPtr);\
hspace*{.5cm}void clear();
hspace*{.5cm}int size() const;\
$}$;
newpage
subsection{Priority Queues}
label{User Implementations Priority Queues}
Any class $prio_impl$ that provides the following operations can be used as 
actual implementation parameter for the $_priority_queue<K,I,prio_impl>$
data type (cf. section ref{Priority Queues}).
typedef ... prio_impl_item;
class prio_impl { 
hspace*{.5cm}virtual int  cmp(GenPtr, GenPtr) const = 0;\
hspace*{.5cm}virtual int  int_type()hspace*{2.3cm}const = 0;\
hspace*{.5cm}virtual void clear_key(GenPtr&)hspace*{.35cm}const = 0;\
hspace*{.5cm}virtual void clear_inf(GenPtr&)hspace*{.45cm}const = 0;\
hspace*{.5cm}virtual void copy_key(GenPtr&)hspace*{.35cm}const = 0;\
hspace*{.5cm}virtual void copy_inf(GenPtr&)hspace*{.5cm}const = 0;
public:
hspace*{.5cm}prio_impl();\
hspace*{.5cm}prio_impl(int);\
hspace*{.5cm}prio_impl(int,int);\
hspace*{.5cm}prio_impl(const prio_impl&);\
hspace*{.5cm}virtual ~prio_impl();
hspace*{.5cm}prio_impl& operator=(const prio_impl&);
hspace*{.5cm}prio_impl_item insert(GenPtr,GenPtr);\
hspace*{.5cm}prio_impl_item find_min()  const;\
hspace*{.5cm}prio_impl_item first_item() const;\
hspace*{.5cm}prio_impl_item next_item(prio_impl_item) const;
hspace*{.5cm}prio_impl_item item(void$*$ $p$) const ${$ return prio_impl_item(p); $}$
 
hspace*{.5cm}GenPtr key(prio_impl_item) const;\
hspace*{.5cm}GenPtr inf(prio_impl_item)  const;
hspace*{.5cm}void del_min();\
hspace*{.5cm}void del_item(prio_impl_item);\
hspace*{.5cm}void decrease_key(prio_impl_item,GenPtr);\
hspace*{.5cm}void change_inf(prio_impl_item,GenPtr);\
hspace*{.5cm}void clear();
  
hspace*{.5cm}int  size()  const;\
$}$;
newpage
subsection{Sorted Sequences}
label{User Implementations Sorted Sequences}
Any class $seq_impl$ that provides the following operations can be used as 
actual implementation parameter for the $_sortseq<K,I,seq_impl>$ data
type (cf. section ref{Sorted Sequences}).
typedef ... seq_impl_item;
class seq_impl  ${$
hspace*{.5cm}virtual int  cmp(GenPtr, GenPtr) const = 0;\
hspace*{.5cm}virtual int  int_type()hspace*{2.25cm}const = 0;\
hspace*{.5cm}virtual void clear_key(GenPtr&)hspace*{.3cm}const = 0;\
hspace*{.5cm}virtual void clear_inf(GenPtr&)hspace*{.4cm}const = 0;\
hspace*{.5cm}virtual void copy_key(GenPtr&)hspace*{.3cm}const = 0;\
hspace*{.5cm}virtual void copy_inf(GenPtr&)hspace*{.45cm}const = 0;
public:
hspace*{.5cm}seq_impl();\
hspace*{.5cm}seq_impl(const seq_impl&);\
hspace*{.5cm}virtual ~seq_impl();
hspace*{.5cm}seq_impl& operator=(const seq_impl&);\
hspace*{.5cm}seq_impl& conc(seq_impl&);
 
hspace*{.5cm}seq_impl_item insert(GenPtr,GenPtr);\
hspace*{.5cm}seq_impl_item insert_at_item(seq_impl_item,GenPtr,GenPtr);\
hspace*{.5cm}seq_impl_item lookup(GenPtr)hspace*{.9cm}const;\
hspace*{.5cm}seq_impl_item locate(GenPtr)hspace*{1.05cm}const;\
hspace*{.5cm}seq_impl_item locate_pred(GenPtr) const;\
hspace*{.5cm}seq_impl_item succ(seq_impl_item)hspace*{.25cm}const;\
hspace*{.5cm}seq_impl_item pred(seq_impl_item)hspace*{.05cm} const;\
hspace*{.5cm}seq_impl_item item(void$*$ $p$) const ${$ return seq_impl_item($p$); $}$
 
hspace*{.5cm}GenPtr key(seq_impl_item) const;\
hspace*{.5cm}GenPtr inf(seq_impl_item)  const;
 
hspace*{.5cm}void del(GenPtr);\ 
hspace*{.5cm}void del_item(seq_impl_item);\ 
hspace*{.5cm}void change_inf(seq_impl_item,GenPtr);\
hspace*{.5cm}void split_at_item(seq_impl_item,seq_impl&,seq_impl&);\
hspace*{.5cm}void reverse_items(seq_impl_item,seq_impl_item);\ 
hspace*{.5cm}void clear();
 
hspace*{.5cm}int  size()  const;\
$}$;

						