home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / historic / v941.tgz / icon.v941src.tar / icon.v941src / ipl / gpacks / htetris / matrix.icn < prev    next >
Text File  |  2000-07-29  |  10KB  |  332 lines
  1. ############################################################################
  2. #
  3. # File  :   matrix.icn
  4. # Author:   Henrik Sandin
  5. # Date  :   May 3, 1999
  6. #
  7. ############################################################################
  8. #
  9. #   This file is in the public domain.
  10. #
  11. ############################################################################
  12. #
  13. # This file contains procedures for creating and manipulate a two-
  14. # dimensional matrix structure.
  15. # A matrix is represented with a list of lists and an element is accessed
  16. # in the same way as with lists, row first and column second.
  17. # For example my_matrix[3][4] is the fourth element in the third row
  18. # of my_matrix.
  19. #
  20. ############################################################################
  21.  
  22. $define POS_INF   11
  23. $define NEG_INF   0
  24. $define NO_VALUE -1
  25.  
  26. ############################################################################
  27. #
  28. # Record: non_zero
  29. # Fields: min_row - The first row with non-zero elements in it.
  30. #         max_row - The last row with non-zero elements in it.
  31. #         min_col - The first column with non-zero elements in it.
  32. #         max_col - The last column with non-zero elements in it.
  33. #
  34. # This record represents the smallest rectangular area within a matrix that
  35. # covers all non-zero elements. It contains the top and bottom row numbers
  36. # and left and right column numbers for such an area.
  37. #
  38. ############################################################################
  39.  
  40. record non_zero( min_row, max_row, min_col, max_col)
  41.  
  42. ############################################################################
  43. #
  44. # Procedure: new_matrix
  45. # Arguments: nr_rows    - The number of rows in the new matrix.
  46. #            nr_columns - The number of columns in the new matrix.
  47. # Returns  : matrix     - A new matrix structure.
  48. #
  49. # This procedure constructs and returns a new matrix structure with
  50. # 'nr_rows' rows and 'nr_columns' columns.
  51. # The new matrix is filled with zeroes.
  52. #
  53. ############################################################################
  54.  
  55. procedure new_matrix( nr_rows, nr_columns)
  56.  
  57.     matrix := list( nr_rows, &null)
  58.     every r := 1 to nr_rows do
  59.     matrix[r] := list( nr_columns, 0)
  60.  
  61.     return matrix
  62. end
  63.  
  64. ############################################################################
  65. #
  66. # Procedure: rotate_matrix
  67. # Arguments: matrix  - The matrix to be rotated.
  68. # Returns  : rotated - A new rotated matrix structure.
  69. #
  70. # This procedure constructs and returns a new matrix structure that is
  71. # the argument matrix rotated 90 degrees counter-clockwise.
  72. # The number of rows in the new matrix is the number of columns in the
  73. # original and vice versa.
  74. #
  75. ############################################################################
  76.  
  77. procedure rotate_matrix( matrix)
  78.  
  79.     old_width  := *matrix[1]
  80.     old_height := *matrix
  81.  
  82.     rotated := list( old_width, &null)
  83.     every r := 1 to *rotated do
  84.     rotated[r] := list( old_height, &null)
  85.  
  86.     every r := 1 to old_height do
  87.     every c := old_width to 1 by -1 do
  88.         rotated[old_width-c+1][r] := matrix[r][c]
  89.  
  90.     return rotated
  91. end
  92.  
  93. ############################################################################
  94. #
  95. # Procedure: non_zero_limits
  96. # Arguments: matrix - The matrix to be analyzed.
  97. # Returns  : A used_area structure.
  98. #
  99. # This procedure analyzes the elements of the given matrix and determines
  100. # the limits of the smallest rectangular area covering all the non-zero
  101. # elements in it in terms of a used_area structure.
  102. #
  103. ############################################################################
  104.  
  105. procedure non_zero_limits( matrix)
  106.  
  107.     rows    := []
  108.     min_col := POS_INF
  109.     max_col := NEG_INF
  110.  
  111.     every r := 1 to *matrix do {
  112.     new_min_col := NO_VALUE
  113.     new_max_col := NO_VALUE
  114.  
  115.     every c := 1 to *matrix[1] do
  116.         if matrix[r][c] ~= 0 then {
  117.         new_min_col := c
  118.             break
  119.         }
  120.     every c := *matrix[1] to 1 by -1 do
  121.         if matrix[r][c] ~= 0 then {
  122.         new_max_col := c
  123.         break
  124.         }
  125.     if new_min_col ~= NO_VALUE & new_max_col ~= NO_VALUE then {
  126.         if new_min_col < min_col then
  127.         min_col := new_min_col
  128.         if new_max_col > max_col then
  129.         max_col := new_max_col
  130.         put( rows, r)
  131.     }
  132.     }
  133.     if *rows = 1 then {
  134.     min_row := get( rows)
  135.     max_row := min_row
  136.     }
  137.     else {
  138.     min_row := get( rows)
  139.     max_row := pull( rows)
  140.     }
  141.     return non_zero( min_row, max_row, min_col, max_col)
  142. end
  143.  
  144. ############################################################################
  145. #
  146. # Procedure: trim_matrix
  147. # Arguments: matrix  - The matrix to be trimmed.
  148. # Returns  : trimmed - A new trimmed matrix.
  149. #
  150. # This procedure peels off possibly unused outer rows and columns.
  151. # A row or column is concidered unused if it contains only zeros.
  152. # A new matrix with a possibly smaller size and the contents of the
  153. # non-zero rows and columns in the original is constructed and returned.
  154. #
  155. ############################################################################
  156.  
  157. procedure trim_matrix( matrix)
  158.  
  159.     non_zero_area := non_zero_limits( matrix)
  160.  
  161.     trimmed := new_matrix( non_zero_area.max_row-non_zero_area.min_row+1,
  162.                non_zero_area.max_col-non_zero_area.min_col+1)
  163.     trimmed_row := 1
  164.     every matrix_row := non_zero_area.min_row to non_zero_area.max_row do {
  165.     trimmed_col := 1
  166.     every matrix_col := non_zero_area.min_col to non_zero_area.max_col do {
  167.         trimmed[trimmed_row][trimmed_col] := matrix[matrix_row][matrix_col]
  168.         trimmed_col := trimmed_col+1
  169.     }
  170.     trimmed_row := trimmed_row+1
  171.     }
  172.     return trimmed
  173. end
  174.  
  175. ############################################################################
  176. #
  177. # Procedure: mtos
  178. # Arguments: matrix        - A matrix containing only ones and zeros.
  179. # Returns  : matrix_string - Its string representation.
  180. #
  181. # This procedure returns the string representation of the given matrix.
  182. # It has the following format:
  183. # <nr rows>,<nr columns>;<row 1>;...;<row n>
  184. # Where nr rows and nr columns are integers and row i is a string of ones
  185. # and/or zeros.
  186. #
  187. ############################################################################
  188.  
  189. procedure mtos( matrix)
  190.  
  191.     matrix_string := *matrix || "," || *matrix[1] || ";"
  192.  
  193.     every r := 1 to *matrix do {
  194.     every c := 1 to *matrix[1] do
  195.         matrix_string := matrix_string || matrix[r][c]
  196.  
  197.     if r < *matrix then
  198.         matrix_string := matrix_string || ";"
  199.     }
  200.     return matrix_string
  201. end
  202.  
  203. ############################################################################
  204. #
  205. # Procedure: stom
  206. # Arguments: matrix_string - String representation of a matrix.
  207. # Returns  : matrix        - The corresponding matrix.
  208. #
  209. # This procedure returns a matrix corresponding to the given string
  210. # representation which represents a matrix containing only ones and zeros.
  211. #
  212. ############################################################################
  213.  
  214. procedure stom( matrix_string)
  215.  
  216.     matrix_string ? {
  217.     rows := integer( tab( upto( ',')))
  218.     move( 1)
  219.     columns := integer( tab( upto( ';')))
  220.     matrix  := new_matrix( rows, columns, 0)
  221.     move( 1)
  222.     every r := 1 to rows do {
  223.         row_string := tab( many( '01'))
  224.         row_string ? {
  225.         every c := 1 to columns do
  226.             matrix[r][c] := move( 1)
  227.         }
  228.         move( 1)
  229.     }
  230.     }
  231.     return matrix
  232. end
  233.  
  234. ############################################################################
  235. #
  236. # Procedure: copy_matrix
  237. # Arguments: matrx   - A matrix.
  238. # Returns  : new_mtx - A copy of the original list of matrices.
  239. #
  240. # This procedure constructs and returns a copy of a given  matrix.
  241. # Only the top-level of the elements (if they are structures) are copied.
  242. #
  243. ############################################################################
  244.  
  245. procedure copy_matrix( matrix)
  246.  
  247.     new_mtx := list( *matrix, &null)
  248.     every r := 1 to *matrix do {
  249.  
  250.     new_r := list( *matrix[r], &null)
  251.     every c := 1 to *matrix[r] do {
  252.         
  253.         new_r[c] := copy( matrix[r][c])
  254.     }
  255.     new_mtx[r] := new_r
  256.     }
  257.     return new_mtx
  258. end
  259.  
  260. ############################################################################
  261. #
  262. # Procedure: copy_matrices
  263. # Arguments: matrices - A list of matrices.
  264. # Returns  : new_lst  - A copy of the original list of matrices.
  265. #
  266. # This procedure constructs and returns a copu of a given list of matrices.
  267. #
  268. ############################################################################
  269.  
  270. procedure copy_matrices( matrices)
  271.  
  272.     new_lst := list( *matrices, &null)
  273.     every matrix := 1 to *matrices do
  274.     new_lst[matrix] := copy_matrix( matrices[matrix])
  275.  
  276.     return new_lst
  277. end
  278.  
  279. ############################################################################
  280. #
  281. # Procedure: init_positions
  282. # Arguments: matrix - Matrix representing a brick which is to be initialized.
  283. # Returns  : Nothing.
  284. #
  285. # This procedure initializes a brick matrix with the starting positions in
  286. # the game pane matrix. Each element is set to a record containing the
  287. # row/column position of the game pane matrix and whether that square
  288. # (of the brick) is transparent or not.
  289. #
  290. ############################################################################
  291.  
  292. procedure init_positions( matrix)
  293.  
  294.     start_column := MIDDLE+1 - (*matrix[1])/2
  295.  
  296.     init_row := 1
  297.     every r := 1 to *matrix do {
  298.     init_column := start_column
  299.     every c := 1 to *matrix[r] do {
  300.         if matrix[r][c] = 0 then
  301.         matrix[r][c] := position( init_row, init_column, TRUE)
  302.         else
  303.         matrix[r][c] := position( init_row, init_column, FALSE)
  304.         init_column := init_column+1
  305.     }
  306.     init_row := init_row+1
  307.     }
  308.     return matrix
  309. end
  310.  
  311. ############################################################################
  312. #
  313. # Procedure: print_matrix
  314. # Arguments: matrix - A matrix.
  315. # Returns  : Nothing.
  316. #
  317. # This procedure writes the given matrix to standard output, one row
  318. # per line. Used for debugging.
  319. #
  320. ############################################################################
  321.  
  322. procedure print_matrix( matrix)
  323.  
  324.     every r := 1 to *matrix do {
  325.     every c := 1 to *matrix[r] do
  326.         writes( image( matrix[r][c]) || " ")
  327.     write()
  328.     }
  329.     write()
  330.     return    
  331. end
  332.