×
Samples Blogs Make Payment About Us Reviews 4.9/5 Order Now

Create A Standard Map Interface in Java Assignment Solution

June 29, 2024
Dr. Anil Kumar
Dr. Anil
🇸🇬 Singapore
Java
Dr. Anil Kumar, with a Ph.D. in Information Technology from the National University of Singapore, has completed over 600 assignments in the Array class interface domain. His expertise lies in dynamic arrays, memory management, and error handling. Anil's ability to simplify intricate concepts and provide clear, detailed explanations ensures that students gain a solid grasp of their assignments and improve their programming skills.
Key Topics
  • Instructions
  • Requirements and Specifications
Tip of the day
Use modular coding in Verilog assignments by breaking the design into smaller modules. This improves readability, simplifies debugging, and allows for easier testing and reuse of code components in larger designs.
News
In 2024, Visual Studio Code now offers enhanced GitHub Copilot integration for faster, while PyCharm has improved debugging and testing tools, making it ideal for Python students​

Instructions

Objective
Write a java assignment program to create a standard map interface.

Requirements and Specifications

Program to create a standard map interface in Java
Program to create a standard map interface in Java 1

Source Code

package edu.uwm.cs351.ps;

import java.util.*;

import edu.uwm.cs351.SortedSequence;

import edu.uwm.cs351.util.AbstractEntry;

import junit.framework.TestCase;

public class Dictionary extends AbstractMap{

    private static class Node extends AbstractEntry{

        Name key;

        Object data;

        Node left, right;

        Node(Name k, Object d) {

            key = k;

            data = d;

        }

        @Override

        public Name getKey() {

            return key;

        }

        @Override

        public Object getValue() {

            return data;

        }

        @Override

        public Object setValue(Object o) {

            Object result = data;

            data = o;

            return result;

        }

    }

    private Node root;

    private int size;

    private EntrySet entrySet;

    private String version;

    private static boolean doReport = true;

    private static boolean report(String s) {

        if (doReport) System.err.println("Invariant error: " + s);

        return false;

    }

    // This method is useful for checkTree if errors are found.

    private static int reportNeg(String s) {

        report(s);

        return -1;

    }

    /**

     * Check if a subtree is well formed.

     * None of the keys may be null and all of the keys must be

     * in the given range (lo,hi) exclusive, except that a null bound means

     * there is no bound in that direction, and finally all subtrees

     * must also be well formed.

     *

     * @param r root of the subtree, may be null

     * @param lo exclusive lower bound. If null, then no lower bound.

     * @param hi exclusive upper bound. If null, then no upper bound.

     * @return number of nodes in subtree, if well formed, -1 otherwise.

     */

    private static int checkTree(Node r, String lo, String hi) {

        if (r == null) return 0;

        if (r.key == null || r.key.rep == null) return reportNeg("null key found");

        if (lo != null && lo.compareTo(r.key.rep) >= 0 ||

                hi != null && hi.compareTo(r.key.rep) <= 0) {

            return reportNeg("key out of place: " + r.key + " in (" + lo + "," + hi + ")");

        }

        int n1 = checkTree(r.left, lo, r.key.rep);

        int n2 = checkTree(r.right, r.key.rep, hi);

        if (n1 < 0 || n2 < 0) return -1;

        return n1 + n2 + 1;

    }

    private boolean wellFormed() {

        int n = checkTree(root, null, null);

        if (n < 0) return false;

        if (n != size) return report("Size wrong: " + size + " should be " + n);

        return true;

    }

    /**

     * Create an empty dictionary.

     */

    public Dictionary() {

        root = null;

        size = 0;

        entrySet = new EntrySet();

        version = toString();

        assert wellFormed() : "invariant broken in constructor";

    }

    private Node getNode(Node r, Name n) {

        if (r == null) return r;

        if (n == null) return null;

        int c = r.key.rep.compareTo(n.rep);

        if (c == 0) return r;

        if (c > 0) return getNode(r.left, n);

        else return getNode(r.right, n);

    }

    /**

     * Return the definition of a name in this dictionary

     *

     * @param n name to lookup, may not be null

     * @return definition for the name

     * @throws ExecutionException if there is no definition, or if the name is null

     */

    public Object get(Name n) throws ExecutionException {

        assert wellFormed() : "invariant broken at start of get()";

        Node r = getNode(root, n);

        if (r != null) return r.data;

        throw new ExecutionException("undefined");

    }

    @Override

    public Object get(Object o) throws ExecutionException {

        assert wellFormed() : "invariant broken at start of get()";

        if (o instanceof Name) {

            Node r = getNode(root, (Name) o);

            if (r == null) {

                return null;

            }

            return r.data;

        }

        return null;

    }

    /**

     * Return whether the parameter is a name in the dictionary

     *

     * @param n name to look up, may be null

     * @return whether n is a name in the dictionary

     */

    public boolean known(Name n) {

        assert wellFormed() : "invariant broken at start of known()";

        Node r = getNode(root, n);

        if (r != null) return true;

        return false;

    }

    /**

     * Return the number of names defined in the dictionary.

     *

     * @return number of names in dictionary.

     */

    public int size() {

        assert wellFormed() : "invariant broken at start of size()";

        return size;

    }

    private Node doPut(Node r, Name n, Object d) {

        if (r == null) {

            r = new Node(n, d);

            ++size;

        } else {

            int c = r.key.rep.compareTo(n.rep);

            if (c == 0) r.data = d;

            else if (c > 0) r.left = doPut(r.left, n, d);

            else r.right = doPut(r.right, n, d);

        }

        return r;

    }

    /**

     * Define a name in the dictionary.

     * If the name already has a definition, the old definition is replaced

     * with the new definition.

     *

     * @param n name to defined (must not be null)

     * @param x (new) definition of the name (may be null)

     * @throws ExecutionException if the name is null

     */

    public Object put(Name n, Object x) {

        assert wellFormed() : "invariant broken at start of put()";

        if (n == null || n.rep == null) throw new ExecutionException("null key not allowed");

        Object oldValue = get((Object) n);

        root = doPut(root, n, x);

        assert wellFormed() : "invariant broken at end of put()";

        version = toString();

        return oldValue;

    }

    private void doCopy(Node r) {

        if (r == null) return;

        put(r.key, r.data);

        doCopy(r.left);

        doCopy(r.right);

    }

    /**

     * Copy all the definitions from the argument into this dictionary

     * replacing previous definitions (if any).

     *

     * @param dict1 dictionary whose definition we copy (must not be null)

     * NB: Behavior if the argument is null is not defined.

     */

    public void copy(Dictionary dict1) {

        assert wellFormed() : "invariant broken at start of copy()";

        doCopy(dict1.root);

        assert wellFormed() : "invariant broken at start of copy()";

    }

    @Override

    public Set> entrySet() {

        return entrySet;

    }

    private Node getParent(Node curr, Node target) {

        if (curr == null) {

            return null;

        }

        Name currValue = curr.getKey();

        Name targetValue = target.getKey();

        int diff = currValue.rep.compareTo(targetValue.rep);

        if (diff > 0) {

            if (curr.left == target) {

                return curr;

            }

            return getParent(curr.left, target);

        } else {

            if (curr.right == target) {

                return curr;

            }

            return getParent(curr.right, target);

        }

    }

    @Override

    public Object remove(Object key) {

        if (!(key instanceof Name)) {

            return null;

        }

        Node current = getNode(root, (Name) key);

        if (current == null) {

            return null;

        }

        Object result = current.getValue();

        Node parent = getParent(root, current);

        if (current.right == null && current.left == null) {

            if (parent == null) {

                root = null;

            } else if (parent.left == current) {

                parent.left = null;

            } else {

                parent.right = null;

            }

            size--;

        } else if (current.right == null) {

            if (parent == null) {

                root = current.left;

            } else if (parent.left == current) {

                parent.left = current.left;

            } else {

                parent.right = current.left;

            }

            size--;

        } else if (current.left == null) {

            if (parent == null) {

                root = current.right;

            } else if (parent.left == current) {

                parent.left = current.right;

            } else {

                parent.right = current.right;

            }

            size--;

        } else {

            Node curr = current.right;

            if (curr.left == null) {

                curr.left = current.left;

                if (parent == null) {

                    root = curr;

                } else if (parent.left == current) {

                    parent.left = curr;

                } else {

                    parent.right = curr;

                }

                size--;

            } else {

                Node par = null;

                while (curr.left != null) {

                    par = curr;

                    curr = curr.left;

                }

                Node newNode = par.left;

                par.left = newNode.right;

                newNode.left = current.left;

                newNode.right = current.right;

                if (parent == null) {

                    root = newNode;

                } else if (parent.left == current) {

                    parent.left = newNode;

                } else {

                    parent.right = newNode;

                }

                size--;

            }

        }

        version = toString();

        return result;

    }

    @Override

    public void clear() {

        root = null;

        size = 0;

        entrySet = new EntrySet();

        version = toString();

    }

 @Override

 public boolean containsKey(Object o) {

  if (!(o instanceof Name)) {

   return false;

  }

  return known((Name) o);

 }

    private void doToString(Node r, StringBuilder into) {

        if (r == null) return;

        doToString(r.left, into);

        into.append(' ');

        into.append(r.key);

        into.append(' ');

        into.append(r.data);

        doToString(r.right, into);

    }

    /**

     * Return a string of the form << name1 value1 name2 value2 ... namek valuek >>

     * where the names are in order and everything is separated by single spaces.

     *

     * @see java.lang.Object#toString()

     */

    @Override

    public String toString() {

        StringBuilder sb = new StringBuilder();

        sb.append("<<");

        doToString(root, sb);

        sb.append(" >>");

        return sb.toString();

    }

    private class EntrySet extends AbstractSet> {

        @Override

        public Iterator> iterator() {

            return new MyIterator();

        }

        @Override

        public int size() {

            return size;

        }

        @Override

        public void clear() {

            Dictionary.this.clear();

        }

    }

    private class MyIterator implements Iterator> {

        private Stack cursorStack;

        private Stack prevStack;

        private String version;

        MyIterator() {

            version = Dictionary.this.version;

            cursorStack = new Stack<>();

            prevStack = null;

            Node curr = root;

            while (curr != null) {

                cursorStack.add(curr);

                curr = curr.left;

            }

        }

        /**

         * Returns {@code true} if the iteration has more elements.

         * (In other words, returns {@code true} if {@link #next} would

         * return an element rather than throwing an exception.)

         *

         * @return {@code true} if the iteration has more elements

         */

        @Override

        public boolean hasNext() {

            if (!version.equals(Dictionary.this.version)) {

                throw new ConcurrentModificationException();

            }

            return !cursorStack.empty();

        }

        /**

         * Returns the next element in the iteration.

         *

         * @return the next element in the iteration

         * @throws NoSuchElementException if the iteration has no more elements

         */

        @Override

        public AbstractEntrynext() {

            if (!version.equals(Dictionary.this.version)) {

                throw new ConcurrentModificationException();

            }

            if (cursorStack.empty()) {

                throw new NoSuchElementException();

            }

            prevStack = new Stack<>();

            for (Node node : cursorStack) {

                prevStack.push(node);

            }

            Node result = cursorStack.peek();

            Node curr = cursorStack.pop().right;

            while (curr != null) {

                cursorStack.push(curr);

                curr = curr.left;

            }

            return result;

        }

        @Override

        public void remove() {

   if (!version.equals(Dictionary.this.version)) {

    throw new ConcurrentModificationException();

   }

   if (prevStack == null) {

                throw new IllegalStateException();

            }

            Node current = prevStack.peek();

            Node parent = getParent(root, current);

            if (current.right == null && current.left == null) {

                if (parent == null) {

                    root = null;

                } else if (parent.left == current) {

                    parent.left = null;

                } else {

                    parent.right = null;

                }

                prevStack.pop();

                size--;

            } else if (current.right == null) {

                if (parent == null) {

                    root = current.left;

                } else if (parent.left == current) {

                    parent.left = current.left;

                } else {

                    parent.right = current.left;

                }

                prevStack.pop();

                size--;

            } else if (current.left == null) {

                if (parent == null) {

                    root = current.right;

                } else if (parent.left == current) {

                    parent.left = current.right;

                } else {

                    parent.right = current.right;

                }

                prevStack.pop();

                Node curr = current.right;

                while (curr != null) {

                    prevStack.push(curr);

                    curr = curr.left;

                }

                size--;

            } else {

                Node curr = current.right;

                if (curr.left == null) {

                    prevStack.pop();

                    prevStack.push(curr);

                    curr.left = current.left;

                    if (parent == null) {

                        root = curr;

                    } else if (parent.left == current) {

                        parent.left = curr;

                    } else {

                        parent.right = curr;

                    }

                    size--;

                } else {

                    Node par = null;

                    while (curr.left != null) {

                        par = curr;

                        curr = curr.left;

                    }

                    Node newNode = par.left;

                    par.left = newNode.right;

                    newNode.left = current.left;

                    newNode.right = current.right;

                    prevStack.pop();

                    prevStack.push(newNode);

                    if (parent == null) {

                        root = newNode;

                    } else if (parent.left == current) {

                        parent.left = newNode;

                    } else {

                        parent.right = newNode;

                    }

                    size--;

                }

            }

   cursorStack = new Stack<>();

   for (Node node : prevStack) {

    cursorStack.push(node);

   }

   prevStack = null;

   Dictionary.this.version = Dictionary.this.toString();

   version = Dictionary.this.version;

        }

    }

    public static class TestInvariant extends TestCase {

        protected Dictionary self;

        private Node[] n;

        private Name n0 = new Name("N");

        protected Name n(int i) {

            return new Name("N" + (1000 + i));

        }

        @Override

        protected void setUp() {

            self = new Dictionary();

            self.root = null;

            self.size = 0;

            n = new Node[15];

            for (int i = 0; i < 15; ++i) {

                n[i] = new Node(n(i * 10), i);

            }

            n[0].key = null;

            n[6].left = n[2];

            n[6].right = n[10];

            n[2].left = n[1];

            n[2].right = n[5];

            n[5].left = n[3];

            n[3].right = n[4];

            n[10].left = n[9];

            n[10].right = n[12];

            n[9].left = n[7];

            n[7].right = n[8];

            n[12].left = n[11];

            n[12].right = n[13];

            doReport = false;

        }

        public void testA() {

            assertEquals(0, checkTree(null, null, null));

            assertEquals(-1, checkTree(n[0], null, null));

            assertEquals(1, checkTree(n[1], null, null));

            assertEquals(0, checkTree(null, "bar", "foo"));

        }

        public void testB() {

            assertEquals(1, checkTree(n[1], n(9).rep, n(11).rep));

            assertEquals(1, checkTree(n[1], n(0).rep, null));

            assertEquals(1, checkTree(n[1], null, n(20).rep));

            assertEquals(-1, checkTree(n[1], n(9).rep, n(10).rep));

            assertEquals(-1, checkTree(n[1], n(10).rep, n(11).rep));

            assertEquals(-1, checkTree(n[1], n(10).rep, null));

            assertEquals(-1, checkTree(n[1], null, n(10).rep));

        }

        public void testC() {

            assertEquals(13, checkTree(n[6], null, null));

            assertEquals(13, checkTree(n[6], n(0).rep, n(140).rep));

            assertEquals(-1, checkTree(n[6], n(15).rep, null));

            assertEquals(-1, checkTree(n[6], null, n(125).rep));

        }

        public void testD() {

            self.root = null;

            self.size = 0;

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testE() {

            self.root = n[1];

            self.size = 0;

            assertFalse(self.wellFormed());

            self.size = 2;

            assertFalse(self.wellFormed());

            self.size = -1;

            assertFalse(self.wellFormed());

            self.size = 1;

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testF() {

            self.root = n[0];

            self.size = 1;

            assertFalse(self.wellFormed());

            n[0].key = n0;

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testG() {

            self.root = n[14];

            self.size = 2;

            n[14].right = n[1];

            assertFalse(self.wellFormed());

            n[14].right = null;

            n[14].left = n[1];

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testH() {

            self.root = n[1];

            self.size = 2;

            n[1].left = n[14];

            assertFalse(self.wellFormed());

            n[1].left = null;

            n[1].right = n[14];

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testI() {

            self.root = n[3]; // n[3]'s right is n[4]

            self.size = 3;

            n[4].left = n[0];

            assertFalse(self.wellFormed());

            self.size = 0;

            assertFalse(self.wellFormed());

            n[0].key = n0;

            assertFalse(self.wellFormed());

            self.size = 3;

            assertFalse(self.wellFormed());

            n[4].left = null;

            n[4].right = n[14];

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testJ() {

            self.root = n[5]; //n[5].left = n[3]; n[3].right = n[4]

            self.size = 4;

            n[4].right = n[14];

            assertFalse(self.wellFormed());

            self.size = 1;

            assertFalse(self.wellFormed());

            n[0].key = n0;

            assertFalse(self.wellFormed());

            self.size = 4;

            assertFalse(self.wellFormed());

            n[4].right = null;

            assertFalse(self.wellFormed());

            self.size = 3;

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testK() {

            self.root = n[5]; //n[5].left = n[3]; n[3].right = n[4]

            self.size = 4;

            n[4].left = n[0];

            assertFalse(self.wellFormed());

            self.size = 1;

            assertFalse(self.wellFormed());

            n[0].key = n0;

            assertFalse(self.wellFormed());

            self.size = 4;

            assertFalse(self.wellFormed());

            n[0].key = n(35);

            doReport = true;

            assertTrue(self.wellFormed());

        }

        // The following tests concern the tree

        // (((10)20(((30(40))50)60((70(80))90)))100((110)120(130)))

        public void testL() {

            self.root = n[6]; // whole tree

            self.size = 13;

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testM() {

            self.root = n[6];

            self.size = 14;

            n[1].left = n[0];

            assertFalse(self.wellFormed());

            n[0].key = n(10);

            assertFalse(self.wellFormed());

            n[1].left = n[1];

            assertFalse(self.wellFormed());

            n[1].left = n[0];

            n[0].key = n(05);

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testN() {

            self.root = n[6];

            self.size = 14;

            n[1].right = n[14];

            assertFalse(self.wellFormed());

            n[1].right = n[0];

            assertFalse(self.wellFormed());

            n[0].key = n(20);

            assertFalse(self.wellFormed());

            n[1].right = n[2];

            assertFalse(self.wellFormed());

            n[1].right = n[0];

            n[0].key = n(15);

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testO() {

            self.root = n[6];

            self.size = 14;

            n[3].left = n[1];

            assertFalse(self.wellFormed());

            n[3].left = n[0];

            assertFalse(self.wellFormed());

            n[0].key = n(20);

            assertFalse(self.wellFormed());

            n[3].left = n[2];

            assertFalse(self.wellFormed());

            n[3].left = n[0];

            n[0].key = n(25);

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testP() {

            self.root = n[6];

            self.size = 14;

            n[4].left = n[1];

            assertFalse(self.wellFormed());

            n[4].left = n[0];

            assertFalse(self.wellFormed());

            n[0].key = n(30);

            assertFalse(self.wellFormed());

            n[4].left = n[3];

            assertFalse(self.wellFormed());

            n[4].left = n[0];

            n[0].key = n(35);

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testQ() {

            self.root = n[6];

            self.size = 14;

            n[4].right = n[14];

            assertFalse(self.wellFormed());

            n[4].right = n[0];

            assertFalse(self.wellFormed());

            n[0].key = n(50);

            assertFalse(self.wellFormed());

            n[4].right = n[5];

            assertFalse(self.wellFormed());

            n[4].right = n[0];

            n[0].key = n(45);

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testR() {

            self.root = n[6];

            self.size = 14;

            n[5].right = n[14];

            assertFalse(self.wellFormed());

            n[5].right = n[0];

            assertFalse(self.wellFormed());

            n[0].key = n(60);

            assertFalse(self.wellFormed());

            n[5].right = n[6];

            assertFalse(self.wellFormed());

            n[5].right = n[0];

            n[0].key = n(55);

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testS() {

            self.root = n[6];

            self.size = 14;

            n[7].left = n[1];

            assertFalse(self.wellFormed());

            n[7].left = n[0];

            assertFalse(self.wellFormed());

            n[0].key = n(60);

            assertFalse(self.wellFormed());

            n[7].left = n[6];

            assertFalse(self.wellFormed());

            n[7].left = n[0];

            n[0].key = n(65);

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testT() {

            self.root = n[6];

            self.size = 14;

            n[8].left = n[1];

            assertFalse(self.wellFormed());

            n[8].left = n[0];

            assertFalse(self.wellFormed());

            n[0].key = n(70);

            assertFalse(self.wellFormed());

            n[8].left = n[7];

            assertFalse(self.wellFormed());

            n[8].left = n[0];

            n[0].key = n(75);

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testU() {

            self.root = n[6];

            self.size = 14;

            n[8].right = n[14];

            assertFalse(self.wellFormed());

            n[8].right = n[0];

            assertFalse(self.wellFormed());

            n[0].key = n(90);

            assertFalse(self.wellFormed());

            n[8].right = n[9];

            assertFalse(self.wellFormed());

            n[8].right = n[0];

            n[0].key = n(85);

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testV() {

            self.root = n[6];

            self.size = 14;

            n[9].right = n[14];

            assertFalse(self.wellFormed());

            n[9].right = n[0];

            assertFalse(self.wellFormed());

            n[0].key = n(100);

            assertFalse(self.wellFormed());

            n[9].right = n[10];

            assertFalse(self.wellFormed());

            n[9].right = n[0];

            n[0].key = n(95);

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testW() {

            self.root = n[6];

            self.size = 14;

            n[11].left = n[1];

            assertFalse(self.wellFormed());

            n[11].left = n[0];

            assertFalse(self.wellFormed());

            n[0].key = n(100);

            assertFalse(self.wellFormed());

            n[11].left = n[10];

            assertFalse(self.wellFormed());

            n[11].left = n[0];

            n[0].key = n(105);

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testX() {

            self.root = n[6];

            self.size = 14;

            n[11].right = n[14];

            assertFalse(self.wellFormed());

            n[11].right = n[0];

            assertFalse(self.wellFormed());

            n[0].key = n(120);

            assertFalse(self.wellFormed());

            n[11].right = n[12];

            assertFalse(self.wellFormed());

            n[11].right = n[0];

            n[0].key = n(115);

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testY() {

            self.root = n[6];

            self.size = 14;

            n[13].left = n[1];

            assertFalse(self.wellFormed());

            n[13].left = n[0];

            assertFalse(self.wellFormed());

            n[0].key = n(120);

            assertFalse(self.wellFormed());

            n[13].left = n[12];

            assertFalse(self.wellFormed());

            n[13].left = n[0];

            n[0].key = n(125);

            doReport = true;

            assertTrue(self.wellFormed());

        }

        public void testZ() {

            self.root = n[6];

            self.size = 14;

            n[13].right = n[0];

            assertFalse(self.wellFormed());

            n[0].key = n(130);

            assertFalse(self.wellFormed());

            n[13].right = n[13];

            assertFalse(self.wellFormed());

            n[13].right = n[14];

            doReport = true;

            assertTrue(self.wellFormed());

        }

    }

}

Related Samples

Discover our Java Assignment Samples showcasing expert solutions to diverse programming challenges. These examples span basic algorithms to advanced data structures, embodying clarity, efficiency, and adherence to coding standards. Strengthen your Java programming skills with our comprehensive collection and excel in your assignments effortlessly.