lib/standard/collection/range.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2004-2008 Jean Privat <jean@pryen.org>
   4 #
   5 # This file is free software, which comes along with NIT.  This software is
   6 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
   7 # without  even  the implied warranty of  MERCHANTABILITY or  FITNESS FOR A
   8 # PARTICULAR PURPOSE.  You can modify it is you want,  provided this header
   9 # is kept unaltered, and a notification of the changes is added.
  10 # You  are  allowed  to  redistribute it and sell it, alone or is a part of
  11 # another product.
  12
  13 # Module for range of discrete objects.
  14 module range
  15
  16 import abstract_collection
  17
  18 # Range of discrete objects.
  19 class Range[E: Discrete]
  20         super Collection[E]
  21
  22         redef var first: E
  23
  24         # Get the last element.
  25         var last: E
  26
  27         # Get the element after the last one.
  28         var after: E
  29
  30         #     assert [1..10].has(5)
  31         #     assert [1..10].has(10)
  32         #     assert not [1..10[.has(10)
  33         redef fun has(item) do return item isa Comparable and item >= first and item <= last
  34
  35         #     assert [1..1].has_only(1)
  36         #     assert not [1..10].has_only(1)
  37         redef fun has_only(item) do return first == item and item == last or is_empty
  38
  39         #     assert [1..10].count(1)   == 1
  40         #     assert [1..10].count(0)   == 0
  41         redef fun count(item)
  42         do
  43                 if has(item) then
  44                         return 1
  45                 else
  46                         return 0
  47                 end
  48         end
  49
  50         redef fun iterator do return new IteratorRange[E](self)
  51
  52         # Gets an iterator starting at the end and going backwards
  53         #
  54         #     var reviter = [1..4].reverse_iterator
  55         #     assert reviter.to_a == [4,3,2,1]
  56         #
  57         #     reviter = [1..4[.reverse_iterator
  58         #     assert reviter.to_a == [3,2,1]
  59         fun reverse_iterator: Iterator[E] do return new ReverseIteratorRange[E](self)
  60
  61         #     assert [1..10].length             == 10
  62         #     assert [1..10[.length             == 9
  63         #     assert [1..1].length              == 1
  64         #     assert [1..-10].length    == 0
  65         redef fun length
  66         do
  67                 if is_empty then return 0
  68                 var nb = first.distance(after)
  69                 if nb > 0 then
  70                         return nb
  71                 else
  72                         return 0
  73                 end
  74         end
  75
  76         #     assert not [1..10[.is_empty
  77         #     assert not [1..1].is_empty
  78         #     assert [1..-10].is_empty
  79         redef fun is_empty do return first >= after
  80
  81         # Create a range [`from`, `to`].
  82         # The syntax `[from..to]` is equivalent.
  83         #
  84         #     var a = [10..15]
  85         #     var b = new Range[Int] (10,15)
  86         #     assert a == b
  87         #     assert a.to_a == [10, 11, 12, 13, 14, 15]
  88         init(from: E, to: E) is old_style_init do
  89                 first = from
  90                 last = to
  91                 after = to.successor(1)
  92         end
  93
  94         # Create a range [`from`, `to`[.
  95         # The syntax `[from..to[` is equivalent.
  96         #
  97         #     var a = [10..15[
  98         #     var b = new Range[Int].without_last(10,15)
  99         #     assert a == b
 100         #     assert a.to_a == [10, 11, 12, 13, 14]
 101         init without_last(from: E, to: E)
 102         do
 103                 first = from
 104                 if from <= to then
 105                         last = to.predecessor(1)
 106                         after = to
 107                 else
 108                         last = to.successor(1)
 109                         after = to
 110                 end
 111         end
 112
 113         # Two ranges are equals if they have the same first and last elements.
 114         #
 115         #     var a = new Range[Int](10, 15)
 116         #     var b = new Range[Int].without_last(10, 15)
 117         #     assert a == [10..15]
 118         #     assert a == [10..16[
 119         #     assert not a == [10..15[
 120         #     assert b == [10..15[
 121         #     assert b == [10..14]
 122         #     assert not b == [10..15]
 123         redef fun ==(o) do
 124                 return o isa Range[E] and self.first == o.first and self.last == o.last
 125         end
 126
 127         #     var a = new Range[Int](10, 15)
 128         #     assert a.hash == 455
 129         #     var b = new Range[Int].without_last(10, 15)
 130         #     assert b.hash == 432
 131         redef fun hash do
 132                 # 11 and 23 are magic numbers empirically determined to be not so bad.
 133                 return first.hash * 11 + last.hash * 23
 134         end
 135
 136         # Gets an iterator that progress with a given step.
 137         #
 138         # The main usage is in `for` construction.
 139         #
 140         # ~~~
 141         # for i in [10..25].step(10) do assert i == 10 or i == 20
 142         # ~~~
 143         #
 144         # But `step` is usable as any kind of iterator.
 145         #
 146         # ~~~
 147         # assert [10..27].step(5).to_a == [10,15,20,25]
 148         # ~~~
 149         #
 150         # If `step == 1`, then it is equivalent to the default `iterator`.
 151         #
 152         # ~~~
 153         # assert [1..5].step(1).to_a == [1..5].to_a
 154         # ~~~
 155         #
 156         # If `step` is negative, then the iterator will iterate on ranges whose `first` > `last`.
 157         #
 158         # ~~~
 159         # assert [25..12].step(-5).to_a == [25,20,15]
 160         # ~~~
 161         #
 162         # On such ranges, the default `iterator` will be empty
 163         #
 164         # ~~~
 165         # assert [5..1].step(1).to_a.is_empty
 166         # assert [5..1].iterator.to_a.is_empty
 167         # assert [5..1].to_a.is_empty
 168         # assert [5..1].is_empty
 169         # ~~~
 170         #
 171         # Note that on non-empty range, iterating with a negative step will be empty
 172         #
 173         # ~~~
 174         # assert [1..5].step(-1).to_a.is_empty
 175         # ~~~
 176         fun step(step: Int): Iterator[E]
 177         do
 178                 var i
 179                 if step >= 0 then
 180                         i = iterator
 181                 else
 182                         i = new DowntoIteratorRange[E](self)
 183                         step = -step
 184                 end
 185
 186                 if step == 1 then return i
 187                 return i.to_step(step)
 188         end
 189 end
 190
 191 # Iterator on ranges.
 192 private class IteratorRange[E: Discrete]
 193         super Iterator[E]
 194         var range: Range[E]
 195         redef var item is noinit
 196
 197         redef fun is_ok do return _item < _range.after
 198
 199         redef fun next do _item = _item.successor(1)
 200
 201         init
 202         do
 203                 _item = _range.first
 204         end
 205 end
 206
 207 # Reverse iterator on ranges.
 208 private class ReverseIteratorRange[E: Discrete]
 209         super Iterator[E]
 210         var range: Range[E]
 211         redef var item is noinit
 212
 213         redef fun is_ok do return _item >= _range.first
 214
 215         redef fun next do _item = _item.predecessor(1)
 216
 217         init
 218         do
 219                 _item = _range.last
 220         end
 221 end
 222
 223 # Iterator on ranges.
 224 private class DowntoIteratorRange[E: Discrete]
 225         super IndexedIterator[E]
 226         var range: Range[E]
 227         redef var item is noinit
 228         redef fun index do return _item.distance(_range.first)
 229
 230         redef fun is_ok do return _item >= _range.last
 231
 232         redef fun next do _item = _item.predecessor(1)
 233
 234         init
 235         do
 236                 _item = _range.first
 237         end
 238 end
 239
 240 redef class Int
 241         # Returns the range from 0 to `self-1`, is used to do:
 242         #
 243         #     var s = new Array[String]
 244         #     for i in 3.times do s.add "cool"
 245         #     assert s.join(" ") == "cool cool cool"
 246         #
 247         #     s.clear
 248         #     for i in 10.times do s.add(i.to_s)
 249         #     assert s.to_s == "0123456789"
 250         fun times: Range[Int] do return [0 .. self[
 251 end