gee/collection.vala

   1 /* collection.vala
   2  *
   3  * Copyright (C) 2007-2009  Jürg Billeter
   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  *      Jürg Billeter <j@bitron.ch>
  21  */
  22
  23 /**
  24  * A generic collection of objects.
  25  */
  26 [GenericAccessors]
  27 public interface Gee.Collection<G> : Iterable<G> {
  28         /**
  29          * The number of items in this collection.
  30          */
  31         public abstract int size { get; }
  32
  33         /**
  34          * Specifies whether this collection is empty.
  35          */
  36         public virtual bool is_empty { get { return size == 0; } }
  37
  38         /**
  39          * Specifies whether this collection can change - i.e. wheather {@link add},
  40          * {@link remove} etc. are legal operations.
  41          */
  42         public abstract bool read_only { get; }
  43
  44         /**
  45          * Determines whether this collection contains the specified item.
  46          *
  47          * @param item the item to locate in the collection
  48          *
  49          * @return     ``true`` if item is found, ``false`` otherwise
  50          */
  51         public abstract bool contains (G item);
  52
  53         /**
  54          * Adds an item to this collection. Must not be called on read-only
  55          * collections.
  56          *
  57          * @param item the item to add to the collection
  58          *
  59          * @return     ``true`` if the collection has been changed, ``false`` otherwise
  60          */
  61         public abstract bool add (G item);
  62
  63         /**
  64          * Removes the first occurence of an item from this collection. Must not
  65          * be called on read-only collections.
  66          *
  67          * @param item the item to remove from the collection
  68          *
  69          * @return     ``true`` if the collection has been changed, ``false`` otherwise
  70          */
  71         public abstract bool remove (G item);
  72
  73         /**
  74          * Removes all items from this collection. Must not be called on
  75          * read-only collections.
  76          */
  77         public abstract void clear ();
  78
  79         /**
  80          * Adds all items in the input collection to this collection.
  81          *
  82          * @param collection the collection which items will be added to this
  83          *                   collection.
  84          *
  85          * @return     ``true`` if the collection has been changed, ``false`` otherwise
  86          */
  87         public virtual bool add_all (Collection<G> collection) {
  88                 return collection.fold<bool> ((item, changed) => changed | add (item), false);
  89         }
  90
  91         /**
  92          * Returns ``true`` it this collection contains all items as the input
  93          * collection.
  94          *
  95          * @param collection the collection which items will be compared with
  96          *                   this collection.
  97          *
  98          * @return     ``true`` if the collection has been changed, ``false`` otherwise
  99          */
 100         public virtual bool contains_all (Collection<G> collection) {
 101                 return collection.foreach ((item) => contains (item));
 102         }
 103
 104         /**
 105          * Removes the subset of items in this collection corresponding to the
 106          * elments in the input collection. If there is several occurrences of
 107          * the same value in this collection they are decremented of the number
 108          * of occurrences in the input collection.
 109          *
 110          * @param collection the collection which items will be compared with
 111          *                   this collection.
 112          *
 113          * @return     ``true`` if the collection has been changed, ``false`` otherwise
 114          */
 115         public virtual bool remove_all (Collection<G> collection) {
 116                 return collection.fold<bool> ((item, changed) => changed | remove (item), false);
 117         }
 118
 119         /**
 120          * Removes all items in this collection that are not contained in the input
 121          * collection. In other words all common items of both collections are
 122          * retained in this collection.
 123          *
 124          * @param collection the collection which items will be compared with
 125          *                   this collection.
 126          *
 127          * @return     ``true`` if the collection has been changed, ``false`` otherwise
 128          */
 129         public virtual bool retain_all (Collection<G> collection) {
 130                 bool changed = false;
 131                 for (Iterator<G> iter = iterator(); iter.next ();) {
 132                         G item = iter.get ();
 133                         if (!collection.contains (item)) {
 134                                 iter.remove ();
 135                                 changed = true;
 136                         }
 137                 }
 138                 return changed;
 139         }
 140
 141         /**
 142          * Returns an array containing all of items from this collection.
 143          *
 144          * @return an array containing all of items from this collection
 145          */
 146         public virtual G[] to_array () {
 147                 var t = typeof (G);
 148                 if (t == typeof (bool)) {
 149                         return (G[]) to_bool_array ((Collection<bool>) this);
 150                 } else if (t == typeof (char)) {
 151                         return (G[]) to_char_array ((Collection<char>) this);
 152                 } else if (t == typeof (uchar)) {
 153                         return (G[]) to_uchar_array ((Collection<uchar>) this);
 154                 } else if (t == typeof (int)) {
 155                         return (G[]) to_int_array ((Collection<int>) this);
 156                 } else if (t == typeof (uint)) {
 157                         return (G[]) to_uint_array ((Collection<uint>) this);
 158                 } else if (t == typeof (int64)) {
 159                         return (G[]) to_int64_array ((Collection<int64>) this);
 160                 } else if (t == typeof (uint64)) {
 161                         return (G[]) to_uint64_array ((Collection<uint64>) this);
 162                 } else if (t == typeof (long)) {
 163                         return (G[]) to_long_array ((Collection<long>) this);
 164                 } else if (t == typeof (ulong)) {
 165                         return (G[]) to_ulong_array ((Collection<ulong>) this);
 166                 } else if (t == typeof (float)) {
 167                         return (G[]) to_float_array ((Collection<float>) this);
 168                 } else if (t == typeof (double)) {
 169                         return (G[]) to_double_array ((Collection<double>) this);
 170                 } else {
 171                         G[] array = new G[size];
 172                         int index = 0;
 173                         foreach (G element in this) {
 174                                 array[index++] = (owned)element;
 175                         }
 176                         return array;
 177                 }
 178         }
 179
 180         /**
 181          * Adds all items in the input array to this collection.
 182          *
 183          * @param array the array which items will be added to this
 184          *              collection.
 185          *
 186          * @return     ``true`` if the collection has been changed, ``false`` otherwise
 187          */
 188         public bool add_all_array (G[] array) {
 189                 // FIXME: Change to virtual after bug #693455 is fixed
 190                 var t = typeof (G);
 191                 if (t == typeof (bool)) {
 192                         return add_all_bool_array ((Collection<bool>) this, (bool [])array);
 193                 } else if (t == typeof (char)) {
 194                         return add_all_char_array ((Collection<char>) this, (char [])array);
 195                 } else if (t == typeof (uchar)) {
 196                         return add_all_uchar_array ((Collection<uchar>) this, (uchar [])array);
 197                 } else if (t == typeof (int)) {
 198                         return add_all_int_array ((Collection<int>) this, (int [])array);
 199                 } else if (t == typeof (uint)) {
 200                         return add_all_uint_array ((Collection<uint>) this, (uint [])array);
 201                 } else if (t == typeof (int64)) {
 202                         return add_all_int64_array ((Collection<int64?>) this, (int64? [])array);
 203                 } else if (t == typeof (uint64)) {
 204                         return add_all_uint64_array ((Collection<uint64?>) this, (uint64? [])array);
 205                 } else if (t == typeof (long)) {
 206                         return add_all_long_array ((Collection<long>) this, (long [])array);
 207                 } else if (t == typeof (ulong)) {
 208                         return add_all_ulong_array ((Collection<ulong>) this, (ulong [])array);
 209                 } else if (t == typeof (float)) {
 210                         return add_all_float_array ((Collection<float>) this, (float? [])array);
 211                 } else if (t == typeof (double)) {
 212                         return add_all_double_array ((Collection<double>) this, (double? [])array);
 213                 } else {
 214                         bool changed = false;
 215                         foreach (unowned G item in array) {
 216                                 changed |= add (item);
 217                         }
 218                         return changed;
 219                 }
 220         }
 221
 222         /**
 223          * Returns ``true`` it this collection contains all items as the input
 224          * array.
 225          *
 226          * @param array the array which items will be compared with
 227          *              this collection.
 228          *
 229          * @return     ``true`` if the collection has been changed, ``false`` otherwise
 230          */
 231         public bool contains_all_array (G[] array) {
 232                 // FIXME: Change to virtual after bug #693455 is fixed
 233                 var t = typeof (G);
 234                 if (t == typeof (bool)) {
 235                         return contains_all_bool_array ((Collection<bool>) this, (bool [])array);
 236                 } else if (t == typeof (char)) {
 237                         return contains_all_char_array ((Collection<char>) this, (char [])array);
 238                 } else if (t == typeof (uchar)) {
 239                         return contains_all_uchar_array ((Collection<uchar>) this, (uchar [])array);
 240                 } else if (t == typeof (int)) {
 241                         return contains_all_int_array ((Collection<int>) this, (int [])array);
 242                 } else if (t == typeof (uint)) {
 243                         return contains_all_uint_array ((Collection<uint>) this, (uint [])array);
 244                 } else if (t == typeof (int64)) {
 245                         return contains_all_int64_array ((Collection<int64?>) this, (int64? [])array);
 246                 } else if (t == typeof (uint64)) {
 247                         return contains_all_uint64_array ((Collection<uint64?>) this, (uint64? [])array);
 248                 } else if (t == typeof (long)) {
 249                         return contains_all_long_array ((Collection<long>) this, (long [])array);
 250                 } else if (t == typeof (ulong)) {
 251                         return contains_all_ulong_array ((Collection<ulong>) this, (ulong [])array);
 252                 } else if (t == typeof (float)) {
 253                         return contains_all_float_array ((Collection<float>) this, (float? [])array);
 254                 } else if (t == typeof (double)) {
 255                         return contains_all_double_array ((Collection<double>) this, (double? [])array);
 256                 } else {
 257                         foreach (unowned G item in array) {
 258                                 if (!contains (item)) {
 259                                         return false;
 260                                 }
 261                         }
 262                         return true;
 263                 }
 264         }
 265
 266         /**
 267          * Removes the subset of items in this collection corresponding to the
 268          * elments in the input array. If there is several occurrences of
 269          * the same value in this collection they are decremented of the number
 270          * of occurrences in the input array.
 271          *
 272          * @param array the array which items will be compared with
 273          *              this collection.
 274          *
 275          * @return     ``true`` if the collection has been changed, ``false`` otherwise
 276          */
 277         public bool remove_all_array (G[] array) {
 278                 // FIXME: Change to virtual after bug #693455 is fixed
 279                 var t = typeof (G);
 280                 if (t == typeof (bool)) {
 281                         return remove_all_bool_array ((Collection<bool>) this, (bool [])array);
 282                 } else if (t == typeof (char)) {
 283                         return remove_all_char_array ((Collection<char>) this, (char [])array);
 284                 } else if (t == typeof (uchar)) {
 285                         return remove_all_uchar_array ((Collection<uchar>) this, (uchar [])array);
 286                 } else if (t == typeof (int)) {
 287                         return remove_all_int_array ((Collection<int>) this, (int [])array);
 288                 } else if (t == typeof (uint)) {
 289                         return remove_all_uint_array ((Collection<uint>) this, (uint [])array);
 290                 } else if (t == typeof (int64)) {
 291                         return remove_all_int64_array ((Collection<int64?>) this, (int64? [])array);
 292                 } else if (t == typeof (uint64)) {
 293                         return remove_all_uint64_array ((Collection<uint64?>) this, (uint64? [])array);
 294                 } else if (t == typeof (long)) {
 295                         return remove_all_long_array ((Collection<long>) this, (long [])array);
 296                 } else if (t == typeof (ulong)) {
 297                         return remove_all_ulong_array ((Collection<ulong>) this, (ulong [])array);
 298                 } else if (t == typeof (float)) {
 299                         return remove_all_float_array ((Collection<float>) this, (float? [])array);
 300                 } else if (t == typeof (double)) {
 301                         return remove_all_double_array ((Collection<double>) this, (double? [])array);
 302                 } else {
 303                         bool changed = false;
 304                         foreach (unowned G item in array) {
 305                                 changed |= remove (item);
 306                         }
 307                         return changed;
 308                 }
 309         }
 310
 311         /**
 312          * The read-only view of this collection.
 313          */
 314         public abstract Collection<G> read_only_view { owned get; }
 315
 316         /**
 317          * Returns an immutable empty collection.
 318          *
 319          * @return an immutable empty collection
 320          */
 321         public static Collection<G> empty<G> () {
 322                 return new HashSet<G> ().read_only_view;
 323         }
 324
 325         private static bool[] to_bool_array (Collection<bool> coll) {
 326                 bool[] array = new bool[coll.size];
 327                 int index = 0;
 328                 foreach (bool element in coll) {
 329                         array[index++] = element;
 330                 }
 331                 return array;
 332         }
 333
 334         private static char[] to_char_array (Collection<char> coll) {
 335                 char[] array = new char[coll.size];
 336                 int index = 0;
 337                 foreach (char element in coll) {
 338                         array[index++] = element;
 339                 }
 340                 return array;
 341         }
 342
 343         private static uchar[] to_uchar_array (Collection<uchar> coll) {
 344                 uchar[] array = new uchar[coll.size];
 345                 int index = 0;
 346                 foreach (uchar element in coll) {
 347                         array[index++] = element;
 348                 }
 349                 return array;
 350         }
 351
 352         private static int[] to_int_array (Collection<int> coll) {
 353                 int[] array = new int[coll.size];
 354                 int index = 0;
 355                 foreach (int element in coll) {
 356                         array[index++] = element;
 357                 }
 358                 return array;
 359         }
 360
 361         private static uint[] to_uint_array (Collection<uint> coll) {
 362                 uint[] array = new uint[coll.size];
 363                 int index = 0;
 364                 foreach (uint element in coll) {
 365                         array[index++] = element;
 366                 }
 367                 return array;
 368         }
 369
 370         private static int64?[] to_int64_array (Collection<int64?> coll) {
 371                 int64?[] array = new int64?[coll.size];
 372                 int index = 0;
 373                 foreach (int64? element in coll) {
 374                         array[index++] = (owned)element;
 375                 }
 376                 return array;
 377         }
 378
 379         private static uint64?[] to_uint64_array (Collection<uint64?> coll) {
 380                 uint64?[] array = new uint64?[coll.size];
 381                 int index = 0;
 382                 foreach (uint64? element in coll) {
 383                         array[index++] = (owned)element;
 384                 }
 385                 return array;
 386         }
 387
 388         private static long[] to_long_array (Collection<long> coll) {
 389                 long[] array = new long[coll.size];
 390                 int index = 0;
 391                 foreach (long element in coll) {
 392                         array[index++] = element;
 393                 }
 394                 return array;
 395         }
 396
 397         private static ulong[] to_ulong_array (Collection<ulong> coll) {
 398                 ulong[] array = new ulong[coll.size];
 399                 int index = 0;
 400                 foreach (ulong element in coll) {
 401                         array[index++] = element;
 402                 }
 403                 return array;
 404         }
 405
 406         private static float?[] to_float_array (Collection<float?> coll) {
 407                 float?[] array = new float?[coll.size];
 408                 int index = 0;
 409                 foreach (float? element in coll) {
 410                         array[index++] = (owned)element;
 411                 }
 412                 return array;
 413         }
 414
 415         private static double?[] to_double_array (Collection<double?> coll) {
 416                 double?[] array = new double?[coll.size];
 417                 int index = 0;
 418                 foreach (double? element in coll) {
 419                         array[index++] = (owned)element;
 420                 }
 421                 return array;
 422         }
 423
 424         private static bool add_all_bool_array (Collection<bool> coll, bool[] arr) {
 425                 bool changed = false;
 426                 foreach (bool el in arr) {
 427                         changed |= coll.add (el);
 428                 }
 429                 return changed;
 430         }
 431
 432         private static bool add_all_char_array (Collection<char> coll, char[] arr) {
 433                 bool changed = false;
 434                 foreach (char el in arr) {
 435                         changed |= coll.add (el);
 436                 }
 437                 return changed;
 438         }
 439
 440         private static bool add_all_uchar_array (Collection<uchar> coll, uchar[] arr) {
 441                 bool changed = false;
 442                 foreach (uchar el in arr) {
 443                         changed |= coll.add (el);
 444                 }
 445                 return changed;
 446         }
 447
 448         private static bool add_all_int_array (Collection<int> coll, int[] arr) {
 449                 bool changed = false;
 450                 foreach (int el in arr) {
 451                         changed |= coll.add (el);
 452                 }
 453                 return changed;
 454         }
 455
 456         private static bool add_all_uint_array (Collection<uint> coll, uint[] arr) {
 457                 bool changed = false;
 458                 foreach (uint el in arr) {
 459                         changed |= coll.add (el);
 460                 }
 461                 return changed;
 462         }
 463
 464         private static bool add_all_int64_array (Collection<int64?> coll, int64?[] arr) {
 465                 bool changed = false;
 466                 foreach (unowned int64? el in arr) {
 467                         changed |= coll.add (el);
 468                 }
 469                 return changed;
 470         }
 471
 472         private static bool add_all_uint64_array (Collection<uint64?> coll, uint64?[] arr) {
 473                 bool changed = false;
 474                 foreach (unowned uint64? el in arr) {
 475                         changed |= coll.add (el);
 476                 }
 477                 return changed;
 478         }
 479
 480         private static bool add_all_long_array (Collection<long> coll, long[] arr) {
 481                 bool changed = false;
 482                 foreach (long el in arr) {
 483                         changed |= coll.add (el);
 484                 }
 485                 return changed;
 486         }
 487
 488         private static bool add_all_ulong_array (Collection<ulong> coll, ulong[] arr) {
 489                 bool changed = false;
 490                 foreach (ulong el in arr) {
 491                         changed |= coll.add (el);
 492                 }
 493                 return changed;
 494         }
 495
 496         private static bool add_all_float_array (Collection<float?> coll, float?[] arr) {
 497                 bool changed = false;
 498                 foreach (unowned float? el in arr) {
 499                         changed |= coll.add (el);
 500                 }
 501                 return changed;
 502         }
 503
 504         private static bool add_all_double_array (Collection<double?> coll, double?[] arr) {
 505                 bool changed = false;
 506                 foreach (unowned double? el in arr) {
 507                         changed |= coll.add (el);
 508                 }
 509                 return changed;
 510         }
 511
 512         private static bool contains_all_bool_array (Collection<bool> coll, bool[] arr) {
 513                 foreach (bool el in arr) {
 514                         if (!coll.contains (el)) {
 515                                 return false;
 516                         }
 517                 }
 518                 return true;
 519         }
 520
 521         private static bool contains_all_char_array (Collection<char> coll, char[] arr) {
 522                 foreach (char el in arr) {
 523                         if (!coll.contains (el)) {
 524                                 return false;
 525                         }
 526                 }
 527                 return true;
 528         }
 529
 530         private static bool contains_all_uchar_array (Collection<uchar> coll, uchar[] arr) {
 531                 foreach (uchar el in arr) {
 532                         if (!coll.contains (el)) {
 533                                 return false;
 534                         }
 535                 }
 536                 return true;
 537         }
 538
 539         private static bool contains_all_int_array (Collection<int> coll, int[] arr) {
 540                 foreach (int el in arr) {
 541                         if (!coll.contains (el)) {
 542                                 return false;
 543                         }
 544                 }
 545                 return true;
 546         }
 547
 548         private static bool contains_all_uint_array (Collection<uint> coll, uint[] arr) {
 549                 foreach (uint el in arr) {
 550                         if (!coll.contains (el)) {
 551                                 return false;
 552                         }
 553                 }
 554                 return true;
 555         }
 556
 557         private static bool contains_all_int64_array (Collection<int64?> coll, int64?[] arr) {
 558                 foreach (unowned int64? el in arr) {
 559                         if (!coll.contains (el)) {
 560                                 return false;
 561                         }
 562                 }
 563                 return true;
 564         }
 565
 566         private static bool contains_all_uint64_array (Collection<uint64?> coll, uint64?[] arr) {
 567                 foreach (unowned uint64? el in arr) {
 568                         if (!coll.contains (el)) {
 569                                 return false;
 570                         }
 571                 }
 572                 return true;
 573         }
 574
 575         private static bool contains_all_long_array (Collection<long> coll, long[] arr) {
 576                 foreach (long el in arr) {
 577                         if (!coll.contains (el)) {
 578                                 return false;
 579                         }
 580                 }
 581                 return true;
 582         }
 583
 584         private static bool contains_all_ulong_array (Collection<ulong> coll, ulong[] arr) {
 585                 foreach (ulong el in arr) {
 586                         if (!coll.contains (el)) {
 587                                 return false;
 588                         }
 589                 }
 590                 return true;
 591         }
 592
 593         private static bool contains_all_float_array (Collection<float?> coll, float?[] arr) {
 594                 foreach (unowned float? el in arr) {
 595                         if (!coll.contains (el)) {
 596                                 return false;
 597                         }
 598                 }
 599                 return true;
 600         }
 601
 602         private static bool contains_all_double_array (Collection<double?> coll, double?[] arr) {
 603                 foreach (unowned double? el in arr) {
 604                         if (!coll.contains (el)) {
 605                                 return false;
 606                         }
 607                 }
 608                 return true;
 609         }
 610
 611         private static bool remove_all_bool_array (Collection<bool> coll, bool[] arr) {
 612                 bool changed = false;
 613                 foreach (bool el in arr) {
 614                         changed |= coll.remove (el);
 615                 }
 616                 return changed;
 617         }
 618
 619         private static bool remove_all_char_array (Collection<char> coll, char[] arr) {
 620                 bool changed = false;
 621                 foreach (char el in arr) {
 622                         changed |= coll.remove (el);
 623                 }
 624                 return changed;
 625         }
 626
 627         private static bool remove_all_uchar_array (Collection<uchar> coll, uchar[] arr) {
 628                 bool changed = false;
 629                 foreach (uchar el in arr) {
 630                         changed |= coll.remove (el);
 631                 }
 632                 return changed;
 633         }
 634
 635         private static bool remove_all_int_array (Collection<int> coll, int[] arr) {
 636                 bool changed = false;
 637                 foreach (int el in arr) {
 638                         changed |= coll.remove (el);
 639                 }
 640                 return changed;
 641         }
 642
 643         private static bool remove_all_uint_array (Collection<uint> coll, uint[] arr) {
 644                 bool changed = false;
 645                 foreach (uint el in arr) {
 646                         changed |= coll.remove (el);
 647                 }
 648                 return changed;
 649         }
 650
 651         private static bool remove_all_int64_array (Collection<int64?> coll, int64?[] arr) {
 652                 bool changed = false;
 653                 foreach (unowned int64? el in arr) {
 654                         changed |= coll.remove (el);
 655                 }
 656                 return changed;
 657         }
 658
 659         private static bool remove_all_uint64_array (Collection<uint64?> coll, uint64?[] arr) {
 660                 bool changed = false;
 661                 foreach (unowned uint64? el in arr) {
 662                         changed |= coll.remove (el);
 663                 }
 664                 return changed;
 665         }
 666
 667         private static bool remove_all_long_array (Collection<long> coll, long[] arr) {
 668                 bool changed = false;
 669                 foreach (long el in arr) {
 670                         changed |= coll.remove (el);
 671                 }
 672                 return changed;
 673         }
 674
 675         private static bool remove_all_ulong_array (Collection<ulong> coll, ulong[] arr) {
 676                 bool changed = false;
 677                 foreach (ulong el in arr) {
 678                         changed |= coll.remove (el);
 679                 }
 680                 return changed;
 681         }
 682
 683         private static bool remove_all_float_array (Collection<float?> coll, float?[] arr) {
 684                 bool changed = false;
 685                 foreach (unowned float? el in arr) {
 686                         changed |= coll.remove (el);
 687                 }
 688                 return changed;
 689         }
 690
 691         private static bool remove_all_double_array (Collection<double?> coll, double?[] arr) {
 692                 bool changed = false;
 693                 foreach (unowned double? el in arr) {
 694                         changed |= coll.remove (el);
 695                 }
 696                 return changed;
 697         }
 698 }
 699