From 663631f0456fcc245dd835889f86541d75161c53 Mon Sep 17 00:00:00 2001
From: Roman Shevchenko <roman.shevchenko@jetbrains.com>
Date: Thu, 28 Aug 2014 20:52:43 +0400
Subject: java-decompiler: post-import cleanup (classes moved)

---
 .../java/decompiler/util/FastSparseSetFactory.java | 549 +++++++++++++++++++++
 1 file changed, 549 insertions(+)
 create mode 100644 src/org/jetbrains/java/decompiler/util/FastSparseSetFactory.java

(limited to 'src/org/jetbrains/java/decompiler/util/FastSparseSetFactory.java')

diff --git a/src/org/jetbrains/java/decompiler/util/FastSparseSetFactory.java b/src/org/jetbrains/java/decompiler/util/FastSparseSetFactory.java
new file mode 100644
index 0000000..352dc2a
--- /dev/null
+++ b/src/org/jetbrains/java/decompiler/util/FastSparseSetFactory.java
@@ -0,0 +1,549 @@
+/*
+ *    Fernflower - The Analytical Java Decompiler
+ *    http://www.reversed-java.com
+ *
+ *    (C) 2008 - 2010, Stiver
+ *
+ *    This software is NEITHER public domain NOR free software 
+ *    as per GNU License. See license.txt for more details.
+ *
+ *    This software is distributed WITHOUT ANY WARRANTY; without 
+ *    even the implied warranty of MERCHANTABILITY or FITNESS FOR 
+ *    A PARTICULAR PURPOSE. 
+ */
+
+package org.jetbrains.java.decompiler.util;
+
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Set;
+
+public class FastSparseSetFactory<E> {
+
+	private VBStyleCollection<int[], E> colValuesInternal = new VBStyleCollection<int[], E>();  
+
+	private int lastBlock;
+	
+	private int lastMask;
+	
+	public FastSparseSetFactory(Collection<E> set) {
+		
+		int block = -1;
+		int mask = -1;
+		int index = 0;
+		
+		for(E element : set) {
+		
+			block = index / 32;
+
+			if(index % 32 == 0) {
+				mask = 1;
+			} else {
+				mask <<= 1;
+			}
+			
+			colValuesInternal.putWithKey(new int[] {block, mask}, element);
+			
+			index++;
+		}
+		
+		lastBlock = block;
+		lastMask = mask;
+	}
+
+	private int[] addElement(E element) {
+		
+		if(lastMask == -1 || lastMask == 0x80000000) {
+			lastMask = 1;
+			lastBlock++;
+		} else {
+			lastMask <<= 1;
+		}
+		
+		int[] pointer = new int[] {lastBlock, lastMask};
+		colValuesInternal.putWithKey(pointer, element);
+		
+		return pointer;
+	}
+	
+	public FastSparseSet<E> spawnEmptySet() {
+		return new FastSparseSet<E>(this);
+	}
+	
+	public int getLastBlock() {
+		return lastBlock;
+	}
+
+	public int getLastMask() {
+		return lastMask;
+	}
+
+	private VBStyleCollection<int[], E> getInternalValuesCollection() {
+		return colValuesInternal;
+	}
+	
+
+	public static class FastSparseSet<E> implements Iterable<E> {
+		
+		private FastSparseSetFactory<E> factory;
+
+		private VBStyleCollection<int[], E> colValuesInternal;
+		
+		private int[] data;
+		private int[] next;
+		
+		private FastSparseSet(FastSparseSetFactory<E> factory) {
+			this.factory = factory;
+			this.colValuesInternal = factory.getInternalValuesCollection();
+			
+			int length = factory.getLastBlock()+1;
+			this.data = new int[length];
+			this.next = new int[length];
+		}
+		
+		private FastSparseSet(FastSparseSetFactory<E> factory, int[] data, int[] next) {
+			this.factory = factory;
+			this.colValuesInternal = factory.getInternalValuesCollection();
+			
+			this.data = data;
+			this.next = next;
+		}
+
+		public FastSparseSet<E> getCopy() {
+			
+			int arrlength = data.length;
+			int[] cpdata = new int[arrlength];
+			int[] cpnext = new int[arrlength];
+		
+			System.arraycopy(data, 0, cpdata, 0, arrlength);
+			System.arraycopy(next, 0, cpnext, 0, arrlength);
+
+			FastSparseSet<E> copy = new FastSparseSet<E>(factory, cpdata, cpnext);
+			
+			return copy;
+		}
+		
+		private int[] ensureCapacity(int index) {
+
+			int newlength = data.length;
+			if(newlength == 0) {
+				newlength = 1;
+			}
+			
+			while(newlength <= index) {
+				newlength *=2;
+			}
+			
+			int[] newdata = new int[newlength];
+			System.arraycopy(data, 0, newdata, 0, data.length);
+			data = newdata;
+			
+			int[] newnext = new int[newlength];
+			System.arraycopy(next, 0, newnext, 0, next.length);
+			next = newnext;
+			
+			return newdata;
+		}
+
+		public void add(E element) {
+			int[] index = colValuesInternal.getWithKey(element);
+			
+			if(index == null) {
+				index = factory.addElement(element);
+			}
+			
+			int block = index[0];
+			if(block >= data.length) {
+				ensureCapacity(block);	
+			}
+			
+			data[block] |= index[1];
+			
+			changeNext(next, block, next[block], block);
+		}
+		
+		public void setAllElements() {
+
+			int lastblock = factory.getLastBlock();
+			int lastmask = factory.getLastMask();
+			
+			if(lastblock >= data.length) {
+				ensureCapacity(lastblock);	
+			}
+			
+			for(int i=lastblock-1;i>=0;i--) {
+				data[i] = 0xFFFFFFFF;
+				next[i] = i+1;
+			}
+			
+			data[lastblock] = lastmask | (lastmask-1);
+			next[lastblock] = 0;
+		}
+		
+		public void addAll(Set<E> set) {
+			for(E element : set) {
+				add(element);
+			}
+		}
+
+		public void remove(E element) {
+			int[] index = colValuesInternal.getWithKey(element);
+			
+			if(index == null) {
+				index = factory.addElement(element);
+			}
+			
+			int block = index[0]; 
+			if(block < data.length) {
+				data[block] &= ~index[1];
+				
+				if(data[block] == 0) {
+					changeNext(next, block, block, next[block]);
+				}
+			}
+		}
+
+		public void removeAll(Set<E> set) {
+			for(E element : set) {
+				remove(element);
+			}
+		}
+		
+		public boolean contains(E element) {
+			int[] index = colValuesInternal.getWithKey(element);
+			
+			if(index == null) {
+				index = factory.addElement(element);
+			}
+			
+			return index[0] >= data.length?false:((data[index[0]] & index[1]) != 0);
+		}
+
+		public boolean contains(FastSparseSet<E> set) {
+			int[] extdata = set.getData();
+			int[] intdata = data;
+			
+			int minlength = Math.min(extdata.length, intdata.length); 
+			
+			for(int i=minlength-1;i>=0;i--) {
+				if((extdata[i] & ~intdata[i]) != 0) {
+					return false;
+				}
+			}
+
+			for(int i=extdata.length-1;i>=minlength;i--) {
+				if(extdata[i] != 0) {
+					return false;
+				}
+			}
+			
+			return true;
+		}
+		
+		private void setNext() {
+			
+			int link = 0;
+			for(int i=data.length-1;i>=0;i--) {
+				next[i] = link;
+				if(data[i] != 0) {
+					link = i;
+				}
+			}
+		}
+		
+		private void changeNext(int[] arrnext, int key, int oldnext, int newnext) {
+			for(int i=key-1;i>=0;i--) {
+				if(arrnext[i] == oldnext) {
+					arrnext[i] = newnext;
+				} else {
+					break;
+				}
+			}
+		}
+		
+		public void union(FastSparseSet<E> set) {
+
+			int[] extdata = set.getData();
+			int[] extnext = set.getNext();
+			int[] intdata = data;
+			int intlength = intdata.length;
+
+			int pointer = 0;
+			do {
+				if(pointer >= intlength) {
+					intdata = ensureCapacity(extdata.length - 1);
+				}
+				
+				boolean nextrec = (intdata[pointer] == 0);
+				intdata[pointer] |= extdata[pointer];
+				
+				if(nextrec) {
+					changeNext(next, pointer, next[pointer], pointer);
+				}
+				
+				pointer = extnext[pointer];
+
+			} while(pointer!=0);
+		}
+
+		public void intersection(FastSparseSet<E> set) {
+			int[] extdata = set.getData();
+			int[] intdata = data;
+	
+			int minlength = Math.min(extdata.length, intdata.length); 
+			
+			for(int i=minlength-1;i>=0;i--) {
+				intdata[i] &= extdata[i];
+			}
+			
+			for(int i=intdata.length-1;i>=minlength;i--) {
+				intdata[i] = 0;
+			}
+			
+			setNext();
+		}
+		
+		public void symdiff(FastSparseSet<E> set) {
+			int[] extdata = set.getData();
+			int[] intdata = data;
+
+			int minlength = Math.min(extdata.length, intdata.length); 
+
+			for(int i=minlength-1;i>=0;i--) {
+				intdata[i] ^= extdata[i];
+			}
+			
+			boolean expanded = false;
+			for(int i=extdata.length-1;i>=minlength;i--) {
+				if(extdata[i] != 0) {
+					if(!expanded) {
+						intdata = ensureCapacity(extdata.length - 1);
+					}
+					intdata[i] = extdata[i];
+				}
+			}
+			
+			setNext();
+		}
+		
+		public void complement(FastSparseSet<E> set) {
+			
+			int[] extdata = set.getData();
+			int[] intdata = data;
+			int extlength = extdata.length;
+
+			int pointer = 0;
+			do {
+				if(pointer >= extlength) {
+					break;
+				}
+				
+				intdata[pointer] &= ~extdata[pointer];
+				if(intdata[pointer] == 0) {
+					changeNext(next, pointer, pointer, next[pointer]);
+				}
+				
+				pointer = next[pointer];
+
+			} while(pointer!=0);
+		}
+		
+		
+		public boolean equals(Object o) {
+      if(o == this) return true;
+      if(o == null || !(o instanceof FastSparseSet)) return false;
+			
+			int[] longdata = ((FastSparseSet)o).getData();
+			int[] shortdata = data;
+			
+			if(data.length > longdata.length) {
+				shortdata = longdata;
+				longdata = data;
+			}
+
+			for(int i=shortdata.length-1;i>=0;i--) {
+				if(shortdata[i] != longdata[i]) {
+					return false;
+				}
+			}
+			
+			for(int i=longdata.length-1;i>=shortdata.length;i--) {
+				if(longdata[i] != 0) {
+					return false;
+				}
+			}
+			
+			return true;
+		}
+		
+		public int getCardinality() {
+			
+			boolean found = false;
+			int[] intdata = data;
+			
+			for(int i=intdata.length-1;i>=0;i--) {
+				int block = intdata[i];  
+				if(block != 0) {
+					if(found) {
+						return 2; 
+					} else {
+						if ((block & (block-1)) == 0) {
+							found = true;
+						} else {
+							return 2;
+						}
+					}
+				}
+			}
+			
+			return found?1:0;
+		}
+		
+		public boolean isEmpty() {
+			return data.length == 0 || (next[0] == 0 && data[0] == 0);
+		}
+		
+		public Iterator<E> iterator() {
+			return new FastSparseSetIterator<E>(this);
+		}
+		
+		public Set<E> toPlainSet() {
+			HashSet<E> set = new HashSet<E>();
+			
+			int[] intdata = data;
+			
+			int size = data.length*32;
+			if(size > colValuesInternal.size()) {
+				size = colValuesInternal.size();
+			}
+			
+			for(int i=size-1;i>=0;i--) {
+				int[] index = colValuesInternal.get(i);
+				
+				if((intdata[index[0]] & index[1]) != 0) {
+					set.add(colValuesInternal.getKey(i));
+				}
+			}
+			
+			return set;
+		}
+
+		public String toString() {
+			return toPlainSet().toString();
+		}
+
+		public String toBinary() {
+			
+			StringBuilder buffer = new StringBuilder();
+			int[] intdata = data;
+			
+			for(int i=0;i<intdata.length;i++) {
+				buffer.append(" ").append(Integer.toBinaryString(intdata[i]));
+			}
+				
+			return buffer.toString();	
+		}
+		
+		private int[] getData() {
+			return data;
+		}
+
+		private int[] getNext() {
+			return next;
+		}
+
+		public int[] getLoad() {
+			int[] intdata = data;
+			int notempty = 0;
+			
+			for(int i=0;i<intdata.length;i++) {
+				if(intdata[i] != 0) {
+					notempty++;
+				}
+			}
+			
+			return new int[]{intdata.length, notempty};
+		}
+		
+		public FastSparseSetFactory<E> getFactory() {
+			return factory;
+		}
+	}
+
+	public static class FastSparseSetIterator<E> implements Iterator<E> {
+
+		private VBStyleCollection<int[], E> colValuesInternal;
+		private int[] data;
+		private int[] next;
+		private int size;
+
+		private int pointer = -1;
+		private int next_pointer = -1;
+		
+		private FastSparseSetIterator(FastSparseSet<E> set) {
+			colValuesInternal = set.getFactory().getInternalValuesCollection();
+			data = set.getData();
+			next = set.getNext();
+			size = colValuesInternal.size();
+		}
+		
+		private int getNextIndex(int index) {
+			
+			index++;
+			int bindex = index >>> 5;
+			int dindex = index & 0x1F;
+			
+			while(bindex < data.length) {
+				int block = data[bindex];
+				
+				if(block != 0) {
+					block >>>= dindex;
+					while(dindex < 32) {
+						if((block & 1) != 0) {
+							return (bindex << 5) + dindex;
+						}
+						block >>>= 1;
+						dindex++;
+					}
+				}
+				
+				dindex = 0;
+				bindex = next[bindex];
+				
+				if(bindex == 0) {
+					break;
+				}
+			}
+			
+			return -1;
+		}
+		
+		public boolean hasNext() {
+			next_pointer = getNextIndex(pointer);
+			return (next_pointer >= 0);
+		}
+
+		public E next() {
+			if(next_pointer >= 0) {
+				pointer = next_pointer;
+			} else {
+				pointer = getNextIndex(pointer);
+				if(pointer == -1) {
+					pointer = size;
+				}
+			}
+
+			next_pointer = -1;
+			return pointer<size?colValuesInternal.getKey(pointer):null;
+		}
+
+		public void remove() {
+			int[] index = colValuesInternal.get(pointer);
+			data[index[0]] &= ~index[1];
+		}
+		
+	}
+	
+}
+
-- 
cgit v1.2.3