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         super ArrayCapable[Int]
  16         var _capacity: Int
  17         var _length: Int
  18         redef fun length do return _length
  19         var _keys: NativeArray[Int]
  20         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         init(capacity: Int)
  81         do
  82                 _capacity = capacity
  83                 _keys = calloc_array(capacity)
  84                 _values = calloc_array(capacity)
  85         end
  86 end
  87
  88 class DummyIterator
  89         super Iterator[Int]
  90         var _array: DummyArray
  91         var _pos: Int
  92
  93         redef fun item: Int
  94         do
  95                 assert is_ok
  96                 return _array.value_at(_pos)
  97         end
  98
  99         redef fun is_ok: Bool
 100         do
 101                 return _pos < _array.length
 102         end
 103
 104         redef fun next do _pos = _pos + 1 end
 105
 106         init(array: DummyArray)
 107         do
 108                 _pos = 0
 109                 _array = array
 110         end
 111 end