bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/MapSet.java

   1 /*******************************************************************************
   2  * Copyright (c) 2007, 2010 Association for Decentralized Information Management
   3  * in Industry THTH ry.
   4  * All rights reserved. This program and the accompanying materials
   5  * are made available under the terms of the Eclipse Public License v1.0
   6  * which accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *
   9  * Contributors:
  10  *     VTT Technical Research Centre of Finland - initial API and implementation
  11  *******************************************************************************/
  12 package org.simantics.utils.datastructures;
  13
  14 import java.util.Collections;
  15 import java.util.Comparator;
  16 import java.util.HashMap;
  17 import java.util.HashSet;
  18 import java.util.Map;
  19 import java.util.Set;
  20 import java.util.TreeMap;
  21
  22 /**
  23  * MapSet is an associative data structure a key type on the left side (L) and a
  24  * set element type of the right side.
  25  *
  26  * <p>
  27  * Based on {@link MapList} by Toni Kalajainen.
  28  * </p>
  29  *
  30  * @author Tuukka Lehtonen
  31  */
  32 public abstract class MapSet<L, R> {
  33
  34     protected Map<L, Set<R>> sets;
  35
  36     public static class Hash<L, R> extends MapSet<L, R> {
  37         public Hash() {
  38                 sets = new HashMap<L, Set<R>>();
  39         }
  40         protected Set<R> getOrCreateSet(L key) {
  41             Set<R> set = sets.get(key);
  42             if (set == null) {
  43                 set = new HashSet<R>();
  44                 sets.put(key, set);
  45             }
  46             return set;
  47         }
  48     }
  49
  50     public static class Tree<L, R> extends MapSet<L, R> {
  51         public Tree() {
  52                 sets = new TreeMap<L, Set<R>>();
  53         }
  54         public Tree(Comparator<? super L> comparator) {
  55                 sets = new TreeMap<L, Set<R>>(comparator);
  56         }
  57         protected Set<R> getOrCreateSet(L key) {
  58             Set<R> set = sets.get(key);
  59             if (set == null) {
  60                 set = new HashSet<R>();
  61                 sets.put(key, set);
  62             }
  63             return set;
  64         }
  65     }
  66
  67     public boolean add(L key, R value) {
  68         Set<R> set = getOrCreateSet(key);
  69         return set.add(value);
  70     }
  71
  72     protected abstract Set<R> getOrCreateSet(L key);
  73
  74     private Set<R> getSet(L key) {
  75         return sets.get(key);
  76     }
  77
  78     /**
  79      * @param key
  80      * @return a valid set, empty if no values exist
  81      */
  82     public Set<R> removeValues(L key) {
  83         Set<R> set = sets.remove(key);
  84         if (set == null)
  85             return Collections.emptySet();
  86         return set;
  87     }
  88
  89     public boolean remove(L key, R value) {
  90         Set<R> set = getSet(key);
  91         if (set == null)
  92             return false;
  93         boolean result = set.remove(value);
  94         if (set.isEmpty())
  95             sets.remove(key);
  96         return result;
  97     }
  98
  99     public void clear() {
 100         sets.clear();
 101     }
 102
 103     public L[] getKeys(L[] list) {
 104         return sets.keySet().toArray(list);
 105     }
 106
 107     public Set<L> getKeys() {
 108         return sets.keySet();
 109     }
 110
 111     public boolean hasValues(L key) {
 112         return sets.containsKey(key);
 113     }
 114
 115     public R[] getValues(L key, R[] list) {
 116         Set<R> l = sets.get(key);
 117         if (l == null)
 118             return null;
 119         return l.toArray(list);
 120     }
 121
 122     public Set<R> getValues(L key) {
 123         Set<R> l = sets.get(key);
 124         if (l == null)
 125             return null;
 126         return new HashSet<R>(l);
 127     }
 128
 129     public Set<R> getValuesUnsafe(L key) {
 130         return sets.get(key);
 131     }
 132
 133 }