JAVA

Using an SSet as your underlying structure, design and implement an application that reads a (large) text file and allows you to search, interactively, for any substring contained in the text. As the user types their query, a matching part of the text (if any) should appear as a result.

Hint 1: Every substring is a prefix of some suffix, so it suffices to store all suffixes of the text file. Hint 2: Any suffix can be represented compactly as a single integer indicating where the suffix begins in the text.

Test your application on some large texts, such as some of the books available at Project Gutenberg [1]. If done correctly, your applications will be very responsive; there should be no noticeable lag between typing keystrokes and seeing the results.

// // Source code recreated from a .class file by IntelliJ IDEA // (powered by Fernflower decompiler) // package ods; import java.lang.reflect.Array; import java.util.Arrays; import java.util.Comparator; import java.util.Iterator; import java.util.Random; public class SkiplistSSet implements SSet { protected Comparator c; protected SkiplistSSet.Node sentinel; int h; int n; Random rand; protected SkiplistSSet.Node[] stack; public SkiplistSSet.Finger getFinger() { return new SkiplistSSet.Finger(); } public T find(SkiplistSSet.Finger var1, T var2) { int var3 = 0; SkiplistSSet.Node var4; for(var4 = var1.s[var3]; var3 < this.h && (var4 != this.sentinel && this.c.compare(var2, var4.x) <= 0 || var4.next[var3] != null && this.c.compare(var2, var4.next[var3].x) > 0); var4 = var1.s[var3]) { ++var3; } --var3; while(var3 >= 0) { while(var4.next[var3] != null && this.c.compare(var4.next[var3].x, var2) < 0) { var4 = var4.next[var3]; } var1.s[var3] = var4; --var3; } return var4.next[0] == null ? null : var4.next[0].x; } public SkiplistSSet(Comparator var1) { this.c = var1; this.n = 0; this.sentinel = new SkiplistSSet.Node((Object)null, 32); this.stack = (SkiplistSSet.Node[])((SkiplistSSet.Node[])Array.newInstance(SkiplistSSet.Node.class, this.sentinel.next.length)); this.h = 0; this.rand = new Random(); } public SkiplistSSet() { this(new DefaultComparator()); } protected SkiplistSSet.Node findPredNode(T var1) { SkiplistSSet.Node var2 = this.sentinel; for(int var3 = this.h; var3 >= 0; --var3) { while(var2.next[var3] != null && this.c.compare(var2.next[var3].x, var1) < 0) { var2 = var2.next[var3]; } } return var2; } public T find(T var1) { SkiplistSSet.Node var2 = this.findPredNode(var1); return var2.next[0] == null ? null : var2.next[0].x; } public T findGE(T var1) { if (var1 == null) { return this.sentinel.next[0] == null ? null : this.sentinel.next[0].x; } else { return this.find(var1); } } public T findLT(T var1) { if (var1 != null) { return this.findPredNode(var1).x; } else { SkiplistSSet.Node var2 = this.sentinel; for(int var3 = this.h; var3 >= 0; --var3) { while(var2.next[var3] != null) { var2 = var2.next[var3]; } } return var2.x; } } public boolean remove(T var1) { boolean var2 = false; SkiplistSSet.Node var3 = this.sentinel; int var4 = this.h; for(int var5 = 0; var4 >= 0; --var4) { while(var3.next[var4] != null && (var5 = this.c.compare(var3.next[var4].x, var1)) < 0) { var3 = var3.next[var4]; } if (var3.next[var4] != null && var5 == 0) { var2 = true; var3.next[var4] = var3.next[var4].next[var4]; if (var3 == this.sentinel && var3.next[var4] == null) { --this.h; } } } if (var2) { --this.n; } return var2; } protected int pickHeight() { int var1 = this.rand.nextInt(); int var2 = 0; for(int var3 = 1; (var1 & var3) != 0; var3 <<= 1) { ++var2; } return var2; } public void clear() { this.n = 0; this.h = 0; Arrays.fill(this.sentinel.next, (Object)null); } public int size() { return this.n; } public Comparator comparator() { return this.c; } protected Iterator iterator(SkiplistSSet.Node var1) { class SkiplistIterator implements Iterator { SkiplistSSet.Node u; SkiplistSSet.Node prev; public SkiplistIterator(SkiplistSSet.Node var2) { this.u = var2; this.prev = null; } public boolean hasNext() { return this.u.next[0] != null; } public T next() { this.prev = this.u; this.u = this.u.next[0]; return this.u.x; } public void remove() { SkiplistSSet.this.remove(this.prev.x); } } return new SkiplistIterator(var1); } public Iterator iterator() { return this.iterator(this.sentinel); } public Iterator iterator(T var1) { return this.iterator(this.findPredNode(var1)); } public boolean add(T var1) { SkiplistSSet.Node var2 = this.sentinel; int var3 = this.h; for(int var4 = 0; var3 >= 0; this.stack[var3--] = var2) { while(var2.next[var3] != null && (var4 = this.c.compare(var2.next[var3].x, var1)) < 0) { var2 = var2.next[var3]; } if (var2.next[var3] != null && var4 == 0) { return false; } } SkiplistSSet.Node var5; for(var5 = new SkiplistSSet.Node(var1, this.pickHeight()); this.h < var5.height(); this.stack[++this.h] = this.sentinel) { } for(int var6 = 0; var6 < var5.next.length; ++var6) { var5.next[var6] = this.stack[var6].next[var6]; this.stack[var6].next[var6] = var5; } ++this.n; return true; } public static void main(String[] var0) { int var1 = 100000; SkiplistSSet var2 = new SkiplistSSet(); System.out.println("Adding " + var1 + " elements"); int var3; for(var3 = 0; var3 < var1; ++var3) { var2.add(2 * var3); } System.out.println("Searching"); for(var3 = 0; var3 < 2 * var1; ++var3) { Integer var4 = (Integer)var2.find(var3); Utils.myassert(var3 > 2 * (var1 - 1) || Math.abs(var4 - var3) <= 1); } System.out.println("Searching (sequential - with finger)"); SkiplistSSet.Finger var8 = var2.getFinger(); for(int var9 = 0; var9 < 2 * var1; ++var9) { Integer var5 = (Integer)var2.find(var8, var9); Utils.myassert(var9 > 2 * (var1 - 1) || Math.abs(var5 - var9) <= 1); } System.out.println("Searching (random - with finger)"); Random var10 = new Random(); int var11; for(var11 = 0; var11 < 2 * var1; ++var11) { int var6 = var10.nextInt(2 * var1); Integer var7 = (Integer)var2.find(var8, var6); Utils.myassert(var6 > 2 * (var1 - 1) || Math.abs(var7 - var6) <= 1); } System.out.println("Searching (backwards - with finger)"); Integer var12; for(var11 = 2 * var1; var11 >= 0; --var11) { var12 = (Integer)var2.find(var8, var11); Utils.myassert(var11 > 2 * (var1 - 1) || Math.abs(var12 - var11) <= 1); } System.out.println("Removing"); for(var11 = 0; var11 < var1 / 2; ++var11) { var2.remove(4 * var11); } System.out.println("Verifying"); for(var11 = 0; var11 < 2 * var1; ++var11) { var12 = (Integer)var2.find(var11); Utils.myassert(var11 > 2 * (var1 - 1) || Math.abs(var12 - var11) <= 3); } System.out.println("Done - size() = " + var2.size()); } public class Finger { protected SkiplistSSet.Node[] s; public Finger() { this.s = (SkiplistSSet.Node[])((SkiplistSSet.Node[])Array.newInstance(SkiplistSSet.Node.class, SkiplistSSet.this.h + 1)); for(int var2 = 0; var2 <= SkiplistSSet.this.h; ++var2) { this.s[var2] = SkiplistSSet.this.sentinel; } } } protected static class Node { T x; SkiplistSSet.Node[] next; public Node(T var1, int var2) { this.x = var1; this.next = (SkiplistSSet.Node[])((SkiplistSSet.Node[])Array.newInstance(SkiplistSSet.Node.class, var2 + 1)); } public int height() { return this.next.length - 1; } } }