Thread: Sets/Maps help needed

You guys were more than helpful during my last assignment so I figured I would give you guys another try. After all, I have learned more from everyone here than my professor whom I am paying over a thousand dollars this semester to teach me this stuff. /rant

I mainly need help with setting up the map and set. We didn't really cover these data types much before he gave us the assignment, sent us on Spring Break, and told us it would be due the first day back. I have done numerous Google searches to find some basic information on setting these us, but have not had any success. We will be using an AVL tree in coordination with a text file.

Our instructions are to "read a text file and extract all of the identifiers in the file, along with the line numbers on which the identifier appear. An identifier is defined as a string that begins with a letter (A-Z, a-z) and is followed by zero or more other characters that are a letter or a digit (0-9). Note that, if an identifier appears multiple times in a line, only one line number is recorded."

The input is a text file, for example a source code or a text document. The concordance outputs the information for each identifier in the following format:

identifier_1 n_1: L_1, L_2, L_3,...
identifier_2 n_2: L_1, L_2, L_3,...
...

Here n_1 is the number of lines containing the identifier_1 and L_i(i >= 1) is the list of line numbers on which it appears.

The provided avlTree.java class:
(I also have my regular driver class which really doesn't have much in it because I am stuck trying to figure out how to read the inputs into a set. I also have an AVLMap and AVLSet class which are blank.)

import java.util.Set;
import java.io.FileNotFoundException;
import java.util.Collection;
import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;
 
// AvlTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x (unimplemented)
// boolean contains( x )  --> Return true if x is present
// boolean remove( x )    --> Return true if x was present
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as appropriate
 
/**
 * Implements an AVL tree.
 * Note that all "matching" is based on the compareTo method.
 * @author Mark Allen Weiss
 */
public class avlTree<AnyType extends Comparable<? super AnyType>> implements Set
{
    /**
     * Construct the tree.
     */
    public avlTree( )
    {
        root = null;
    }
 
    /**
     * Insert into the tree; duplicates are ignored.
     * @param x the item to insert.
     */
    public void insert( AnyType x )
    {
        root = insert( x, root );
    }
 
    /**
     * Remove from the tree. Nothing is done if x is not found.
     * @param x the item to remove.
     */
    public void remove( AnyType x )
    {
        root = remove( x, root );
    }
 
 
    /**
     * Internal method to remove from a subtree.
     * @param x the item to remove.
     * @param t the node that roots the subtree.
     * @return the new root of the subtree.
     */
    private AvlNode<AnyType> remove( AnyType x, AvlNode<AnyType> t )
    {
        if( t == null )
            return t;   // Item not found; do nothing
 
        int compareResult = x.compareTo( t.element );
 
        if( compareResult < 0 )
            t.left = remove( x, t.left );
        else if( compareResult > 0 )
            t.right = remove( x, t.right );
        else if( t.left != null && t.right != null ) // Two children
        {
            t.element = findMin( t.right ).element;
            t.right = remove( t.element, t.right );
        }
        else
            t = ( t.left != null ) ? t.left : t.right;
        return balance( t );
    }
 
    /**
     * Find the smallest item in the tree.
     * @return smallest item or null if empty.
     */
    public AnyType findMin( )
    {
        if( isEmpty( ) )
            throw new UnderflowException( );
        return findMin( root ).element;
    }
 
    /**
     * Find the largest item in the tree.
     * @return the largest item of null if empty.
     */
    public AnyType findMax( )
    {
        if( isEmpty( ) )
            throw new UnderflowException( );
        return findMax( root ).element;
    }
 
    /**
     * Find an item in the tree.
     * @param x the item to search for.
     * @return true if x is found.
     */
    public boolean contains( AnyType x )
    {
        return contains( x, root );
    }
 
    /**
     * Make the tree logically empty.
     */
    public void makeEmpty( )
    {
        root = null;
    }
 
    /**
     * Test if the tree is logically empty.
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty( )
    {
        return root == null;
    }
 
    /**
     * Print the tree contents in sorted order.
     */
    public void printTree( )
    {
        if( isEmpty( ) )
            System.out.println( "Empty tree" );
        else
            printTree( root );
    }
 
    private static final int ALLOWED_IMBALANCE = 1;
 
    // Assume t is either balanced or within one of being balanced
    private AvlNode<AnyType> balance( AvlNode<AnyType> t )
    {
        if( t == null )
            return t;
 
        if( height( t.left ) - height( t.right ) > ALLOWED_IMBALANCE )
            if( height( t.left.left ) >= height( t.left.right ) )
                t = rotateWithLeftChild( t );
            else
                t = doubleWithLeftChild( t );
        else
        if( height( t.right ) - height( t.left ) > ALLOWED_IMBALANCE )
            if( height( t.right.right ) >= height( t.right.left ) )
                t = rotateWithRightChild( t );
            else
                t = doubleWithRightChild( t );
 
        t.height = Math.max( height( t.left ), height( t.right ) ) + 1;
        return t;
    }
 
    public void checkBalance( )
    {
        checkBalance( root );
    }
 
    private int checkBalance( AvlNode<AnyType> t )
    {
        if( t == null )
            return -1;
 
        if( t != null )
        {
            int hl = checkBalance( t.left );
            int hr = checkBalance( t.right );
            if( Math.abs( height( t.left ) - height( t.right ) ) > 1 ||
                    height( t.left ) != hl || height( t.right ) != hr )
                System.out.println( "OOPS!!" );
        }
 
        return height( t );
    }
 
 
    /**
     * Internal method to insert into a subtree.
     * @param x the item to insert.
     * @param t the node that roots the subtree.
     * @return the new root of the subtree.
     */
    private AvlNode<AnyType> insert( AnyType x, AvlNode<AnyType> t )
    {
        if( t == null )
            return new AvlNode<>( x, null, null );
 
        int compareResult = x.compareTo( t.element );
 
        if( compareResult < 0 )
            t.left = insert( x, t.left );
        else if( compareResult > 0 )
            t.right = insert( x, t.right );
        else
            ;  // Duplicate; do nothing
        return balance( t );
    }
 
    /**
     * Internal method to find the smallest item in a subtree.
     * @param t the node that roots the tree.
     * @return node containing the smallest item.
     */
    private AvlNode<AnyType> findMin( AvlNode<AnyType> t )
    {
        if( t == null )
            return t;
 
        while( t.left != null )
            t = t.left;
        return t;
    }
 
    /**
     * Internal method to find the largest item in a subtree.
     * @param t the node that roots the tree.
     * @return node containing the largest item.
     */
    private AvlNode<AnyType> findMax( AvlNode<AnyType> t )
    {
        if( t == null )
            return t;
 
        while( t.right != null )
            t = t.right;
        return t;
    }
 
    /**
     * Internal method to find an item in a subtree.
     * @param x is item to search for.
     * @param t the node that roots the tree.
     * @return true if x is found in subtree.
     */
    private boolean contains( AnyType x, AvlNode<AnyType> t )
    {
        while( t != null )
        {
            int compareResult = x.compareTo( t.element );
 
            if( compareResult < 0 )
                t = t.left;
            else if( compareResult > 0 )
                t = t.right;
            else
                return true;    // Match
        }
 
        return false;   // No match
    }
 
    /**
     * Internal method to print a subtree in sorted order.
     * @param t the node that roots the tree.
     */
    private void printTree( AvlNode<AnyType> t )
    {
        if( t != null )
        {
            printTree( t.left );
            System.out.println( t.element );
            printTree( t.right );
        }
    }
 
    /**
     * Return the height of node t, or -1, if null.
     */
    private int height( AvlNode<AnyType> t )
    {
        return t == null ? -1 : t.height;
    }
 
    /**
     * Rotate binary tree node with left child.
     * For AVL trees, this is a single rotation for case 1.
     * Update heights, then return new root.
     */
    private AvlNode<AnyType> rotateWithLeftChild( AvlNode<AnyType> k2 )
    {
        AvlNode<AnyType> k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        k2.height = Math.max( height( k2.left ), height( k2.right ) ) + 1;
        k1.height = Math.max( height( k1.left ), k2.height ) + 1;
        return k1;
    }
 
    /**
     * Rotate binary tree node with right child.
     * For AVL trees, this is a single rotation for case 4.
     * Update heights, then return new root.
     */
    private AvlNode<AnyType> rotateWithRightChild( AvlNode<AnyType> k1 )
    {
        AvlNode<AnyType> k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1;
        k2.height = Math.max( height( k2.right ), k1.height ) + 1;
        return k2;
    }
 
    /**
     * Double rotate binary tree node: first left child
     * with its right child; then node k3 with new left child.
     * For AVL trees, this is a double rotation for case 2.
     * Update heights, then return new root.
     */
    private AvlNode<AnyType> doubleWithLeftChild( AvlNode<AnyType> k3 )
    {
        k3.left = rotateWithRightChild( k3.left );
        return rotateWithLeftChild( k3 );
    }
 
    /**
     * Double rotate binary tree node: first right child
     * with its left child; then node k1 with new right child.
     * For AVL trees, this is a double rotation for case 3.
     * Update heights, then return new root.
     */
    private AvlNode<AnyType> doubleWithRightChild( AvlNode<AnyType> k1 )
    {
        k1.right = rotateWithLeftChild( k1.right );
        return rotateWithRightChild( k1 );
    }
 
    private static class AvlNode<AnyType>
    {
            // Constructors
        AvlNode( AnyType theElement )
        {
            this( theElement, null, null );
        }
 
        AvlNode( AnyType theElement, AvlNode<AnyType> lt, AvlNode<AnyType> rt )
        {
            element  = theElement;
            left     = lt;
            right    = rt;
            height   = 0;
        }
 
        AnyType           element;      // The data in the node
        AvlNode<AnyType>  left;         // Left child
        AvlNode<AnyType>  right;        // Right child
        int               height;       // Height
    }
 
      /** The tree root. */
    private AvlNode<AnyType> root;
 
 
        // Test program
    public static void main( String [ ] args )
    {
        avlTree<Integer> t = new avlTree<>( );
        final int SMALL = 40;
        final int NUMS = 1000000;  // must be even
        final int GAP  =   37;
 
        System.out.println( "Checking... (no more output means success)" );
 
        for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
        {
        //    System.out.println( "INSERT: " + i );
            t.insert( i );
            if( NUMS < SMALL )
                t.checkBalance( );
        }
 
        for( int i = 1; i < NUMS; i+= 2 )
        {
         //   System.out.println( "REMOVE: " + i );
            t.remove( i );
            if( NUMS < SMALL )
                t.checkBalance( );
        }
        if( NUMS < SMALL )
            t.printTree( );
        if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )
            System.out.println( "FindMin or FindMax error!" );
 
        for( int i = 2; i < NUMS; i+=2 )
             if( !t.contains( i ) )
                 System.out.println( "Find error1!" );
 
        for( int i = 1; i < NUMS; i+=2 )
        {
            if( t.contains( i ) )
                System.out.println( "Find error2!" );
        }
    }
 
	@Override
	public boolean add(Object e) {
		// TODO Auto-generated method stub
		return false;
	}
 
	@Override
	public boolean addAll(Collection c) {
		// TODO Auto-generated method stub
		return false;
	}
 
	@Override
	public void clear() {
		// TODO Auto-generated method stub
 
	}
 
	@Override
	public boolean contains(Object o) {
		// TODO Auto-generated method stub
		return false;
	}
 
	@Override
	public boolean containsAll(Collection c) {
		// TODO Auto-generated method stub
		return false;
	}
 
	@Override
	public Iterator iterator() {
		// TODO Auto-generated method stub
		return null;
	}
 
	@Override
	public boolean remove(Object o) {
		// TODO Auto-generated method stub
		return false;
	}
 
	@Override
	public boolean removeAll(Collection c) {
		// TODO Auto-generated method stub
		return false;
	}
 
	@Override
	public boolean retainAll(Collection c) {
		// TODO Auto-generated method stub
		return false;
	}
 
	@Override
	public int size() {
		// TODO Auto-generated method stub
		return 0;
	}
 
	@Override
	public Object[] toArray() {
		// TODO Auto-generated method stub
		return null;
	}
 
	@Override
	public Object[] toArray(Object[] a) {
		// TODO Auto-generated method stub
		return null;
	}
}

This is my treemap and treeset class. i have another pair of classes called hashmap and hashset but will not include them as they are pretty similar. I pulled most of this information from the Java API and just need to know how to use sets/maps in order to fill out the methods.

The second step has me running three different variants of the previously listed program. Each variant will use a different type of tree/map. The variants are AVL Map/Set, Tree Map/Set, and Hash Map/Set.

import java.util.AbstractMap;
 
 
 
 
//a red-black tree based navigablemap implementation. *the map is sorted according to the natural ordering of its keys
//...or by a comparator provided at map creation time, depending on which constructor is used
public class TreeMap<K,V> extends AbstractMap<K,V> {
 
 
 
 
	//constructs a new, empty tree map, using the natural ordering of its keys. *all keys inserted into the map must implement
	//...the Comparable interface.
	public TreeMap(){
 
	}
 
	//returns the number of key-value mappings in this map
	public int size(){
 
	}
 
	//returns true if this map contains a mapping for the specified key
	public boolean containsKey(Object key){
 
	}
 
	//returns true if this map maps one or more keys to the specified value. *more formally, returns true if and only if this map
	//...contains at least one mapping to a value v such that (value == null ? v == null : value.equals(v)).
	public boolean containsValue(Object value){
 
	}
 
	//returns the value to which the specified key is mapped, or null if this map contains no mapping for the key
	public V get(Object key){
 
	}
 
	//removes the mapping for this key from this TreeMap if present
	public V remove(Object key){
 
	}
 
	//removes all of the mappings from this map. *the map will be empty after this call returns
	public void clear(){
 
	}
}

import java.util.AbstractSet;
import java.util.Iterator;
 
//stores elements in a red-black tree, orders its elements based on their values;  substantially slower than HashSet
public class TreeSet<E> extends AbstractSet<E> {
 
	//constructs a new, empty tree set, sorted according to the natural ordering of its elements
	public TreeSet(){
 
	}
 
	//returns an iterator over the elements in this set in ascending order
	public Iterator<E> iterator(){
 
	}
 
	//returns the number of elements in this set
	public int size(){
 
	}
 
	//returns true if this set contains no elements
	public boolean isEmpty(){
 
	}
 
	//returns true if this set contains the specified element
	public boolean contains(Object o){
 
	}
 
	//adds the specified element to this set if it is not already present
	public boolean add(E e){
 
	}
 
	//removes the specified element from this set if it is present
	public boolean remove(Object o){
 
	}
 
	//removes all of the elements from this set.  this set will be empty after this call returns
	public void clear(){
 
	}
}

Thanks in advance for any assistance you guys can provide.

Originally Posted by Norm

Can you explain what objects are to go in the set and how the data from the file is used to create those objects?

he said it could be any reasonably sized document with numbers, punctuation, as well as words. it will not count word occurances that happen more than once on a line
Ex:
Apple Cooperation Monitor Apple
blah blah Apple

The output will be:
ID Occurance Line Numbers
Apple 2 1,2
Cooperation 1 1
Monitor 1 1
blah 1 2

(With better formatting, this was just a rough sketch)
I am also updating my first post with more code/classes

Originally Posted by Norm

Why are you using a Set vs a Map? It looks like a Map would be more useful: key= token, value= list of line numbers

Im sorry, when I added the new classes, I forgot to add the second step of the instructions. The second step has me running three different variants of the previously listed program. Each variant will use a different type of tree/map. The variants are AVL Map/Set, Tree Map/Set, and Hash Map/Set. Updated the original post.

To answer your question, I thought maps and sets were used together.