gee/linkedlist.vala

   1 /* linkedlist.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  Mark Lee, 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  *      Mark Lee <marklee@src.gnome.org>
  24  *      Didier 'Ptitjes Villevalois <ptitjes@free.fr>
  25  */
  26
  27 /**
  28  * Doubly-linked list implementation of the {@link List} interface.
  29  *
  30  * This implementation is pretty well designed for highly mutable data. When
  31  * indexed access is privileged prefer using {@link ArrayList}.
  32  *
  33  * @see ArrayList
  34  */
  35 public class Gee.LinkedList<G> : AbstractBidirList<G>, Queue<G>, Deque<G> {
  36         private int _size = 0;
  37         private int _stamp = 0;
  38         private Node<G>? _head = null;
  39         private weak Node<G>? _tail = null;
  40
  41         /**
  42          * The elements' equality testing function.
  43          */
  44         [CCode (notify = false)]
  45         public EqualDataFunc<G> equal_func { private set; get; }
  46
  47         /**
  48          * Constructs a new, empty linked list.
  49          *
  50          * If not provided, the function parameter is requested to the
  51          * {@link Functions} function factory methods.
  52          *
  53          * @param equal_func an optional element equality testing function
  54          */
  55         public LinkedList (owned EqualDataFunc<G>? equal_func = null) {
  56                 if (equal_func == null) {
  57                         equal_func = Functions.get_equal_func_for (typeof (G));
  58                 }
  59                 this.equal_func = equal_func;
  60         }
  61
  62         ~LinkedList () {
  63                 this.clear ();
  64         }
  65
  66         /**
  67          * {@inheritDoc}
  68          */
  69         public override bool foreach(ForallFunc<G> f) {
  70                 for (weak Node<G>? node = _head; node != null; node = node.next) {
  71                         if (!f (node.data)) {
  72                                 return false;
  73                         }
  74                 }
  75                 return true;
  76         }
  77
  78         /**
  79          * {@inheritDoc}
  80          */
  81         public override Gee.Iterator<G> iterator () {
  82                 return new Iterator<G> (this);
  83         }
  84
  85         /**
  86          * {@inheritDoc}
  87          */
  88         public override ListIterator<G> list_iterator () {
  89                 return new Iterator<G> (this);
  90         }
  91
  92         /**
  93          * {@inheritDoc}
  94          */
  95         public override BidirListIterator<G> bidir_list_iterator () {
  96                 return new Iterator<G> (this);
  97         }
  98
  99         /**
 100          * {@inheritDoc}
 101          */
 102         public override int size {
 103                 get { return this._size; }
 104         }
 105
 106         /**
 107          * {@inheritDoc}
 108          */
 109         public override bool read_only {
 110                 get { return false; }
 111         }
 112
 113         /**
 114          * {@inheritDoc}
 115          */
 116         public override bool contains (G item) {
 117                 return this.index_of (item) != -1;
 118         }
 119
 120         /**
 121          * {@inheritDoc}
 122          */
 123         public override bool add (G item) {
 124                 Node<G> n = new Node<G> (item);
 125                 if (this._head == null && this._tail == null) {
 126                         this._tail = n;
 127                         this._head = (owned) n;
 128                 } else {
 129                         n.prev = this._tail;
 130                         this._tail.next = (owned) n;
 131                         this._tail = this._tail.next;
 132                 }
 133
 134                 // Adding items to the list during iterations is allowed.
 135                 //++this._stamp;
 136
 137                 this._size++;
 138                 return true;
 139         }
 140
 141         /**
 142          * {@inheritDoc}
 143          */
 144         public override bool remove (G item) { // Should remove only the first occurence (a test should be added)
 145                 for (weak Node<G> n = this._head; n != null; n = n.next) {
 146                         if (this.equal_func (item, n.data)) {
 147                                 this._remove_node (n);
 148                                 return true;
 149                         }
 150                 }
 151                 return false;
 152         }
 153
 154         /**
 155          * {@inheritDoc}
 156          */
 157         public override void clear () {
 158                 while (_head != null) {
 159                         _remove_node (_head);
 160                 }
 161
 162                 ++this._stamp;
 163                 this._head = null;
 164                 this._tail = null;
 165                 this._size = 0;
 166         }
 167
 168         /**
 169          * {@inheritDoc}
 170          */
 171         public override G get (int index) {
 172                 assert (index >= 0);
 173                 assert (index < this._size);
 174
 175                 unowned Node<G>? n = this._get_node_at (index);
 176                 assert (n != null);
 177                 return n.data;
 178         }
 179
 180         /**
 181          * {@inheritDoc}
 182          */
 183         public override void set (int index, G item) {
 184                 assert (index >= 0);
 185                 assert (index < this._size);
 186
 187                 unowned Node<G>? n = this._get_node_at (index);
 188                 return_if_fail (n != null);
 189                 n.data = item;
 190         }
 191
 192         /**
 193          * {@inheritDoc}
 194          */
 195         public override int index_of (G item) {
 196                 int idx = 0;
 197                 for (weak Node<G>? node = _head; node != null; node = node.next, idx++) {
 198                         if (this.equal_func (item, node.data)) {
 199                                 return idx;
 200                         }
 201                 }
 202                 return -1;
 203         }
 204
 205         /**
 206          * {@inheritDoc}
 207          */
 208         public override void insert (int index, G item) {
 209                 assert (index >= 0);
 210                 assert (index <= this._size);
 211
 212                 if (index == this._size) {
 213                         this.add (item);
 214                 } else {
 215                         Node<G> n = new Node<G> (item);
 216                         if (index == 0) {
 217                                 n.next = (owned) this._head;
 218                                 n.next.prev = n;
 219                                 this._head = (owned)n;
 220                         } else {
 221                                 weak Node prev = this._head;
 222                                 for (int i = 0; i < index - 1; i++) {
 223                                         prev = prev.next;
 224                                 }
 225                                 n.prev = prev;
 226                                 n.next = (owned) prev.next;
 227                                 n.next.prev = n;
 228                                 prev.next = (owned) n;
 229                         }
 230
 231                         // Adding items to the list during iterations is allowed.
 232                         //++this._stamp;
 233
 234                         this._size++;
 235                 }
 236         }
 237
 238         /**
 239          * {@inheritDoc}
 240          */
 241         public override G remove_at (int index) {
 242                 assert (index >= 0);
 243                 assert (index < this._size);
 244
 245                 unowned Node<G>? n = this._get_node_at (index);
 246                 assert (n != null);
 247                 G element = n.data;
 248                 this._remove_node (n);
 249                 return element;
 250         }
 251
 252         /**
 253          * {@inheritDoc}
 254          */
 255         public override List<G>? slice (int start, int stop) {
 256                 return_val_if_fail (start <= stop, null);
 257                 return_val_if_fail (start >= 0, null);
 258                 return_val_if_fail (stop <= this._size, null);
 259
 260                 List<G> slice = new LinkedList<G> (this.equal_func);
 261                 weak Node<G> n = this._get_node_at (start);
 262                 for (int i = start; i < stop; i++) {
 263                         slice.add (n.data);
 264                         n = n.next;
 265                 }
 266
 267                 return slice;
 268         }
 269
 270         /**
 271          * {@inheritDoc}
 272          */
 273         public G first () {
 274                 assert (_size > 0);
 275                 return _head.data;
 276         }
 277
 278         /**
 279          * {@inheritDoc}
 280          */
 281         public G last () {
 282                 assert (_size > 0);
 283                 return _tail.data;
 284         }
 285
 286         /**
 287          * {@inheritDoc}
 288          */
 289         public int capacity {
 290                 get { return UNBOUNDED_CAPACITY; }
 291         }
 292
 293         /**
 294          * {@inheritDoc}
 295          */
 296         public int remaining_capacity {
 297                 get { return UNBOUNDED_CAPACITY; }
 298         }
 299
 300         /**
 301          * {@inheritDoc}
 302          */
 303         public bool is_full {
 304                 get { return false; }
 305         }
 306
 307         /**
 308          * {@inheritDoc}
 309          */
 310         public bool offer (G element) {
 311                 return offer_tail (element);
 312         }
 313
 314         /**
 315          * {@inheritDoc}
 316          */
 317         public G? peek () {
 318                 return peek_head ();
 319         }
 320
 321         /**
 322          * {@inheritDoc}
 323          */
 324         public G? poll () {
 325                 return poll_head ();
 326         }
 327
 328         /**
 329          * {@inheritDoc}
 330          */
 331         public int drain (Collection<G> recipient, int amount = -1) {
 332                 return drain_head (recipient, amount);
 333         }
 334
 335         /**
 336          * {@inheritDoc}
 337          */
 338         public bool offer_head (G element) {
 339                 insert (0, element);
 340                 return true;
 341         }
 342
 343         /**
 344          * {@inheritDoc}
 345          */
 346         public G? peek_head () {
 347                 if (this._size == 0) {
 348                         return null;
 349                 }
 350                 return get (0);
 351         }
 352
 353         /**
 354          * {@inheritDoc}
 355          */
 356         public G? poll_head () {
 357                 if (this._size == 0) {
 358                         return null;
 359                 }
 360                 return remove_at (0);
 361         }
 362
 363         /**
 364          * {@inheritDoc}
 365          */
 366         public int drain_head (Collection<G> recipient, int amount = -1) {
 367                 if (amount == -1) {
 368                         amount = this._size;
 369                 }
 370                 for (int i = 0; i < amount; i++) {
 371                         if (this._size == 0) {
 372                                 return i;
 373                         }
 374                         recipient.add (remove_at (0));
 375                 }
 376                 return amount;
 377         }
 378
 379         /**
 380          * {@inheritDoc}
 381          */
 382         public bool offer_tail (G element) {
 383                 return add (element);
 384         }
 385
 386         /**
 387          * {@inheritDoc}
 388          */
 389         public G? peek_tail () {
 390                 if (this._size == 0) {
 391                         return null;
 392                 }
 393                 return get (_size - 1);
 394         }
 395
 396         /**
 397          * {@inheritDoc}
 398          */
 399         public G? poll_tail () {
 400                 if (this._size == 0) {
 401                         return null;
 402                 }
 403                 return remove_at (_size - 1);
 404         }
 405
 406         /**
 407          * {@inheritDoc}
 408          */
 409         public int drain_tail (Collection<G> recipient, int amount = -1) {
 410                 if (amount == -1) {
 411                         amount = this._size;
 412                 }
 413                 for (int i = 0; i < amount; i++) {
 414                         if (this._size == 0) {
 415                                 return i;
 416                         }
 417                         recipient.add (remove_at (this._size - 1));
 418                 }
 419                 return amount;
 420         }
 421
 422         [Compact]
 423         private class Node<G> { // Maybe a compact class should be used?
 424                 public G data;
 425                 public weak Node<G>? prev = null;
 426                 public Node<G>? next = null;
 427                 public Node (owned G data) {
 428                         this.data = data;
 429                 }
 430         }
 431
 432         private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G>, BidirIterator<G>, ListIterator<G>, BidirListIterator<G> {
 433                 private bool started = false;
 434                 private bool removed = false;
 435                 private unowned Node<G>? position;
 436                 private int _stamp;
 437                 private LinkedList<G> _list;
 438                 private int _index;
 439
 440                 public Iterator (LinkedList<G> list) {
 441                         this._list = list;
 442                         this.position = null;
 443                         this._index = -1;
 444                         this._stamp = list._stamp;
 445                 }
 446
 447                 public bool next () {
 448                         assert (this._stamp == this._list._stamp);
 449
 450                         if (this.removed) {
 451                                 if (this.position != null) {
 452                                         this.removed = false;
 453                                         return true;
 454                                 } else {
 455                                         return false;
 456                                 }
 457                         } else if (!this.started) {
 458                                 if (this._list._head != null) {
 459                                         this.started = true;
 460                                         this.position = this._list._head;
 461                                         this._index++;
 462                                         return true;
 463                                 } else {
 464                                         return false;
 465                                 }
 466                         } else if (this.position != null) {
 467                                 if (this.position.next != null) {
 468                                         this.position = this.position.next;
 469                                         this._index++;
 470                                         return true;
 471                                 } else {
 472                                         return false;
 473                                 }
 474                         }
 475                         return false;
 476                 }
 477
 478                 public bool has_next () {
 479                         assert (this._stamp == this._list._stamp);
 480
 481                         if (this.removed) {
 482                                 return this.position != null;
 483                         } else if (!this.started) {
 484                                 return this._list._head != null;
 485                         } else if (this.position != null) {
 486                                 return this.position.next != null;
 487                         }
 488                         return false;
 489                 }
 490
 491                 public bool first () {
 492                         assert (this._stamp == this._list._stamp);
 493                         if (this._list.size == 0) {
 494                                 return false;
 495                         }
 496                         this.position = this._list._head;
 497                         this.started = true;
 498                         this._index = 0;
 499                         this.removed = false;
 500                         return this.position != null;
 501                 }
 502
 503                 public new G get () {
 504                         assert (this._stamp == this._list._stamp);
 505                         assert (this.position != null);
 506
 507                         return this.position.data;
 508                 }
 509
 510                 public void remove () {
 511                         assert (this._stamp == this._list._stamp);
 512                         assert (this.position != null);
 513
 514                         unowned Node<G>? new_position = this.position.next;
 515                         if (new_position == null) {
 516                                 started = false;
 517                         }
 518                         _list._remove_node (this.position);
 519                         this.position = new_position;
 520                         this.removed = true;
 521                         this._stamp = this._list._stamp;
 522                 }
 523
 524                 public bool previous () {
 525                         assert (this._stamp == this._list._stamp);
 526
 527                         if (!this.started) {
 528                                 this.position = null;
 529                                 return false;
 530                         } else if (this.position != null && this.position.prev != null) {
 531                                 this.position = this.position.prev;
 532                                 this._index--;
 533                                 return true;
 534                         }
 535                         return false;
 536                 }
 537
 538                 public bool has_previous () {
 539                         assert (this._stamp == this._list._stamp);
 540
 541                         if (!this.started) {
 542                                 return false;
 543                         } else if (this.position != null) {
 544                                 return this.position.prev != null;
 545                         }
 546                         return false;
 547                 }
 548
 549                 public bool last () {
 550                         assert (this._stamp == this._list._stamp);
 551
 552                         if (this._list.size == 0) {
 553                                 return false;
 554                         }
 555                         this.position = this._list._tail;
 556                         this.started = true;
 557                         this._index = this._list._size - 1;
 558                         return this.position != null;
 559                 }
 560
 561                 public new void set (G item) {
 562                         assert (this._stamp == this._list._stamp);
 563                         assert (this.position != null);
 564
 565                         this.position.data = item;
 566                 }
 567
 568                 public void insert (G item) {
 569                         assert (this._stamp == this._list._stamp);
 570                         assert (this.position != null);
 571
 572                         Node<G> n = new Node<G> (item);
 573                         if (this.position.prev != null) {
 574                                 Node<G> position = (owned) this.position.prev.next;
 575                                 n.prev = position.prev;
 576                                 position.prev = n;
 577                                 n.next = (owned) position;
 578                                 weak Node<G> _n = n;
 579                                 _n.prev.next = (owned) n;
 580                         } else {
 581                                 Node<G> position = (owned) this._list._head;
 582                                 position.prev = n;
 583                                 n.next = (owned) position;
 584                                 this._list._head = (owned) n;
 585                         }
 586                         this._list._size++;
 587                         this._index++;
 588                         _stamp = _list._stamp;
 589                 }
 590
 591                 public void add (G item) {
 592                         assert (this._stamp == this._list._stamp);
 593                         assert (this.position != null);
 594
 595                         Node<G> n = new Node<G> (item);
 596                         if (this.position.next != null) {
 597                                 this.position.next.prev = n;
 598                                 n.next = (owned) this.position.next;
 599                         } else {
 600                                 this._list._tail = n;
 601                         }
 602                         this.position.next = (owned) n;
 603                         this.position.next.prev = this.position;
 604                         this.position = this.position.next;
 605                         this._list._size++;
 606                         this._index++;
 607                         _stamp = _list._stamp;
 608                 }
 609
 610                 public int index () {
 611                         assert (this._stamp == this._list._stamp);
 612                         assert (this.position != null);
 613
 614                         return this._index;
 615                 }
 616
 617                 public bool read_only {
 618                         get {
 619                                 return false;
 620                         }
 621                 }
 622
 623                 public bool valid {
 624                         get {
 625                                 return !this.removed && this.position != null;
 626                         }
 627                 }
 628
 629                 public bool foreach (ForallFunc<G> f) {
 630                         assert (_stamp == _list._stamp);
 631                         if (!started) {
 632                                 position = _list._head;
 633                                 if (position != null)
 634                                         started = true;
 635                         }
 636                         removed = false;
 637                         while (position != null) {
 638                                 if (!f (position.data)) {
 639                                         return false;
 640                                 }
 641                                 position = position.next;
 642                         }
 643                         position = _list._tail;
 644                         return true;
 645                 }
 646         }
 647
 648         private unowned Node<G>? _get_node_at (int index) {
 649                 unowned Node<G>? n = null;;
 650                 if (index == 0) {
 651                         n = this._head;
 652                 } else if (index == this._size - 1) {
 653                         n = this._tail;
 654                 } else if (index <= this._size / 2) {
 655                         n = this._head;
 656                         for (int i = 0; index != i; i++) {
 657                                 n = n.next;
 658                         }
 659                 } else {
 660                         n = this._tail;
 661                         for (int i = this._size - 1; index != i; i--) {
 662                                 n = n.prev;
 663                         }
 664                 }
 665                 return n;
 666         }
 667
 668         private void _remove_node (Node<G> _n) {
 669                 Node<G> n;
 670                 weak Node<G> next;
 671                 if (_n == this._head) {
 672                         n = (owned) this._head;
 673                         next = this._head = (owned) n.next;
 674                 } else {
 675                         n = (owned) _n.prev.next;
 676                         next = n.prev.next = (owned) n.next;
 677                 }
 678                 if (n == this._tail) {
 679                         this._tail = n.prev;
 680                 } else {
 681                         next.prev = n.prev;
 682                 }
 683                 n.prev = null;
 684                 n.next = null;
 685                 n.data = null;
 686                 ++this._stamp;
 687                 this._size--;
 688         }
 689 }
 690