gee/abstractmultiset.vala

   1 /* abstractmultiset.vala
   2  *
   3  * Copyright (C) 2009  Ali Sabil
   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  *      Ali Sabil <ali.sabil@gmail.com>
  21  *      Didier 'Ptitjes Villevalois <ptitjes@free.fr>
  22  */
  23
  24 /**
  25  * Skeletal implementation of the {@link MultiSet} interface.
  26  *
  27  * @see HashMultiSet
  28  * @see TreeMultiSet
  29  */
  30 public abstract class Gee.AbstractMultiSet<G> : AbstractCollection<G>, MultiSet<G> {
  31         public override int size {
  32                 get { return _nitems; }
  33         }
  34
  35         public override bool read_only {
  36                 get { return false; }
  37         }
  38
  39         protected Map<G, int> _storage_map;
  40         private int _nitems = 0;
  41
  42         /**
  43          * Constructs a new, empty abstract multi set.
  44          */
  45         public AbstractMultiSet (Map<G, int> storage_map) {
  46                 this._storage_map = storage_map;
  47         }
  48
  49         public int count (G item) {
  50                 int result = 0;
  51                 if (_storage_map.has_key (item)) {
  52                         result = _storage_map.get (item);
  53                 }
  54                 return result;
  55         }
  56
  57         public override bool contains (G item) {
  58                 return _storage_map.has_key (item);
  59         }
  60
  61         public override Gee.Iterator<G> iterator () {
  62                 return new Iterator<G> (this);
  63         }
  64
  65         public override bool add (G item) {
  66                 if (_storage_map.has_key (item)) {
  67                         int current_count = _storage_map.get (item);
  68                         _storage_map.set (item, current_count + 1);
  69                 } else {
  70                         _storage_map.set (item, 1);
  71                 }
  72                 _nitems++;
  73                 return true;
  74         }
  75
  76         public override bool remove (G item) {
  77                 if (_nitems > 0 && _storage_map.has_key (item)) {
  78                         int current_count = _storage_map.get (item);
  79                         if (current_count <= 1) {
  80                                 _storage_map.unset (item);
  81                         } else {
  82                                 _storage_map.set (item, current_count - 1);
  83                         }
  84                         _nitems--;
  85                         return true;
  86                 }
  87                 return false;
  88         }
  89
  90         public override void clear () {
  91                 _storage_map.clear ();
  92                 _nitems = 0;
  93         }
  94
  95         // Future-proofing
  96         internal new virtual void reserved0() {}
  97         internal new virtual void reserved1() {}
  98         internal new virtual void reserved2() {}
  99         internal new virtual void reserved3() {}
 100         internal new virtual void reserved4() {}
 101         internal new virtual void reserved5() {}
 102         internal new virtual void reserved6() {}
 103         internal new virtual void reserved7() {}
 104         internal new virtual void reserved8() {}
 105         internal new virtual void reserved9() {}
 106
 107         private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G> {
 108                 private AbstractMultiSet<G> _set;
 109
 110                 private MapIterator<G, int> _iter;
 111                 private int _pending = 0;
 112                 private bool _removed = false;
 113
 114                 public Iterator (AbstractMultiSet<G> set) {
 115                         _set = set;
 116                         _iter = _set._storage_map.map_iterator ();
 117                 }
 118
 119                 public bool next () {
 120                         _removed = false;
 121                         if (_pending == 0) {
 122                                 if (_iter.next ()) {
 123                                         _pending = _iter.get_value () - 1;
 124                                         return true;
 125                                 }
 126                         } else {
 127                                 _pending--;
 128                                 return true;
 129                         }
 130                         return false;
 131                 }
 132
 133                 public bool has_next () {
 134                         return _pending > 0 || _iter.has_next ();
 135                 }
 136
 137                 public new G get () {
 138                         assert (! _removed);
 139                         return _iter.get_key ();
 140                 }
 141
 142                 public void remove () {
 143                         assert (! _removed);
 144                         _iter.set_value (_pending = _iter.get_value () - 1);
 145                         if (_pending == 0) {
 146                                 _iter.unset ();
 147                         }
 148                         _set._nitems--;
 149                         _removed = true;
 150                 }
 151
 152                 public bool read_only {
 153                         get {
 154                                 return false;
 155                         }
 156                 }
 157
 158                 public bool valid {
 159                         get {
 160                                 return ! _removed && _iter.valid;
 161                         }
 162                 }
 163
 164                 public bool foreach (ForallFunc<G> f) {
 165                         if (_iter.valid) {
 166                                 if (!_removed) {
 167                                         if (!f(_iter.get_key())) {
 168                                                 return false;
 169                                         }
 170                                 }
 171                                 for(int i = _pending - 1; i >= 0; --i) {
 172                                         if (!f(_iter.get_key())) {
 173                                                 _pending = i;
 174                                                 return false;
 175                                         }
 176                                 }
 177                         }
 178                         while(_iter.next()) {
 179                                 for(int i = _iter.get_value() - 1; i >= 0; --i) {
 180                                         if (!f(_iter.get_key())) {
 181                                                 _removed = false;
 182                                                 _pending = i;
 183                                                 return false;
 184                                         }
 185                                 }
 186                         }
 187                         _removed = false;
 188                         _pending = 0;
 189                         return true;
 190                 }
 191         }
 192 }