程式扎記: [ Data Structures with Java ] Section 12.5 : OrderedList Collection

標籤

2011年2月15日 星期二

[ Data Structures with Java ] Section 12.5 : OrderedList Collection


Preface :
The LinkedList class describe a general sequential list. For many applications, we need a list structure that stores elements in order. Rather than building an OrderedList collection class from scratch, we can use inheritance to create one by extending the LinkedList class. The subclass can use the basic Collection interface methods in the superclass(LinkedList). It can also use the index-based remove() and get() methods that are defined in LinkedList. All of thses methods do not affect the ordering of the elements. However, list update methods such add() and set() are a different issue. They can destroy the ordering of the list. Iterators pose a separate problem. The OrderedList collection can use iterators and most of the functionality provided by list iterators in the superclass. The exceptions, of course, are the list iterator methods add() and set(), which can likewise destroy the ordering of list.
Designing the OrderedList class involves a few simple strategies. Let the LinkedList superclass store the elements and provides methods that give maximal functionality without destroying the integrity of a collection. Override the add(item) method that inserts the element at the back of the list. A new implementation for add(item) uses the insertOrder() algorithm from the previous section that places a new element in its correct location. For all of the other LinkedList methods, you can invalidate their use by overriding them with code that throws an exception. We use this strategy to override the methods add(index, element), addFirst(), addLst(), and set(). For the iterator, the OrderedList class should create an new ListIterator class that invalidates any call to add() or set(). We don't include this feature in our implementation of the OrderedList class.

OrderedList Class Methods :
The OrderedList class has a constructor that creates an empty list. Its implementation simply calls the detail constructor in the superclass. Below is the implementation on OrderedList based on we discuss previously :
- OrderedList.java Implementation :
  1. package DSwJ.S12;  
  2.   
  3. import java.util.LinkedList;  
  4.   
  5. public class OrderedListextends Comparablesuper T>> extends LinkedList{  
  6.     public OrderedList(){  
  7.         super();  
  8.     }  
  9.       
  10.     @Override  
  11.     public boolean add(T item) {  
  12.         java.util.ListIterator iter = this.listIterator();  
  13.         while(iter.hasNext()) {  
  14.             if(item.compareTo(iter.next())>0continue;  
  15.             iter.previous();  
  16.             break;  
  17.         }  
  18.         iter.add(item);  
  19.         return true;  
  20.     }  
  21.       
  22.     @Override  
  23.     public void add(int i, T item) {  
  24.         throw new UnsupportedOperationException(  
  25.                 "OrderedList add(index, element): Invalid operation");  
  26.     }  
  27.       
  28.     @Override  
  29.     public T set(int i, T item) {  
  30.         throw new UnsupportedOperationException(  
  31.         "OrderedList set(index, element): Invalid operation");  
  32.     }  
  33. }  

Application-Word Frequencies :
An application that determines the number of occurrences of each word in a document illustrates the use of an OrderedList collection. A document is input from a text file, and output displays the distinct words and their frequencies in alphabetical order. The application uses the class WordFreq, whose instance store a word and the number of times the word has occurred (the word frequency). The class has a constructor that creates an object with the word and a frequency of 1 as its data value. The toString() method output an object in the format word(frequency). When a word is first encountered in the document, a WordFreq object is created. For each subsequent occurrence of the word, the class supplies the method increment(), which increments the frequency field in the corresponding WordFreq object. In order that its objects can be stored in an OrderedList collection, the WordFreq class implements equals() and compareTo(). These methods use the word field to compare objects.
The main application declares the OrderedList collection wordList and a Scanner that is linked to a user-designated text file. The heart of the implementation is a while-loop that process each word from the file. After reading a word, use the constructor to create a WordFreq object wf with the word as its argument. We need to determine whether the word (actually object wf) is already in the list or must be added to the list. For this purpose, we implement the method search() that looks for a target in an OrderedList and returns an iterator referencing the value of null if the target is not in the list. The method takes advantages of list ordering by returning null if an existing list value is greater than the target. Below is the major implementation of this application :
- Method search() Implementation (In Bags.java) :
  1. public static extends Comparablesuper T>>  
  2.        java.util.ListIterator search(OrderedList ordList, T target) {  
  3.     java.util.ListIterator iter = ordList.listIterator();  
  4.     while(iter.hasNext()) {  
  5.         T cur = iter.next();  
  6.         if(cur.equals(target)) {  
  7.             iter.previous();  
  8.             return iter;  
  9.         } else if(target.compareTo(cur)<0){  
  10.             break;  
  11.         }  
  12.     }  
  13.     return null;  
  14. }  

- WordFreq.java Implementation :
  1. package DSwJ.S12;  
  2.   
  3. public class WordFreq implements Comparable{  
  4.     private String word;  
  5.     private int freq = 1;  
  6.       
  7.     public WordFreq(String w) {  
  8.         word = w;  
  9.     }  
  10.       
  11.     public void increment(){freq++;}  
  12.       
  13.     @Override  
  14.     public String toString(){  
  15.         return word+" ("+freq+")";  
  16.     }  
  17.   
  18.     @Override  
  19.     public boolean equals(Object target){  
  20.         if(target instanceof WordFreq) {  
  21.             WordFreq wf = (WordFreq)target;  
  22.             return wf.getWord().equals(getWord());  
  23.         }  
  24.         return false;  
  25.     }  
  26.       
  27.     @Override  
  28.     public int compareTo(WordFreq o) {        
  29.         return getWord().compareTo(o.getWord());  
  30.     }  
  31.       
  32.     public String getWord(){return word;}  
  33.     public int getFreq(){return freq;}  
  34. }  

Program 12.1 Word Frequencies :
The program implements the word frequency application using an OrderedList to store WordFreq objects. The user uses a command-line argument for the name of a file containing the document. After the file is opened, a loop reads successive words from the file. For each word, the program adds a new WordFreq object or updates the frequency field of the corresponding WordFreq object. After processing all the words in the file, the program display the calculating result :
- Implementation of Word Frequencies :
  1. public static void prog12_1(){  
  2.     try {  
  3.         Scanner fileIn = new Scanner(new FileReader(new File("./data/data.txt")));  
  4.         OrderedList wordList = new OrderedList();  
  5.         WordFreq wf;  
  6.         java.util.ListIterator iter;  
  7.         while(fileIn.hasNext()) {  
  8.             wf = new WordFreq(fileIn.next());  
  9.             iter = Bags.search(wordList, wf);  
  10.             if(iter==null) wordList.add(wf);  
  11.             else iter.next().increment();  
  12.         }  
  13.         iter = wordList.listIterator();  
  14.         int cnt = 1;  
  15.         while(iter.hasNext()) {  
  16.             wf = iter.next();  
  17.             System.out.print(wf.toString());  
  18.             for(int i=0; i<(12-wf.toString().length()); i++) System.out.print(" ");  
  19.             if(cnt%4==0) System.out.println();  
  20.             cnt++;  
  21.         }  
  22.     } catch (FileNotFoundException e) {           
  23.         e.printStackTrace();  
  24.     }  
  25. }  
This message was edited 4 times. Last update was at 06/10/2010 11:51:27

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!