Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

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

  1. #1
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default 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?


  2. #2
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,424
    My Mood
    Hungover
    Thanks
    144
    Thanked 636 Times in 540 Posts

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

    ...why are you doing this? Why don't you just use the wheel that's already been invented, instead of chiseling out a square one?
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,320
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

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

    Indeed, why reinvent the wheel. If this is just an exercise, then I suggest reading the following:
    Hash table - Wikipedia, the free encyclopedia

  4. The Following User Says Thank You to copeg For This Useful Post:

    javapenguin (August 4th, 2011)

  5. #4
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

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

    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.

Similar Threads

  1. classes and methods??
    By paddy1 in forum Member Introductions
    Replies: 1
    Last Post: May 20th, 2011, 09:02 AM
  2. Need Help with using classes [HELP]
    By dragon40226 in forum Java Theory & Questions
    Replies: 4
    Last Post: May 19th, 2011, 01:59 PM
  3. help with using multiple classes
    By finalfantasyfreak15 in forum What's Wrong With My Code?
    Replies: 0
    Last Post: March 5th, 2011, 12:18 AM
  4. Classes problem
    By Skyton in forum What's Wrong With My Code?
    Replies: 1
    Last Post: March 3rd, 2011, 03:26 PM
  5. [SOLVED] Java program using two classes
    By AZBOY2000 in forum Object Oriented Programming
    Replies: 7
    Last Post: April 21st, 2009, 06:55 AM