001    package cnslab.cnsnetwork;
002    
003    import java.io.PrintStream;
004    import java.util.Map;
005    
006    import cnslab.cnsmath.*;
007    
008    /***********************************************************************
009    * Implement my customized Queue with Red-backtree data structure. 
010    * 
011    * @version
012    *   $Date: 2012-08-04 13:43:22 -0500 (Sat, 04 Aug 2012) $
013    *   $Rev: 104 $
014    *   $Author: croft $
015    * @author
016    *   Yi Dong
017    * @author
018    *   David Wallace Croft
019    ***********************************************************************/
020    public class  MTreeQueue<T extends Comparable<T>>
021      implements Queue<T>
022    ////////////////////////////////////////////////////////////////////////
023    ////////////////////////////////////////////////////////////////////////
024    {
025    
026    private RBTree<T> treeQueue = new RBTree<T>();
027
028    private T first;
029
030    private RBCell<T> firstNode;
031    
032    ////////////////////////////////////////////////////////////////////////
033    ////////////////////////////////////////////////////////////////////////
034
035    @Override
036    public synchronized void  deleteItem ( final T  item )
037    ////////////////////////////////////////////////////////////////////////
038    {
039      treeQueue.removeOneOf(item);
040      
041      if(treeQueue.root()==null)
042      {
043        firstNode=null;
044        
045        first=null;
046      }
047      else
048      {
049        firstNode = treeQueue.root().leftmost();
050        
051        first=firstNode.element();
052      }
053    }
054
055
056    @Override
057    public synchronized void  insertItem ( final T  item )
058    ////////////////////////////////////////////////////////////////////////
059    {
060      treeQueue.add(item);
061      
062      firstNode = treeQueue.root().leftmost();
063      
064      first=firstNode.element();
065    }
066
067    @Override
068    public synchronized T  firstItem ( )
069    ////////////////////////////////////////////////////////////////////////
070    {
071      return first;
072    }
073
074    @Override
075    public synchronized void  show ( final PrintStream  p )
076    ////////////////////////////////////////////////////////////////////////
077    {
078      if(treeQueue.root()!=null)
079      {
080        p.println("<");
081        
082        treeQueue.inorderTreeWalk(treeQueue.root(),p);
083        
084        p.println(">");
085      }
086    }
087
088    @Override
089    public synchronized String  show ( )
090    ////////////////////////////////////////////////////////////////////////
091    {
092      StringWrap p =  new StringWrap();
093      
094      if(treeQueue.root()!=null)
095      {
096        p.out=p.out+"<";
097        
098        treeQueue.inorderTreeWalk(treeQueue.root(),p);
099        
100        p.out=p.out+">";
101      }
102      
103      return p.out;
104    }
105
106    @Override
107    public synchronized void  clear ( )
108    ////////////////////////////////////////////////////////////////////////
109    {
110      treeQueue.clear();
111      
112      first = null;
113      
114      firstNode = null;
115    }
116    
117    ////////////////////////////////////////////////////////////////////////
118    ////////////////////////////////////////////////////////////////////////
119    
120    public synchronized T  lastItem ( )
121    ////////////////////////////////////////////////////////////////////////
122    {
123      if(treeQueue.root()==null)
124      {
125        return null;
126      }
127      else
128      {
129        RBCell<T> tmp = treeQueue.root().rightmost();
130        
131        return tmp.element();
132      }
133    }
134
135    ////////////////////////////////////////////////////////////////////////
136    ////////////////////////////////////////////////////////////////////////
137    }