home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / doc / range.tex < prev    next >
Encoding:
Text File  |  1993-05-05  |  6.4 KB  |  173 lines
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. %%
  3. %A  range.tex                   GAP documentation            Martin Schoenert
  4. %%
  5. %A  @(#)$Id: range.tex,v 3.7 1993/02/19 10:48:42 gap Exp $
  6. %%
  7. %Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. %%
  9. %%  This file describes those functions that mainly deal with ranges.
  10. %%
  11. %H  $Log: range.tex,v $
  12. %H  Revision 3.7  1993/02/19  10:48:42  gap
  13. %H  adjustments in line length and spelling
  14. %H
  15. %H  Revision 3.6  1993/02/12  11:39:35  felsch
  16. %H  new example fixed
  17. %H
  18. %H  Revision 3.5  1993/02/10  18:56:42  martin
  19. %H  changed the description for extended ranges
  20. %H
  21. %H  Revision 3.4  1993/02/05  08:07:20  felsch
  22. %H  examples fixed
  23. %H
  24. %H  Revision 3.3  1991/12/27  16:07:04  martin
  25. %H  revised everything for GAP 3.1 manual
  26. %H
  27. %H  Revision 3.2  1991/07/26  09:01:07  martin
  28. %H  changed |\GAP\ | to |{\GAP}|
  29. %H
  30. %H  Revision 3.1  1991/07/25  16:16:59  martin
  31. %H  fixed some minor typos
  32. %H
  33. %H  Revision 3.0  1991/04/11  11:32:53  martin
  34. %H  Initial revision under RCS
  35. %H
  36. %%
  37. \Chapter{Ranges}
  38.  
  39. A *range* is a dense list of integers,  such  that the difference between
  40. consecutive  elements is a nonzero  constant.   Ranges can be abbreviated
  41. with the syntactic construct '[ <first>, <second> .. <last> ]' or, if the
  42. difference between consecutive elements is 1, as '[ <first> .. <last> ]'.
  43.  
  44. If  '<first> > <last>',  '[<first>,<second>..<last>]' is  the empty list,
  45. which   by  definition  is   also   a  range.    If   <first>  =  <last>,
  46. '[<first>,<second>..<last>]' is a singleton list,  which is a range  too.
  47. Note that '<last> - <first>' must be divisable by the increment '<second>
  48. - <first>', otherwise an error is signalled.
  49.  
  50. Note  that a range is  just a special case of a list.  So everything that
  51. is  possible for lists (see "Lists") is also  possible for ranges.   Thus
  52. you can  access elements in such a range (see "List Elements"),  test for
  53. membership  (see  "In"), etc.   You can even assign to such a  range (see
  54. "List   Assignment").   Of   course,  unless   you   assign   '<last>   +
  55. <second>-<first>'  to   the   entry   '<range>[Length(<range>)+1]',   the
  56. resulting list will no longer be a range.
  57.  
  58. Most often ranges are used in connection with the 'for'-loop (see "For").
  59. Here  the construct \\
  60. 'for <var>  in [<first>..<last>]  do <statements>  od' replaces the \\
  61. 'for <var>  from <first>  to <last>  do <statements>  od',  which is more
  62. usual in other programming languages.
  63.  
  64. Note that a range is at the same time also a set (see "Sets"), because it
  65. contains no  holes or duplicates  and is sorted, and  also a  vector (see
  66. "Vectors"), because it contains no holes and all elements are integers.
  67.  
  68. |    gap> r := [10..20];
  69.     [ 10 .. 20 ]
  70.     gap> Length( r );
  71.     11
  72.     gap> r[3];
  73.     12
  74.     gap> 17 in r;
  75.     true
  76.     gap> r[12] := 25;; r;
  77.     [ 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 25 ]
  78.     gap> r := [1,3..17];
  79.     [ 1, 3 .. 17 ]
  80.     gap> Length( r );
  81.     9
  82.     gap> r[4];
  83.     7
  84.     gap> r := [0,-1..-9];
  85.     [ 0, -1 .. -9 ]
  86.     gap> r[5];
  87.     -4
  88.     gap> r := [ 1, 4 .. 32 ];
  89.     Error, Range: <high>-<low> must be divisable by <inc>
  90.     gap> s := [];;  for i  in [10..20]  do Add( s, i^2 );  od;  s;
  91.     [ 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400 ] |
  92.  
  93. The first section in this chapter describes  the function that tests if a
  94. list is a range (see "IsRange").
  95.  
  96. The  other section tells  you more  about  the internal representation of
  97. ranges (see "More about Ranges").
  98.  
  99. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  100. \Section{IsRange}\index{test!for a range}
  101.  
  102. 'IsRange( <obj> )'
  103.  
  104. 'IsRange' returns 'true' if <obj>, which may be an object of any type, is
  105. a range and 'false' otherwise.  A range is a list without holes such that
  106. the elements are integers with a constant increment.  Will cause an error
  107. if <obj> is an unassigned variable.
  108.  
  109. |    gap> IsRange( [1,2,3] );
  110.     true    # this list is a range
  111.     gap> IsRange( [7,5,3,1] );
  112.     true    # this list is a range
  113.     gap> IsRange( [1,2,4,5] );
  114.     false    # this list is a set and a vector, but not a range
  115.     gap> IsRange( [1,,3,,5,,7] );
  116.     false    # this list contains holes
  117.     gap> IsRange( 1 );
  118.     false    # is not even a list
  119.     gap> IsRange( [] );
  120.     true    # the empty list is a range by definition
  121.     gap> IsRange( [1] );
  122.     true    # singleton lists are a range by definition too |
  123.  
  124. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  125. \Section{More about Ranges}
  126.  
  127. For some  lists the kernel knows   that they are  in fact  ranges.  Those
  128. lists are represented internally in a compact way instead of the ordinary
  129. way.  This is important since this representation needs only 12 bytes for
  130. the entire list while the ordinary representation needs $4 length$ bytes.
  131.  
  132. Note that a list that is represented in the ordinary way might still be a
  133. range.  It is just that {\GAP} does not  know this.   This  section tells
  134. you under which circumstances a range is represented  in the compact way,
  135. so you can write your  program in such  a  way that you make best  use of
  136. this compact representation for ranges.
  137.  
  138. Lists  created by the syntactic construct '[ <first>, <second>  .. <last>
  139. ]' are  of  course known to be ranges and  are represented in the compact
  140. way.
  141.  
  142. If  you call  'IsRange' for a  list represented the ordinary  way that is
  143. indeed a range, 'IsRange' will note this,  change the representation from
  144. the ordinary to the compact representation, and then return 'true';
  145.  
  146.  
  147. If   you change a   range  that is  represented   in the compact  way, by
  148. assignment, 'Add'   or 'Append', the   range will  be   converted to  the
  149. ordinary representation, even  if the change is  such that the  resulting
  150. list is still a proper range.
  151.  
  152. Suppose  you have   built a proper   range  in  such  a way   that  it is
  153. represented in the  ordinary way and that you  now want to convert  it to
  154. the compact representation to save space.  Then you should call 'IsRange'
  155. with that list as an argument.  If it is indeed a proper range, 'IsRange'
  156. will convert it to the compact representation.  You can think of the call
  157. to 'IsRange' as a hint to {\GAP} that this list is a proper range.
  158.  
  159. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  160. %%
  161. %E  Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables
  162. %%
  163. %%  Local Variables:
  164. %%  mode:               outline
  165. %%  outline-regexp:     "\\\\Chapter\\|\\\\Section"
  166. %%  fill-column:        73
  167. %%  eval:               (hide-body)
  168. %%  End:
  169. %%
  170.  
  171.  
  172.  
  173.