gee/arraylist.vala

   1 /* arraylist.vala
   2  *
   3  * Copyright (C) 2004-2005  Novell, Inc
   4  * Copyright (C) 2005  David Waite
   5  * Copyright (C) 2007-2008  Jürg Billeter
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with this library; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
  20  *
  21  * Author:
  22  *      Jürg Billeter <j@bitron.ch>
  23  */
  24
  25 using GLib;
  26
  27 /**
  28  * Arrays of arbitrary elements which grow automatically as elements are added.
  29  */
  30 public class Vala.ArrayList<G> : List<G> {
  31         public override int size {
  32                 get { return _size; }
  33         }
  34
  35         public EqualFunc<G> equal_func {
  36                 set { _equal_func = value; }
  37         }
  38
  39         internal G[] _items = new G[4];
  40         internal int _size;
  41         private EqualFunc<G> _equal_func;
  42
  43         // concurrent modification protection
  44         private int _stamp = 0;
  45
  46         public ArrayList (EqualFunc<G> equal_func = GLib.direct_equal) {
  47                 this.equal_func = equal_func;
  48         }
  49
  50         public override Type get_element_type () {
  51                 return typeof (G);
  52         }
  53
  54         public override Vala.Iterator<G> iterator () {
  55                 return new Iterator<G> (this);
  56         }
  57
  58         public override bool contains (G item) {
  59                 return (index_of (item) != -1);
  60         }
  61
  62         public override int index_of (G item) {
  63                 for (int index = 0; index < _size; index++) {
  64                         if (_equal_func (_items[index], item)) {
  65                                 return index;
  66                         }
  67                 }
  68                 return -1;
  69         }
  70
  71         public override G? get (int index) {
  72                 assert (index >= 0 && index < _size);
  73
  74                 return _items[index];
  75         }
  76
  77         public override void set (int index, G item) {
  78                 assert (index >= 0 && index < _size);
  79
  80                 _items[index] = item;
  81         }
  82
  83         public override bool add (G item) {
  84                 if (_size == _items.length) {
  85                         grow_if_needed (1);
  86                 }
  87                 _items[_size++] = item;
  88                 _stamp++;
  89                 return true;
  90         }
  91
  92         public override void insert (int index, G item) {
  93                 assert (index >= 0 && index <= _size);
  94
  95                 if (_size == _items.length) {
  96                         grow_if_needed (1);
  97                 }
  98                 shift (index, 1);
  99                 _items[index] = item;
 100                 _stamp++;
 101         }
 102
 103         public override bool remove (G item) {
 104                 for (int index = 0; index < _size; index++) {
 105                         if (_equal_func (_items[index], item)) {
 106                                 remove_at (index);
 107                                 return true;
 108                         }
 109                 }
 110                 return false;
 111         }
 112
 113         public override G remove_at (int index) {
 114                 assert (index >= 0 && index < _size);
 115
 116                 G item = _items[index];
 117                 _items[index] = null;
 118
 119                 shift (index + 1, -1);
 120
 121                 _stamp++;
 122                 return item;
 123         }
 124
 125         public override void clear () {
 126                 for (int index = 0; index < _size; index++) {
 127                         _items[index] = null;
 128                 }
 129                 _size = 0;
 130                 _stamp++;
 131         }
 132
 133         private void shift (int start, int delta) {
 134                 assert (start >= 0 && start <= _size && start >= -delta);
 135
 136                 _items.move (start, start + delta, _size - start);
 137
 138                 _size += delta;
 139         }
 140
 141         private void grow_if_needed (int new_count) {
 142                 assert (new_count >= 0);
 143
 144                 int minimum_size = _size + new_count;
 145                 if (minimum_size > _items.length) {
 146                         // double the capacity unless we add even more items at this time
 147                         set_capacity (new_count > _items.length ? minimum_size : 2 * _items.length);
 148                 }
 149         }
 150
 151         private void set_capacity (int value) {
 152                 assert (value >= _size);
 153
 154                 _items.resize (value);
 155         }
 156
 157         private class Iterator<G> : Vala.Iterator<G> {
 158                 public ArrayList<G> list {
 159                         set {
 160                                 _list = value;
 161                                 _stamp = _list._stamp;
 162                         }
 163                 }
 164
 165                 private ArrayList<G> _list;
 166                 private int _index = -1;
 167                 protected bool _removed = false;
 168
 169                 // concurrent modification protection
 170                 public int _stamp = 0;
 171
 172                 public Iterator (ArrayList list) {
 173                         this.list = list;
 174                 }
 175
 176                 public override bool next () {
 177                         assert (_stamp == _list._stamp);
 178                         if (_index < _list._size) {
 179                                 _index++;
 180                                 _removed = false;
 181                         }
 182                         return (_index < _list._size);
 183                 }
 184
 185                 public override bool has_next () {
 186                         assert (_stamp == _list._stamp);
 187                         return (_index + 1 < _list._size);
 188                 }
 189
 190                 public override G? get () {
 191                         assert (_stamp == _list._stamp);
 192                         assert (! _removed);
 193
 194                         if (_index < 0 || _index >= _list._size) {
 195                                 return null;
 196                         }
 197
 198                         return _list.get (_index);
 199                 }
 200
 201                 public override void remove () {
 202                         assert (_stamp == _list._stamp);
 203                         assert (! _removed && _index >= 0);
 204                         assert (_index < _list._size);
 205
 206                         _list.remove_at (_index);
 207                         _index--;
 208                         _removed = true;
 209                         _stamp = _list._stamp;
 210                 }
 211
 212                 public override bool valid {
 213                         get {
 214                                 return _index >= 0 && _index < _list._size && ! _removed;
 215                         }
 216                 }
 217         }
 218 }
 219