隨筆 - 8, 文章 - 0, 評論 - 6, 引用 - 0
          

          


          		
	
          

          

          
	
          
		
			
          
				數據加載中……
			
          
		          		
		
			
          
				
					

          
			  
	2007年5月15日
	

          


		
          
			
          實現一個棧,使其push,pop,min(取得棧中的最小元素)均為O(1)
          
			
          
			實現一個棧,使其push,pop,min(取得棧中的最小元素)均為O(1)

          我的解
          

          interface IntStack
          {
                        int pop();
                        void push(int i);
                        int get();
          }

          class MinStack
          {
                        //store all the element
              private IntStack elemStack = new IntStack();
              
                        //store current and historical smallest element
              private IntStack minStack = new IntStack();
              
                        public void push(int i)
                        {
                  elemStack.push(i);
                  
                            int currentMin = minStack.get();
                            if(i <= currentMin) minStack.push(i);
              }
              
                        public int pop()
                        {
                            int result = elemStack.pop();
                            if(result == minStack.get()) minStack.pop();
                            return result;
              }
              
                        public int getMinElem()
                        {
                            return minStack.get();
              }
          }
          

			
          
			
          		
			posted @ 2007-07-18 20:57 Job Hu 閱讀(902) | 評論 (0) | 編輯 收藏
			
          
		
          
	
		
          
			
          二叉排序樹變為雙向鏈表
          
			
          
			
          把一個二叉排序樹(也許不叫這個)變為遞增的雙向鏈表,不能夠生成額外的結點.
          eg 6
                 / \
                4   8
               / \ / \
              3  5 7  9
          

          3=4=5=6=7=8=9

          我的解:
          

          class Node
          {
                        public Node left;
                        public Node right;
              
                        private static Node getLinkListTail(Node head)
                        {
                  Node result           = head;
                            if(result==null) return null;
                            while(result.right!=null)
                            {
                      result           = result.right;
                  }
                            return result;
              }
              
                        public static Node flatten(Node root)
                        {
                            if(root==null) return null;
                  
                  Node result           = root;
                  
                            // A leaf node
                  if(root.left==null&&root.right==null) return root;
                  
                            //divide-and-conquer
                  Node leftSubTreeLinkListHead = flatten(root.left);
                  Node rightSubTreeLinkListHead           = flatten(root.right);
                  
                            //merge
                  Node leftSubTreeLinkListTail = getLinkListTail(leftSubTreeLinkListHead);
                  root.left           = leftSubTreeLinkListTail;
                  root.right           = rightSubTreeLinkListHead;
                            if(leftSubTreeLinkListHead!=null) 
                            {
                      result           = leftSubTreeLinkListHead;
                      leftSubTreeLinkListTail.right           = root;
                  }
                            if(rightSubTreeLinkListHead!=null) rightSubTreeLinkListHead.left = root;
                  
                            return result;
              }
          }

          

			
          
			
          		
			posted @ 2007-07-18 20:37 Job Hu 閱讀(648) | 評論 (0) | 編輯 收藏
			
          
		
          
	
		
          
			
          Byte in Java
          
			
          
			

          public class ByteTest
          {
                        public static void main(String[] args)
                        {
                            byte b;
                            byte c;
                            //b = 255; //Cannot convert from int to byte
                            //b = 0xFF; //Cannot convert from int to byte
                  b = 127;
                  c           = 0x7F;
                            if(b == c) System.out.println("b == c");
                            if(127 == 0x7F) System.out.println("127 == 0x7F");
                  
                  b           = -128;
                            //c = 0x80; //Cannot convert from int to byte
                  c = (byte)0x80;
                            if(b == c) System.out.println("b == c");
                            if(-128 == 0x80) System.out.println("-128 == 0x80");
                            if(128 == 0x80) System.out.println("128 == 0x80"); 
                  
                  c           = (byte)0x80;
                            if(128 == c) System.out.println("128 == c");
                            if(-128 == c) System.out.println("-128 == c");
                            if(128 == (c&0xFF)) System.out.println("128 == (c&0xFF)");
              }
          }
          
輸出:
          b == c
          127 == 0x7F
          b == c
          128 == 0x80
          -128 == c
          128 == (c&0xFF)

			
          
			
          		
			posted @ 2007-07-17 23:22 Job Hu 閱讀(293) | 評論 (0) | 編輯 收藏
			
          
		
          
	
		
          
			
          Java Language Keywords
          
			
          
			Here's a list of keywords in the Java programming language.
You cannot
use any of the following as identifiers in your programs. The keywords
const and goto are reserved, even though they are not
currently used.
true, false, and null
might seem like keywords, but they are actually literals; you cannot
use them as identifiers in your programs.

          
    
        
          
            abstract
            continue
            for
            new
            switch
        
          
        
          
            assert***
            default
            goto*
            package
            synchronized
        
          
        
          
            boolean
            do
            if
            private
            this
        
          
        
          
            break
            double
            implements
            protected
            throw
        
          
        
          
            byte
            else
            import
            public
            throws
        
          
        
          
            case
            enum****
            instanceof
            return
            transient 
        
          
        
          
            catch
            extends
            int
            short
            try
        
          
        
          
            char
            final
            interface
            static
            void
        
          
        
          
            class
            finally
            long
            strictfp**
            volatile
        
          
        
          
            const*
            float
            native
            super
            while
        
          
              

          
			
          
			
          		
			posted @ 2007-07-09 22:38 Job Hu 閱讀(201) | 評論 (1) | 編輯 收藏
			
          
		
          
	
		
          
			
          Tomcat筆記（三）
          
			
          
			來看看ContainerBase的start方法：
          

           1public synchronized void start() throws LifecycleException {
           2
           3        //如果Container已經處于start狀態，直接返回
           4        if (started) {
           5            if(log.isInfoEnabled())
           6                log.info(sm.getString("containerBase.alreadyStarted", logName()));
           7            return;
           8        }
           9        
          10        // Notify our interested LifecycleListeners
          11        lifecycle.fireLifecycleEvent(BEFORE_START_EVENT, null);
          12
          13        started = true;
          14
          15        // Start our subordinate components, if any
          16        if ((loader != null) && (loader instanceof Lifecycle))
          17            ((Lifecycle) loader).start();
          18        logger = null;
          19        getLogger();
          20        if ((logger != null) && (logger instanceof Lifecycle))
          21            ((Lifecycle) logger).start();
          22    //用來管理session
          23        if ((manager != null) && (manager instanceof Lifecycle))
          24            ((Lifecycle) manager).start();
          25    //看名字就知道是干什么的，不過研究集群的優先級很低
          26        if ((cluster != null) && (cluster instanceof Lifecycle))
          27            ((Lifecycle) cluster).start();
          28    //用來進行訪問控制，或者權限控制的
          29        if ((realm != null) && (realm instanceof Lifecycle))
          30            ((Lifecycle) realm).start();
          31    //和JNDI相關
          32        if ((resources != null) && (resources instanceof Lifecycle))
          33            ((Lifecycle) resources).start();
          34
          35        //啟動所有子container
          36        Container children[] = findChildren();
          37        for (int i = 0; i < children.length; i++) {
          38            if (children[i] instanceof Lifecycle)
          39                ((Lifecycle) children[i]).start();
          40        }
          41
          42        // 啟動Container內部持有的pipeline對象，Container對Pipeline接口的實現就是通過調用這個內部持有的Pipeline對象
          43        if (pipeline instanceof Lifecycle)
          44            ((Lifecycle) pipeline).start();
          45
          46        // Notify our interested LifecycleListeners
          47        lifecycle.fireLifecycleEvent(START_EVENT, null);
          48
          49        // 注釋說這個函數用來check session是否過期，但看的不是太懂
          50        threadStart();
          51
          52        // Notify our interested LifecycleListeners
          53        lifecycle.fireLifecycleEvent(AFTER_START_EVENT, null);
          54
          55}
          56
          
           

          所有和cluster、realm相關都放在最后來研究了，不管怎么樣先把tomcat如何處理request的整個過程串起來對現在的我來說是最重要的。另外還有Tomcat中的很多部件都用到了JMX API，即SNMP的Java實現來進行性能檢測和管理，這個也會放在最后研究。
          

          ContainerBase就看這么多了，下面來看看StandardEngine這個類。除去和cluster、realm、JMX相關的方法后，StanderdEngine剩下的方法就很很少了。
          

          StandardEngine有一個Service類型的成員。Java doc中指出Service就是由很多共享同一個Container的Connector組成。一個Service對應于一個Container，來自這個Service的任何一個Connector的request都會由其對應的Container進行處理?？吹浆F在的感覺就是Connector對Container提供request對象，并接受Container返回的response對象。在Tomcat中有很多類別都被用來體現現request或者response，例如org.apache.catalina.connector .Request就是Coyote request的一個wrapper類，Coyote這個framework幫助封裝了底層的網絡復雜性，向上提供一個統一的接口。我想tomcat既能夠成為一個standalone的http、jsp/Servlet服務器，也能夠同apache http server集成，很可能就是依賴于Coyote提供的統一接口。
          
在構造函數中會將StandardEngine這個Pipeline的最后一個Valve，即Basic設置為StandardEngineValve。來看看StandardEnginValue的invoke方法
          

           1public final void invoke(Request request, Response response)
           2        throws IOException, ServletException {
           3
           4        // Select the Host to be used for this Request
           5        Host host = request.getHost();
           6        if (host == null) {
           7            response.sendError
           8                (HttpServletResponse.SC_BAD_REQUEST,
           9                 sm.getString("standardEngine.noHost", 
          10                              request.getServerName()));
          11            return;
          12        }
          13
          14        // Ask this Host to process this request
          15        host.getPipeline().getFirst().invoke(request, response);
          16
          17    }
          18
          
 

          可以看出在處理到StandardEngine這個Pipeline的最后一個Valve時，會根據當前request所指定的Host，將當前的request和response傳遞給該Host這個Pipeline的第一個Valve進行處理。
          

          我想Tomcat中的Engine、Host、Context、Wrapper處理request生成response的過程大概是這樣的：
          
Engine在收到request后在其Pipeline中的每一個Valve對request進行處理，也可能會生成response的某些部分，在最后一個Valve中將request和response傳給下一級Container即Host的第一個Valve。Host重復同樣過程，繼續傳遞給Context，Context再傳遞給Wrapper。由于Wrapper代表的是Servlet對象，因此在Wrapper處所有的處理都結束了，response對象生成完畢。當然了，如果在某一級中無法找到request要求的下一級對象，則整個處理過程也會立即結束。

			
          
			
          		
			posted @ 2007-05-30 22:58 Job Hu 閱讀(360) | 評論 (1) | 編輯 收藏
			
          
		
          
	
		
          
			
          Tomcat筆記（二）
          
			
          
			
          ContainerBase對Pipeline接口的實現完全依賴于其內部的一個Pipeline類型的成員pipeline（實現類為StandardPipeline）。
                        在Tomcat的doc中這樣介紹Pipeline接口：該接口的invoke（）方法被調用時，將會引發一系列Value對象的序列調用。要求一個Pipeline中的存在一個Value對象（多為最后一個Value對象）完成對request的處理，并生成相應的response，而不能試圖將Request繼續傳遞給其它Value對象（這個Value對象被稱為Basic）。通常，每個Container對象都持有一個Pipline類型(實際上為StandardPipeline)的成員。在Pipeline的doc中，方法getBasic，getFirst兩個方法的Method Summary完全一樣，Apache的牛人們也不能免俗啊。
          

          StandardPipeline除實現Pipeline接口外，也實現了Lifecycle接口。這個類的start和stop方法，首先檢查是否已經被start或stop，如果是則會拋出一個LifecycleException的異常，否則便fire和生命期改變的相關事件，并調用其內部valve對象（如果該valve對象也實現了Lifecycle接口）的start和stop方法。addValve方法用來向StandardPipeline中加入Valve對象，新加入的Value對象被放在一個叫做Basic的特殊Valve（就是一個Pipeline的最后一個Valve）的前面，如果在添加Valve的時候該StandardPipeline已經處于start狀態，則會進行一些注冊（調用apache commons庫的一個類，完全沒有看懂這個地方是什么作用>_<）
          

			
          
			
          		
			posted @ 2007-05-28 07:39 Job Hu 閱讀(307) | 評論 (0) | 編輯 收藏
			
          
		
          
	
		
          
			
          一個簡化的java線程池示例
          
			
          
			//以前寫在blogger上的一篇老文了
          曾經很好奇線程池是怎么實現的，.net中有現成的線程池可以使用，但是java中沒有。還有就是Servlet的service方法是怎么樣為每一個 Request在不同的線程中獨立服務的，由于Servlet接口沒有繼承自Runnable接口，因此無法直接由一個Servlet對象生成多個線程。后來在網上找到了一個java版本的線程池的例子（http://www.informit.com/articles/article.asp?p= 30483&seqNum=1&rl=1）在該例子的基礎上簡化得到了下面這個版本的java線程池，記錄在這里。

          *******************
          ThreadPool.java
          *******************

          package threadPool;

          import java.util.ArrayList;
          import java.util.Collection;

          public class ThreadPool
          {
              Thread[] threadArray;
              Collection          <Runnable> jobs = new ArrayList<Runnable>();
           
                        public ThreadPool(int threadNum)
                        {
                  threadArray           = new WorkerThread[threadNum];
                            for (Thread thread : threadArray)
                            {
                      thread           = new WorkerThread();
                      thread.start();
                  }
              }
           
                        public synchronized void addJob(Runnable job)
                        {
                  jobs.add(job);
                  notify();
              }
           
                        private synchronized Runnable getJob()
                        {
                            while(jobs.isEmpty())
                            {
                                try
                                {
                          wait();
                      }           catch (InterruptedException e)
                                {
                          e.printStackTrace();
                      }
                  }
                  Runnable job           =  jobs.iterator().next();
                  jobs.remove(job);
                            return job;
              }
              
                        private class WorkerThread extends Thread
                        {
                            public void run()
                            {
                      Runnable job           = null;
                                while(job == null)
                                {
                          job           = getJob();
                                    if(job != null)
                                    {
                              job.run();
                          }
                          job           = null;
                      }
                 }
              }
          }

           

          *******************
          ThreadPoolTest.java
          *******************

          package threadPool;

          public class ThreadTest
          {
                        private static class PrintClass implements Runnable
                        {
                            private int threadNo;
            
                            public PrintClass(int threadNo)
                            {
                                this.threadNo = threadNo;
                  }
                  
                            public void run()
                            {
                                for(int i = 0; i < 10; i++)
                                {
                                    synchronized (System.out)
                                    {
                              System.out.println(          "Thread "+threadNo+": "+i);
                          }
                                    try
                                    {
                              Thread.sleep(          1000);
                          }           catch (InterruptedException e)
                                    {
                              e.printStackTrace();
                          }
                      }
                  }           
              }
           
                        public static void main(String[] args)
                        {
                  ThreadPool tp           = new ThreadPool(3);
                            for(int i=0; i <10; i++)
                            {
                      tp.addJob(          new PrintClass(i));
                  }
                            synchronized (System.out)
                            {
                      System.out.println(          "Job adding finished");
                  }
              }
          }
          

          

			
          
			
          		
			posted @ 2007-05-15 12:53 Job Hu 閱讀(906) | 評論 (3) | 編輯 收藏
			
          
		
          
	


				
			
          
		          		
	
          
	
          
		
			

		
	
          

          



    
          
        
	




主站蜘蛛池模板：
兴文县|
五大连池市|
永新县|
皮山县|
衡东县|
渭南市|
淳安县|
河间市|
闸北区|
麻栗坡县|
天祝|
敖汉旗|
大宁县|
濉溪县|
阜阳市|
时尚|
西乌珠穆沁旗|
应城市|
泸州市|
濉溪县|
石嘴山市|
基隆市|
攀枝花市|
仁布县|
广平县|
霸州市|
称多县|
镇康县|
巴彦淖尔市|
新安县|
清徐县|
城步|
左云县|
宝丰县|
田东县|
平山县|
桦甸市|
闸北区|
高密市|
株洲县|
福泉市|