Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package trials;
- import java.util.HashMap;
- import java.util.Stack;
- public class PQWithSearch {
- private Phrase[] pq;
- private HashMap<Phrase, Integer> positionsMap = new HashMap<Phrase, Integer>();
- public int size = 0;
- public PQWithSearch(int maxLength){
- pq = new Phrase[maxLength+1];
- }
- public void stringInsert(String text){
- System.out.println("Trying to insert text: " + text);
- Phrase ph = new Phrase(text);
- if (positionsMap.containsKey(ph)){
- System.out.println("found it: " + ph);
- int phraseIndex = positionsMap.get(ph);
- pq[phraseIndex].incrementCount();
- } else {
- System.out.println("Didn't find it, adding it");
- insert(ph);
- }
- }
- public void insert(Phrase k){
- size++;
- assign(size, k);
- swim(size);
- }
- public Phrase delMin(){
- Phrase min = pq[1];
- size--;
- exch(1, size);
- assign(size+1, null);
- sink(1);
- removeFromPositionsMap(min);
- return min;
- }
- public boolean isEmpty(){
- return size == 0;
- }
- private void assign(int index, Phrase value){
- pq[index] = value;
- if(value != null){
- positionsMap.put(value, index);
- }
- }
- private void removeFromPositionsMap(Phrase phrase){
- positionsMap.remove(phrase);
- }
- private void swim(int k){
- while(k>1 && greater(k/2, k)){
- exch(k,k/2);
- k = k/2;
- }
- }
- private void sink(int k){
- while(2*k <= size){
- int j = 2 *k;
- if (j < size && greater(j,j+1)){
- j++;
- }
- if (greater(k,j)){
- exch(k,j);
- k = j;
- } else {
- break;
- }
- }
- }
- private boolean less(int i, int j){
- if (pq[i].compareTo(pq[j]) < 0){
- return true;
- }
- return false;
- }
- private boolean greater(int i, int j){
- if (pq[i].compareTo(pq[j]) > 0){
- return true;
- }
- return false;
- }
- private void exch(int i, int j) {
- Phrase t = pq[i];
- assign(i, pq[j]);
- assign(j, t);
- }
- public static void main(String[] args) {
- int maxSize = 5;
- PQWithSearch pq = new PQWithSearch(maxSize+1);
- String [] fileContents = new String[]{"a","a","c","d","e","f","g","a","b","b","c"};
- for (String text : fileContents){
- pq.stringInsert(text);
- if (pq.size > maxSize){
- pq.delMin();
- }
- }
- Stack<Phrase> stack = new Stack<Phrase>();
- while (!pq.isEmpty()) stack.push(pq.delMin());
- for (Phrase t : stack)
- System.out.println(t);
- }
- }
- class Phrase implements Comparable<Phrase>{
- private String text;
- private int count = 1;
- public Phrase(String text){
- this.text = text;
- }
- @Override
- public int compareTo(Phrase o) {
- if (this.count < o.count){
- return -1;
- }
- else if (this.count > o.count){
- return 1;
- }
- return 0;
- }
- public int hashCode(){
- return this.text.hashCode();
- }
- public boolean equals(Object other){
- Phrase otherPhrase = (Phrase) other;
- boolean isEqual = this.text.equals(otherPhrase.text);
- return isEqual;
- }
- public void incrementCount(){
- this.count += 1;
- }
- public String toString(){
- return this.text + ": " + this.count;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement