home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / ledar34.zip / leda-r-3_4_tar / LEDA-3.4 / CHANGES < prev    next >
Text File  |  1996-09-03  |  69KB  |  2,141 lines
  1. +==============================================================================+
  2. |                                           |
  3. |                               LEDA-R 3.4                                     |
  4. |                                                                              |
  5. |                           RESEARCH VERSION                                   |
  6. |                                                                              |
  7. +==============================================================================+
  8.  
  9.  
  10. -------------------------------------------------------------------------------
  11. GENERAL
  12. -------------------------------------------------------------------------------
  13.  
  14. IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT
  15.  
  16. Name of window library has changed  
  17.  
  18.       OLD name:  libWx  (-lWx)
  19.       NEW name:  libW   (-lW)
  20.  
  21. AND it now has to  appear in front of all other libraries 
  22.  
  23.      ... -lW -lP -lG -lL -lX11  ....
  24.  
  25.  
  26.  
  27. -------------------------------------------------------------------------------
  28. Print and Read
  29. -------------------------------------------------------------------------------
  30.  
  31. Functions "Print" and "Read"  are no longer used to implement
  32. user defined I/O routines. Now, the usual output and input stream 
  33. operators (operator<< and opertor>>) are used. For backward
  34. compatibility Print and Read functions will still work but 
  35. should be avoided. Missing I/O operators will be reported at
  36. compile time.
  37.  
  38.  
  39.  
  40. -------------------------------------------------------------------------------
  41. Linear Orders (compare)
  42. -------------------------------------------------------------------------------
  43.  
  44. There is no default implementation of "int compare(const T&, const T&)
  45. giving an error message at run time. Now <LEDA/param_types.h>
  46. only contains a template {\bf declaration} for compare. The effect is
  47. that missing compare functions will be reported by the linker. Now 
  48. the use of a compare functions (e.g. in a parameterized data type as
  49. in dictionary<key,inf>) and its definition can be located in different 
  50. source files (which was not possible in the previous version
  51. with many compilers).
  52.  
  53. Example:
  54.  
  55. #include <LEDA/list.h>
  56.  
  57. class pair {
  58.  
  59.  double  x;
  60.  double  y;
  61.  
  62. public:
  63.  
  64. pair(double a=0, double b=0) : x(a), y(b) {}
  65. pair(const pair& p) x(p.x), y(p.y) {}
  66.  
  67. friend istream& operator>>(istream& is, pair& p)
  68. { return is >> p.x >> p.y; }
  69.  
  70. friend ostream& operator<<(ostream& os, const pair& p)
  71. { return os << p.x << " " << p.y; }
  72.  
  73. friend int compare(const pair& p, const pair& q);
  74. };
  75.  
  76. main()
  77. { list<pair> L;
  78.   L.read("list of pairs: ");
  79.   L.sort();
  80.   L.print("sorted:\n",'\n');
  81.   return 0;
  82. }
  83.  
  84. int compare(const pair& p, const pair& q)
  85. {  if (p.x < q.x) return -1; 
  86.    if (p.x > q.x) return  1; 
  87.    if (p.y < q.y) return -1; 
  88.    if (p.y > q.y) return  1; 
  89.    return 0;  
  90. }
  91.  
  92.  
  93.  
  94.  
  95. -------------------------------------------------------------------------------
  96. New Compilers/Platforms   (lconfig)
  97. -------------------------------------------------------------------------------
  98.  
  99.   Win32 (NT, Win95) 
  100.  
  101.     - Borland C++
  102.     - Microsoft Viusal C++ 
  103.     - Watcom C++
  104.  
  105.   (please contact LEDA GmbH for DLL's)
  106.  
  107.  
  108.   LINUX: shared Libraries
  109.    
  110.  
  111. -------------------------------------------------------------------------------
  112. Documentation and manual tools
  113. -------------------------------------------------------------------------------
  114.  
  115.    please see section 1.12 of the LEDA manual
  116.  
  117. -------------------------------------------------------------------------------
  118. Memory Management
  119. -------------------------------------------------------------------------------
  120.  
  121.    encapsulated into class memory_manager
  122.    - multiple managers
  123.    - table size parameter
  124.  
  125.  
  126.  
  127. -------------------------------------------------------------------------------
  128. multi-threads
  129. -------------------------------------------------------------------------------
  130.  
  131.   Multithread safety is available for posix, cps package and solaris package.
  132.   To use the right package, please edit the file incl/LEDA/thread.h  
  133.  
  134. -------------------------------------------------------------------------------
  135. Graphs & Planar Maps
  136. -------------------------------------------------------------------------------
  137.  
  138.   G.move_edge(edge e, node v,  node w)
  139.   G.move_edge(edge e, edge e1, edge e2)
  140.   G.move_edge(edge e, edge e1, node w)
  141.  
  142.   Reversals and Faces
  143.  
  144.   G.make_map()
  145.  
  146.   G.reversal(e);
  147.   G.face_cycle_succ();
  148.   G.face_cycle_pred();
  149.  
  150.   G.compute_faces();
  151.   ...
  152.  
  153.   face_array, face_map
  154.  
  155.  
  156. See the section on graphs and related data types in the user manual 
  157. for more details. 
  158.  
  159.  
  160. -------------------------------------------------------------------------------
  161. Graph Algorithms
  162. -------------------------------------------------------------------------------
  163.  
  164.    MIN_COST_FLOW(G,lcap,ucap, cost,supply,flow)
  165.    MIN_COST_FLOW(G,cap, cost,supply,flow)
  166.    MIN_COST_MAX_FLOW(G,s,t,cap,cost,flow)
  167.  
  168.  
  169.  
  170. -------------------------------------------------------------------------------
  171. GEOMETRY
  172. -------------------------------------------------------------------------------
  173.  
  174.    all objects now both with floating point and exact rational arithmetic
  175.  
  176.  -  new types  
  177.      ray 
  178.      rat_ray
  179.      rat_circle
  180.      rat_line
  181.  
  182.  - name changes
  183.      x.vertical()    --> x.is_vertical()
  184.      x.horizontal()  --> x.is_horizontal()
  185.  
  186.      converting rational to floating point objects:
  187.  
  188.      x.topoint()   --> x.to_point()
  189.      x.tosegment() --> x.to_segment()
  190.      x.toline()    --> x.to_line()
  191.      x.tocircle()  --> x.to_circle()
  192.  
  193.  
  194.  - new transformations
  195.    x.reflect(p,q)
  196.    x.reflect(p)
  197.  
  198.  
  199.  - delaunay_tree removed 
  200.    replaced by "delaunay_triang", an efficient and robust data structure 
  201.    base on LEDA graphs and exact arithmetic (see section on advanced
  202.    data types for geometry and the delaunay_demo program on <LEDA>demo/geo
  203.  
  204.  
  205.  
  206.  - new algorithms (plane_alg.h)
  207.  
  208.    all algorithms for both float and rational objects 
  209.  
  210.    Balaban
  211.    Mulmuley
  212.    DELAUNAY_FLIPPING
  213.    VORONOI
  214.  
  215.  
  216.  
  217.  
  218. -------------------------------------------------------------------------------
  219. windows and graphics
  220. -------------------------------------------------------------------------------
  221.  
  222.    many bugs fixed
  223.    improved panels and menues
  224.    choice_items and buttons with bitmaps 
  225.    graphwin (experimental)
  226.  
  227.  
  228. -------------------------------------------------------------------------------
  229. New Demos
  230. -------------------------------------------------------------------------------
  231.  
  232.    in <LEDA>/prog/demo  and <LEDA>/demo/...
  233.  
  234.     segint_demo:   segment intersection
  235.     delaunay_demo: delaunay and voronoi diagrams
  236.     graphwin:      graphwin demo
  237.  
  238.  
  239.  
  240. +==============================================================================+
  241. |                                           |
  242. |                              LEDA-R 3.3.1                                    |
  243. |                                                                              |
  244. |                           RESEARCH VERSION                                   |
  245. |                                                                              |
  246. +==============================================================================+
  247.  
  248. - bug fix release
  249.   see file FIXES
  250.  
  251. - lconfig.bat now works with Windows NT and Windows 95 with compilers Watcom
  252.   10.5 (lconfig wcnt) and MSVC++ 4.0  (lconfig msvc).
  253.   The graphics part is also running under Windows!
  254.   see INSTALL.W32
  255.  
  256. - new tools (based on perl) for extracting and viewing the manual.  
  257.   see directory Manual
  258.   the old methods are still available (directory man)
  259.  
  260. +==============================================================================+
  261. |                              LEDA-R 3.3                                    |
  262. +==============================================================================+
  263. - new installation & configuration procedures for UNIX, dos, windows
  264.   (see INSTALL and INSTALL.dos ).
  265.  
  266. - new mechanism for avoiding name conflicts with other packages (STL), 
  267.   (experimental, see the INSTALL file ).
  268.  
  269. - shared libraries for Solaris with SunPro C++ and g++ 
  270.   (see the INSTALL file ).
  271.  
  272.  
  273. - const-ref parameters 
  274.    All parameterized data types now use const reference parameters 
  275.    for argument passing. This avoids unnecessary copy operations
  276.    which is particularly important when using non-simple type parameters.  
  277.  
  278.  
  279. - strings
  280.    string length explicityly stored in string_rep  (efficiency)
  281.    bug in string::operator[](int) fixed
  282.  
  283.  
  284. - hashing (h_array, _d_array<I,E,ch_hash>)
  285.    bugs in ch_hash fixed 
  286.    missing iteration statements added
  287.  
  288.  
  289. - set<T>
  290.    new operations for intersection, union, and  difference of sets
  291.  
  292.  
  293. - graphs
  294.  
  295.   The implementation of graphs has been rewritten. Now undirected graphs
  296.   again have ordered adjacency lists (as in previous versions of LEDA)
  297.   and you can specify where a new edge is to be inserted into the adjacency
  298.   lists of both the source and target node of the edge. 
  299.   Please read the new manual pages for graphs !
  300.  
  301. - planarity test 
  302.    PLANAR: now works for multi-graphs
  303.    PLANAR1: new and faster test based on PQ-Trees
  304.  
  305.  
  306. - planar_map
  307.    int M.number_of_faces()  new
  308.    int M.size(face f)       new
  309.  
  310.  
  311.  
  312. -Geometry
  313.  
  314.    bug in circle::intersection(line/segment) fixed
  315.    bug in line::perpendicular(point) fixed
  316.    bugs in DELAUNAY_TRIANG fixed
  317.    use member initializationa in segment_rep(point,point)
  318.    new data type  "rat_polygon"
  319.  
  320.    point/rat_point
  321.      side_of_circle(a,b,c,d)
  322.      incircle(a,b,c,d)
  323.      outcircle(a,b,c,d)
  324.      cocircular(a,b,c,d)
  325.  
  326.  
  327.  
  328. - windows, panels, and colors
  329.  
  330.   The window and panel types have been extended and (hopefully) improved.
  331.   Now panels and windows are essentially the same and you can include
  332.   panel items into your windows. A short description of the new features
  333.   can be found in "Changes.win" in this directory.
  334.  
  335.   Two of the changes that probably will cause problems with old code are
  336.  
  337.   + W.read_mouse(...) now returns the constants MOUSE_BUTTON(i) (i=1,2,3)
  338.     instead of 1,2,3 for the left/middle/right button
  339.  
  340.   + windows have to be opened explicitely by W.open(...) 
  341.  
  342.   Please read the new manual pages for windows !
  343.  
  344.  
  345.  
  346.  
  347. - Changes of global function and macro names
  348.  
  349.   internally used functions:
  350.  
  351.   Copy      --> leda_copy
  352.   Convert   --> leda_cast
  353.   Access    --> leda_access
  354.   Clear     --> leda_clear
  355.   Create    --> leda_create
  356.   Int_Type  --> leda_itype
  357.   Type_Name --> leda_tname
  358.  
  359.   reverse iteration:
  360.  
  361.   Forall(x,S)       --> forall_rev(x,S)
  362.   Forall_nodes(v,G) --> forall_rev_nodes(v,G)
  363.   Forall_edges(e,G) --> forall_rev_edges(e,G)
  364.   
  365.  
  366.  
  367.  
  368.  
  369.  
  370. +==============================================================================+
  371. |   LEDA-R 3.2.2                                                               |
  372. +==============================================================================+
  373.  
  374. Bugfix Release (see Fixes)
  375.  
  376.  
  377. +==============================================================================+
  378. |   LEDA-R 3.2.1                                                               |
  379. +==============================================================================+
  380.  
  381. Bugfix Release (see Fixes)
  382.  
  383.  
  384. +==============================================================================+
  385. |                                           |
  386. |                              LEDA-R 3.2                                      |
  387. |                          RESEARCH VERSION                                    |
  388. |                                                                              |
  389. +==============================================================================+
  390.  
  391. The new release is mainly a bug-fix release, however it also contains some new 
  392. algorithms for graphs and computational geometry. 
  393. See the "Fixes" file for the list of fixed bugs.
  394.  
  395.  
  396. ------------------------------------------------------------------------------
  397. 1. GENERAL CHANGES
  398. ------------------------------------------------------------------------------
  399.  
  400. SYSTEM DEPENDENT FLAGS
  401. <LEDA/basic.h> has been split into a number of smaller files
  402. The most important is <LEDA/system.h>. Here several flags are
  403. defined indicating particular features or limitations of
  404. compilers. Examples are
  405.  
  406.          __BUILTIN_BOOL__
  407.          __NEW_SCOPE_RULES__
  408.          __TEMPLATE_FUNCTIONS__
  409.          __EXPLICIT_DESTRUCTION__
  410.  
  411. The current settings in <LEDA/system.h> have been tested with 
  412. g++-2.5.8, g++-2.6.3, g++-2.7.0, AT&T cfront 2.0.3, sunpro c++ 4.0.1, 
  413. lucid c++ 3.1 , watcom 10.0, zortech 3.1, borland 4.5
  414.  
  415. IF YOU ARE USING A DIFFERENT COMPILER OR VERSION YOU MAY HAVE TO EDIT THIS FILE.
  416.  
  417.  
  418.  
  419. MACROS
  420. Macros  "forever" and "loop"  are no longer defined
  421.  
  422.  
  423. ITERATION
  424. The "forall(x,S)" macro can now be used to iterate over the elements
  425. of arrays and d_arrays.
  426.  
  427.  
  428.  
  429. PARAMETERIZED DATA TYPES
  430. The implementation of parameterized data types (<LEDA/param_types.h>) has 
  431. been rewritten to make it more readable and stable. It now should work with
  432. all c++ compilers supporting function templates. In particular the problems
  433. on 64 bit architectures and the one-word bug have been fixed.
  434. There is no special treatement of handle types anymore.
  435.  
  436.  
  437.  
  438. ------------------------------------------------------------------------------
  439. 2. Data Types
  440. ------------------------------------------------------------------------------
  441.  
  442. string
  443.              the printf-like string(const char*,...) constructor has been
  444.              rewritten (should work now with all varargs - implementations)
  445.  
  446.  
  447. vector/matrix  
  448.              Read & Print with dimensions
  449.  
  450.  
  451. integer
  452.              speed of addition/subtraction improved on SPARC
  453.  
  454.  
  455. list
  456.              the split operation now has an additional parameter "dir"
  457.              indicating whether the splitting should happen before or after
  458.              the provided item
  459.  
  460.  
  461. priority queues
  462.  
  463.              new data structure: r_heap (redistributive heap)
  464.  
  465.  
  466. d_array 
  467.              delete operation:  d_array<I,E>::undefine(I i)
  468.  
  469.  
  470.  
  471. planar_map
  472.              new iteration macro:
  473.  
  474.              forall_adj_faces(f,v) 
  475.              { "v is successively assigned all faces adjacent to node v" }
  476.  
  477.  
  478. random_planar_graph 
  479.  
  480.              generates connected graphs now
  481.  
  482.  
  483. New Graph Algorithms
  484.  
  485.              MAX_WEIGHT_MATCHING
  486.              MIN_CUT
  487.  
  488.  
  489. ------------------------------------------------------------------------------
  490. 3. GEOMETRY
  491. ------------------------------------------------------------------------------
  492.  
  493. New Operations on (rat_)points and (rat_)segments
  494.  
  495.              point::rot90
  496.              segment::rot90
  497.              rat_point::rot90
  498.              rat_segment::rot90
  499.  
  500. geometric primitives (evaluated exactly for rat_ ...):
  501.  
  502.              orientation(point,point,point)
  503.              left_turn(point,point,point)
  504.              right_turn(point,point,point)
  505.              collinear(point,point,point)
  506.              incircle(point,point,point,point)
  507.              cmp_slopes(segment,segment)
  508.  
  509.  
  510.              
  511. Algorithms
  512.  
  513. void TRIANGULATE_POINTS(list<point> L, GRAPH<point,edge>& G);
  514.  
  515.  
  516. void DELAUNAY_TRIANGULATION(const list<point>& L, GRAPH<point,edge>& T);
  517.  
  518. void DELAUNAY_TRIANGULATION(const list<point>& L, graph& T, 
  519.                                                   node_array<point>& pos,
  520.                                                   edge_array<edge>&  rev);
  521.  
  522. void DELAUNAY_TRIANGULATION(const list<point>& L, planar_map& T, 
  523.                                                   node_array<point>& pos);
  524.  
  525.  
  526.  
  527. SWEEP_SEGMENTS
  528.  
  529. The SWEEP_SEGMENTS function has been completely rewritten. It is 
  530. based on the new geometric primitives mentioned above which makes
  531. the code more readable, robust and efficient. This also fixes bugs
  532. in the SEGMENT_INTERSECTION function and the polygon::intersection
  533. method (see also <LEDA>/web/sweep).
  534.  
  535.  
  536.  
  537.  
  538.  
  539. +==============================================================================+
  540. |                                           |
  541. |                             VERSION 3.1                                      |
  542. |                                                                              |
  543. +==============================================================================+
  544.  
  545. Many changes were made to make LEDA work with new compilers (g++-2.6.3,
  546. Lucid \CC, Watcom \CC Sunpro \CC, ...) and on more platforms (Silicon 
  547. Graphics, IBM, HP, Solaris-2.3, Linux, ...). All reported bugs of version
  548. 3.0 we were able to find and understand have been fixed (see LEDA/Fixes
  549. for a list). Several new data types and algorithms (especially in the graph 
  550. and window section) have been included.
  551.  
  552. ------------------------------------------------------------------------------
  553.        Changes that might cause unexpected behavior or problems
  554. ------------------------------------------------------------------------------
  555. The following list is not complete, please report all problems to 
  556. leda@mpi-sb.mpg.de
  557.  
  558.  
  559. 1. compare, Print, Read, and Hash  
  560.  
  561.    + there are no predefined versions for pointer types anymore
  562.      so you will receive a run time error "compare undefined"
  563.      when, for example, sorting a list of pointers without having
  564.      defined a compare function for the pointer type.
  565.  
  566.    + in general, if you use one of these functions before declaring it
  567.      you will receive an error message. Uses can be hidden in instantiations
  568.      of parameterized types. Example:
  569.  
  570.      list<T>  D;  // here the default error template compare is instantiated.
  571.                   // since list has an operation (sort) that uses compare
  572.   
  573.      int compare(const T&, const T&); // error : compare multiply defined
  574.      dictionary<T,int> D; 
  575.  
  576.  
  577.  
  578.    + a possible bug in g++ :
  579.      if you declare a compare function static and define it later
  580.      in the file, g++ will not use it but will use the default
  581.      template version from <LEDA/param_types.h>.
  582.  
  583.      Example:
  584.  
  585.                  class pair {
  586.                  ...
  587.                  };
  588.  
  589.                  // declaration
  590.                  static int compare(const pair&, const pair&);
  591.  
  592.                  // use
  593.                  dictionary<pair,int> D;
  594.  
  595.                  
  596.                  // definition
  597.                  int compare(const pair& p, const pair& q) {  ... }
  598.  
  599.  
  600.      Using inline compare functions seems to be a work-around for this problem
  601.      (maybe extern works also ?).
  602.  
  603.  
  604. 2. ugraph
  605.  
  606.    Some of the functionality of ugraphs available in previous versions, e.g., 
  607.    a linear ordering of all adjacent edges, is not supported in the
  608.    current version.
  609.  
  610.  
  611. 3. PLANAR(graph&, bool embed=false)
  612.  
  613.    PLANAR has a different behavior: an embedding is constructed only
  614.    if the optional boolean flag embed is set to true.
  615.  
  616.  
  617. 4. random
  618.  
  619.    There is no LEDA random function any more ( they caused a lot of problems 
  620.    with existing random functions on many systems). Now LEDA contains
  621.    a new data type "random source" for the generation of different
  622.    types of random numbers.
  623.  
  624.  
  625.  
  626. 5. The newly introduced numerical types bigfloat and real might cause problems 
  627.    on several systems. If so, please report ...  You can ignore all compiler 
  628.    error messages if you do not intend to use these types.
  629.  
  630.  
  631.  
  632. ------------------------------------------------------------------------------
  633.                  Fixed Bugs (see also LEDA/Fixes)
  634. ------------------------------------------------------------------------------
  635. - array::operator=  fixed
  636. - graph::read and graph::write
  637. - node_set edge_set rewritten
  638. - int_set: hard coded word size replaced by sizeof-call
  639. - list<T>::sort(cmp_func), ... for types T with sizeof(T) > sizeof(void*)
  640. - array<T>::sort(cmp_func), ... for types T with sizeof(T) > sizeof(void*)
  641. - bug in vector::operator=(const vector&) fixed
  642. - bug in rs_tree (set<T>) copy constructor fixed
  643. - LEDA_MEMORY: operator new & delete now use the size argument 
  644. - array copy constructor fixed
  645. - memory leak in list::assign() fixed
  646. - polygon CONVEX_HULL(list<point>)  new algorithm (Graham's Scan)
  647. - bugs in segment::intersection() and line::intersection() fixed
  648. - bug in binary heaps (negative integer keys) fixed
  649. - UGRAPH::assign(node/edge,...) fixed
  650. - bug in list<node> graph::adj_nodes() (undirected graphs) fixed 
  651. - Iteration (forall_defined) for h_arrays 
  652. - some problems in _leda_panel.c fixed (slider items, buttons, ...)
  653. - multi-definition problem with read_mouse(window, ...) and g++ fixed
  654. - skiplist copy constructor
  655. - memory leaks in leda panels
  656. - nested forall-loops
  657. - string::read now can read strings of arbitrary length
  658. - made dlist::bucket_sort stable 
  659. - memory bug in dp_hash (dynamic perfect hashing) fixed
  660. - k_heap::del_item fixed
  661. - made rs_tree::change_inf (dictionary) clear old and copy new information
  662. - dlist::search (replaced != by call of virtual cmp function)
  663. - fixed bug in queue::append (replaced Convert by Copy)
  664. - bugs in MAX_WEIGHT_BIPARTITE_MATCHING fixed (by M. Paul)
  665. - prio.h: added missing ostream argument cout to Print calls
  666. - stack::push(x)    replaced Convert(x) by Copy(x)
  667. - segment::angle()  now returns zero for segments of length zero
  668. - memory leak in draw_(filled_)polygon fixed
  669. - bug in ab_tree::clear() fixed (forgot to set counter to zero)
  670. - made dlist update operations protected
  671. - missing operation ugraph::read(istream&) inserted
  672.  
  673.  
  674.  
  675. --------------------------------------------------------------------------------
  676. NEW FEATURES
  677. --------------------------------------------------------------------------------
  678.  
  679. Manual Pages
  680.  
  681.   All manual pages have been incorporated into the corresponding
  682.   header files. There are tools (see LEDA/man/README) to extract and
  683.   typeset the new user manual from these files. A postscript and
  684.   LaTeX version of the manual is available on the ftp server.
  685.  
  686. Parameterized Data Types
  687.  
  688.   The  LEDA_TYPE_PARAMERER macro that had to be called for type
  689.   arguments in parameterized data types when using the \gg compiler
  690.   is not needed anymore for \gg versions $>=$ 2.6.3.
  691.  
  692.  
  693. Linear Orders, I/O, and Hashing
  694.  
  695.   $compare$, $Hash$, $Read$ and $Print$ functions only have to be 
  696.   defined for type parameters of a parameterized data type if they are 
  697.   actually used by operations of the data type. If one of these function 
  698.   is called and has not been defined explicitely, a default version giving
  699.   an error message is instantiated from a function template.
  700.   Except for the built-in types and some basic LEDA types ($string$ and
  701.   $point$) there are no predefined versions of these functions any more.
  702.   In particular, they are not predefined for arbitrary pointer types. 
  703.   You will notice the effect of this change, for instance, when calling 
  704.   the sort operation on a list of pointers $list<T*>$ for
  705.   without a definition of a compare function for $T*$.  Previous LEDA 
  706.   releases sorted the list by increasing addresses of the pointers in 
  707.   this case. In version~3.1 the program will exit with the exception
  708.   ``no compare function defined for $T*$". Operations based on functions
  709.   $Hash$, $Read$, or $Print$ show a similar behavior.
  710.  
  711.  
  712.  
  713. compare, ord, and hash function arguments 
  714.  
  715.   used e.g. in list::sort, array::sort, list::bucket_sort, ...
  716.   have to use const reference parameters, i.e., have to be of type
  717.   int cmp(const T&, const T&) 
  718.   int ord(const T&)
  719.  
  720.  
  721.  
  722. Nested Forall Loops
  723.  
  724.    The limitation of previous versions that {\bf forall}-loops (e.g.
  725.    on lists) could not be nested is no longer valid.
  726.  
  727.  
  728. Graphs
  729.  
  730. The distinction in directed and undirected graphs is not as strict as
  731. in previous versions. Data type $graph$ represents both directed and
  732. undirected graphs. Directed and undirected graphs only differ in the
  733. definition of adjacent edges or nodes. Now, two lists of edges are 
  734. associated with every node $v$: the list
  735. $out_edges(v) = \{\ e \in E\ | source(e) = v\ \}$ of edges starting in $v$,
  736. and the list $in_edges(v) = \{\ e \in E\ | target(e) = v\ \}$ of
  737. edges ending in $v$. 
  738. A graph is either {\em directed} or {\em undirected}.
  739. In a directed graph an edge is adjacent to its source and in an undirected
  740. graph it is adjacent to its source and target. In a directed graph a node $w$
  741. is adjacent to a node $v$ if there is an edge $(v,w) \in E$; in an undirected
  742. graph $w$ is adjacent to $v$ if there is an edge $(v,w)$ or $(w,v)$ in the
  743. graph.  There are iteration macros allowing to iterate over the list of
  744. starting, ending or adjacent edges (cf. \ref{Graphs} for details).
  745.  
  746.  
  747.  
  748. New Data Types
  749.  
  750. The old priority queue type $priority_queue<K,I>$ caused
  751. a lot of confusion because of the non-standard semantics of the type 
  752. parameters $K$ and $I$ (the meaning of {\em key} and {\em information} 
  753. was exchanged compared to most text book presentations of priority queues).
  754. To eliminate this confusion we introduced a new priority queue type
  755. $p_queue<P,I>$. Now $P$ is called the priority type of the queue.
  756.  
  757. The basic library has been extended by several new numerical data types
  758. including an arbitrary length integer type ($integer$), a type of
  759. rational numbers ($rational$), and two filter types $ffloat$ and
  760. $real$ especially useful for floating point computations
  761. in geometric applications.
  762.  
  763. Note that the temporarily (LEDA-3.1c) introduced data types $node_data$,
  764. $node_stack$, $node_queue$ are no longer available. Please use $node_map$, 
  765. $edge_map$, $stack<node>$ and $queue<node>$ instead.
  766.  
  767. A list of the new data types:
  768.  
  769. priority queues        p_queue<P,I>
  770. singly linked lists    slist<T>
  771. big integers           integer
  772. rational numbers       rational
  773. floating point filter  ffloat
  774. real numbers           real
  775. rational point         rat_point
  776. rational segments      rat_segment
  777. maps                   map<I,E>
  778. node and edge maps     node/edge_map<T>
  779. node lists             node_list
  780. bounded node p_queues  b_node_pq<n>
  781.  
  782.  
  783.  
  784. Graph Generators and Algorithms
  785.  
  786. LEDA now offers more generators for different types of graphs (see 
  787. \ref{Graph Generators} for a complete list).
  788. The planarity test $PLANAR$ has been re-implemented and
  789. now has a boolean flag parameter $embed$. An embedding of the graph
  790. is computed only if $embed = true$. A second variant of $PLANAR$
  791. computes a Kuratowsky-subgraph in the case of non-planarity.
  792. A new graph algorithm is $MIN_COST_MAX_FLOW$ computing
  793. a maximal flow with minimal cost. 
  794.  
  795.  
  796.  
  797. Windows and Panels
  798.  
  799. The window and panel data types  now are base on a plain X11 implementation.
  800. New features include
  801. -- opening more than one window or panel
  802. -- positioning, displaying, and closing of panels and windows
  803. -- changing the label of windows and panels
  804. -- 16 predefined colors
  805. -- accessing colors from the X11 data base by name
  806. -- drawing arcs, arc edges, and arc arrows
  807. -- changing the default fonts, 
  808. -- reading and handling X11 events
  809. -- a simple graph editor (cf. <LEDA/graph_edit.h>)
  810.  
  811.  
  812.  
  813.  
  814.  
  815.  
  816.  
  817.  
  818. +==============================================================================+
  819. |                                           |
  820. |                             VERSION 3.0                                      |
  821. |                                                                              |
  822. +==============================================================================+
  823.  
  824. LEDA-3.0    (template version)
  825.  
  826. LEDA-N-3.0  (non-template version)
  827.  
  828.  
  829. ------------------------------------------------------------------------------
  830. TEMPLATES & PARAMETERIZED DATA TYPES   (cf. manual, section 1.1)
  831. ------------------------------------------------------------------------------
  832.   
  833. Starting with version 3.0 LEDA is using C++ templates for parameterized 
  834. data types (e.g. dictionary<string,int>). This makes declare macros 
  835. (e.g. declare2(dictionary,string,int)) and the "LEDA_TYPE_PARAMETER" macro 
  836. obsolete. Any built-in, pointer, item, or user-defined class type can be used 
  837. as actual type parameter for a parameterized data type. Class types however 
  838. have to provide the following operations:
  839.  
  840.   a constructor taking no arguments   T::T()
  841.   a copy constructor                  T::T(const T&)
  842.   a Read function                     void Read(T&, istream&)
  843.   a Print function                    void Print(const T&, ostream&)
  844.  
  845. A compare function  "int compare(const T&, const T&)" (cf. section 1.4 of the 
  846. user manual) has to be defined if required by the data type.
  847.  
  848. Currently, the template version can be used with cfront 3.0.1 and g++-2.3.1.
  849. Note however that there are still many bugs in g++-2.3 (most of them should
  850. be fixed in the next version). In particular, there are problems with function
  851. templates that still make the use of the "LEDA_TYPE_PARAMETER" macro necessary 
  852. for non-pointer type parameters.
  853.  
  854. For compilers not supporting templates there is a non-template variant "LEDA-N"
  855. available whose parameterized data types are based on declare-macros as in
  856. the previous LEDA versions.
  857.  
  858. See "prog/basic/param.c" for an example.
  859.  
  860.  
  861. ------------------------------------------------------------------------------
  862.  IMPLEMENTATION PARAMETERS         (cf. user manual, section 1.2)
  863. ------------------------------------------------------------------------------
  864.    
  865. For many of the parameterized data types (dictionary,priority queue,d_array,
  866. sortseq) there are variants taking an additional data structure parameter 
  867. for choosing a particular implementation, e.g. 
  868.  
  869. _dictionary<string,int,skiplist>  D 
  870.  
  871. creates a dictionary D with key type string and information type int 
  872. implemented by the skiplist data structure.
  873.  
  874. Any such type _XYZ<T1,...,Tk,impl> is derived from the corresponding
  875. "normal" parameterized type XYZ<T1,...,Tk>, i.e., an instance of type 
  876. _XYZ<T1,...,Tk,impl> can be passed as argument to functions with a 
  877. formal parameter of type XYZ<T1,...,Tk>&. This provides a mechanism for
  878. choosing implementations of data types in pre-compiled algorithms.
  879.  
  880. See "prog/graph/dijkstra.c" for an example.
  881.  
  882.  
  883.  
  884. Language Limitations: 
  885. --------------------
  886. Templates cannot be overloaded (why ?), so we have to use different names. 
  887. The names of data types with implementation parameters start with an 
  888. underscore:
  889.  
  890. _dictionary<K,I,impl>
  891. _priority_queue<K,I,impl>
  892. _d_array<I,E,impl>
  893. _sortseq<K,I,impl>
  894.  
  895.  
  896. Compiler Limitations: 
  897. --------------------
  898. Cfront 3.0.1 does not allow template arguments to be used as base classes.
  899. Therefore, we still have to use the macros from <generic.h> here:
  900.  
  901. declare3(_dictionary,K,I,impl)        ---->    _dictionary(K,I,impl)
  902. declare3(_priority_queue,K,I,impl)    ---->    _priority_queue(K,I,impl)
  903. declare3(_sortseq,K,I,impl)           ---->    _sortseq(K,I,impl)
  904. declare3(_d_array,I,E,impl)           ---->    _d_array(K,I,impl)
  905.  
  906.  
  907.  
  908. Example Programs:
  909. -----------------
  910. _dictionary<K,I,impl>              prog/dict/dic_test.c
  911. _priority_queue<K,I,impl>          prog/graph/dijkstra.c
  912. _sortseq<K,I,impl>                 prog/plane/seg_int.c
  913. _d_array<K,I,impl>                 prog/dict/d_array_test.c
  914.  
  915.  
  916. A data structure "impl" for a data type has to provide a certain 
  917. set of operations and to use certain virtual functions for type 
  918. dependent operations (cf. manual, section 9). 
  919.  
  920. Sample header files for implementations of dictionaries, priority_queues, 
  921. and sorted sequences can be found in <LEDA/impl/dic_impl.h>,
  922. <LEDA/impl/prio_impl.h>, <LEDA/impl/seq_impl.h>.
  923.  
  924.  
  925.  
  926. ------------------------------------------------------------------------------
  927. LINEAR ODERS
  928. ------------------------------------------------------------------------------
  929.  
  930. There is a new mechanism for deriving differently ordered type variants from
  931. a data type. 
  932.  
  933. The macro call
  934.  
  935.          DEFINE_LINEAR_ORDER(T,cmp,T1)  
  936.  
  937. introduces a new type T1 equivalent to type T with the linear order
  938. defined by the compare function "cmp".
  939.  
  940.  
  941. Examples:   prog/basic/order.c
  942.             prog/plane/order.c
  943.   
  944.  
  945.  
  946. ------------------------------------------------------------------------------
  947.  GENERAL
  948. ------------------------------------------------------------------------------
  949.  
  950. "forall_xyz_items" no longer supported, use "forall_items"  
  951.  
  952.  
  953. ------------------------------------------------------------------------------
  954. Efficiency
  955. ------------------------------------------------------------------------------
  956. The efficiency of many data types and algorithms has been improved.
  957.  
  958. In particular:
  959.  
  960. sorting  (array::sort, list::sort)
  961.  
  962. dictionaries, sets, d_arrays, sorted sequences 
  963. (now implemented by randomized search trees)
  964.  
  965.  
  966. network algorithms:
  967.  
  968. matching, minimum spanning tree  (performance improved by a start heuristic)
  969.  
  970.  
  971. Macro LEDA_CHECKING_OFF: 
  972. turns off range checking for arrays and  node/edge_arrays
  973. (has to be defined before including LEDA header files)
  974.  
  975.  
  976. ------------------------------------------------------------------------------
  977.  Graphs
  978. ------------------------------------------------------------------------------
  979.  
  980. new operations:
  981.  
  982. node G.first_node()         
  983. node G.last_node()
  984. node G.succ_node(node)
  985. node G.pred_node(node)
  986.  
  987. edge G.first_edge()
  988. edge G.last_edge()
  989. edge G.succ_edge(edge)
  990. edge G.pred_edge(edge)
  991.  
  992.  
  993. void G.make_undirected()  inserts all edges (v,w) into the adjacency list of w
  994.                           i.e. both outgoing and incoming edges are traversed
  995.                           by forall_adj_edges
  996.  
  997. void G.make_directed()    removes all incoming edges from the adjacency lists
  998.               
  999.  
  1000.  
  1001. void graph_edit(window& W, GRAPH<point,int>& G) 
  1002.  
  1003.  
  1004. cmdline_graph(graph& G, int argc, char** argv)
  1005.  
  1006.         builds a graph according to the command line arguments 
  1007.      
  1008.         command line:  <prog>        ---> test_graph()
  1009.                        <prog> n      ---> complete graph with n nodes
  1010.                        <prog> n m    ---> random graph with n nodes and m edges
  1011.                        <prog> file   ---> read graph from "file"
  1012.      
  1013.  
  1014. --------------------------------------------------------------------------------
  1015. planar_map (PLANAR_MAP)
  1016. --------------------------------------------------------------------------------
  1017.  
  1018.  
  1019. edge  P.split_edge(edge e)
  1020. edge  P.split_edge(edge e, vtype x)
  1021.  
  1022.       splits edge e and its reversal by introducing a new node u
  1023.  
  1024.  
  1025. node  p.new_node(face f)
  1026. node  p.new_node(face f, vtype x)
  1027.  
  1028.       splits face f into triangles by introducing a new node u
  1029.       and connecting it to all nodes of f
  1030.  
  1031.  
  1032.  
  1033. node  p.new_node(list<edge> el)
  1034. node  p.new_node(list<edge> el, vtype x)
  1035.  
  1036.       splits face bounded by the edges in el by introducing a new node u
  1037.       and connecting it to all source nodes of edges in el
  1038.  
  1039.  
  1040.  
  1041. ------------------------------------------------------------------------------
  1042.  node_pq<I>
  1043. ------------------------------------------------------------------------------
  1044.  
  1045. I    PQ.inf(node v)               returns information of node v
  1046.  
  1047. bool PQ.member(node v)            true if v in PQ false otherwise
  1048.  
  1049.  
  1050. ------------------------------------------------------------------------------
  1051.  STRING
  1052. ------------------------------------------------------------------------------
  1053.  
  1054. additional constructor    
  1055.  
  1056. string::string(char c)        creates the one-character string "c"
  1057.  
  1058.  
  1059.  
  1060. ------------------------------------------------------------------------------
  1061.  MEMORY
  1062. ------------------------------------------------------------------------------
  1063.  
  1064. LEDA_MEMORY_WITH_CHECK
  1065.  
  1066. A debug version of the LEDA_MEMORY macro (cf. manual, section 7.3), gives
  1067. an error message if the same pointer is deleted twice (slow!).
  1068.  
  1069.  
  1070. ------------------------------------------------------------------------------
  1071. Directory Structure
  1072. ------------------------------------------------------------------------------
  1073.  
  1074. a) All implementation header files have been moved to a new header subdirectory
  1075.    <LEDA/impl>.
  1076.  
  1077. b) There is a new directory "util" containing some utility programs. Currently 
  1078.    it contains a ksh variant of the Lman shell script, a program for shortening 
  1079.    all file names to 15 characters (required by SCO UNIX/XENIX) and some DOS 
  1080.    installation batch files.
  1081.  
  1082.  
  1083.  
  1084.  
  1085. +==============================================================================+
  1086. |                                           |
  1087. |                           VERSION 2.2.2                        |
  1088. |                                                                              |
  1089. +==============================================================================+
  1090.  
  1091. minor changes for use with g++-2.2 and some bugs fixed 
  1092.  
  1093.  
  1094. +==============================================================================+
  1095. |                                           |
  1096. |                           VERSION 2.2.1                        |
  1097. |                                                                              |
  1098. +==============================================================================+
  1099.  
  1100. Some changes made for use with g++-2.1 and libg++-2.0
  1101.  
  1102. Some bugs fixed : 
  1103.  
  1104. string::operator+ 
  1105. matrix::operator=
  1106. matrix::triang 
  1107. GRAPH::assign
  1108.  ...
  1109.  
  1110.  
  1111. +==============================================================================+
  1112. |                                           |
  1113. |                           VERSION 2.2.0                        |
  1114. |                                                                              |
  1115. +==============================================================================+
  1116.  
  1117.  
  1118. --------------------------------------------------------------------------------
  1119. Parameterized data types
  1120. --------------------------------------------------------------------------------
  1121.  
  1122. Now, arbitrary data types (not only pointer and simple types) can be used as 
  1123. type parameters. This makes data type "real" obsolete (use "double" or "float" 
  1124. instead), "real" is no longer included in the header file <LEDA/basic.h> but 
  1125. is still available in <LEDA/real.h>.
  1126.  
  1127.  
  1128. Rules for type parameters:
  1129. --------------------------
  1130.  
  1131. 1. Build-in types (char,int,long,float,double), pointer types, and LEDA 
  1132.    simple types can be used as type parameters.
  1133.  
  1134. 2. A class type T can be used as type parameter under the following conditions:
  1135.  
  1136.  
  1137.    a) The following operations and functions must be defined for T
  1138.  
  1139.       a constructor without arguments:  T::T()
  1140.       an input operator:                istream& operator>>(istream&,T&)
  1141.       an output operator:               ostream& operator<<(ostream&,const T&)
  1142.       a compare function:               int compare(const T&, const T&)
  1143.  
  1144.    b) The macro call 
  1145.  
  1146.                       LEDA_TYPE_PARAMETER(T) 
  1147.  
  1148.       must appear before the first use of T as actual type parameter.
  1149.  
  1150.  
  1151.    c) If defined, destructor and copy constructor are used for copying and 
  1152.       destroying objects.
  1153.  
  1154.  
  1155.  
  1156. See "<LEDA>/prog/basic/param.c" for an example and for more informations and 
  1157. implementaion details: "S. N\"aher: Parameterized data types in LEDA", in 
  1158. preparation.
  1159.  
  1160.  
  1161.  
  1162. --------------------------------------------------------------------------------
  1163. simple data types 
  1164. --------------------------------------------------------------------------------
  1165.  
  1166. Data type "real" is no longer supported (it is still available in <LEDA/real.h>)
  1167. All parameters of type real have been replaced by double parameters. When
  1168. reading the user manual take "real" as a synonym for "double".
  1169.  
  1170.  
  1171.  
  1172. --------------------------------------------------------------------------------
  1173. graph
  1174. --------------------------------------------------------------------------------
  1175.  
  1176. read & write overloaded for streams
  1177.  
  1178. int  G.read(istream I)     reads compressed representation of G from I
  1179.                            returns  ... (see manual)
  1180.  
  1181. int  G.read(string file)   reads compressed representation of G from file
  1182.                            returns  ... (see manual)
  1183.  
  1184. void G.write(ostream O)    writes compressed representation of G to O
  1185.  
  1186. void G.write(string file)  writes compressed representation of G to file
  1187.  
  1188.  
  1189.  
  1190.  
  1191. --------------------------------------------------------------------------------
  1192. graph algorithms
  1193. --------------------------------------------------------------------------------
  1194.  
  1195. bool PLANAR(graph& G)   
  1196.  
  1197.                  Planarity test: returns true iff $G$ is planar.
  1198.                  If G is planar, it is transformed into a planar map by 
  1199.                  rearranging the adjaceny lists
  1200.                  precondition:  G is biconnected
  1201.  
  1202.  
  1203.  
  1204. int BICONNECTED_COMPONENTS(ugraph& G, edge_array(int)& compnum)
  1205.  
  1206.                  computes the biconnected components of the undirected graph G
  1207.                  returns the number of biconnected components and in 
  1208.                  edge_array(int) compnum for each edge an integer with
  1209.                  compnum[x]=compnum[y] iff edge x and y belong to the same 
  1210.                  biconnected component and 0 <= compnum[e]<=m-1 for all edges e
  1211.  
  1212.  
  1213.  
  1214. --------------------------------------------------------------------------------
  1215. window
  1216. --------------------------------------------------------------------------------
  1217.  
  1218.  
  1219. int  W.get_button()         non-blocking mouse read operation
  1220.                             returns number of button (see read_mouse)
  1221.                             if a button has been pressed and 0 otherwise
  1222.  
  1223. void W.set_frame_label(string label)
  1224.                             makes string "label" the window frame label
  1225.  
  1226.  
  1227.  
  1228. --------------------------------------------------------------------------------
  1229. Memory Management:
  1230. --------------------------------------------------------------------------------
  1231.  
  1232. Macro for making LEDA's memory managment available for user-defined data types
  1233.  
  1234. LEDA_MEMORY(type)     defines new & delete operators for "type" allocating and 
  1235.                       deallocating memory by LEDA's internal memory manager
  1236.  
  1237.  
  1238. Example: class 3d_point 
  1239.          { 
  1240.            double x,y,z;
  1241.          
  1242.            public: ...
  1243.          
  1244.            LEDA_MEMORY(3d_point)
  1245.           };
  1246.  
  1247.  
  1248.  
  1249.  
  1250. Two functions for returning memory allocated by the LEDA memory manager to 
  1251. the system.
  1252.  
  1253. void memory_clear()       frees all currently not used memory blocks
  1254.  
  1255. void memory_kill()        frees all memory blocks regardless
  1256.                           if they are still in use or not
  1257.  
  1258.  
  1259.  
  1260.  
  1261. --------------------------------------------------------------------------------
  1262. New header files:
  1263. --------------------------------------------------------------------------------
  1264.  
  1265. The basic two-dimensional data types point, segment, line, circle, polygon,
  1266. and the 2d algorithms can be used separately by including the corresponding 
  1267. header files. The stream data types (file_istream, file_ostream, ...) are no 
  1268. longer included in <LEDA/basic.h> but are still available in <LEDA/stream.h>
  1269.  
  1270.  
  1271.  
  1272. --------------------------------------------------------------------------------
  1273. Libraries:
  1274. --------------------------------------------------------------------------------
  1275.  
  1276. The window library libWx.a (-lWx) or libWs.a (-lWs) now must appear
  1277. after the plane library libP.a (-lP) on the compiler/linker command line.
  1278.  
  1279. For example:
  1280.  
  1281.      CC prog.c -lP -lG -lL -lWx -lxview -lolgx -lX11 -lm
  1282.  
  1283. or
  1284.  
  1285.      CC prog.c -lP -lG -lL -lWs -lsuntools -lsunwindow -lpixrect -lm
  1286.  
  1287.  
  1288.  
  1289.  
  1290.  
  1291.  
  1292.  
  1293. +==============================================================================+
  1294. |                                           |
  1295. |                           VERSION 2.1.1                        |
  1296. |                                                                              |
  1297. +==============================================================================+
  1298.  
  1299.  
  1300. --------------------------------------------------------------------------------
  1301. vector/matrix
  1302. --------------------------------------------------------------------------------
  1303.  
  1304. 1. Assignment (=) and  comparison (==/!=) operators now can be applied to
  1305.    vectors/matrices with different dimensions.
  1306.  
  1307. 2. The default initialization for arrays of vectors/matrices is the
  1308.    vector/matrix of dimension 0.
  1309.  
  1310. 3. Problems with vector/matrix type parameters fixed.
  1311.  
  1312.  
  1313.  
  1314. --------------------------------------------------------------------------------
  1315. graphics
  1316. --------------------------------------------------------------------------------
  1317.  
  1318.  
  1319. graph_edit(window W, GRAPH(point,int) G, bool directed = true);
  1320.  
  1321.         Graph editor, edges are represented by arrows if directed = true
  1322.         and by segments if directed = false
  1323.         (declaration in <LEDA/graph_edit.h>)
  1324.  
  1325.         see example program "prog/graphics/matching.c" for details.
  1326.  
  1327.  
  1328. --------------------------------------------------------------------------------
  1329. string
  1330. --------------------------------------------------------------------------------
  1331.  
  1332.  
  1333. string(const char*, ...)               new printf/form - like constructor
  1334.                                        e.g.  s = string("x = %5.2f",x);
  1335.  
  1336.  
  1337. --------------------------------------------------------------------------------
  1338. graph algorithms
  1339. --------------------------------------------------------------------------------
  1340.  
  1341.  
  1342. list(edge) MAX_CARD_MATCHING(graph G) 
  1343.  
  1344.                               Maximum cardinality matching for general graphs,
  1345.                               implemented by Edmond's Algorithm, returns list
  1346.                               of matched edges.
  1347.                               (source in  "src/graph_alg/_mc_matching.c")
  1348.                 
  1349.                               (worst-case running time  O(n*m) )
  1350.                 
  1351.  
  1352.  
  1353.  
  1354. +==============================================================================+
  1355. |                                           |
  1356. |                           VERSION 2.1.0                        |
  1357. |                                                                              |
  1358. +==============================================================================+
  1359.  
  1360.  
  1361. --------------------------------------------------------------------------------
  1362.         !!!!!!!!!!!!  CHANGES IN HEADER FILES  !!!!!!!!!!!!!!!!!!
  1363. --------------------------------------------------------------------------------
  1364.  
  1365. I. <LEDA/graph.h> 
  1366.  
  1367.  
  1368. Header file <LEDA/graph.h> has been split into  
  1369.  
  1370.  
  1371. <LEDA/graph.h>            : graph, GRAPH, node_array, edge_array
  1372.  
  1373. <LEDA/ugraph.h>           : ugraph, UGRAPH
  1374.  
  1375. <LEDA/planar_map.h>       : planar_map, PLANAR_MAP
  1376.  
  1377. <LEDA/graph_alg.h>        : graph algorithms + predefined node/edge array types
  1378.  
  1379.                             node_array(int)   edge_array(int)
  1380.                             node_array(edge)  edge_array(edge)
  1381.                             node_array(bool)  edge_array(bool);
  1382.                             node_array(real)  edge_array(real)
  1383.                             node_matrix(bool)
  1384.                             node_matrix(int)
  1385.                             node_matrix(real)
  1386.  
  1387. <LEDA/node_set.h>         : node_set
  1388.  
  1389. <LEDA/edge_set.h>         : edge_set
  1390.  
  1391. <LEDA/node_partition.h>   : node_partition
  1392.  
  1393. <LEDA/node_pq.h>          : node_pq
  1394.  
  1395. --------------------------------------------------------------------------------
  1396.  
  1397.  
  1398. II. <LEDA/plane.h> 
  1399.  
  1400.  
  1401. Header file <LEDA/plane.h> has been split into  
  1402.  
  1403. <LEDA/plane.h>      : basic geometric objects (point,segment, ...) and 
  1404.                       predefined types list(point), list(segment), ...
  1405.  
  1406. <LEDA/plane_alg.h>  : plane algorithms, predefined type GRAPH(point,point)
  1407.  
  1408.  
  1409. --------------------------------------------------------------------------------
  1410.  
  1411.  
  1412. --------------------------------------------------------------------------------
  1413. data type "string"
  1414. --------------------------------------------------------------------------------
  1415.  
  1416. int       s.pos (string s_1, int i ) 
  1417.  
  1418.                       returns the first position of s_1 in s right of  
  1419.                       position i (-1 if no such position exists)  
  1420.  
  1421.  
  1422. string    s.insert (string s_1, int i ) 
  1423.  
  1424.                       returns s(0,i-1) + s_1 + s(i+1,s.length())  
  1425.                       Precondition:0 <= i <= s.length()-1  
  1426.  
  1427.  
  1428. string    s.replace (string s_1, string s_2, int i=1 ) 
  1429.  
  1430.                       returns the string created from s by replacing  
  1431.                       the i-th occurence of s_1 in s by s_2  
  1432.  
  1433.  
  1434. string    s.replace_all (string s_1, string s_2 ) 
  1435.  
  1436.                       returns the string created from s by replacing  
  1437.                       all occurences of s_1 in s by s_2  
  1438.  
  1439.  
  1440. string    s.replace (int i, int j, string s_1 ) 
  1441.  
  1442.                       returns the string created from s by replacing  
  1443.                       s(i,j) by s_1  
  1444.  
  1445.  
  1446. string    s.replace (int i, string s_1 ) 
  1447.  
  1448.                       returns the string created from s by replacing  
  1449.                       s[i] by s_1  
  1450.  
  1451.  
  1452. string    s.del (string s_1, int i=1 ) 
  1453.  
  1454.                       returns s.replace(s_1,"",i)  
  1455.  
  1456.  
  1457. string    s.del_all (string s_1 ) 
  1458.  
  1459.                       returns s.replace_all(s_1,"")  
  1460.  
  1461.  
  1462. string    s.del (int i, int j ) 
  1463.  
  1464.                       returns s.replace(i,j,"")  
  1465.  
  1466.  
  1467. string    s.del (int i ) 
  1468.  
  1469.                       returns s.replace(i,"")  
  1470.  
  1471.  
  1472. void      s.read (istream I, char delim = ' ' ) 
  1473.  
  1474.                       reads characters from input stream I into s  
  1475.                       until the first occurence of character delim  
  1476.  
  1477.  
  1478. void      s.read (char delim = ' ' ) 
  1479.  
  1480.                       read(cin,delim)  
  1481.  
  1482.  
  1483. void      s.readline (istream I ) 
  1484.  
  1485.                       read(I,'\n')  
  1486.  
  1487.  
  1488. void      s.readline () 
  1489.  
  1490.                       readline(cin)  
  1491.  
  1492.  
  1493.  
  1494. --------------------------------------------------------------------------------
  1495. matrix
  1496. --------------------------------------------------------------------------------
  1497.  
  1498. Operations   matrix matrix::inv()                O(n^3)
  1499.              vector matrix::solve(vector)        O(n^2)
  1500.              double matrix::det()                O(n^2)
  1501.  
  1502. are now implemented by Gaussian eliminiation.
  1503.  
  1504.  
  1505. matrix M.solve(matrix A)    solves  M*x_i = b_i simultaneously for all 
  1506.                             columns b_i of A, returns matrix (x_0,...,x_n-1)
  1507.                             Preconditions: a) M is quadratic 
  1508.                                            b) A.dim2() = M.dim1()
  1509.  
  1510.  
  1511. --------------------------------------------------------------------------------
  1512. list
  1513. --------------------------------------------------------------------------------
  1514.  
  1515. list_item  L[int i]        returns i-th item (nil if i<0 or i>L.length()-1)
  1516.                            cost: O(i)
  1517.  
  1518.  
  1519.  
  1520. --------------------------------------------------------------------------------
  1521. sortseq
  1522. --------------------------------------------------------------------------------
  1523.  
  1524. void      S.split (seq_item it, sortseq& S_1, sortseq& S_2 ) 
  1525.  
  1526.                       splits S at item it into sequences S_1 and S_2  
  1527.                       and makes S empty. More precisely, if  
  1528.                       S = x_1,...,x_k-1,it,x_k+1,...,x_n then  
  1529.                       S1 = x_1,...,x_k-1,it and S2 = x_k+1,...,x_n  
  1530.                       Precondition: it is an item in S.  
  1531.  
  1532. sortseq&  S.conc (sortseq& S_1 ) 
  1533.  
  1534.                       appends S_1 to S, makes S_1 empty, and returns S.
  1535.                       Precondition: S.key(S.max()) <= S_1.key(S_1.min()).  
  1536.  
  1537.  
  1538.  
  1539.  
  1540.  
  1541.  
  1542. --------------------------------------------------------------------------------
  1543. graph  G
  1544. --------------------------------------------------------------------------------
  1545.  
  1546. void      G.sort_nodes (node_array(T) A ) 
  1547.  
  1548.                       the nodes of G are sorted according to the  
  1549.                       entries of node_array A (cf. section 5.7)  
  1550.                       Precondition: T must be linearly ordered  
  1551.  
  1552. void      G.sort_edges (edge_array(T) A ) 
  1553.  
  1554.                       the edges of G are sorted according to the  
  1555.                       entries of edge_array A (cf. section 5.7)  
  1556.                       Precondition: T must be linearly ordered  
  1557.  
  1558.  
  1559.  
  1560. pretty printing:
  1561.  
  1562. void      G.print(string s, ostream O)
  1563. void      G.print(string s)
  1564. void      G.print(ostream O)
  1565. void      G.print()
  1566.  
  1567. void      G.print_node(node v, ostream O = cout)
  1568. void      G.print_edge(edge e, ostream O = cout)
  1569.  
  1570.  
  1571.  
  1572.  
  1573. --------------------------------------------------------------------------------
  1574. GRAPH(vtype,etype)  G
  1575. --------------------------------------------------------------------------------
  1576.  
  1577. void      G.sort_nodes () 
  1578.  
  1579.                       the nodes of G are sorted according to their  
  1580.                       informations. Precondition: vtype is linearly  
  1581.                       ordered.  
  1582.  
  1583. void      G.sort_edges () 
  1584.  
  1585.                       the edges of G are sorted according to their  
  1586.                       informations. Precondition: etype is linearly  
  1587.                       ordered.  
  1588.  
  1589. --------------------------------------------------------------------------------
  1590. node/edge_array
  1591. --------------------------------------------------------------------------------
  1592.  
  1593. Creation of a node array (edge array)::
  1594.  
  1595. a) ...
  1596. b) ...
  1597. c) ...
  1598.  
  1599. d) node/edge_array(E)  A(graph G, int n, E x)    array for n nodes/edges of G
  1600.                                                  Precondition: n >= |V| (|E|)
  1601.  
  1602.  
  1603.  
  1604.  
  1605.  
  1606.  
  1607.  
  1608.  
  1609.  
  1610.  
  1611. +==============================================================================+
  1612. |                                           |
  1613. |                           VERSION 2.0.1                       |
  1614. |                                                                              |
  1615. +==============================================================================+
  1616.  
  1617.  
  1618. --------------------------------------------------------------------------------
  1619. GENERAL
  1620. --------------------------------------------------------------------------------
  1621.  
  1622. forall_items(x,...)    can be used for all kinds of items
  1623.  
  1624.  
  1625. Read and Write functions for user defined I/O (cf. User Manual, section 1.5)
  1626. must have an additional stream argument: 
  1627.  
  1628.                    Read(T&, istream&)
  1629.  
  1630.                    defines an input function for reading objects of type T 
  1631.                    from an input stream.
  1632.  
  1633.                    Write(T&,ostream&)
  1634.  
  1635.                    defines an output function for printing objects of type T 
  1636.                    to an output stream.
  1637.  
  1638. --------------------------------------------------------------------------------
  1639. string (section 2.3)
  1640. --------------------------------------------------------------------------------
  1641.  
  1642.  
  1643. string  s.tail(int i)       returns the last  i characters of s
  1644.  
  1645. string  s.head(int i)       returns the first i characters of s
  1646.  
  1647.  
  1648.  
  1649. --------------------------------------------------------------------------------
  1650. array (section 3.1)
  1651. --------------------------------------------------------------------------------
  1652.  
  1653.  
  1654. void     A.sort (int (*cmp)(E&, E&), int l, int h ) 
  1655.  
  1656.                       applies the sorting operation to the sub-array  
  1657.                       [l..h].  
  1658.  
  1659. void     A.read (istream I ) 
  1660.  
  1661.                       reads b-a+1 objects of type E from the input  
  1662.                       stream I into the array A using the overloaded  
  1663.                       Read function (section 1.5)  
  1664.  
  1665. void     A.read () 
  1666.  
  1667.                       Calls A.read(cin) to read A from  
  1668.                       the standard input stream cin.  
  1669.  
  1670. void     A.read (string s ) 
  1671.  
  1672.                       As above, but uses string s as a prompt.  
  1673.  
  1674. void     A.print (ostream O, char space = ' ' ) 
  1675.  
  1676.                       Prints the contents of array A to the output  
  1677.                       stream O using the overload Print function  
  1678.                       (section 1.5) to print each element. The elements  
  1679.                       are separated by the space character space.  
  1680.  
  1681. void     A.print (char space = ' ' ) 
  1682.  
  1683.                       Calls A.print(cout, space) to print A on  
  1684.                       the standard output stream cout.  
  1685.  
  1686. void     A.print (string s, char space = ' ' ) 
  1687.  
  1688.                       As above, but uses string s as a header.  
  1689.  
  1690.  
  1691.  
  1692.  
  1693. --------------------------------------------------------------------------------
  1694. list  (section 3.7)
  1695. --------------------------------------------------------------------------------
  1696.  
  1697.  
  1698. void     L.read (istream I, char delim = '\n' ) 
  1699.  
  1700.                       reads a sequence of objects of type E terminated  
  1701.                       by the delimiter delim from the input stream I  
  1702.                       using the overloaded Read function (section 1.5)  
  1703.                       L is made a list of appropriate length and the  
  1704.                       sequence is stored in L.  
  1705.  
  1706. void     L.read (char delim = '\n' ) 
  1707.  
  1708.                       Calls L.read(cin, delim) to read L from  
  1709.                       the standard input stream cin.  
  1710.  
  1711. void     L.read (string s, char delim = '\n' ) 
  1712.  
  1713.                       As above, but uses string s as a prompt.  
  1714.  
  1715. void     L.print (ostream O, char space = ' ' ) 
  1716.  
  1717.                       Prints the contents of list L to the output  
  1718.                       stream O using the overload Print function  
  1719.                       (section 1.5) to print each element. The elements  
  1720.                       are separated by the space character space.  
  1721.  
  1722. void     L.print (char space = ' ' ) 
  1723.  
  1724.                       Calls L.print(cout, space) to print L on  
  1725.                       the standard output stream cout.  
  1726.  
  1727. void     L.print (string s, char space = ' ' ) 
  1728.  
  1729.                       As above, but uses string s as a header.  
  1730.  
  1731.  
  1732.  
  1733. void     L.write (string fname ) 
  1734.  
  1735.                       writes G to the file with name fname. The  
  1736.                       overloaded functions Print(vtype,ostream)  
  1737.                       and Print(etype,ostream) (cf. section 1.6)  
  1738.                       are used to write the node and edge entries  
  1739.                       of G respectively.  
  1740.  
  1741. void     L.read (string fname ) 
  1742.  
  1743.                       reads G from the file with name fname. The  
  1744.                       overloaded functions Read(vtype,istream)  
  1745.                       and Read(etype,istream) (cf. section 1.6)  
  1746.                       are used to read the node and edge entries  
  1747.                       of G respectively.  
  1748.  
  1749. --------------------------------------------------------------------------------
  1750. priority_queue  (section 4.1)
  1751. --------------------------------------------------------------------------------
  1752.  
  1753. Operation del_min has been overloaded
  1754.  
  1755. K    del_min()
  1756.  
  1757. void del_min(K& k, I& i)
  1758.  
  1759.                       removes an item x with minimal information
  1760.                       assigns key(x) to k and inf(x) to i.
  1761.  
  1762.  
  1763. --------------------------------------------------------------------------------
  1764. sortseq  (section 4.6)
  1765. --------------------------------------------------------------------------------
  1766.  
  1767. Operations "succ" and "pred" have been overloaded:
  1768.  
  1769. seq_item  S.succ(seq_item x)
  1770. seq_item  S.succ(K k)
  1771. seq_item  S.pred(seq_item x)
  1772. seq_item  S.pred(K k)
  1773.  
  1774.  
  1775.  
  1776. NEW DATA TYPE:
  1777. --------------------------------------------------------------------------------
  1778. 4.7 Persistent Dictionaries (p_dictionary)
  1779. --------------------------------------------------------------------------------
  1780.  
  1781.  
  1782. 1. DEFINITION
  1783.  
  1784. The difference between dictionaries (cf. section~4.3) and persistent 
  1785. dictionaries lies in the fact that update operations performed 
  1786. on a persistent dictionary D do not change D but create and return a 
  1787. new dictionary D'. For example, D.del(k) returns the dictionary D' 
  1788. containing all items it of D with key(it) != k. 
  1789.  
  1790. An instance D of the data type p_dictionary is a set of items (type 
  1791. p_dic_item). Every item in D contains a key from a linearly ordered 
  1792. data type K, called the key type of D, and an information from a data 
  1793. type I, called the information type  of D. The number of items in D 
  1794. is called the size of D. A dictionary of size zero is called empty. 
  1795. We use <k,i> to denote an item with key k and information 
  1796. i (i is said to be the information associated with key k).  For each 
  1797. k in K there is at most one item <k,i> in D.
  1798.  
  1799.  
  1800.  
  1801. 2. DECLARATION
  1802.  
  1803. declare2(p_dictionary,K,I)
  1804.  
  1805. introduces a new data type with name p_dictionary(K,I) consisting of all 
  1806. persistent dictionaries with key type K and information type I.
  1807. precond K is linearly ordered.
  1808.  
  1809.  
  1810.  
  1811. 3. CREATION
  1812.  
  1813. p_dictionary(K,I) D ;
  1814.  
  1815. creates an instance D of type p_dictionary(K,I) and initializes D to an 
  1816. empty persistent dictionary. 
  1817.  
  1818.  
  1819.  
  1820. 4. OPERATIONS
  1821.  
  1822. K         D.key (dic_item it ) 
  1823.  
  1824.                       returns the key of item it.  
  1825.                       Precondition: it in D.  
  1826.  
  1827. I         D.inf (dic_item it ) 
  1828.  
  1829.                       returns the information of item it.  
  1830.                       Precondition: it in D.  
  1831.  
  1832. dic_item  D.lookup (K k ) 
  1833.  
  1834.                       returns the item with key k (nil if  
  1835.                       no such item exists in D).  
  1836.  
  1837. I         D.access (K k ) 
  1838.  
  1839.                       returns the information associated with key k  
  1840.                       Precondition: there is an item with  
  1841.                       key k in D.  
  1842.  
  1843. p_dictionary(K,I) D.del (K k ) 
  1844.  
  1845.                       returns { x in D | key(x) != k }.  
  1846.  
  1847. p_dictionary(K,I) D.del_item (dic_item it ) 
  1848.  
  1849.                       returns { x in D | x != it }.  
  1850.  
  1851. p_dictionary(K,I) D.insert (K k, I i ) 
  1852.  
  1853.                       returns D.del(k) cup {<k,i>}.  
  1854.  
  1855. p_dictionary(K,I) D.change_inf (dic_item it, I i ) 
  1856.  
  1857.                       Let k = key(it), returns D.del_item(it) cup  
  1858.                       {<k,i>}. Precondition: it in D.  
  1859.  
  1860. p_dictionary(K,I) D.clear () 
  1861.  
  1862.                       returns an empty persistent dictionary.  
  1863.  
  1864. bool      D.empty () 
  1865.  
  1866.                       returns true if D is empty, false otherwise.  
  1867.  
  1868. int       D.size () 
  1869.  
  1870.                       returns the size of D.  
  1871.  
  1872.  
  1873.  
  1874. 5. ITERATION
  1875.  
  1876. forall_items(i,D) 
  1877. { ``the items of D are successively assigned to i '' }
  1878.  
  1879.  
  1880.  
  1881. 6. IMPLEMENTATION
  1882.  
  1883. Persistent Dictionaries are implemented by leaf oriented 
  1884. persistent red black trees (cf. [DSST89]).
  1885. Operations insert, lookup, del_item, del take time O(log n), key, inf, 
  1886. empty, size, change_inf and clear take time O(1). The space requirement 
  1887. is O(n). Here n is the number of all created persistent dictionaries (= number 
  1888. of all performed update operations). 
  1889.  
  1890.  
  1891. --------------------------------------------------------------------------------
  1892. GRAPH    (section 5.4)
  1893. --------------------------------------------------------------------------------
  1894.  
  1895.  
  1896. void      G.write (string fname ) 
  1897.  
  1898.                       writes G to the file with name fname. The  
  1899.                       overloaded functions Print(vtype,ostream)  
  1900.                       and Print(etype,ostream) (cf. section 1.6)  
  1901.                       are used to write the node and edge entries  
  1902.                       of G respectively.  
  1903.  
  1904. int       G.read (string fname ) 
  1905.  
  1906.                       reads G from the file with name fname. The  
  1907.                       overloaded functions Read(vtype,istream)  
  1908.                       and Read(etype,istream) (cf. section 1.6)  
  1909.                       are used to read the node and edge entries  
  1910.                       of G respectively. Returns error code
  1911.                       1  if file fname does not exist
  1912.                       2  if graph is not of type GRAPH(vtype,etype)
  1913.                       3  if file fname does not contain a graph
  1914.                       0  otherwise.
  1915.  
  1916.  
  1917.  
  1918.  
  1919. --------------------------------------------------------------------------------
  1920. PLANE  (section 6.1.6)
  1921. --------------------------------------------------------------------------------
  1922.  
  1923.  
  1924.  
  1925. Function VORONOI  (cf. section 6.1.6) has a new interface:
  1926.  
  1927.  
  1928. void VORONOI(list(point), double R, GRAPH(point,point) )
  1929.  
  1930.         VORONOI takes as input a list of points  sites and a real number 
  1931.         R. It computes a directed graph G representing the planar subdivision
  1932.         defined by the Voronoi-diagram of sites where all ``infinite" edges have
  1933.         length R. For each node v G.inf(v) is the corresponding Voronoi 
  1934.         vertex (point) and for each edge e  G.inf(e) is the site (point) 
  1935.         whose Voronoi region is bounded by e. 
  1936.  
  1937.  
  1938.  
  1939.  
  1940. --------------------------------------------------------------------------------
  1941. point_set  (section 6.3)
  1942. --------------------------------------------------------------------------------
  1943.  
  1944. list(ps_item) S.convex_hull () 
  1945.  
  1946.                       returns the list of items containing  
  1947.                       all points of the convex hull of  
  1948.                       in clockwise order.  
  1949.  
  1950.  
  1951.  
  1952.  
  1953.  
  1954.  
  1955. --------------------------------------------------------------------------------
  1956. graphic windows  (section 6.7)
  1957. --------------------------------------------------------------------------------
  1958.  
  1959. Data type gwindow no longer exists, it is replaced by data type window
  1960.  
  1961. The data type window provides an interface for the input and 
  1962. output of basic two-dimensinal geometric objects (cf. section 5.1) 
  1963. using the X11 (xview) or SunView window system.
  1964. There are two object code libraries (libWs.a, libWx.a) containing 
  1965. implementations for different environments. Application programs using data 
  1966. type window have to be linked with one of these libraries (cf. section~1.6):
  1967.  
  1968.  
  1969. a) For the SunView window system:
  1970.  
  1971.    CC prog.c -lWs -lP -lG -lL -lm  -lsuntool -lsunwindow -lpixrect
  1972.  
  1973.  
  1974. b) For the X11 (open windows) window system:
  1975.  
  1976.    CC prog.c -lWx -lP -lG -lL -lm  -lxview -lolgx -lX11 
  1977.  
  1978.  
  1979.  
  1980. --------------------------------------------------------------------------------
  1981. Creation of a graphic window
  1982. --------------------------------------------------------------------------------
  1983.  
  1984.  
  1985. a) window W(int xpix, int ypix, int xpos, int ypos);
  1986.  
  1987. b) window W(int xpix, int ypix);
  1988.  
  1989. c) window W();
  1990.  
  1991. Variant a) creates a window W of physical size xpix times ypix pixels 
  1992. with its upper left corner at position (xpos,ypos) on the screen,
  1993. variant b) places W into the upper right corner of the screen, and
  1994. variant c) creates a 850 times 850 pixel window positioned into the
  1995. upper right corner.
  1996.  
  1997. All three variants initialize the coordinates of W to x0 = 0,
  1998. x1 = 100 and y0 = 0. The init operation (see  below) can later 
  1999. be used to change the window coordinates and scaling.
  2000.  
  2001.  
  2002.  
  2003. --------------------------------------------------------------------------------
  2004. Additional operations
  2005. --------------------------------------------------------------------------------
  2006.  
  2007.  
  2008. int       W.read_panel (string h, int n, string* S ) 
  2009.  
  2010.                       displays a panel with header h and an array S[n]  
  2011.                       of n string buttons, returns the index of the selected  
  2012.                       button.  
  2013.  
  2014. int       W.read_vpanel (string h, int n, string* S ) 
  2015.  
  2016.                       read_panel with vertical button layout
  2017.  
  2018.  
  2019. int       W.read_int (string p ) 
  2020.  
  2021.                       displays a panel with prompt p for integer input,  
  2022.                       returns the input  
  2023.  
  2024.  
  2025. real      W.read_real (string p ) 
  2026.  
  2027.                       displays a panel with prompt p for real input  
  2028.                       returns the input  
  2029.  
  2030.  
  2031. string    W.read_string (string p ) 
  2032.  
  2033.                       displays a panel with prompt p for string input,  
  2034.                       returns the input  
  2035.  
  2036.  
  2037.         
  2038. string    W.read_string (string p, list(string) menu)
  2039.  
  2040.                       as above, adds an additional menu button which
  2041.                       can be used to select a string from menu.
  2042.      
  2043. string    W.read_string (string p, string label, list(string) menu)
  2044.                       as above, the menu button is labelled with label.
  2045.  
  2046.  
  2047.  
  2048.  
  2049. --------------------------------------------------------------------------------
  2050. PANELS
  2051. --------------------------------------------------------------------------------
  2052.  
  2053.  
  2054. Creation:
  2055. --------
  2056.  
  2057. panel P(string header);
  2058.  
  2059. panel P;
  2060.  
  2061.  
  2062. Operations:
  2063. ----------
  2064.  
  2065. void P.text_item(string s)
  2066.  
  2067. void P.bool_item(string label, bool& x)
  2068.  
  2069. void P.real_item(string label, real& x)
  2070.  
  2071. void P.color_item(string label, color& x)
  2072.  
  2073. void P.int_item(string label, int& x)
  2074. void P.int_item(string label, int& x, int min, int max)              // slider
  2075. void P.int_item(string label, int& x, int low, int high, int step)   // choice
  2076.  
  2077. void P.string_item(string label, string& x)
  2078. void P.string_item(string label,string& x,list(string) L)  // menu
  2079.  
  2080. void P.choice_item(string label, int& x, list(string) L)
  2081. void P.choice_item(string label, int& x, int l, string* L)
  2082. void P.choice_item(string label, int& x, string, ... )
  2083.  
  2084. void P.button(string label)
  2085.  
  2086. void P.new_button_line()
  2087. void P.new_button_line(list(string) buttons)
  2088.  
  2089.  
  2090. int  P.open()
  2091. int  P.open(list(string)& buttons)
  2092.  
  2093.  
  2094. --------------------------------------------------------------------------------
  2095. 7. Miscellaneous
  2096. --------------------------------------------------------------------------------
  2097.  
  2098. --------------------------------------------------------------------------------
  2099. Command input streams (cmd_istream)
  2100. --------------------------------------------------------------------------------
  2101.  
  2102. An instance I of the data type cmd_istream is an C++ istream
  2103. connected to the output of a shell command cmd, i.e., all input operations 
  2104. or operators applied to I read from the standard output of command cmd. 
  2105.  
  2106. 1. Creation of a command input stream 
  2107.  
  2108. cmd_istream   in(string cmd);
  2109.  
  2110. creates an instance in of type cmd_istream connected to the output of command cmd.
  2111.  
  2112. 2. Operations
  2113.  
  2114. All operations and operators (>>) defined for C++ istreams can
  2115. be applied to command input streams as well.
  2116.  
  2117.  
  2118.  
  2119.  
  2120. --------------------------------------------------------------------------------
  2121. Command output streams (cmd_ostream)
  2122. --------------------------------------------------------------------------------
  2123.  
  2124. An instance O of the data type cmd_ostream is an C++ ostream
  2125. connected to the input of a shell command cmd, i.e., all output operations 
  2126. or operators applied to O write into the standard input of command cmd. 
  2127.  
  2128. 1. Creation of a command output stream} 
  2129.  
  2130. cmd_ostream   out(string cmd);
  2131.  
  2132. creates an instance out of type cmd_ostream connected to the input of 
  2133. command cmd. 
  2134.  
  2135. 2. Operations 
  2136.  
  2137. All operations and operators (<<) defined for C++ ostreams can
  2138. be applied to command output streams as well.
  2139.  
  2140.  
  2141.