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;
  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                 _items = new G[4];
  81                 _size = 0;
  82         }
  83
  84         /**
  85          * Constructs a new array list based on provided array.
  86          *
  87          * If not provided, the function parameter is requested to the
  88          * {@link Functions} function factory methods.
  89          *
  90          * @param items initial items to be put into array
  91          * @param equal_func an optional element equality testing function
  92          */
  93         public ArrayList.wrap (owned G[] items, owned EqualDataFunc<G>? equal_func = null) {
  94                 if (equal_func == null) {
  95                         equal_func = Functions.get_equal_func_for (typeof (G));
  96                 }
  97                 this.equal_func = equal_func;
  98                 _items = items;
  99                 _size = items.length;
 100         }
 101
 102         /**
 103          * {@inheritDoc}
 104          */
 105         public override bool foreach(ForallFunc<G> f) {
 106                 for (int i = 0; i < _size; i++) {
 107                         if (!f (_items[i])) {
 108                                 return false;
 109                         }
 110                 }
 111                 return true;
 112         }
 113
 114         /**
 115          * {@inheritDoc}
 116          */
 117         public override Gee.Iterator<G> iterator () {
 118                 return new Iterator<G> (this);
 119         }
 120
 121         /**
 122          * {@inheritDoc}
 123          */
 124         public override ListIterator<G> list_iterator () {
 125                 return new Iterator<G> (this);
 126         }
 127
 128         /**
 129          * {@inheritDoc}
 130          */
 131         public override BidirListIterator<G> bidir_list_iterator () {
 132                 return new Iterator<G> (this);
 133         }
 134
 135         /**
 136          * {@inheritDoc}
 137          */
 138         public override bool contains (G item) {
 139                 return (index_of (item) != -1);
 140         }
 141
 142         /**
 143          * {@inheritDoc}
 144          */
 145         public override int index_of (G item) {
 146                 for (int index = 0; index < _size; index++) {
 147                         if (equal_func (_items[index], item)) {
 148                                 return index;
 149                         }
 150                 }
 151                 return -1;
 152         }
 153
 154         /**
 155          * {@inheritDoc}
 156          */
 157         public override G get (int index) {
 158                 assert (index >= 0);
 159                 assert (index < _size);
 160
 161                 return _items[index];
 162         }
 163
 164         /**
 165          * {@inheritDoc}
 166          */
 167         public override void set (int index, G item) {
 168                 assert (index >= 0);
 169                 assert (index < _size);
 170
 171                 _items[index] = item;
 172         }
 173
 174         /**
 175          * {@inheritDoc}
 176          */
 177         public override bool add (G item) {
 178                 if (_size == _items.length) {
 179                         grow_if_needed (1);
 180                 }
 181                 _items[_size++] = item;
 182                 _stamp++;
 183                 return true;
 184         }
 185
 186         /**
 187          * {@inheritDoc}
 188          */
 189         public override void insert (int index, G item) {
 190                 assert (index >= 0);
 191                 assert (index <= _size);
 192
 193                 if (_size == _items.length) {
 194                         grow_if_needed (1);
 195                 }
 196                 shift (index, 1);
 197                 _items[index] = item;
 198                 _stamp++;
 199         }
 200
 201         /**
 202          * {@inheritDoc}
 203          */
 204         public override bool remove (G item) {
 205                 for (int index = 0; index < _size; index++) {
 206                         if (equal_func (_items[index], item)) {
 207                                 remove_at (index);
 208                                 return true;
 209                         }
 210                 }
 211                 return false;
 212         }
 213
 214         /**
 215          * {@inheritDoc}
 216          */
 217         public override G remove_at (int index) {
 218                 assert (index >= 0);
 219                 assert (index < _size);
 220
 221                 G item = _items[index];
 222                 _items[index] = null;
 223
 224                 shift (index + 1, -1);
 225
 226                 _stamp++;
 227                 return item;
 228         }
 229
 230         /**
 231          * {@inheritDoc}
 232          */
 233         public override void clear () {
 234                 for (int index = 0; index < _size; index++) {
 235                         _items[index] = null;
 236                 }
 237                 _size = 0;
 238                 _stamp++;
 239         }
 240
 241         /**
 242          * {@inheritDoc}
 243          */
 244         public override List<G>? slice (int start, int stop) {
 245                 return_val_if_fail (start <= stop, null);
 246                 return_val_if_fail (start >= 0, null);
 247                 return_val_if_fail (stop <= _size, null);
 248
 249                 var slice = new ArrayList<G> (this.equal_func);
 250                 for (int i = start; i < stop; i++) {
 251                         slice.add (this[i]);
 252                 }
 253
 254                 return slice;
 255         }
 256
 257         /**
 258          * {@inheritDoc}
 259          */
 260         public bool add_all (Collection<G> collection) {
 261                 if (collection.is_empty) {
 262                         return false;
 263                 }
 264
 265                 grow_if_needed (collection.size);
 266                 collection.foreach ((item) => {_items[_size++] = item; return true;});
 267                 _stamp++;
 268                 return true;
 269         }
 270
 271         private void shift (int start, int delta) {
 272                 assert (start >= 0);
 273                 assert (start <= _size);
 274                 assert (start >= -delta);
 275
 276                 _items.move (start, start + delta, _size - start);
 277
 278                 _size += delta;
 279         }
 280
 281         private void grow_if_needed (int new_count) {
 282                 assert (new_count >= 0);
 283
 284                 int minimum_size = _size + new_count;
 285                 if (minimum_size > _items.length) {
 286                         // double the capacity unless we add even more items at this time
 287                         set_capacity (new_count > _items.length ? minimum_size : 2 * _items.length);
 288                 }
 289         }
 290
 291         private void set_capacity (int value) {
 292                 assert (value >= _size);
 293
 294                 _items.resize (value);
 295         }
 296
 297         private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G>, BidirIterator<G>, ListIterator<G>, BidirListIterator<G> {
 298                 private ArrayList<G> _list;
 299                 private int _index = -1;
 300                 private bool _removed = false;
 301
 302                 // concurrent modification protection
 303                 private int _stamp = 0;
 304
 305                 public Iterator (ArrayList list) {
 306                         _list = list;
 307                         _stamp = _list._stamp;
 308                 }
 309
 310                 public bool next () {
 311                         assert (_stamp == _list._stamp);
 312                         if (_index + 1 < _list._size) {
 313                                 _index++;
 314                                 _removed = false;
 315                                 return true;
 316                         }
 317                         return false;
 318                 }
 319
 320                 public bool has_next () {
 321                         assert (_stamp == _list._stamp);
 322                         return (_index + 1 < _list._size);
 323                 }
 324
 325                 public bool first () {
 326                         assert (_stamp == _list._stamp);
 327                         if (_list.size == 0) {
 328                                 return false;
 329                         }
 330                         _index = 0;
 331                         _removed = false;
 332                         return true;
 333                 }
 334
 335                 public new G get () {
 336                         assert (_stamp == _list._stamp);
 337                         assert (_index >= 0);
 338                         assert (_index < _list._size);
 339                         assert (! _removed);
 340                         return _list._items[_index];
 341                 }
 342
 343                 public void remove () {
 344                         assert (_stamp == _list._stamp);
 345                         assert (_index >= 0);
 346                         assert (_index < _list._size);
 347                         assert (! _removed);
 348                         _list.remove_at (_index);
 349                         _index--;
 350                         _removed = true;
 351                         _stamp = _list._stamp;
 352                 }
 353
 354                 public bool previous () {
 355                         assert (_stamp == _list._stamp);
 356                         if (_index > 0) {
 357                                 _index--;
 358                                 return true;
 359                         }
 360                         return false;
 361                 }
 362
 363                 public bool has_previous () {
 364                         assert (_stamp == _list._stamp);
 365                         return (_index - 1 >= 0);
 366                 }
 367
 368                 public bool last () {
 369                         assert (_stamp == _list._stamp);
 370                         if (_list.size == 0) {
 371                                 return false;
 372                         }
 373                         _index = _list._size - 1;
 374                         return true;
 375                 }
 376
 377                 public new void set (G item) {
 378                         assert (_stamp == _list._stamp);
 379                         assert (_index >= 0);
 380                         assert (_index < _list._size);
 381                         _list._items[_index] = item;
 382                         _stamp = ++_list._stamp;
 383                 }
 384
 385                 public void insert (G item) {
 386                         assert (_stamp == _list._stamp);
 387                         assert (_index >= 0);
 388                         assert (_index < _list._size);
 389                         _list.insert (_index, item);
 390                         _index++;
 391                         _stamp = _list._stamp;
 392                 }
 393
 394                 public void add (G item) {
 395                         assert (_stamp == _list._stamp);
 396                         assert (_index >= 0);
 397                         assert (_index < _list._size);
 398                         _list.insert (_index + 1, item);
 399                         _index++;
 400                         _stamp = _list._stamp;
 401                 }
 402
 403                 public int index () {
 404                         assert (_stamp == _list._stamp);
 405                         assert (_index >= 0);
 406                         assert (_index < _list._size);
 407                         return _index;
 408                 }
 409
 410                 public bool read_only {
 411                         get {
 412                                 return false;
 413                         }
 414                 }
 415
 416                 public bool valid {
 417                         get {
 418                                 return _index >= 0 && _index < _list._size && ! _removed;
 419                         }
 420                 }
 421
 422                 public bool foreach (ForallFunc<G> f) {
 423                         assert (_stamp == _list._stamp);
 424                         if (_index < 0 || _removed) {
 425                                 _index++;
 426                         }
 427                         while (_index < _list._size) {
 428                                 if (!f (_list._items[_index])) {
 429                                         return false;
 430                                 }
 431                                 _index++;
 432                         }
 433                         _index = _list._size - 1;
 434                         return true;
 435                 }
 436         }
 437 }
 438