bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/prioritystack/PriorityStack.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 \r
  13 package org.simantics.utils.datastructures.prioritystack;\r
  14 \r
  15 import java.lang.reflect.Array;\r
  16 import java.lang.reflect.Method;\r
  17 import java.util.ArrayList;\r
  18 import java.util.HashMap;\r
  19 import java.util.LinkedList;\r
  20 import java.util.List;\r
  21 import java.util.ListIterator;\r
  22 import java.util.Map;\r
  23 \r
  24 import org.simantics.utils.strings.EString;\r
  25 import org.simantics.utils.threads.IThreadWorkQueue;\r
  26 import org.simantics.utils.threads.SyncListenerList;\r
  27 \r
  28 \r
  29 /**\r
  30  * Implementation to IPriorityStack.\r
  31  * \r
  32  * <p>\r
  33  * Note!\r
  34  * getAllItems() is optimized for result with the penalty of slower add/remove methods. \r
  35  *\r
  36  * @author Toni Kalajainen\r
  37  * @param <E>\r
  38  */\r
  39 public class PriorityStack<E> implements IPriorityStack<E> {\r
  40         \r
  41         @SuppressWarnings({ "rawtypes" })\r
  42     private SyncListenerList<IPriorityStackListener> listeners =\r
  43                 new SyncListenerList<IPriorityStackListener>(IPriorityStackListener.class);\r
  44         \r
  45         private LinkedList<E> list = \r
  46                 new LinkedList<E>(); \r
  47         \r
  48         private E[] snapshotArray;\r
  49         \r
  50         private Map<E, Integer> priorities = \r
  51                 new HashMap<E, Integer>(); \r
  52         \r
  53         final Class<E> clazz;\r
  54         \r
  55         public PriorityStack(Class<E> clazz) {\r
  56                 this.clazz = clazz;\r
  57                 snapshotArray = createArray(0);\r
  58         }\r
  59         \r
  60         @Override\r
  61         public void add(E interactor, int priority) {\r
  62                 abu:\r
  63                 synchronized(this) {\r
  64                         if (list.contains(interactor))\r
  65                                 throw new IllegalArgumentException("InteractorStack already contains item "+interactor);\r
  66                 \r
  67                         priorities.put(interactor, priority);\r
  68                 \r
  69                         if (list.size()==0)\r
  70                         {\r
  71                                 list.add(interactor);\r
  72                                 snapshotArray = createSnapshot(list);\r
  73                                 break abu;\r
  74                         }\r
  75                                 \r
  76                         ListIterator<E> li = list.listIterator();\r
  77                         while (li.hasNext()) {\r
  78                                 E i = li.next();\r
  79                                 double w = priorities.get( i );\r
  80                                 if (w > priority) {\r
  81                                         li.previous();\r
  82                                         li.add(interactor);\r
  83                                         snapshotArray = createSnapshot(list);\r
  84                                         break abu;\r
  85                                 }\r
  86                         }\r
  87                         list.addLast(interactor);\r
  88                         snapshotArray = createSnapshot(list);\r
  89                 }\r
  90                 fireInteractorAdded(interactor);                \r
  91         }\r
  92         \r
  93         @Override\r
  94         public boolean remove(E interactor) {\r
  95                 synchronized(this) {\r
  96                         if (!priorities.containsKey(interactor)) \r
  97                                 return false;\r
  98                         priorities.remove(interactor);\r
  99                         list.remove(interactor);\r
 100                         snapshotArray = createSnapshot(list);\r
 101                 }\r
 102                 fireInteractorRemoved(interactor);\r
 103                 return true;\r
 104         }       \r
 105 \r
 106         @Override\r
 107         public synchronized Integer getPriority(E interactor) {\r
 108                 return priorities.get(interactor);\r
 109         }       \r
 110 \r
 111         @SuppressWarnings({ "unchecked" })\r
 112         private E[] createArray(int length)\r
 113         {\r
 114                 return (E[]) Array.newInstance(clazz, length);\r
 115         }\r
 116 \r
 117         E[] createSnapshot(List<E> list) {\r
 118                 E[] result = createArray(list.size());\r
 119                 int index = 0;\r
 120                 for (E i : list)\r
 121                         result[index++] = i; \r
 122                 return result;\r
 123         }\r
 124                 \r
 125         public synchronized int indexOf(E item)\r
 126         {\r
 127                 for (int i=0; i<snapshotArray.length; i++)\r
 128                         if (snapshotArray[i]==item)\r
 129                                 return i;\r
 130                 return -1;\r
 131         }       \r
 132         \r
 133         @Override\r
 134         public synchronized E[] toArray() {\r
 135                 return snapshotArray;\r
 136         }\r
 137 \r
 138         public synchronized <R extends E> R getSingleItem(Class<R> clazz)\r
 139         {\r
 140                 R array[] = getItemsByClass(clazz);\r
 141                 if (array.length!=1)\r
 142                         throw new RuntimeException("one "+clazz.getName()+" expected in PriorityStack, got "+array.length);\r
 143                 return (R) array[0];\r
 144         }\r
 145         \r
 146         @SuppressWarnings("unchecked")\r
 147     @Override\r
 148         public synchronized <R extends E> R[] getItemsByClass(Class<R> clazz)\r
 149         {\r
 150                 List<E> result = new ArrayList<E>(list.size());\r
 151                 for (E i : list)\r
 152                         if (clazz.isAssignableFrom(i.getClass()))\r
 153                                 result.add(i);\r
 154                 return (R[])result.toArray(createArray(result.size()));\r
 155         }\r
 156 \r
 157         private static Method itemAdded = SyncListenerList.getMethod(IPriorityStackListener.class, "itemAdded");\r
 158         private void fireInteractorAdded(E interactor)\r
 159         {\r
 160                 listeners.fireEventSync(itemAdded, this, interactor);\r
 161         }\r
 162         \r
 163         private static Method itemRemoved = SyncListenerList.getMethod(IPriorityStackListener.class, "itemRemoved");\r
 164         private void fireInteractorRemoved(E interactor)\r
 165         {\r
 166                 listeners.fireEventSync(itemRemoved, this, interactor);\r
 167         }\r
 168 \r
 169         @Override\r
 170         public synchronized void addStackListener(IPriorityStackListener<E> listener) {\r
 171                 listeners.add(listener);\r
 172         }\r
 173 \r
 174         @Override\r
 175         public synchronized void removeStackListener(IPriorityStackListener<E> listener) {\r
 176                 listeners.remove(listener);\r
 177         }\r
 178 \r
 179         @Override\r
 180         public synchronized boolean contains(E interactor) {\r
 181                 return list.contains(interactor);\r
 182         }\r
 183 \r
 184         @Override\r
 185         public void addStackListener(IThreadWorkQueue thread,\r
 186                         IPriorityStackListener<E> listener) {\r
 187                 listeners.add(thread, listener);\r
 188         }\r
 189 \r
 190         @Override\r
 191         public void removeStackListener(IThreadWorkQueue thread,\r
 192                         IPriorityStackListener<E> listener) {\r
 193                 listeners.remove(thread, listener);\r
 194         }\r
 195 \r
 196         @Override\r
 197         public String toString() {\r
 198             return EString.implode(snapshotArray, "\n");\r
 199         }\r
 200 \r
 201 }\r