程式扎記: [ Java 代碼範本 ] Java Set operation - Union/Intersect/Complement

標籤

2013年5月14日 星期二

[ Java 代碼範本 ] Java Set operation - Union/Intersect/Complement


Preface:
因為在 Java 提供的 Set 介面中並沒有我需要的集合操作, 所以就自己建立類別 SetOP 來處理:
- Unions (連集)
集合 S1 與 集合 S2 進行 Union 後 (S1 ∪ S2), 在操作完成後產生的 集合 會包含所有 S1 與 S2 的所有元素. 簡單範例如下:
- {1, 2} ∪ {red, white} ={1, 2, red, white}.
- {1, 2, green} ∪ {red, white, green} ={1, 2, red, white, green}.
- {1, 2} ∪ {1, 2} = {1, 2}.

- Intersections (交集)
集合 S1 與 集合 S2 進行 Intersection (S1 ∩ S2), 在操作完成後產生的 集合 中的元素會同時出現在 集合 S1 與 S2 中. 簡單範例如下:
- {1, 2} ∩ {red, white} = ∅.
- {1, 2, green} ∩ {red, white, green} = {green}.
- {1, 2} ∩ {1, 2} = {1, 2}.

- Complements (差集)
集合 S1 與 集合 S2 進行 Complement (S1 \ S2 或 S1 - S2), 在操作完成後產生的 集合 中的元素是 集合 S1 中所有元素但不包括出現在 集合 S2 中的那些元素. 簡單範例如下:
- {1, 2} \ {red, white} = {1, 2}.
- {1, 2, green} \ {red, white, green} = {1, 2}.
- {1, 2} \ {1, 2} = ∅.
- {1, 2, 3, 4} \ {1, 3} = {2, 4}.

Implementation:
- Class SetOP
  1. package flib.util;  
  2.   
  3. import java.util.HashSet;  
  4. import java.util.Iterator;  
  5. import java.util.Set;  
  6.   
  7. public class SetOP {  
  8.     /** 
  9.      * BD: Two sets can also be "subtracted". The relative complement of B in A (also called the set-theoretic difference of A and B),  
  10.      *     denoted by A \ B (or A − B), is the set of all elements that are members of A but not members of B.  
  11.      *     Note that it is valid to "subtract" members of a set that are not in the set, such as removing the element green from  
  12.      *     the set {1, 2, 3}; doing so has no effect. 
  13.      * REF: http://en.wikipedia.org/wiki/Set_(mathematics)#Complements 
  14.      * @param sa 
  15.      * @param sb 
  16.      * @return sa - sb 
  17.      */  
  18.     public Set DIFF(Set sa, Set sb)  
  19.     {  
  20.         Set s1 = UNION(sa,sb);  
  21.         Set s2 = INTERSECT(sa,sb);  
  22.         s1.removeAll(s2);  
  23.         return s1;  
  24.     }  
  25.       
  26.     /** 
  27.      * BD: Two sets can also be "subtracted". The relative complement of B in A (also called the set-theoretic difference of A and B),  
  28.      *     denoted by A \ B (or A − B), is the set of all elements that are members of A but not members of B.  
  29.      *     Note that it is valid to "subtract" members of a set that are not in the set, such as removing the element green from  
  30.      *     the set {1, 2, 3}; doing so has no effect. 
  31.      * REF: http://en.wikipedia.org/wiki/Set_(mathematics)#Complements 
  32.      * @param sa 
  33.      * @param sb 
  34.      * @return sa - sb 
  35.      */  
  36.     public Set COMPLEMENT(Set sa, Set sb)  
  37.     {  
  38.         return DIFF(sa,sb);  
  39.     }  
  40.       
  41.     /** 
  42.      * BD: A new set can also be constructed by determining which members two sets have "in common".  
  43.      *     The intersection of A and B, denoted by A ∩ B, is the set of all things that are members of both A and B.  
  44.      *     If A ∩ B = ∅, then A and B are said to be disjoint. 
  45.      * REF: http://en.wikipedia.org/wiki/Set_(mathematics)#Intersections 
  46.      * @param sa 
  47.      * @param sb 
  48.      * @return sa ∩ sb 
  49.      */  
  50.     public Set INTERSECT(Set sa, Set sb)  
  51.     {  
  52.         Set s =  new HashSet();         
  53.         if(sa.size()>sb.size())  
  54.         {  
  55.             s.addAll(sa);  
  56.             s.retainAll(sb);  
  57.         }  
  58.         else  
  59.         {  
  60.             s.addAll(sb);  
  61.             s.retainAll(sa);  
  62.         }  
  63.         return s;  
  64.     }  
  65.       
  66.     /** 
  67.      * BD: Two sets can be "added" together. The union of A and B, denoted by A ∪ B,  
  68.      *     is the set of all things that are members of either A or B. 
  69.      * REF: http://en.wikipedia.org/wiki/Set_(mathematics)#Unions 
  70.      * @param sa 
  71.      * @param sb 
  72.      * @return sa ∪ sb 
  73.      */  
  74.     public Set UNION(Set sa, Set sb)  
  75.     {  
  76.         Set s =  new HashSet();         
  77.         if(sa.size()>sb.size())  
  78.         {  
  79.             s.addAll(sa);  
  80.             s.addAll(sb);  
  81.         }  
  82.         else  
  83.         {  
  84.             s.addAll(sb);  
  85.             s.addAll(sa);  
  86.         }  
  87.         return s;  
  88.     }  
  89.       
  90.     public void ADD(Set set, E...elms)  
  91.     {  
  92.         for(E e:elms) set.add(e);  
  93.     }  
  94.       
  95.     public String PrintSet(Set set)  
  96.     {  
  97.         StringBuffer strBuf = new StringBuffer("[");  
  98.         Iterator iter = set.iterator();  
  99.         E s = null;  
  100.         while(iter.hasNext())  
  101.         {  
  102.             if(s!=null) strBuf.append(",");  
  103.             strBuf.append(String.format("%s", s=iter.next()));  
  104.         }  
  105.         strBuf.append("]");  
  106.         return strBuf.toString();  
  107.     }  
  108. }  
Usage example:
  1. public static void main(String args[])  
  2. {  
  3.     Set sa = new HashSet();  
  4.     Set sb = new HashSet();  
  5.     SetOP sop = new SetOP();  
  6.     sop.ADD(sa, 1,2,3,4);  
  7.     sop.ADD(sb, 3,4,5,6);  
  8.     Set so = null;  
  9.     System.out.printf("\t[Info] Set sa: %s\n", sop.PrintSet(sa));  
  10.     System.out.printf("\t[Info] Set sb: %s\n", sop.PrintSet(sb));  
  11.       
  12.     System.out.printf("\t[Info] Union of sa,sb: ");  
  13.     so = sop.UNION(sa, sb);  
  14.     if(so.size()==0) System.out.printf("\t[]\n");  
  15.     else  
  16.     {  
  17.         Integer elms[] = new Integer[so.size()];  
  18.         so.toArray(elms);  
  19.         System.out.printf(" [%d", elms[0]);  
  20.         for(int i=1; i",%d", elms[i]);  
  21.         System.out.println("]");  
  22.     }  
  23.     System.out.printf("\t[Info] Difference of sa,sb: ");  
  24.     so = sop.DIFF(sa, sb);  
  25.     if(so.size()==0) System.out.printf(" []\n");  
  26.     else  
  27.     {  
  28.         Integer elms[] = new Integer[so.size()];  
  29.         so.toArray(elms);  
  30.         System.out.printf(" [%d", elms[0]);  
  31.         for(int i=1; i",%d", elms[i]);  
  32.         System.out.println("]");  
  33.     }  
  34.     System.out.printf("\t[Info] Intersection of sa,sb: ");  
  35.     so = sop.INTERSECT(sa, sb);  
  36.     if(so.size()==0) System.out.printf(" []\n");  
  37.     else  
  38.     {  
  39.         Integer elms[] = new Integer[so.size()];  
  40.         so.toArray(elms);  
  41.         System.out.printf(" [%d", elms[0]);  
  42.         for(int i=1; i",%d", elms[i]);  
  43.         System.out.println("]");  
  44.     }  
  45. }  
執行結果:
[Info] Set sa: [1,2,3,4]
[Info] Set sb: [3,4,5,6]
[Info] Union of sa,sb: [1,2,3,4,5,6]
[Info] Difference of sa,sb: [1,2,5,6]
[Info] Intersection of sa,sb: [3,4]
This message was edited 12 times. Last update was at 14/05/2013 15:27:46

沒有留言:

張貼留言

網誌存檔

關於我自己

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