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  * Copyright (C) 2009  Didier Villevalois
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
  21  *
  22  * Author:
  23  *      Jürg Billeter <j@bitron.ch>
  24  *      Didier 'Ptitjes Villevalois <ptitjes@free.fr>
  25  */
  26
  27 using GLib;
  28
  29 /**
  30  * Resizable array implementation of the {@link List} interface.
  31  *
  32  * The storage array grows automatically when needed.
  33  *
  34  * This implementation is pretty good for rarely modified data. Because they are
  35  * stored in an array this structure does not fit for highly mutable data. For an
  36  * alternative implementation see {@link LinkedList}.
  37  *
  38  * @see LinkedList
  39  */
  40 public class Gee.ArrayList<G> : AbstractBidirList<G> {
  41         /**
  42          * {@inheritDoc}
  43          */
  44         public override int size {
  45                 get { return _size; }
  46         }
  47
  48         /**
  49          * {@inheritDoc}
  50          */
  51         public override bool read_only {
  52                 get { return false; }
  53         }
  54
  55         /**
  56          * The elements' equality testing function.
  57          */
  58         [CCode (notify = false)]
  59         public EqualDataFunc<G> equal_func { private set; get; }
  60
  61         internal G[] _items = new G[4];
  62         internal int _size;
  63
  64         // concurrent modification protection
  65         private int _stamp = 0;
  66
  67         /**
  68          * Constructs a new, empty array list.
  69          *
  70          * If not provided, the function parameter is requested to the
  71          * {@link Functions} function factory methods.
  72          *
  73          * @param equal_func an optional element equality testing function
  74          */
  75         public ArrayList (owned EqualDataFunc<G>? equal_func = null) {
  76                 if (equal_func == null) {
  77                         equal_func = Functions.get_equal_func_for (typeof (G));
  78                 }
  79                 this.equal_func = equal_func;
  80         }
  81
  82         /**
  83          * {@inheritDoc}
  84          */
  85         public override Gee.Iterator<G> iterator () {
  86                 return new Iterator<G> (this);
  87         }
  88
  89         /**
  90          * {@inheritDoc}
  91          */
  92         public override ListIterator<G> list_iterator () {
  93                 return new Iterator<G> (this);
  94         }
  95
  96         /**
  97          * {@inheritDoc}
  98          */
  99         public override BidirListIterator<G> bidir_list_iterator () {
 100                 return new Iterator<G> (this);
 101         }
 102
 103         /**
 104          * {@inheritDoc}
 105          */
 106         public override bool contains (G item) {
 107                 return (index_of (item) != -1);
 108         }
 109
 110         /**
 111          * {@inheritDoc}
 112          */
 113         public override int index_of (G item) {
 114                 for (int index = 0; index < _size; index++) {
 115                         if (equal_func (_items[index], item)) {
 116                                 return index;
 117                         }
 118                 }
 119                 return -1;
 120         }
 121
 122         /**
 123          * {@inheritDoc}
 124          */
 125         public override G get (int index) {
 126                 assert (index >= 0);
 127                 assert (index < _size);
 128
 129                 return _items[index];
 130         }
 131
 132         /**
 133          * {@inheritDoc}
 134          */
 135         public override void set (int index, G item) {
 136                 assert (index >= 0);
 137                 assert (index < _size);
 138
 139                 _items[index] = item;
 140         }
 141
 142         /**
 143          * {@inheritDoc}
 144          */
 145         public override bool add (G item) {
 146                 if (_size == _items.length) {
 147                         grow_if_needed (1);
 148                 }
 149                 _items[_size++] = item;
 150                 _stamp++;
 151                 return true;
 152         }
 153
 154         /**
 155          * {@inheritDoc}
 156          */
 157         public override void insert (int index, G item) {
 158                 assert (index >= 0);
 159                 assert (index <= _size);
 160
 161                 if (_size == _items.length) {
 162                         grow_if_needed (1);
 163                 }
 164                 shift (index, 1);
 165                 _items[index] = item;
 166                 _stamp++;
 167         }
 168
 169         /**
 170          * {@inheritDoc}
 171          */
 172         public override bool remove (G item) {
 173                 for (int index = 0; index < _size; index++) {
 174                         if (equal_func (_items[index], item)) {
 175                                 remove_at (index);
 176                                 return true;
 177                         }
 178                 }
 179                 return false;
 180         }
 181
 182         /**
 183          * {@inheritDoc}
 184          */
 185         public override G remove_at (int index) {
 186                 assert (index >= 0);
 187                 assert (index < _size);
 188
 189                 G item = _items[index];
 190                 _items[index] = null;
 191
 192                 shift (index + 1, -1);
 193
 194                 _stamp++;
 195                 return item;
 196         }
 197
 198         /**
 199          * {@inheritDoc}
 200          */
 201         public override void clear () {
 202                 for (int index = 0; index < _size; index++) {
 203                         _items[index] = null;
 204                 }
 205                 _size = 0;
 206                 _stamp++;
 207         }
 208
 209         /**
 210          * {@inheritDoc}
 211          */
 212         public override List<G>? slice (int start, int stop) {
 213                 return_val_if_fail (start <= stop, null);
 214                 return_val_if_fail (start >= 0, null);
 215                 return_val_if_fail (stop <= _size, null);
 216
 217                 var slice = new ArrayList<G> (this.equal_func);
 218                 for (int i = start; i < stop; i++) {
 219                         slice.add (this[i]);
 220                 }
 221
 222                 return slice;
 223         }
 224
 225         /**
 226          * {@inheritDoc}
 227          */
 228         public bool add_all (Collection<G> collection) {
 229                 if (collection.is_empty) {
 230                         return false;
 231                 }
 232
 233                 grow_if_needed (collection.size);
 234                 foreach (G item in collection) {
 235                         _items[_size++] = item;
 236                 }
 237                 _stamp++;
 238                 return true;
 239         }
 240
 241         private void shift (int start, int delta) {
 242                 assert (start >= 0);
 243                 assert (start <= _size);
 244                 assert (start >= -delta);
 245
 246                 _items.move (start, start + delta, _size - start);
 247
 248                 _size += delta;
 249         }
 250
 251         private void grow_if_needed (int new_count) {
 252                 assert (new_count >= 0);
 253
 254                 int minimum_size = _size + new_count;
 255                 if (minimum_size > _items.length) {
 256                         // double the capacity unless we add even more items at this time
 257                         set_capacity (new_count > _items.length ? minimum_size : 2 * _items.length);
 258                 }
 259         }
 260
 261         private void set_capacity (int value) {
 262                 assert (value >= _size);
 263
 264                 _items.resize (value);
 265         }
 266
 267         private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G>, BidirIterator<G>, ListIterator<G>, BidirListIterator<G> {
 268                 private ArrayList<G> _list;
 269                 private int _index = -1;
 270                 private bool _removed = false;
 271
 272                 // concurrent modification protection
 273                 private int _stamp = 0;
 274
 275                 public Iterator (ArrayList list) {
 276                         _list = list;
 277                         _stamp = _list._stamp;
 278                 }
 279
 280                 public bool next () {
 281                         assert (_stamp == _list._stamp);
 282                         if (_index + 1 < _list._size) {
 283                                 _index++;
 284                                 _removed = false;
 285                                 return true;
 286                         }
 287                         return false;
 288                 }
 289
 290                 public bool has_next () {
 291                         assert (_stamp == _list._stamp);
 292                         return (_index + 1 < _list._size);
 293                 }
 294
 295                 public bool first () {
 296                         assert (_stamp == _list._stamp);
 297                         if (_list.size == 0) {
 298                                 return false;
 299                         }
 300                         _index = 0;
 301                         _removed = false;
 302                         return true;
 303                 }
 304
 305                 public new G get () {
 306                         assert (_stamp == _list._stamp);
 307                         assert (_index >= 0);
 308                         assert (_index < _list._size);
 309                         assert (! _removed);
 310                         return _list._items[_index];
 311                 }
 312
 313                 public void remove () {
 314                         assert (_stamp == _list._stamp);
 315                         assert (_index >= 0);
 316                         assert (_index < _list._size);
 317                         assert (! _removed);
 318                         _list.remove_at (_index);
 319                         _index--;
 320                         _removed = true;
 321                         _stamp = _list._stamp;
 322                 }
 323
 324                 public bool previous () {
 325                         assert (_stamp == _list._stamp);
 326                         if (_index > 0) {
 327                                 _index--;
 328                                 return true;
 329                         }
 330                         return false;
 331                 }
 332
 333                 public bool has_previous () {
 334                         assert (_stamp == _list._stamp);
 335                         return (_index - 1 >= 0);
 336                 }
 337
 338                 public bool last () {
 339                         assert (_stamp == _list._stamp);
 340                         if (_list.size == 0) {
 341                                 return false;
 342                         }
 343                         _index = _list._size - 1;
 344                         return true;
 345                 }
 346
 347                 public new void set (G item) {
 348                         assert (_stamp == _list._stamp);
 349                         assert (_index >= 0);
 350                         assert (_index < _list._size);
 351                         _list._items[_index] = item;
 352                         _stamp = ++_list._stamp;
 353                 }
 354
 355                 public void insert (G item) {
 356                         assert (_stamp == _list._stamp);
 357                         assert (_index >= 0);
 358                         assert (_index < _list._size);
 359                         _list.insert (_index, item);
 360                         _index++;
 361                         _stamp = _list._stamp;
 362                 }
 363
 364                 public void add (G item) {
 365                         assert (_stamp == _list._stamp);
 366                         assert (_index >= 0);
 367                         assert (_index < _list._size);
 368                         _list.insert (_index + 1, item);
 369                         _index++;
 370                         _stamp = _list._stamp;
 371                 }
 372
 373                 public int index () {
 374                         assert (_stamp == _list._stamp);
 375                         assert (_index >= 0);
 376                         assert (_index < _list._size);
 377                         return _index;
 378                 }
 379
 380                 public bool read_only {
 381                         get {
 382                                 return false;
 383                         }
 384                 }
 385
 386                 public bool valid {
 387                         get {
 388                                 return _index >= 0 && _index < _list._size && ! _removed;
 389                         }
 390                 }
 391
 392                 public void foreach (ForallFunc<G> f) {
 393                         assert (_stamp == _list._stamp);
 394                         if (_index < 0 || _removed)
 395                                 _index++;
 396                         while (_index < _list._size) {
 397                                 f (_list._items[_index]);
 398                                 _index++;
 399                         }
 400                         _index = _list._size;
 401                 }
 402         }
 403 }
 404