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

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