gee/arrayqueue.vala

   1 /* arrayqueue.vala
   2  *
   3  * Copyright (C) 2012  Maciej Piechotka
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2.1 of the License, or (at your option) any later version.
   9
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14
  15  * You should have received a copy of the GNU Lesser General Public
  16  * License along with this library; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
  18  *
  19  * Author:
  20  *      Maciej Piechotka <uzytkownik2@gmail.com>
  21  */
  22
  23 /**
  24  * Resizable array implementation of the {@link Deque} interface.
  25  *
  26  * The storage array grows automatically when needed.
  27  *
  28  * This implementation is pretty good for lookups at the end or random.
  29  * Because they are stored in an array this structure does not fit for deleting
  30  * arbitrary elements. For an alternative implementation see {@link LinkedList}.
  31  *
  32  * @see LinkedList
  33  */
  34 public class Gee.ArrayQueue<G> : Gee.AbstractQueue<G>, Deque<G> {
  35         /**
  36          * Constructs a new, empty array queue.
  37          *
  38          * If not provided, the function parameter is requested to the
  39          * {@link Functions} function factory methods.
  40          *
  41          * @param equal_func an optional element equality testing function
  42          */
  43         public ArrayQueue (owned EqualDataFunc<G>? equal_func = null) {
  44                 if (equal_func == null) {
  45                         equal_func = Functions.get_equal_func_for (typeof (G));
  46                 }
  47                 this.equal_func = equal_func;
  48                 this._items = new G[10];
  49         }
  50
  51         [CCode (notify = false)]
  52         public EqualDataFunc<G> equal_func { private set; get; }
  53
  54         /**
  55          * {@inheritDoc}
  56          */
  57         public override int size { get { return _length; } }
  58
  59         public bool is_empty { get { return _length == 0; } }
  60
  61         /**
  62          * {@inheritDoc}
  63          */
  64         public override bool read_only { get { return false; } }
  65
  66         /**
  67          * {@inheritDoc}
  68          */
  69         public override int capacity { get {return Queue.UNBOUNDED_CAPACITY;} }
  70
  71         /**
  72          * {@inheritDoc}
  73          */
  74         public override int remaining_capacity { get {return Queue.UNBOUNDED_CAPACITY;} }
  75
  76         /**
  77          * {@inheritDoc}
  78          */
  79         public override bool is_full { get { return false; } }
  80
  81         /**
  82          * {@inheritDoc}
  83          */
  84         public override Gee.Iterator<G> iterator() {
  85                 return new Iterator<G> (this);
  86         }
  87
  88         /**
  89          * {@inheritDoc}
  90          */
  91         public override bool add (G element) {
  92                 return offer_tail (element);
  93         }
  94
  95         /**
  96          * {@inheritDoc}
  97          */
  98         public override bool contains (G item) {
  99                 return find_index(item) != -1;
 100         }
 101
 102         /**
 103          * {@inheritDoc}
 104          */
 105         public override bool remove (G item) {
 106                 _stamp++;
 107                 int index = find_index (item);
 108                 if (index == -1) {
 109                         return false;
 110                 } else {
 111                         remove_at (index);
 112                         return true;
 113                 }
 114         }
 115
 116         /**
 117          * {@inheritDoc}
 118          */
 119         public override void clear() {
 120                 _stamp++;
 121                 for (int i = 0; i < _length; i++) {
 122                         _items[(_start + i) % _items.length] = null;
 123                 }
 124                 _start = _length = 0;
 125         }
 126
 127         /**
 128          * {@inheritDoc}
 129          */
 130         public override G? peek () {
 131                 return peek_head ();
 132         }
 133
 134         /**
 135          * {@inheritDoc}
 136          */
 137         public override G? poll () {
 138                 return poll_head ();
 139         }
 140
 141         /**
 142          * {@inheritDoc}
 143          */
 144         public bool offer_head (G element) {
 145                 grow_if_needed ();
 146                 _start = (_items.length + _start - 1) % _items.length;
 147                 _length++;
 148                 _items[_start] = element;
 149                 _stamp++;
 150                 return true;
 151         }
 152
 153         /**
 154          * {@inheritDoc}
 155          */
 156         public G? peek_head () {
 157                 return _items[_start];
 158         }
 159
 160         /**
 161          * {@inheritDoc}
 162          */
 163         public G? poll_head () {
 164                 _stamp++;
 165                 if (_length == 0) {
 166                         _start = 0;
 167                         return null;
 168                 } else {
 169                         _length--;
 170                         G result = (owned)_items[_start];
 171                         _start = (_start + 1) % _items.length;
 172                         return (owned)result;
 173                 }
 174         }
 175
 176         /**
 177          * {@inheritDoc}
 178          */
 179         public int drain_head (Collection<G> recipient, int amount = -1) {
 180                 return drain (recipient, amount);
 181         }
 182
 183         /**
 184          * {@inheritDoc}
 185          */
 186         public bool offer_tail (G element) {
 187                 grow_if_needed();
 188                 _items[(_start + _length++) % _items.length] = element;
 189                 _stamp++;
 190                 return true;
 191         }
 192
 193         /**
 194          * {@inheritDoc}
 195          */
 196         public G? peek_tail () {
 197                 return _items[(_items.length + _start + _length - 1) % _items.length];
 198         }
 199
 200         /**
 201          * {@inheritDoc}
 202          */
 203         public G? poll_tail () {
 204                 _stamp++;
 205                 if (_length == 0) {
 206                         _start = 0;
 207                         return null;
 208                 } else {
 209                         return (owned)_items[(_items.length + _start + --_length) % _items.length];
 210                 }
 211         }
 212
 213         /**
 214          * {@inheritDoc}
 215          */
 216         public int drain_tail (Collection<G> recipient, int amount = -1) {
 217                 G? item = null;
 218                 int drained = 0;
 219                 while((amount == -1 || --amount >= 0) && (item = poll_tail ()) != null) {
 220                         recipient.add(item);
 221                         drained++;
 222                 }
 223                 return drained;
 224         }
 225
 226         /**
 227          * {@inheritDoc}
 228          */
 229         private void grow_if_needed () {
 230                 if (_items.length < _length +1 ) {
 231                         _items.resize (2 * _items.length);
 232 #if 0
 233                         _items.move (0, _length, _start);
 234 #else
 235                         // See bug #667452
 236                         for(int i = 0; i < _start; i++)
 237                                 _items[_length + i] = (owned)_items[i];
 238 #endif
 239                 }
 240         }
 241
 242         private int find_index (G item) {
 243                 for (int i = _start; i < int.min(_items.length, _start + _length); i++) {
 244                         if (equal_func(item, _items[i])) {
 245                                 return i;
 246                         }
 247                 }
 248                 for (int i = 0; i < _start + _length - _items.length; i++) {
 249                         if (equal_func(item, _items[i])) {
 250                                 return i;
 251                         }
 252                 }
 253                 return -1;
 254         }
 255
 256         private void remove_at (int index) {
 257                 int end = (_items.length + _start + _length - 1) % _items.length + 1;
 258                 if (index == _start) {
 259                         _items[_start++] = null;
 260                         _length--;
 261                         return;
 262                 } else if (index > _start && end <= _start) {
 263                         _items[index] = null;
 264                         _items.move (index + 1, index, _items.length - 1);
 265                         _items[_items.length - 1] = (owned)_items[0];
 266                         _items.move (1, 0, end - 1);
 267                         _length--;
 268                 } else {
 269                         _items[index] = null;
 270                         _items.move (index + 1, index, end - (index + 1));
 271                         _length--;
 272                 }
 273         }
 274
 275         private class Iterator<G> : GLib.Object, Traversable<G>, Gee.Iterator<G> {
 276                 public Iterator (ArrayQueue<G> queue) {
 277                         _queue = queue;
 278                         _stamp = _queue._stamp;
 279                 }
 280
 281                 public bool next () {
 282                         assert (_queue._stamp == _stamp);
 283                         if (has_next ()) {
 284                                 _offset++;
 285                                 _removed = false;
 286                                 return true;
 287                         } else {
 288                                 return false;
 289                         }
 290                 }
 291
 292                 public bool has_next () {
 293                         assert (_queue._stamp == _stamp);
 294                         return _offset + 1 < _queue._length;
 295                 }
 296
 297                 public new G get () {
 298                         assert (_queue._stamp == _stamp);
 299                         assert (_offset != -1);
 300                         assert (!_removed);
 301                         return _queue._items[(_queue._start + _offset) % _queue._items.length];
 302                 }
 303
 304                 public void remove () {
 305                         assert (_queue._stamp++ == _stamp++);
 306                         _queue.remove_at((_queue._start + _offset) % _queue._items.length);
 307                         _offset--;
 308                         _removed = true;
 309                 }
 310
 311                 public bool valid { get {return _offset != -1 && !_removed;} }
 312
 313                 public bool read_only { get {return false;} }
 314
 315                 public bool foreach (ForallFunc<G> f) {
 316                         assert (_queue._stamp == _stamp);
 317                         if (!valid) {
 318                                 _offset++;
 319                                 _removed = false;
 320                         }
 321                         for (int i = _offset; i < _queue._length; i++) {
 322                                 if (!f (_queue._items[(_queue._start + i) % _queue._items.length])) {
 323                                         _offset = i;
 324                                         return false;
 325                                 }
 326                         }
 327                         return true;
 328                 }
 329
 330                 private ArrayQueue _queue;
 331                 private int _stamp;
 332                 private int _offset = -1;
 333                 private bool _removed = false;
 334         }
 335
 336         private G[] _items;
 337         private int _start = 0;
 338         private int _length = 0;
 339         private int _stamp = 0;
 340 }
 341