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 #
   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 class DummyArray
  14         super Set[Int]
  15         private var capacity: Int
  16         redef var length: Int
  17         private var keys: NativeArray[Int]
  18         private var values: NativeArray[Int]
  19
  20         redef fun add(value: Int)
  21         do
  22                 assert full: _length < (_capacity-1)
  23                 var l = _length
  24                 _values[l] = value
  25                 _keys[value] = l
  26                 _length = l + 1
  27         end
  28
  29         redef fun remove(value: Int)
  30         do
  31                 assert not is_empty
  32                 var l = _length
  33                 if l > 1 then
  34                         var last = _values[l - 1]
  35                         var pos = _keys[value]
  36                         _keys[last] = pos
  37                         _values[pos] = last
  38                 end
  39                 _length = l - 1
  40         end
  41
  42         redef fun has(value: Int): Bool
  43         do
  44                 assert value < _capacity
  45                 var pos = _keys[value]
  46                 if pos < _length then
  47                         return _values[pos] == value
  48                 end
  49                 return false
  50         end
  51
  52         redef fun first: Int
  53         do
  54                 assert _length > 0
  55                 return _values[0]
  56         end
  57
  58         redef fun is_empty: Bool
  59         do
  60                 return not (_length > 0)
  61         end
  62
  63         redef fun clear
  64         do
  65                 _length = 0
  66         end
  67
  68         redef fun iterator: DummyIterator
  69         do
  70                 return new DummyIterator(self)
  71         end
  72
  73         private fun value_at(pos: Int): Int
  74         do
  75                 return _values[pos]
  76         end
  77
  78         init(capacity: Int)
  79         do
  80                 _capacity = capacity
  81                 _keys = new NativeArray[Int](capacity)
  82                 _values = new NativeArray[Int](capacity)
  83         end
  84 end
  85
  86 class DummyIterator
  87         super Iterator[Int]
  88         private var array: DummyArray
  89         private var pos: Int
  90
  91         redef fun item: Int
  92         do
  93                 assert is_ok
  94                 return _array.value_at(_pos)
  95         end
  96
  97         redef fun is_ok: Bool
  98         do
  99                 return _pos < _array.length
 100         end
 101
 102         redef fun next do _pos = _pos + 1 end
 103
 104         init(array: DummyArray)
 105         do
 106                 _pos = 0
 107                 _array = array
 108         end
 109 end