lib/matrix/matrix.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Licensed under the Apache License, Version 2.0 (the "License");
   4 # you may not use this file except in compliance with the License.
   5 # You may obtain a copy of the License at
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 # See the License for the specific language governing permissions and
  13 # limitations under the License.
  14
  15 # Services for matrices of `Float` values
  16 module matrix
  17
  18 # A rectangular array of `Float`
  19 #
  20 # Require: `width > 0 and height > 0`
  21 class Matrix
  22         super Cloneable
  23
  24         # Number of columns
  25         var width: Int
  26
  27         # Number of rows
  28         var height: Int
  29
  30         # Items of this matrix, rows by rows
  31         private var items: Array[Float] is lazy do
  32                 return new Array[Float].filled_with(0.0, width*height)
  33         end
  34
  35         # Create a matrix from nested sequences
  36         #
  37         # Require: all rows are of the same length
  38         #
  39         # ~~~
  40         # var matrix = new Matrix.from([[1.0, 2.0],
  41         #                               [3.0, 4.0]])
  42         # assert matrix.to_s == """
  43         # 1.0 2.0
  44         # 3.0 4.0"""
  45         # ~~~
  46         init from(items: SequenceRead[SequenceRead[Float]])
  47         do
  48                 if items.is_empty then
  49                         init(0, 0)
  50                         return
  51                 end
  52
  53                 init(items.first.length, items.length)
  54
  55                 for j in height.times do assert items[j].length == width
  56
  57                 for j in height.times do
  58                         for i in width.times do
  59                                 self[j, i] = items[j][i]
  60                         end
  61                 end
  62         end
  63
  64         # Create a matrix from an `Array[Float]` composed of rows after rows
  65         #
  66         # Require: `width > 0 and height > 0`
  67         # Require: `array.length >= width*height`
  68         #
  69         # ~~~
  70         # var matrix = new Matrix.from_array(2, 2, [1.0, 2.0,
  71         #                                           3.0, 4.0])
  72         # assert matrix.to_s == """
  73         # 1.0 2.0
  74         # 3.0 4.0"""
  75         # ~~~
  76         init from_array(width, height: Int, array: SequenceRead[Float])
  77         do
  78                 assert width > 0
  79                 assert height > 0
  80                 assert array.length >= width*height
  81
  82                 init(width, height)
  83
  84                 for i in height.times do
  85                         for j in width.times do
  86                                 self[j, i] = array[i + j*width]
  87                         end
  88                 end
  89         end
  90
  91         # Create an identity matrix
  92         #
  93         # Require: `size >= 0`
  94         #
  95         # ~~~
  96         # var i = new Matrix.identity(3)
  97         # assert i.to_s == """
  98         # 1.0 0.0 0.0
  99         # 0.0 1.0 0.0
 100         # 0.0 0.0 1.0"""
 101         # ~~~
 102         new identity(size: Int)
 103         do
 104                 assert size >= 0
 105
 106                 var matrix = new Matrix(size, size)
 107                 for i in size.times do
 108                         for j in size.times do
 109                                 matrix[j, i] = if i == j then 1.0 else 0.0
 110                         end
 111                 end
 112                 return matrix
 113         end
 114
 115         # Create a new clone of this matrix
 116         redef fun clone do return new Matrix.from_array(width, height, items.clone)
 117
 118         # Get the value at column `y` and row `x`
 119         #
 120         # Require: `x >= 0 and x <= width and y >= 0 and y <= height`
 121         #
 122         # ~~~
 123         # var matrix = new Matrix.from([[0.0, 0.1],
 124         #                               [1.0, 1.1]])
 125         #
 126         # assert matrix[0, 0] == 0.0
 127         # assert matrix[0, 1] == 0.1
 128         # assert matrix[1, 0] == 1.0
 129         # assert matrix[1, 1] == 1.1
 130         # ~~~
 131         fun [](y, x: Int): Float
 132         do
 133                 assert x >= 0 and x < width
 134                 assert y >= 0 and y < height
 135
 136                 return items[x + y*width]
 137         end
 138
 139         # Set the `value` at row `y` and column `x`
 140         #
 141         # Require: `x >= 0 and x <= width and y >= 0 and y <= height`
 142         #
 143         # ~~~
 144         # var matrix = new Matrix.identity(2)
 145         #
 146         # matrix[0, 0] = 0.0
 147         # matrix[0, 1] = 0.1
 148         # matrix[1, 0] = 1.0
 149         # matrix[1, 1] = 1.1
 150         #
 151         # assert matrix.to_s == """
 152         # 0.0 0.1
 153         # 1.0 1.1"""
 154         # ~~~
 155         fun []=(y, x: Int, value: Float)
 156         do
 157                 assert x >= 0 and x < width
 158                 assert y >= 0 and y < height
 159
 160                 items[x + y*width] = value
 161         end
 162
 163         # Matrix product (×)
 164         #
 165         # Require: `self.width == other.height`
 166         #
 167         # ~~~
 168         # var m = new Matrix.from([[3.0, 4.0],
 169         #                          [5.0, 6.0]])
 170         # var i = new Matrix.identity(2)
 171         #
 172         # assert m * i == m
 173         # assert (m * m).to_s == """
 174         # 29.0 36.0
 175         # 45.0 56.0"""
 176         #
 177         # var a = new Matrix.from([[1.0, 2.0, 3.0],
 178         #                          [4.0, 5.0, 6.0]])
 179         # var b = new Matrix.from([[1.0],
 180         #                          [2.0],
 181         #                          [3.0]])
 182         # var c = a * b
 183         # assert c.to_s == """
 184         # 14.0
 185         # 32.0"""
 186         # ~~~
 187         fun *(other: Matrix): Matrix
 188         do
 189                 assert self.width == other.height
 190
 191                 var out = new Matrix(other.width, self.height)
 192                 for j in self.height.times do
 193                         for i in other.width.times do
 194                                 var sum = items.first.zero
 195                                 for k in self.width.times do sum += self[j, k] * other[k, i]
 196                                 out[j, i] = sum
 197                         end
 198                 end
 199                 return out
 200         end
 201
 202         # Iterate over the values in this matrix
 203         fun iterator: MapIterator[MatrixCoordinate, Float] do return new MatrixIndexIterator(self)
 204
 205         redef fun to_s
 206         do
 207                 var lines = new Array[String]
 208                 for y in height.times do
 209                         lines.add items.subarray(y*width, width).join(" ")
 210                 end
 211                 return lines.join("\n")
 212         end
 213
 214         redef fun ==(other) do return other isa Matrix and other.items == self.items
 215         redef fun hash do return items.hash
 216 end
 217
 218 private class MatrixIndexIterator
 219         super MapIterator[MatrixCoordinate, Float]
 220
 221         var matrix: Matrix
 222
 223         redef var key = new MatrixCoordinate(0, 0)
 224
 225         redef fun is_ok do return key.y < matrix.height
 226
 227         redef fun item
 228         do
 229                 assert is_ok
 230                 return matrix[key.y, key.x]
 231         end
 232
 233         redef fun next
 234         do
 235                 assert is_ok
 236                 var key = key
 237                 if key.x == matrix.width - 1 then
 238                         key.x = 0
 239                         key.y += 1
 240                 else
 241                         key.x += 1
 242                 end
 243         end
 244 end
 245
 246 # Position key when iterating over the values of a matrix
 247 class MatrixCoordinate
 248         # Index of the current column
 249         var x: Int
 250
 251         # Index of the current row
 252         var y: Int
 253
 254         redef fun to_s do return "({x},{y})"
 255 end