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         private weak MultiSet<G> _read_only_view;
  96         public virtual new MultiSet<G> read_only_view {
  97                 owned get {
  98                         MultiSet<G> instance = _read_only_view;
  99                         if (_read_only_view == null) {
 100                                 instance = new ReadOnlyMultiSet<G> (this);
 101                                 _read_only_view = instance;
 102                                 instance.add_weak_pointer ((void**) (&_read_only_view));
 103                         }
 104                         return instance;
 105                 }
 106         }
 107
 108         // Future-proofing
 109         internal new virtual void reserved0() {}
 110         internal new virtual void reserved1() {}
 111         internal new virtual void reserved2() {}
 112         internal new virtual void reserved3() {}
 113         internal new virtual void reserved4() {}
 114         internal new virtual void reserved5() {}
 115         internal new virtual void reserved6() {}
 116         internal new virtual void reserved7() {}
 117         internal new virtual void reserved8() {}
 118
 119         private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G> {
 120                 private AbstractMultiSet<G> _set;
 121
 122                 private MapIterator<G, int> _iter;
 123                 private int _pending = 0;
 124                 private bool _removed = false;
 125
 126                 public Iterator (AbstractMultiSet<G> set) {
 127                         _set = set;
 128                         _iter = _set._storage_map.map_iterator ();
 129                 }
 130
 131                 public bool next () {
 132                         _removed = false;
 133                         if (_pending == 0) {
 134                                 if (_iter.next ()) {
 135                                         _pending = _iter.get_value () - 1;
 136                                         return true;
 137                                 }
 138                         } else {
 139                                 _pending--;
 140                                 return true;
 141                         }
 142                         return false;
 143                 }
 144
 145                 public bool has_next () {
 146                         return _pending > 0 || _iter.has_next ();
 147                 }
 148
 149                 public new G get () {
 150                         assert (! _removed);
 151                         return _iter.get_key ();
 152                 }
 153
 154                 public void remove () {
 155                         assert (! _removed);
 156                         _iter.set_value (_pending = _iter.get_value () - 1);
 157                         if (_pending == 0) {
 158                                 _iter.unset ();
 159                         }
 160                         _set._nitems--;
 161                         _removed = true;
 162                 }
 163
 164                 public bool read_only {
 165                         get {
 166                                 return false;
 167                         }
 168                 }
 169
 170                 public bool valid {
 171                         get {
 172                                 return ! _removed && _iter.valid;
 173                         }
 174                 }
 175
 176                 public bool foreach (ForallFunc<G> f) {
 177                         if (_iter.valid) {
 178                                 if (!_removed) {
 179                                         if (!f(_iter.get_key())) {
 180                                                 return false;
 181                                         }
 182                                 }
 183                                 for(int i = _pending - 1; i >= 0; --i) {
 184                                         if (!f(_iter.get_key())) {
 185                                                 _pending = i;
 186                                                 return false;
 187                                         }
 188                                 }
 189                         }
 190                         while(_iter.next()) {
 191                                 for(int i = _iter.get_value() - 1; i >= 0; --i) {
 192                                         if (!f(_iter.get_key())) {
 193                                                 _removed = false;
 194                                                 _pending = i;
 195                                                 return false;
 196                                         }
 197                                 }
 198                         }
 199                         _removed = false;
 200                         _pending = 0;
 201                         return true;
 202                 }
 203         }
 204 }