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