Poset迭代次序/用於部分有序集合的自定義迭代器實現

我在java中創建了一個部分有序集作爲抽象數據類型，並且我必須創建一組數字的迭代器版本以及關係的迭代器。現在對於元素，我使用了HashSet的整數，對於關係，我使用了一個ArrayList對（對是我創建的一個類，它需要2個整數作爲參數，基本上就像（x，y））。我需要做2個迭代器，一個用於s，另一個用於r，但它們必須遵循某個順序，如果（x，y）屬於R，則s的迭代器在返回y之前應返回x y 2.如果（x，y）和（y，z）屬於R，則r的迭代器在返回之前返回（x，y）（y，z）Poset迭代次序/用於部分有序集合的自定義迭代器實現

我做了一個輔助方法，檢查集合中的元素n是否是一對中的第一個元素，然後返回它，但我似乎無法檢查它是否是第二個元素，如果它返回或不是，我如何檢查第一個元素？

這裏是我的代碼：

private class IntGenerator implements Iterator { 
     private Iterator<Integer> i; 


     public IntGenerator() { 
      i = S.iterator(); 
     } 

     public boolean hasNext() { 
      return i.hasNext(); 
     } 

     public Object next() { 
      int n = i.next(); 

      for (Pair p : R) { 
       if (isInFirstElmPair(p, n)) return n; 
       else (isInSecondElmPair(p, n)) { 
            // should check for the first element 
            // if it was returned or not 
       } 
      } 
     } 

     public void remove() { throw new UnsupportedOperationException(); } 
    }

我真的很感激任何形式的幫助，或在此代碼提示。感謝

編輯：

好啦，我已經添加了一組新將持有返回的元素後寫的代碼給它，這是我寫的：

Set<Integer> returnedNumbers = new HashSet<Integer>(); 
public Object next() { 
      int n = i.next(); 

      for (Pair p : R) { 
       if (isInSecondElmPair(p, n)) { 
        if (returnedNumbers.contains(p.getFirstElm())) { 
         returnedNumbers.add(n); 
         return n; 
        }else{ 
         returnedNumbers.add(p.getFirstElm()); 
         return p.getFirstElm(); 
        } 
       }else{ 
        returnedNumbers.add(n); 
        return n; 
       } 
      } 
     }

這是代碼正確嗎？另外，eclipse似乎給了我一個錯誤，告訴我我需要在循環外部返回一個值，但是我已經爲每種情況返回，爲什麼它需要更多？欣賞幫助

來源

2012-03-22 hakuna matata

我不完全理解這個問題，但我有一些筆記。如果我找到你的話，你提供的代碼就是's'的實現（下次請使用更清晰的命名約定）。現在看起來有可能來自集合的數字不會被它的迭代器返回，例如當它在任何對中的對應'第一元素'之前返回時。我對嗎？這是打算？而且，在我看來，這不會太可愛，你可以通過很多事情來獲取一個棕褐色，如果我沒有弄錯，r可能會變得非常大。不幸的是，我還不能提供更好的解決方案...... – Vincent 2012-03-22 23:07:39

關於編輯本身：開啓一個新問題通常比編輯一個已經接受答案的問題更好。沒有多少人看到已經回答過的問題，除非他們遇到了標題中指定的相同問題。至於編輯內容：如果'R'是空的，'next'會返回什麼？（你可能認爲它不是，但eclipse不知道這一點。） – 2012-03-23 09:53:24

至於正確性：編寫一個測試或主要方法添加幾對，看看它是否適合，一開始（如果你的元素類型會很好不限於整數，所以你可以用java中沒有的自然順序的元素來測試它）。對於使用整數對進行的非平凡測試，例如：嘗試1-0,2-0,4-3,5-1,5-4,3-2（爲了讓它更有意思，可以添加5 -0之前）。元素迭代器應該按照這個順序返回5-4-3-2-0，然後返回1到2之間的任何一個。是的，我確實發現這是一個非常有趣的問題。 :-) – 2012-03-23 10:02:45

那麼，要檢查一個值是否以前返回，您當然需要跟蹤以前返回的所有值。

所以在你的迭代器，你可以定義

Set<Integer> previouslyReturned = new HashSet<Integer>();

，然後，在你回到它的循環之前，將其添加有：

if (isInFirstElmPair(p, n)) { 
    previouslyReturned.add(n); 
    return n; 
} 
else (isInSecondElmPair(p, n)) { 
    if (previouslyReturned.contains(n) { 
     // do one thing 
    } else { 
     // do another thing 
    } 
}

這種方式，但是，你要構建s的順序應該返回內部的迭代器。創建一次（考慮一個LinkedHashSet）是有意義的，將它保存在其他地方並遍歷它。

通常我不確定這種方法會導致你想要什麼。你知道S和R中元素的順序嗎？如果迭代順序是任意的（即因爲關係是以不可預知的順序添加的），那麼迭代器將首先返回第一個關係對的前半部分，即使該元素位於另一對的後半部分。你有有使用元素HashSet和關係列表嗎？

來源

2012-03-22 23:05:47

+1以保持結構在施工中訂購 – Vincent 2012-03-22 23:09:57

擁有另一個數據結構來保存返回的元素似乎是一個好主意，我會嘗試它並在我執行時發佈結果。謝謝arne.b – 2012-03-23 09:08:46

Poset迭代次序/用於部分有序集合的自定義迭代器實現

回答

相關問題