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)
  32         do
  33                 assert not is_empty
  34                 if not value isa Int then return
  35                 var l = _length
  36                 if l > 1 then
  37                         var last = _values[l - 1]
  38                         var pos = _keys[value]
  39                         _keys[last] = pos
  40                         _values[pos] = last
  41                 end
  42                 _length = l - 1
  43         end
  44
  45         redef fun has(value)
  46         do
  47                 if not value isa Int then return false
  48                 assert value < _capacity
  49                 var pos = _keys[value]
  50                 if pos < _length then
  51                         return _values[pos] == value
  52                 end
  53                 return false
  54         end
  55
  56         redef fun first: Int
  57         do
  58                 assert _length > 0
  59                 return _values[0]
  60         end
  61
  62         redef fun is_empty: Bool
  63         do
  64                 return not (_length > 0)
  65         end
  66
  67         redef fun clear
  68         do
  69                 _length = 0
  70         end
  71
  72         redef fun iterator: DummyIterator
  73         do
  74                 return new DummyIterator(self)
  75         end
  76
  77         private fun value_at(pos: Int): Int
  78         do
  79                 return _values[pos]
  80         end
  81
  82         # initialize a new DummyArray with `capacity`.
  83         init(capacity: Int) is old_style_init do
  84                 _capacity = capacity
  85                 _keys = new NativeArray[Int](capacity)
  86                 _values = new NativeArray[Int](capacity)
  87         end
  88 end
  89
  90 # An iterator over a `DummyArray`.
  91 class DummyIterator
  92         super Iterator[Int]
  93         private var array: DummyArray
  94         private var pos: Int
  95
  96         redef fun item: Int
  97         do
  98                 assert is_ok
  99                 return _array.value_at(_pos)
 100         end
 101
 102         redef fun is_ok: Bool
 103         do
 104                 return _pos < _array.length
 105         end
 106
 107         redef fun next do _pos = _pos + 1 end
 108
 109         # Initialize an iterator for `array`.
 110         init(array: DummyArray) is old_style_init do
 111                 _pos = 0
 112                 _array = array
 113         end
 114 end