Thread: Ok, I'm trying to make my own Map classes.

I've already got my own Collection class, actually an interface, that has DoublyLinkedList and MyArrayList that implement it.

There is another class called MyHashSet that used a DoublyLinkedList object and an equals() method to make sure that there are no duplicates. Haven't gotten to the MyTreeSet, as that would involve either a MyHashSet object that implements Comparable or a DoublyLinkedList that uses equals() and implements Comparable.

I have a class called MyStack that used a DoublyLinkedList to make a stack and a classed called MyQueue that uses a DoublyLinkedList to make a queue.


I also have an interface called MyMap.

I don't know much about maps, but how do I basically set a bunch of values, possibly using a MyCollection object, and paring each one with some key?

public interface MyCollection<T>
{
 
public void add(int index, T data);
public void remove(int index);
public void addFirst(T data);
public void addLast(T data);
public void removeFirst();
public void removeLast();
 
public void removeRange(int from, int to);
public void removeAll();
public int Size();
public T get(int value);
 
 
}

 import javax.swing.Icon;
   import javax.swing.ImageIcon;
   import javax.swing.JOptionPane;
   import java.util.*;
   import java.io.*;
 
//Paul Adcock
// Assignment 4
// Lasted Worked On: 12/31/2010
 
/*
 this class is the Doubly Linked list class.  It has a Node that holds a reference to some date of type T and has a reference
 
 to the next Node and to the previous Node. It is a generic class than can hold date types.  
 */
 
 
   public class DoublyLinkedList<T> implements MyCollection<T>
   {
 
   /* This is the generic class Node, a private innner class of DoublyLnkedList.  
    */
      protected class Node<T>
      {
      /*
       * variables
       * T data - a variable of generic type
       * a Node next, which refers to the Node after the current Node
       * a Node previous, which refers to the Node before the current Node
       */
         private T data;
         private Node<T> next;
         private Node<T> previous;
 
      /*
       * Constructor Node(T data, Node<T> next, Node<T> previous)
       * parameters T data
       * a Node next
       * a Node previous
       */
         public Node(T data,Node<T> next, Node<T> previous)
         {
            this.data = data;
            this.next = next;
            this.previous=previous;
         }
 
      /*
       * returns the data of that Node
       */
         public T getData()
         {
            return data;
         }
 
      /*
       * returns the Node after the current Node
       */
         public Node<T> getNext()
         {
            return next;
         }
 
      /*
       * returns the Node before the current Node
       */
         public Node<T> getPrevious()
         {
            return previous;
         }
 
      /*
       * sets the Node after the current Node to next
       */
         public void setNext(Node<T> next)
         {
            this.next = next;
         }      
 
      /*
       * sets the Node before the current Node to previous
       */
         public void setPrevious(Node<T> previous)
         {
            this.previous = previous;
         }
 
      /*
       * creates a copy of the Node and returns that copy
       * @see java.lang.Object#clone()
       */
         public Node<T> clone()
         {
            Node<T> copy = new Node<T>(this.getData(), this.getNext(), this.getPrevious());
            return copy;
         }
      }
 
   /*
    * data for class DoublyLinkedList
    * Node head - beginning of DoublyLinkedList
    * Node tail - end of DoublyLinkedList
    * int side - size of DoublyLinkedList
    * 
    */
      private Node<T> head;//head of the linked list
      private Node<T> tail; // tail of linked list
      private int size;
      private DoublyLinkedList<T> subDLL;
      private DoublyLinkedList<T> anotherOne, anotherOne2;
      private ImageIcon icon;
      private DoublyLinkedList<T> copiedDLL;
      private Icon icon2;
   /*
    * constructor DoublyLinkedList()
    * no parameters
    */
      public DoublyLinkedList()
      {
      /*
       * sets head and tail to null
       * sets size to 0
       */
         head = null;
         tail = null;
         size = 0;
         icon = new ImageIcon("doh3.jpg");
      }
 
 
 
   /*
    * returns a String of all the elements in the DoublyLinkedList
    * @see java.lang.Object#toString()
    */
      public String toString()
      {
         String str = "[";
 
         Node<T> curr;
 
         for (curr=head;curr!=null;curr = curr.getNext())
         {
            str = str + curr.getData().toString();
            if (curr.getNext()!=null)
               str = str + " ";
         }
         str = str + "]";
         return str;
 
 
      }
 
      public T middle()
      {
 
         int middle = (int) (Size() -1 ) /2;
         return (get(middle));
 
      }
 
   /*
    * removeRange(int from, int to)
    * from - the starting index to remove
    * to - the last index to remove
    * removes all values between from and to
    */
      public void removeRange(int from, int to)
      {
         if (from < 0 || from >= Size() || to < 0 || to >=Size())
         {
            return;
         }
 
         if (from >=to)
         {
            for (int j = from; j >= to; j--)
            {
               remove(j);
            }
            return;
         }
 
         for (int i = from; i <=to; i++)
         {
            remove(i);
         }
      }
 
   // adds the data as the first element.  If the list size is 0, makes first element tail.  If head is not null, it puts the old
   // tail as the second element and the new element as the new head.  
   /*
    * addFirst(T data)
    * data - the type of data
    * adds the data to the beginning of the DoublyLinkedList
    */
      public void addFirst(T data)
      {  
      /*  Since this is the first Object,  previous should be null
       */
         Node<T> newNode = new Node<T>(data,head,null);
      //We know that if head is null, the list is empty
         if (head==null)
         {
         //If the list is empty,  tail will be newNode
            tail = newNode;
         }
 
         if(head!=null)
            head.setPrevious(newNode);
 
      //We want to set head to be newNode
      // if the list was empty before, both head and tail will be set to newNode;
         head = newNode;
      //Increment Size
         size++;
      }
 
   /*
    * removes the data the begining of the DoublyLinkedList
    */
      public void removeFirst()
      {
         if (size == 0)
         {
            JOptionPane pane = new JOptionPane();
            pane.setIcon(icon);
            pane.showMessageDialog(null, "Cannot remove from an empty list!", "Invalid removal", JOptionPane.ERROR_MESSAGE);
            pane.setMessageType(JOptionPane.ERROR_MESSAGE);
 
            return;
         }
         Node<T> current = head; // creates a Node called current and sets it to head.
 
         head = head.getNext(); //move head to the next element
 
         current.setNext(null);
         size--;
      }
 
   /*
    * addLast(T data)
    * parameters data
    * data- the data to be added
    * adds data to end of DoublyLinkedList
    */
      public void addLast(T data)
      {
      //If there are no elements, use the addFirst method
         if (tail == null)
         {
            addFirst(data);
            return;
         }
      /* Create the new Node from the data. Set next to null
       * because this will be the last element and will not
       * have a next. Set previous to tail because tail has
       * not been changed yet and is currently referencing
       * that element that will be directly before this element
       */
         Node<T> newNode = new Node<T>(data,null,tail);
      /* Since the tail variable still references the element
       * directly before the new element, we can set that node's
       * next to our new element.
       */
         tail.setNext(newNode);
      //Set tail to our new Node
         tail = newNode;
      //Increment size
         size++;
      }
 
 
      public void remove (T data)
      {
         for (int i =0; i < Size(); i++)
         {
            if (data.equals(get(i)))
            {
               remove(i);
            }
 
         }
 
      }
   /*
    * returns the size of the DoublyLinkedList
    */
      public int Size()
      {
         return(size);
      }
 
 
      public void add(MyCollection<T> collection)
      {
         for (int i =0; i < collection.Size(); i++)
         {
            addLast(collection.get(i));
 
         }
 
      }
 
 
   /*
    * add(int index, T data)
    * parameters index, data
    * index - the index to add the data
    * data- the data to add
    * adds the data at the specified index
    */
      public void add(int index,T data)
      {
         int i;
         if (index == 0)
         {
            addFirst(data);
            return;
 
         }
         if (index>size)
         {
            JOptionPane.showMessageDialog(null, "Cannot add out of bounds!", "Invalid command", JOptionPane.ERROR_MESSAGE);
            return;
         }
 
 
         if (index < 0)
         {
            JOptionPane.showMessageDialog(null, "Cannot add out of bounds!", "Invalid command", JOptionPane.ERROR_MESSAGE);
            return;
         }
 
         if (head==null)
         {
            addFirst(data);
            return;
         }
 
         if (index == size)
         {
            addLast(data);
            return;
         }
 
      //step 1
         Node<T> current;
 
         current = head;
 
         for (i=0;i<index-1;i++)
         {
            current = current.getNext();
         }
 
      //current now refers to object immediately before new node
 
      //step 2
         Node<T> newnode = new Node<T>(data,current.getNext(), current.getPrevious());
 
      //step 3
 
         current.setNext(newnode);
 
 
         size++;
      }  
 
   /*
    * remove(int index)
    * parameters index
    * index- the index of the data to remove
    * removes the data at the specified index
    */
      public void remove(int index)
      {
         if ((index<0) || (index>=size))
         {
            JOptionPane.showMessageDialog(null, "You cannot remove an out-of-bounds value!", "Invalid removal", JOptionPane.ERROR_MESSAGE);
            return;
         }
 
 
 
         Node <T> next2, previous3;
         Node<T> NodeToRemove = head; // sets Node to remove originally to head
 
 
         for (int v = 0; v < index; v++)
         {
            NodeToRemove = NodeToRemove.getNext(); // traverse to Node we want to remove
         }
 
         previous3 = NodeToRemove.getPrevious(); // sets previous3 to value before Node to remove
         next2 = NodeToRemove.getNext(); // sets next2 to value after Node to remove
 
         if (previous3 == null)
         {
            if (next2 == null)
            {
               head = null;
               tail = null;
            }
 
            else
            {
               head = next2;
            }
         }
 
         else
         {
            previous3.setNext(next2);
         }
 
         if (next2 == null)
         {
            if (previous3 == null)
            {
               head = null;
               tail = null;
            }
 
            else
            {
               tail = previous3;
            }
         }
         else
         {
            next2.setPrevious(previous3);
         }
 
 
         size--;
      }
 
   /*
    * get(int i)
    * parametsrs i
    * i - the index
    * returns the data at index i
    */
      public T get(int i)
      {
         if (i < 0 || i >= size)
            return null;
 
         if (i ==0)
         {
            Node<T> thisNode = head;
            return(head.getData());
         }
 
         if (i == size - 1)
         {
            Node<T> thisNode = tail;
            return(tail.getData());
         }
         Node<T> specialNode = head;
         for (int x = 1; x < i + 1; x++)
         {
            specialNode = specialNode.getNext();
         }
         return(specialNode.getData());
 
      // How do I get it to return the data at i?
 
 
      }
 
      public Node<T> getNodeAt(int index)
      {
         Node<T> temp5 = head;
         for (int i =0; i < index; i++)
         {
            temp5 = temp5.getNext();
         }
         return temp5;
      }
   /*
    * getSubList(int from, int to)
    * parameters from, to
    * from - the starting index
    * to - the ending index
    * gets the data from index from to index to and copies it into another DoublyLinkedList
    * and returns that DoublyLinkedList
    */
      public DoublyLinkedList<T> getSubList(int from, int to)
      {
         DoublyLinkedList<T> sub = new DoublyLinkedList<T>();
         int count = 0;
         for (int value = from; value <=to; value++)
         {
            sub.add(count, this.get(value));
            count++;
         }
         return sub;
      }
 
   /*
    * swap(int first, int second)
    * parameters first, second
    * first - the index of the first value to be swapped
    * second - the index of the second value to be swapped
    * swaps the data at index first and index second
    * Not yet written
    */
      public void swap(int first, int second)
      {
         if (first < 0 || first >=Size() || second < 0 || second >=Size())
            return;
 
      // no use bothering to swap an index with itself
         if (first == second)
            return;
         Node<T> prevTemp;
         Node<T> prevTemp2;
         Node<T> nextTemp;
         Node<T> nextTemp2;
 
 
         prevTemp = getNodeAt(first).getPrevious();
         prevTemp2 = getNodeAt(second).getPrevious();
         nextTemp = getNodeAt(first).getNext();
         nextTemp2 = getNodeAt(second).getNext();
         getNodeAt(first).setPrevious(prevTemp2);
         getNodeAt(first).setNext(nextTemp2);
         getNodeAt(second).setPrevious(prevTemp);
         getNodeAt(second).setNext(nextTemp);
 
      }
 
   /*
    * getIndex(T data)
    * parameters data
    * data - the data to look for
    * if it finds the data, it returns the index where it finds it
    * otherwise it returns -1 if it cannot find it
    */
      public int getIndex(T data)
      {
         for (int x =0; x < Size(); x++)
         {
            if (this.get(x).equals(data))
               return x;
         }
         return -1;
      }
   // calls get method of first index
 
   /*
    * returns the data at the beginning of the DoublyLinkedList
    */
      public T front()
      {
         if (head == null)
            return null;
 
         return(get(0));
      }
 
   // calls get Method of last index
   /*
    * returns the data at the end of the DoublyLinkedList
    */
      public T back()
      {
         if (tail == null)
            return null;
 
         return(get(size - 1));
      }
 
   /*
    * removes the data at the end of the DoublyLinkedList
    */
      public void removeLast()
      {
 
         if (head == null)
         {
            JOptionPane.showMessageDialog(null, "Cannot remove from an empty list!", "Invalid removal", JOptionPane.ERROR_MESSAGE);
            return;
         }
         remove(Size() -1 );
      }
 
   // gets a String for the first bracket.  Then stores each set of first and last, 2nd and 2nd to last, etc, in a String array;
   // it then sets the third string to the concatination of all of the Strings in the array.  It thens puts these together and adds
   // the last set of brackets and returns the final string.  
      public String printAlternate()
      {
      /*
      This method returns a string that has
      the data in the following fashion (assume for this example that the list stores String objects)
      If the list is currently [amit is now here], it will return a string �[amit here is now]�
      If the list is currently [amit is now currently here], it will return a string �[amit here is currently now]�
       */
         String str = "[";
         String [] str2 = new String[size];
         for (int v = 0; v < size; v++)
         {
            str2[v] = this.get(v) + " " + this.get(size - (v+1) );
         }
         String str3 = "";
         for (int x = 0; x < size - 2; x++)
         {
            str3 = str2[x].concat(str2[x+1]);
         }
         String str4 = str + " " + str3 + " " + "]";
         return(str4);
      }
 
   // removes all data
   /*
    * removes all data in the DoublyLinkedList
    */
      public void removeAll()
      {
         int x = 0;
         int y = this.Size() - 1;
 
         removeRange(x,y);
      }
   /*
    * copies the data from this DoublyLinkedList into another one and returns that
    * DoublyLinkedList
    * @see java.lang.Object#clone()
    */
      public DoublyLinkedList<T> clone()
      {
         DoublyLinkedList<T> copy = new DoublyLinkedList<T>();
         for (int x = 0; x < this.Size(); x++)
         {
            copy.add(x, this.get(x));
         }
         return copy;
      }
 
      public void addMyCollection(MyCollection<T> aCollection)
      {
         for (int i =0; i < aCollection.Size(); i++)
         {
            addLast(aCollection.get(i));
         }
 
      }
 
      public DoublyLinkedList<T> getSubList2(MyCollection<T> collection, int from, int to)
      {
 
         DoublyLinkedList<T> sub = new DoublyLinkedList<T>();
         int count = 0;
         for (int value = from; value <=to; value++)
         {
            sub.add(count, collection.get(value));
            count++;
         }
         return sub;
      }
 
 
 
 
 
 
      public DoublyLinkedList<T> getSubList4(Vector<T> aVector, int from, int to)
      {
         DoublyLinkedList<T> sub = new DoublyLinkedList<T>();
         int count = 0;
 
         for (int i = from; i <= to; i++)
         {
            sub.add(count, aVector.get(i));
            count++;
         }
         return sub;
      }
      public DoublyLinkedList ( DoublyLinkedList<T>original)
      {
         copiedDLL = original.clone();
         this.copiedDLL = copiedDLL;
 
      }
 
 
 
 
      public DoublyLinkedList ( MyCollection<T> collection, int from, int to)
      {
         anotherOne = getSubList2(collection, from, to);
         this.anotherOne = anotherOne;
      }
 
 
 
      public Object[] toArray()
      {
         Object[] obj = new Object[this.Size()];
         for (int i =0 ; i < this.Size(); i++)
         {
            obj[i]  = this.get(i);
         }
         return obj;
      }
 
 
   }

import java.util.*;
public class MyArrayList<T> implements MyCollection<T>
{
 
private Object[] array;
private int size = 0;
 
public MyArrayList (int initialSize)
{
array = new Object[initialSize];
this.size = initialSize;
}
 
public void add(int index, T data)
{
if (index >  Size() || index < 0)
return;
Object[] newArray;
if (index == Size())
{
newArray = new Object[Size() * 2];
newArray[Size() ] = data;
this.array= newArray;
this.size = Size() + 1;
}
 
else
{
array[index] = data;
 
}
}
 
public void addLast(T data)
{
if (Size() == 0)
addFirst(data);
 
 
add(Size() , data);
}
 
public void addFirst(T data)
{
add(0, data);
}
public int Size()
{
return size;
}
 
public void remove (int index)
{
if (index < 0 || index >=Size())
return;
// remove index 4 with size 9
// index 8 becomes index 7.  Index 7 becomes index 6.  Index 6 becomes index 5.  Index 5 becomes index 4.  Index 4 value is gone.
// remove index 0 of size 3
// index 2 becomes 1.  Index 1 becomes 0.  Index 0 value is gone.
// remove index 5 of size 6.
// size becomes 5
if (index == Size() -1)
{
Object[] newArray = new Object[Size() -1];
for (int i =0; i < Size() -1; i++)
{
newArray[i] = array[i];
}
this.array = newArray;
this.size = Size() -1;
 
}
 
else if (index ==0)
{
Object[] newArray = new Object[Size() -1];
for (int i = 0; i < Size() -1 ; i++)
{
newArray[i] = array[i+1];
}
this.array = newArray;
this.size = Size() -1;
}
 
else
{
Object[] newArray = new Object[Size() -1];
 
for (int i = Size() -1; i > index; i --)
{
newArray[i-1] = array[i];
}
 
for (int x = index; x > 0; x--)
{
newArray[x] = array[x-1];
}
this.array = newArray;
this.size = Size() -1;
}
}
public void removeFirst()
{
remove(0);
}
 
public void removeLast()
{
remove(Size() -1);
}
 
public void removeRange(int from, int to)
{
if (from < 0 || from >=Size() || to < 0 || to >=Size())
return;
 
if (from >=to)
{
for (int j =from; j >= to; j--)
{
remove(j);
 
}
return;
}
for (int i = from; i <= to; i++)
{
remove(i);
}
}
 
public T get(int index)
{
if (index < 0 || index >= Size())
return null;
 
return (T) array[index];
 
}
 
public void removeAll()
{
for (int i = 0; i < Size(); i++)
{
remove(i);
}
}
 
}

public class MyHashSet<T>
{
 
private DoublyLinkedList<T> dll;
 
 
 
public MyHashSet()
{
dll = new DoublyLinkedList<T>();
}
 
public void add(T data)
{
for (int i =0; i < dll.Size(); i++)
{
if (dll.get(i).equals(data))
return;
}
dll.addLast(data);
}
 
public String toString()
{
return dll.toString();
}
 
public void remove(int index)
{
dll.remove(index);
 
}
 
public int Size()
{
return dll.Size();
}
 
public T get(int index)
{
return dll.get(index);
}
 
public static void main(String[] args)
{
MyHashSet<Integer> mhs = new MyHashSet<Integer>();
mhs.add(125);
mhs.add(125);
System.out.println("Size:" + mhs.Size());
System.out.println(mhs.toString());
}
 
 
}

 
   public interface MyMap<K,V>
   {
 
 
      public static interface Entry<K,V>
      {
 
         public boolean equals(Object obj);
 
         public K getKey();
 
         public V getValue();
 
         public void setKey(K key);
 
         public void setValue(V value);
 
      }
 
      public void clear();
 
      public boolean containsKey(Object key);
 
      public boolean containsValue(Object value);
 
      public boolean equals(Object obj);
 
      public V get(Object key);
 
      public void put(K Key, V value);
 
      public void putAll(MyMap<? extends K, ? extends V> m);
 
		public void remove (Object key);
 
		public MyCollection<V> getValues();
 
		public int Size();
 
 
 
   }

So how do I make, with these classes to build upon, a HashMap and a TreeMap?

How do you set up a mapping?

Ok, this seems like this involves complicated algorithms and lots of tree things I've never heard much of before.


I could possibly make two parallel DoublyLinkedLists instead of a Map.

I'm not going to attempt "Double Generics" i.e. Class<H,J> for a long time till I'm far more skilled if they're that hard.

The most I must use is an ActionMap or something, and I'm definitely not writing my own.