Algorithms-I : 2-Randomized_Queues_Deques: finished

4 files changed, 168 insertions, 25 deletions

diff --git a/Algorithms/Part-I/2-Randomized_Queues_Deques/Deque.java b/Algorithms/Part-I/2-Randomized_Queues_Deques/Deque.java
index e8a17de..d27629f 100644
--- a/Algorithms/Part-I/2-Randomized_Queues_Deques/Deque.java
+++ b/Algorithms/Part-I/2-Randomized_Queues_Deques/Deque.java
@@ -10,9 +10,9 @@ public class Deque<Item> implements Iterable<Item>
 
     private class Node
     {
-        Item item;
-        Node next;
-        Node prev;
+        private Item item;
+        private Node next;
+        private Node prev;
     }
 
     // construct an empty deque
@@ -24,16 +24,10 @@ public class Deque<Item> implements Iterable<Item>
     }
 
     // is the deque empty?
-    public boolean isEmpty()
-    {
-        return (head == null);
-    }
+    public boolean isEmpty() { return n == 0; }
 
     // return the number of items on the deque
-    public int size()
-    {
-        return n;
-    }
+    public int size() { return n; }
 
     // insert the item at the front
     public void addFirst(Item item)
@@ -43,8 +37,11 @@ public class Deque<Item> implements Iterable<Item>
         node.item = item;
         node.next = head;
         node.prev = null;
+        if (head == null)
+            tail = node;
+        else
+            head.prev = node;
         head = node;
-        if (tail == null) tail = head;
         n++;
     }
 
@@ -57,14 +54,10 @@ public class Deque<Item> implements Iterable<Item>
         node.next = null;
         node.prev = tail;
         if (tail == null)
-        {
-            head = tail = node;
-        }
+            head = node;
         else
-        {
             tail.next = node;
-            tail = tail.next;
-        }
+        tail = node;
         n++;
     }
 
@@ -73,9 +66,18 @@ public class Deque<Item> implements Iterable<Item>
     {
         if (head == null) throw new java.util.NoSuchElementException();
         Item item = head.item;
-        if (tail == head) tail = tail.next;
-        head = head.next;
-        head.prev = null;
+        if (head == tail)           // head.next == null
+        {
+            head = null;
+            tail = null;
+        }
+        else
+        {
+            Node prevHead = head;
+            head = head.next;
+            head.prev = null;
+            prevHead.next = null;
+        }
         n--;
         return item;
     }
@@ -85,14 +87,17 @@ public class Deque<Item> implements Iterable<Item>
     {
         if (tail == null) throw new java.util.NoSuchElementException();
         Item item = tail.item;
-        if (head == tail)
+        if (head == tail)           // tail.prev == null
         {
-            head = tail = null;
+            head = null;
+            tail = null;
         }
         else
         {
+            Node prevTail = tail;
             tail = tail.prev;
             tail.next = null;
+            prevTail.prev = null;
         }
         n--;
         return item;
@@ -105,8 +110,10 @@ public class Deque<Item> implements Iterable<Item>
     {
         private Node current = head;
 
-        public boolean hasNext() { return current != null; }
-        public void remove() { throw new java.lang.UnsupportedOperationException(); }
+        public boolean hasNext()
+        { return current != null; }
+        public void remove()
+        { throw new java.lang.UnsupportedOperationException(); }
         public Item next()
         {
             if (current == null) throw new java.util.NoSuchElementException();
diff --git a/Algorithms/Part-I/2-Randomized_Queues_Deques/RandomizedQueue.java b/Algorithms/Part-I/2-Randomized_Queues_Deques/RandomizedQueue.java
new file mode 100644
index 0000000..19d9295
--- /dev/null
+++ b/Algorithms/Part-I/2-Randomized_Queues_Deques/RandomizedQueue.java
@@ -0,0 +1,97 @@
+/* vim: set expandtab tabstop=4 shiftwidth=4 : */
+
+import java.util.Iterator;
+
+public class RandomizedQueue<Item> implements Iterable<Item>
+{
+    private int n;
+    private Item[] items;
+
+    // construct an empty randomized queue
+    public RandomizedQueue()
+    {
+        n = 0;
+        items = (Item[]) new Object[1];
+    }
+
+    // is the queue empty?
+    public boolean isEmpty() { return n == 0; }
+
+    // return the number of items on the queue
+    public int size() { return n; }
+
+    // add the item
+    public void enqueue(Item item)
+    {
+        if (item == null) throw new java.lang.NullPointerException();
+        if (n == items.length)
+        {
+            Item[] copy = (Item[]) new Object[n*2];
+            for (int i = 0; i < n; i++)
+                copy[i] = items[i];
+            items = copy;
+        }
+        items[n++] = item;
+    }
+
+    // delete and return a random item
+    public Item dequeue()
+    {
+        if (n == 0) throw new java.util.NoSuchElementException();
+        int r = StdRandom.uniform(n);
+        Item item = items[r];
+        items[r] = items[--n];
+        items[n] = null;
+        if (n > 0 && n == items.length/4)
+        {
+            Item[] copy = (Item[]) new Object[items.length/2];
+            for (int i = 0; i < n; i++)
+                copy[i] = items[i];
+            items = copy;
+        }
+        return item;
+    }
+
+    // return (but do not delete) a random item
+    public Item sample()
+    {
+        if (n == 0) throw new java.util.NoSuchElementException();
+        return items[StdRandom.uniform(n)];
+    }
+
+    // return an independent iterator over items in random order
+    public Iterator<Item> iterator() { return new RandomizedQueueIterator(); }
+
+    private class RandomizedQueueIterator implements Iterator<Item>
+    {
+        // must be random !!!!
+        private int idx;
+        private int[] random;
+
+        public RandomizedQueueIterator()
+        {
+            idx = 0;
+            random = new int[n];
+            for (int i = 0; i < n; i++)
+                random[i] = i;
+            for (int i = 0; i < n; i++)
+            {
+                int r = StdRandom.uniform(i + 1);
+                int tmp = random[i];
+                random[i] = random[r];
+                random[r] = tmp;
+            }
+        }
+
+        public boolean hasNext()
+        { return idx < n; }
+        public void remove()
+        { throw new java.lang.UnsupportedOperationException(); }
+        public Item next()
+        {
+            if (idx >= n) throw new java.util.NoSuchElementException();
+            Item item = items[random[idx++]];
+            return item;
+        }
+    }
+}
diff --git a/Algorithms/Part-I/2-Randomized_Queues_Deques/Subset.java b/Algorithms/Part-I/2-Randomized_Queues_Deques/Subset.java
new file mode 100644
index 0000000..61a8502
--- /dev/null
+++ b/Algorithms/Part-I/2-Randomized_Queues_Deques/Subset.java
@@ -0,0 +1,18 @@
+/* vim: set expandtab tabstop=4 shiftwidth=4 : */
+
+public class Subset
+{
+    public static void main(String[] args)
+    {
+        int k = Integer.parseInt(args[0]);
+        if (k == 0) return;
+        RandomizedQueue<String> q = new RandomizedQueue<String>();
+        while (!StdIn.isEmpty())
+        {
+            q.enqueue(StdIn.readString());
+        }
+        for (int i = 0; i < k; i++)
+            System.out.println(q.dequeue());
+        System.out.println();
+    }
+}
diff --git a/Algorithms/Part-I/2-Randomized_Queues_Deques/run.sh b/Algorithms/Part-I/2-Randomized_Queues_Deques/run.sh
new file mode 100755
index 0000000..6adde6d
--- /dev/null
+++ b/Algorithms/Part-I/2-Randomized_Queues_Deques/run.sh
@@ -0,0 +1,21 @@
+#! /bin/bash
+
+export "CLASSPATH=$CLASSPATH:.:$HOME/algs4/algs4.jar:$HOME/algs4/stdlib.jar"
+
+CLASSES="Deque RandomizedQueue Subset"
+
+rm *.class *.zip 2>/dev/null
+
+for kls in $CLASSES; do
+    ~/algs4/bin/checkstyle ${kls}.java
+    javac ${kls}.java
+done
+~/algs4/bin/findbugs *.class
+
+echo "RUN..."
+echo A B C D E F G H I | java Subset 3
+echo A B C D E F G H I | java Subset 3
+echo A B C D E F G H I | java Subset 3
+echo AA BB BB BB BB BB CC CC | java Subset 8
+
+zip queues.zip Deque.java RandomizedQueue.java Subset.java