gee/abstractmultimap.vala

   1 /* abstractmultimap.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 MultiMap} interface.
  26  *
  27  * @see HashMultiMap
  28  * @see TreeMultiMap
  29  */
  30 public abstract class Gee.AbstractMultiMap<K,V> : Object, MultiMap<K,V> {
  31         public int size {
  32                 get { return _nitems; }
  33         }
  34
  35         public bool read_only {
  36                 get { return false; }
  37         }
  38
  39         protected Map<K, Collection<V>> _storage_map;
  40         private int _nitems = 0;
  41
  42         public AbstractMultiMap (Map<K, Collection<V>> storage_map) {
  43                 this._storage_map = storage_map;
  44         }
  45
  46         public Set<K> get_keys () {
  47                 return _storage_map.keys;
  48         }
  49
  50         public MultiSet<K> get_all_keys () {
  51                 return new AllKeys<K, V> (this);
  52         }
  53
  54         public Collection<V> get_values () {
  55                 return new Values<K, V> (this);
  56         }
  57
  58         public bool contains (K key) {
  59                 return _storage_map.has_key (key);
  60         }
  61
  62         public new Collection<V> get (K key) {
  63                 Collection<V>? col = _storage_map.get (key);
  64                 return col != null ? col.read_only_view : Set.empty<V> ();
  65         }
  66
  67         public new void set (K key, V value) {
  68                 if (_storage_map.has_key (key)) {
  69                         if (_storage_map.get (key).add (value)) {
  70                                 _nitems++;
  71                         }
  72                 } else {
  73                         var s = create_value_storage ();
  74                         s.add (value);
  75                         _storage_map.set (key, s);
  76                         _nitems++;
  77                 }
  78         }
  79
  80         public bool remove (K key, V value) {
  81                 if (_storage_map.has_key (key)) {
  82                         var values = _storage_map.get (key);
  83                         if (values.contains (value)) {
  84                                 values.remove (value);
  85                                 _nitems--;
  86                                 if (values.size == 0) {
  87                                         _storage_map.unset (key);
  88                                 }
  89                                 return true;
  90                         }
  91                 }
  92                 return false;
  93         }
  94
  95         public bool remove_all (K key) {
  96                 if (_storage_map.has_key (key)) {
  97                         int size = _storage_map.get (key).size;
  98                         if (_storage_map.unset (key)) {
  99                                 _nitems -= size;
 100                                 return true;
 101                         }
 102                 }
 103                 return false;
 104         }
 105
 106         public void clear () {
 107                 _storage_map.clear ();
 108                 _nitems = 0;
 109         }
 110
 111         public Gee.MapIterator<K, V> map_iterator () {
 112                 return new MapIterator<K, V> (_storage_map.map_iterator ());
 113         }
 114
 115         protected abstract Collection<V> create_value_storage ();
 116
 117         protected abstract MultiSet<K> create_multi_key_set ();
 118
 119         protected abstract EqualDataFunc<V> get_value_equal_func ();
 120
 121         private class AllKeys<K, V> : AbstractCollection<K>, MultiSet<K> {
 122                 protected AbstractMultiMap<K, V> _multi_map;
 123
 124                 public AllKeys (AbstractMultiMap<K, V> multi_map) {
 125                         _multi_map = multi_map;
 126                 }
 127
 128                 public override Gee.Iterator<K> iterator () {
 129                         return new KeyIterator<K, V> (_multi_map._storage_map.map_iterator ());
 130                 }
 131
 132                 public override int size { get { return _multi_map.size; } }
 133
 134                 public override bool read_only { get { return true; } }
 135
 136                 public override bool contains (K key) {
 137                         return _multi_map._storage_map.has_key (key);
 138                 }
 139
 140                 public override bool add (K key) {
 141                         assert_not_reached ();
 142                 }
 143
 144                 public override  bool remove (K item) {
 145                         assert_not_reached ();
 146                 }
 147
 148                 public override void clear () {
 149                         assert_not_reached ();
 150                 }
 151
 152                 public int count (K item) {
 153                         Collection<V>? collection = _multi_map._storage_map.get (item);
 154                         return collection != null ? collection.size : 0;
 155                 }
 156         }
 157
 158         private class Values<K, V> : AbstractCollection<V> {
 159                 protected AbstractMultiMap<K, V> _multi_map;
 160
 161                 public Values (AbstractMultiMap<K, V> multi_map) {
 162                         _multi_map = multi_map;
 163                 }
 164
 165                 public override Gee.Iterator<K> iterator () {
 166                         return new ValueIterator<K, V> (_multi_map._storage_map.map_iterator ());
 167                 }
 168
 169                 public override int size { get { return _multi_map.size; } }
 170
 171                 public override bool read_only { get { return true; } }
 172
 173                 public override bool contains (V value) {
 174                         EqualDataFunc<V> func = _multi_map.get_value_equal_func ();
 175                         foreach (var col in _multi_map._storage_map.values) {
 176                                 if (col.contains (value)) {
 177                                         return true;
 178                                 }
 179                         }
 180                         return false;
 181                 }
 182
 183                 public override bool add (K key) {
 184                         assert_not_reached ();
 185                 }
 186
 187                 public override  bool remove (K item) {
 188                         assert_not_reached ();
 189                 }
 190
 191                 public override void clear () {
 192                         assert_not_reached ();
 193                 }
 194         }
 195
 196         private class MappingIterator<K, V> : Object {
 197                 protected Gee.MapIterator<K, Collection<V>> outer;
 198                 protected Iterator<V>? inner = null;
 199
 200                 public MappingIterator (Gee.MapIterator<K, Collection<V>>? outer) {
 201                         this.outer = outer;
 202                 }
 203
 204                 public bool next () {
 205                         if (inner != null && inner.next ()) {
 206                                 return true;
 207                         } else if (outer.next ()) {
 208                                 inner = outer.get_value ().iterator ();
 209                                 assert (inner.next ());
 210                                 return true;
 211                         } else {
 212                                 return false;
 213                         }
 214                 }
 215
 216                 public bool has_next () {
 217                         return inner.has_next () || outer.has_next ();
 218                 }
 219
 220                 public void remove () {
 221                         assert_not_reached ();
 222                 }
 223
 224                 public virtual bool read_only {
 225                         get {
 226                                 return true;
 227                         }
 228                 }
 229
 230                 public void unset () {
 231                         inner.remove ();
 232                         if (outer.get_value ().is_empty) {
 233                                 outer.unset ();
 234                         }
 235                 }
 236
 237                 public bool valid {
 238                         get {
 239                                 return inner != null && inner.valid;
 240                         }
 241                 }
 242         }
 243
 244         private class KeyIterator<K, V> : MappingIterator<K, V>, Traversable<K>, Iterator<K> {
 245                 public KeyIterator (Gee.MapIterator<K, Collection<V>>? outer) {
 246                         base (outer);
 247                 }
 248
 249                 public new K get () {
 250                         assert (valid);
 251                         return outer.get_key ();
 252                 }
 253
 254                 public bool foreach (ForallFunc<K> f) {
 255                         if (inner != null && outer.valid) {
 256                                 K key = outer.get_key ();
 257                                 if (!inner.foreach ((v) => {return f (key);})) {
 258                                         return false;
 259                                 }
 260                                 outer.next ();
 261                         }
 262                         return outer.foreach ((key, col) => {
 263                                 return col.foreach ((v) => {return f (key);});
 264                         });
 265                 }
 266         }
 267
 268         private class ValueIterator<K, V> : MappingIterator<K, V>, Traversable<V>, Iterator<V> {
 269                 public ValueIterator (Gee.MapIterator<K, Collection<V>>? outer) {
 270                         base (outer);
 271                 }
 272
 273                 public new V get () {
 274                         assert (valid);
 275                         return inner.get ();
 276                 }
 277
 278                 public bool foreach (ForallFunc<V> f) {
 279                         if (inner != null && outer.valid) {
 280                                 if (!inner.foreach (f)) {
 281                                         return false;
 282                                 }
 283                                 outer.next ();
 284                         }
 285                         return outer.foreach ((key, col) => {
 286                                 return col.foreach (f);
 287                         });
 288                 }
 289         }
 290
 291         private class MapIterator<K, V> : MappingIterator<K, V>, Gee.MapIterator<K, V> {
 292                 public MapIterator (Gee.MapIterator<K, Collection<V>>? outer) {
 293                         base (outer);
 294                 }
 295
 296                 public K get_key () {
 297                         assert (valid);
 298                         return outer.get_key ();
 299                 }
 300
 301                 public V get_value () {
 302                         assert (valid);
 303                         return inner.get ();
 304                 }
 305
 306                 public void set_value (V value) {
 307                         assert_not_reached ();
 308                 }
 309
 310                 public bool mutable { get { return false; } }
 311         }
 312
 313         // Future-proofing
 314         internal new virtual void reserved0() {}
 315         internal new virtual void reserved1() {}
 316         internal new virtual void reserved2() {}
 317         internal new virtual void reserved3() {}
 318         internal new virtual void reserved4() {}
 319         internal new virtual void reserved5() {}
 320         internal new virtual void reserved6() {}
 321         internal new virtual void reserved7() {}
 322         internal new virtual void reserved8() {}
 323         internal new virtual void reserved9() {}
 324 }