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                         foreach (var col in _multi_map._storage_map.values) {
 175                                 if (col.contains (value)) {
 176                                         return true;
 177                                 }
 178                         }
 179                         return false;
 180                 }
 181
 182                 public override bool add (K key) {
 183                         assert_not_reached ();
 184                 }
 185
 186                 public override  bool remove (K item) {
 187                         assert_not_reached ();
 188                 }
 189
 190                 public override void clear () {
 191                         assert_not_reached ();
 192                 }
 193         }
 194
 195         private class MappingIterator<K, V> : Object {
 196                 protected Gee.MapIterator<K, Collection<V>> outer;
 197                 protected Iterator<V>? inner = null;
 198
 199                 public MappingIterator (Gee.MapIterator<K, Collection<V>>? outer) {
 200                         this.outer = outer;
 201                 }
 202
 203                 public bool next () {
 204                         if (inner != null && inner.next ()) {
 205                                 return true;
 206                         } else if (outer.next ()) {
 207                                 inner = outer.get_value ().iterator ();
 208                                 assert (inner.next ());
 209                                 return true;
 210                         } else {
 211                                 return false;
 212                         }
 213                 }
 214
 215                 public bool has_next () {
 216                         return inner.has_next () || outer.has_next ();
 217                 }
 218
 219                 public void remove () {
 220                         assert_not_reached ();
 221                 }
 222
 223                 public virtual bool read_only {
 224                         get {
 225                                 return true;
 226                         }
 227                 }
 228
 229                 public void unset () {
 230                         inner.remove ();
 231                         if (outer.get_value ().is_empty) {
 232                                 outer.unset ();
 233                         }
 234                 }
 235
 236                 public bool valid {
 237                         get {
 238                                 return inner != null && inner.valid;
 239                         }
 240                 }
 241         }
 242
 243         private class KeyIterator<K, V> : MappingIterator<K, V>, Traversable<K>, Iterator<K> {
 244                 public KeyIterator (Gee.MapIterator<K, Collection<V>>? outer) {
 245                         base (outer);
 246                 }
 247
 248                 public new K get () {
 249                         assert (valid);
 250                         return outer.get_key ();
 251                 }
 252
 253                 public bool foreach (ForallFunc<K> f) {
 254                         if (inner != null && outer.valid) {
 255                                 K key = outer.get_key ();
 256                                 if (!inner.foreach ((v) => {return f (key);})) {
 257                                         return false;
 258                                 }
 259                                 outer.next ();
 260                         }
 261                         return outer.foreach ((key, col) => {
 262                                 return col.foreach ((v) => {return f (key);});
 263                         });
 264                 }
 265         }
 266
 267         private class ValueIterator<K, V> : MappingIterator<K, V>, Traversable<V>, Iterator<V> {
 268                 public ValueIterator (Gee.MapIterator<K, Collection<V>>? outer) {
 269                         base (outer);
 270                 }
 271
 272                 public new V get () {
 273                         assert (valid);
 274                         return inner.get ();
 275                 }
 276
 277                 public bool foreach (ForallFunc<V> f) {
 278                         if (inner != null && outer.valid) {
 279                                 if (!inner.foreach (f)) {
 280                                         return false;
 281                                 }
 282                                 outer.next ();
 283                         }
 284                         return outer.foreach ((key, col) => {
 285                                 return col.foreach (f);
 286                         });
 287                 }
 288         }
 289
 290         private class MapIterator<K, V> : MappingIterator<K, V>, Gee.MapIterator<K, V> {
 291                 public MapIterator (Gee.MapIterator<K, Collection<V>>? outer) {
 292                         base (outer);
 293                 }
 294
 295                 public K get_key () {
 296                         assert (valid);
 297                         return outer.get_key ();
 298                 }
 299
 300                 public V get_value () {
 301                         assert (valid);
 302                         return inner.get ();
 303                 }
 304
 305                 public void set_value (V value) {
 306                         assert_not_reached ();
 307                 }
 308
 309                 public bool mutable { get { return false; } }
 310         }
 311
 312         private weak MultiMap<K, V> _read_only_view;
 313         public virtual new MultiMap<K, V> read_only_view {
 314                 owned get {
 315                         MultiMap<K, V> instance = _read_only_view;
 316                         if (_read_only_view == null) {
 317                                 instance = new ReadOnlyMultiMap<K, V> (this);
 318                                 _read_only_view = instance;
 319                                 instance.add_weak_pointer ((void**) (&_read_only_view));
 320                         }
 321                         return instance;
 322                 }
 323         }
 324
 325         // Future-proofing
 326         internal new virtual void reserved0() {}
 327         internal new virtual void reserved1() {}
 328         internal new virtual void reserved2() {}
 329         internal new virtual void reserved3() {}
 330         internal new virtual void reserved4() {}
 331         internal new virtual void reserved5() {}
 332         internal new virtual void reserved6() {}
 333         internal new virtual void reserved7() {}
 334         internal new virtual void reserved8() {}
 335 }
 336