lib/dummy_array.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2008 Floréal Morandat <morandat@lirmm.fr>
   4 # Copyright 2014 Alexandre Terrasa <alexandre@moz-code.org>
   5 #
   6 # This file is free software, which comes along with NIT.  This software is
   7 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
   8 # without  even  the implied warranty of  MERCHANTABILITY or  FITNESS FOR A
   9 # PARTICULAR PURPOSE.  You can modify it is you want,  provided this header
  10 # is kept unaltered, and a notification of the changes is added.
  11 # You  are  allowed  to  redistribute it and sell it, alone or is a part of
  12 # another product.
  13
  14 # A `Set` that contains only integers.
  15 class DummyArray
  16         super Set[Int]
  17         private var capacity: Int
  18         redef var length: Int
  19         private var keys: NativeArray[Int]
  20         private var values: NativeArray[Int]
  21
  22         redef fun add(value: Int)
  23         do
  24                 assert full: _length < (_capacity-1)
  25                 var l = _length
  26                 _values[l] = value
  27                 _keys[value] = l
  28                 _length = l + 1
  29         end
  30
  31         redef fun remove(value: Int)
  32         do
  33                 assert not is_empty
  34                 var l = _length
  35                 if l > 1 then
  36                         var last = _values[l - 1]
  37                         var pos = _keys[value]
  38                         _keys[last] = pos
  39                         _values[pos] = last
  40                 end
  41                 _length = l - 1
  42         end
  43
  44         redef fun has(value: Int): Bool
  45         do
  46                 assert value < _capacity
  47                 var pos = _keys[value]
  48                 if pos < _length then
  49                         return _values[pos] == value
  50                 end
  51                 return false
  52         end
  53
  54         redef fun first: Int
  55         do
  56                 assert _length > 0
  57                 return _values[0]
  58         end
  59
  60         redef fun is_empty: Bool
  61         do
  62                 return not (_length > 0)
  63         end
  64
  65         redef fun clear
  66         do
  67                 _length = 0
  68         end
  69
  70         redef fun iterator: DummyIterator
  71         do
  72                 return new DummyIterator(self)
  73         end
  74
  75         private fun value_at(pos: Int): Int
  76         do
  77                 return _values[pos]
  78         end
  79
  80         # initialize a new DummyArray with `capacity`.
  81         init(capacity: Int) is old_style_init do
  82                 _capacity = capacity
  83                 _keys = new NativeArray[Int](capacity)
  84                 _values = new NativeArray[Int](capacity)
  85         end
  86 end
  87
  88 # An iterator over a `DummyArray`.
  89 class DummyIterator
  90         super Iterator[Int]
  91         private var array: DummyArray
  92         private var pos: Int
  93
  94         redef fun item: Int
  95         do
  96                 assert is_ok
  97                 return _array.value_at(_pos)
  98         end
  99
 100         redef fun is_ok: Bool
 101         do
 102                 return _pos < _array.length
 103         end
 104
 105         redef fun next do _pos = _pos + 1 end
 106
 107         # Initialize an iterator for `array`.
 108         init(array: DummyArray) is old_style_init do
 109                 _pos = 0
 110                 _array = array
 111         end
 112 end