2009-01-31 Tatsuhiro Tsujikawa <t-tujikawa@users.sourceforge.net>

	Use LongestSequencePieceSelector for HTTP/FTP/BitTorrent
	integrated downloads. This PieceSelector subclass finds the
	longest continuous sequence in the available missing pieces and
	selects the last index of such sequence. This makes HTTP/FTP
	connections less interrupted by the pieces obtained by
	BitTorrent peers.
	* src/DefaultPieceStorage.cc
	* src/DefaultPieceStorage.h
	* src/LongestSequencePieceSelector.cc
	* src/LongestSequencePieceSelector.h
	* src/Makefile.am
	* src/PieceSelector.h
	* src/RarestPieceSelector.h
	* src/RequestGroup.cc
	* test/BtDependencyTest.cc
	* test/DefaultPieceStorageTest.cc
	* test/IteratableChecksumValidatorTest.cc
	* test/LongestSequencePieceSelectorTest.cc
	* test/Makefile.am
	* test/SegmentManTest.cc

17 files changed, 392 insertions, 60 deletions

diff --git a/ChangeLog b/ChangeLog
index e2baa12c..442a63ce 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,28 @@
 2009-01-31  Tatsuhiro Tsujikawa  <t-tujikawa@users.sourceforge.net>
 
+	Use LongestSequencePieceSelector for HTTP/FTP/BitTorrent
+	integrated downloads. This PieceSelector subclass finds the
+	longest continuous sequence in the available missing pieces and
+	selects the last index of such sequence. This makes HTTP/FTP
+	connections less interrupted by the pieces obtained by BitTorrent
+	peers.
+	* src/DefaultPieceStorage.cc
+	* src/DefaultPieceStorage.h
+	* src/LongestSequencePieceSelector.cc
+	* src/LongestSequencePieceSelector.h
+	* src/Makefile.am
+	* src/PieceSelector.h
+	* src/RarestPieceSelector.h
+	* src/RequestGroup.cc
+	* test/BtDependencyTest.cc
+	* test/DefaultPieceStorageTest.cc
+	* test/IteratableChecksumValidatorTest.cc
+	* test/LongestSequencePieceSelectorTest.cc
+	* test/Makefile.am
+	* test/SegmentManTest.cc
+
+2009-01-31  Tatsuhiro Tsujikawa  <t-tujikawa@users.sourceforge.net>
+
 	Fixed the bug that the average speed is wrong in
 	http/ftp/BitTorrent integrated download. Only the download bytes
 	in BitTorrent were considered.
diff --git a/src/DefaultPieceStorage.cc b/src/DefaultPieceStorage.cc
index 85c7c6f0..15962629 100644
--- a/src/DefaultPieceStorage.cc
+++ b/src/DefaultPieceStorage.cc
@@ -61,7 +61,10 @@
 
 namespace aria2 {
 
-DefaultPieceStorage::DefaultPieceStorage(const DownloadContextHandle& downloadContext, const Option* option, bool randomPieceStatsOrdering):
+DefaultPieceStorage::DefaultPieceStorage
+(const DownloadContextHandle& downloadContext,
+ const Option* option,
+ const SharedHandle<PieceSelector>& pieceSelector):
   downloadContext(downloadContext),
   bitfieldMan(BitfieldManFactory::getFactoryInstance()->
 	      createBitfieldMan(downloadContext->getPieceLength(),
@@ -70,9 +73,13 @@ DefaultPieceStorage::DefaultPieceStorage(const DownloadContextHandle& downloadCo
   endGamePieceNum(END_GAME_PIECE_NUM),
   logger(LogFactory::getInstance()),
   option(option),
-  _pieceSelector(new RarestPieceSelector(downloadContext->getNumPieces(),
-					 randomPieceStatsOrdering))
-{}
+  _pieceSelector(pieceSelector)
+{
+  if(_pieceSelector.isNull()) {
+    _pieceSelector.reset
+      (new RarestPieceSelector(downloadContext->getNumPieces(), true));
+  }
+}
 
 DefaultPieceStorage::~DefaultPieceStorage() {
   delete bitfieldMan;
diff --git a/src/DefaultPieceStorage.h b/src/DefaultPieceStorage.h
index 20d64306..b8415f27 100644
--- a/src/DefaultPieceStorage.h
+++ b/src/DefaultPieceStorage.h
@@ -45,7 +45,7 @@ class Logger;
 class Option;
 class DiskWriterFactory;
 class FileEntry;
-class RarestPieceSelector;
+class PieceSelector;
 
 #define END_GAME_PIECE_NUM 20
 
@@ -81,7 +81,7 @@ private:
   const Option* option;
   Haves haves;
 
-  SharedHandle<RarestPieceSelector> _pieceSelector;
+  SharedHandle<PieceSelector> _pieceSelector;
 
   bool getMissingPieceIndex(size_t& index,
 			    const unsigned char* bitfield, size_t& length);
@@ -109,7 +109,9 @@ public:
   // priority.
   DefaultPieceStorage(const SharedHandle<DownloadContext>& downloadContext,
 		      const Option* option,
-		      bool randomPieceStatsOrdering = true);
+		      const SharedHandle<PieceSelector>& pieceSelector
+		      = SharedHandle<PieceSelector>());
+		      
   virtual ~DefaultPieceStorage();
 
   virtual bool hasMissingPiece(const SharedHandle<Peer>& peer);
diff --git a/src/LongestSequencePieceSelector.cc b/src/LongestSequencePieceSelector.cc
new file mode 100644
index 00000000..55436c55
--- /dev/null
+++ b/src/LongestSequencePieceSelector.cc
@@ -0,0 +1,83 @@
+/* <!-- copyright */
+/*
+ * aria2 - The high speed download utility
+ *
+ * Copyright (C) 2009 Tatsuhiro Tsujikawa
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ * In addition, as a special exception, the copyright holders give
+ * permission to link the code of portions of this program with the
+ * OpenSSL library under certain conditions as described in each
+ * individual source file, and distribute linked combinations
+ * including the two.
+ * You must obey the GNU General Public License in all respects
+ * for all of the code used other than OpenSSL.  If you modify
+ * file(s) with this exception, you may extend this exception to your
+ * version of the file(s), but you are not obligated to do so.  If you
+ * do not wish to do so, delete this exception statement from your
+ * version.  If you delete this exception statement from all source
+ * files in the program, then also delete it here.
+ */
+/* copyright --> */
+#include "LongestSequencePieceSelector.h"
+
+namespace aria2 {
+
+bool LongestSequencePieceSelector::select
+(size_t& index,
+ const std::deque<size_t>& candidateIndexes) const
+{
+  size_t maxlen = 0;
+  size_t maxfirst = 0;
+  size_t i = 0;
+  size_t lenA = candidateIndexes.size();
+
+  while(i < lenA) {
+    size_t first = i;
+    size_t len = 1;
+    size_t prev = first;
+    ++i;
+    while(i < lenA && candidateIndexes[prev]+1 == candidateIndexes[i]) {
+      ++len;
+      prev = i;
+      ++i;
+    }
+    if(maxlen < len) {
+      maxlen = len;
+      maxfirst = first;
+    }
+  } 
+  if(maxlen == 0) {
+    return false;
+  } else {
+    index = candidateIndexes[maxfirst+maxlen-1];
+    return true;
+  }
+}
+
+void LongestSequencePieceSelector::addPieceStats
+(const unsigned char* bitfield, size_t bitfieldLength) {}
+
+void LongestSequencePieceSelector::subtractPieceStats
+(const unsigned char* bitfield, size_t bitfieldLength) {}
+
+void LongestSequencePieceSelector::updatePieceStats
+(const unsigned char* newBitfield, size_t newBitfieldLength,
+ const unsigned char* oldBitfield) {}
+
+void LongestSequencePieceSelector::addPieceStats(size_t index) {}
+
+} // namespace aria2
diff --git a/src/LongestSequencePieceSelector.h b/src/LongestSequencePieceSelector.h
new file mode 100644
index 00000000..28838f0d
--- /dev/null
+++ b/src/LongestSequencePieceSelector.h
@@ -0,0 +1,66 @@
+/* <!-- copyright */
+/*
+ * aria2 - The high speed download utility
+ *
+ * Copyright (C) 2009 Tatsuhiro Tsujikawa
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ * In addition, as a special exception, the copyright holders give
+ * permission to link the code of portions of this program with the
+ * OpenSSL library under certain conditions as described in each
+ * individual source file, and distribute linked combinations
+ * including the two.
+ * You must obey the GNU General Public License in all respects
+ * for all of the code used other than OpenSSL.  If you modify
+ * file(s) with this exception, you may extend this exception to your
+ * version of the file(s), but you are not obligated to do so.  If you
+ * do not wish to do so, delete this exception statement from your
+ * version.  If you delete this exception statement from all source
+ * files in the program, then also delete it here.
+ */
+/* copyright --> */
+#ifndef _D_LONGEST_SEQUENCE_PIECE_SELECTOR_H_
+#define _D_LONGEST_SEQUENCE_PIECE_SELECTOR_H_
+
+#include "PieceSelector.h"
+
+namespace aria2 {
+
+class LongestSequencePieceSelector:public PieceSelector {
+public:
+  // Returns the last index of longest continuous sequence in candidateIndexes.
+  // For example, if candidateIndexes is
+  // { 1,2,3,4,7,10,11,12,13,14,15,100,112,113,114 }, then
+  // returns 15 because { 10, 11, 12, 13, 14, 15 } is the longest sequence.
+  virtual bool select
+  (size_t& index, const std::deque<size_t>& candidateIndexes) const;
+
+  virtual void addPieceStats(size_t index);
+
+  virtual void addPieceStats(const unsigned char* bitfield,
+			     size_t bitfieldLength);
+  
+  virtual void subtractPieceStats(const unsigned char* bitfield,
+				  size_t bitfieldLength);
+
+  virtual void updatePieceStats(const unsigned char* newBitfield,
+				size_t newBitfieldLength,
+				const unsigned char* oldBitfield);
+};
+
+} // namespace aria2
+
+#endif // _D_LONGEST_SEQUENCE_PIECE_SELECTOR_H_
diff --git a/src/Makefile.am b/src/Makefile.am
index 152a08bb..1643bd3c 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -204,7 +204,9 @@ SRCS =  Socket.h\
 	HttpListenCommand.cc HttpListenCommand.h\
 	HttpServerCommand.cc HttpServerCommand.h\
 	HttpServerResponseCommand.cc HttpServerResponseCommand.h\
-	HttpServer.cc HttpServer.h
+	HttpServer.cc HttpServer.h\
+	PieceSelector.h\
+	LongestSequencePieceSelector.cc LongestSequencePieceSelector.h
 
 if HAVE_EPOLL
 SRCS += EpollEventPoll.cc EpollEventPoll.h
diff --git a/src/Makefile.in b/src/Makefile.in
index 01adb93c..0a975fc6 100644
--- a/src/Makefile.in
+++ b/src/Makefile.in
@@ -417,10 +417,11 @@ am__libaria2c_a_SOURCES_DIST = Socket.h SocketCore.cc SocketCore.h \
 	HttpListenCommand.cc HttpListenCommand.h HttpServerCommand.cc \
 	HttpServerCommand.h HttpServerResponseCommand.cc \
 	HttpServerResponseCommand.h HttpServer.cc HttpServer.h \
-	EpollEventPoll.cc EpollEventPoll.h TLSContext.h \
-	LibgnutlsTLSContext.cc LibgnutlsTLSContext.h \
-	LibsslTLSContext.cc LibsslTLSContext.h GZipDecoder.cc \
-	GZipDecoder.h Sqlite3MozCookieParser.cc \
+	PieceSelector.h LongestSequencePieceSelector.cc \
+	LongestSequencePieceSelector.h EpollEventPoll.cc \
+	EpollEventPoll.h TLSContext.h LibgnutlsTLSContext.cc \
+	LibgnutlsTLSContext.h LibsslTLSContext.cc LibsslTLSContext.h \
+	GZipDecoder.cc GZipDecoder.h Sqlite3MozCookieParser.cc \
 	Sqlite3MozCookieParser.h AsyncNameResolver.cc \
 	AsyncNameResolver.h IteratableChunkChecksumValidator.cc \
 	IteratableChunkChecksumValidator.h \
@@ -816,13 +817,14 @@ am__objects_22 = SocketCore.$(OBJEXT) Command.$(OBJEXT) \
 	SelectEventPoll.$(OBJEXT) HttpListenCommand.$(OBJEXT) \
 	HttpServerCommand.$(OBJEXT) \
 	HttpServerResponseCommand.$(OBJEXT) HttpServer.$(OBJEXT) \
-	$(am__objects_1) $(am__objects_2) $(am__objects_3) \
-	$(am__objects_4) $(am__objects_5) $(am__objects_6) \
-	$(am__objects_7) $(am__objects_8) $(am__objects_9) \
-	$(am__objects_10) $(am__objects_11) $(am__objects_12) \
-	$(am__objects_13) $(am__objects_14) $(am__objects_15) \
-	$(am__objects_16) $(am__objects_17) $(am__objects_18) \
-	$(am__objects_19) $(am__objects_20) $(am__objects_21)
+	LongestSequencePieceSelector.$(OBJEXT) $(am__objects_1) \
+	$(am__objects_2) $(am__objects_3) $(am__objects_4) \
+	$(am__objects_5) $(am__objects_6) $(am__objects_7) \
+	$(am__objects_8) $(am__objects_9) $(am__objects_10) \
+	$(am__objects_11) $(am__objects_12) $(am__objects_13) \
+	$(am__objects_14) $(am__objects_15) $(am__objects_16) \
+	$(am__objects_17) $(am__objects_18) $(am__objects_19) \
+	$(am__objects_20) $(am__objects_21)
 am_libaria2c_a_OBJECTS = $(am__objects_22)
 libaria2c_a_OBJECTS = $(am_libaria2c_a_OBJECTS)
 am__installdirs = "$(DESTDIR)$(bindir)"
@@ -1151,13 +1153,15 @@ SRCS = Socket.h SocketCore.cc SocketCore.h BinaryStream.h Command.cc \
 	HttpListenCommand.cc HttpListenCommand.h HttpServerCommand.cc \
 	HttpServerCommand.h HttpServerResponseCommand.cc \
 	HttpServerResponseCommand.h HttpServer.cc HttpServer.h \
-	$(am__append_1) $(am__append_2) $(am__append_3) \
-	$(am__append_4) $(am__append_5) $(am__append_6) \
-	$(am__append_7) $(am__append_8) $(am__append_9) \
-	$(am__append_10) $(am__append_11) $(am__append_12) \
-	$(am__append_13) $(am__append_14) $(am__append_15) \
-	$(am__append_16) $(am__append_17) $(am__append_18) \
-	$(am__append_19) $(am__append_20) $(am__append_21)
+	PieceSelector.h LongestSequencePieceSelector.cc \
+	LongestSequencePieceSelector.h $(am__append_1) $(am__append_2) \
+	$(am__append_3) $(am__append_4) $(am__append_5) \
+	$(am__append_6) $(am__append_7) $(am__append_8) \
+	$(am__append_9) $(am__append_10) $(am__append_11) \
+	$(am__append_12) $(am__append_13) $(am__append_14) \
+	$(am__append_15) $(am__append_16) $(am__append_17) \
+	$(am__append_18) $(am__append_19) $(am__append_20) \
+	$(am__append_21)
 noinst_LIBRARIES = libaria2c.a
 libaria2c_a_SOURCES = $(SRCS)
 aria2c_LDADD = libaria2c.a @LIBINTL@ @ALLOCA@ @LIBGNUTLS_LIBS@\
@@ -1436,6 +1440,7 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/LibgnutlsTLSContext.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/LibsslTLSContext.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/LogFactory.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/LongestSequencePieceSelector.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/MSEHandshake.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/MemoryBufferPreDownloadHandler.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/MessageDigestHelper.Po@am__quote@
diff --git a/src/PieceSelector.h b/src/PieceSelector.h
new file mode 100644
index 00000000..b887d61b
--- /dev/null
+++ b/src/PieceSelector.h
@@ -0,0 +1,68 @@
+/* <!-- copyright */
+/*
+ * aria2 - The high speed download utility
+ *
+ * Copyright (C) 2009 Tatsuhiro Tsujikawa
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ * In addition, as a special exception, the copyright holders give
+ * permission to link the code of portions of this program with the
+ * OpenSSL library under certain conditions as described in each
+ * individual source file, and distribute linked combinations
+ * including the two.
+ * You must obey the GNU General Public License in all respects
+ * for all of the code used other than OpenSSL.  If you modify
+ * file(s) with this exception, you may extend this exception to your
+ * version of the file(s), but you are not obligated to do so.  If you
+ * do not wish to do so, delete this exception statement from your
+ * version.  If you delete this exception statement from all source
+ * files in the program, then also delete it here.
+ */
+/* copyright --> */
+#ifndef _D_PIECE_SELECTOR_H_
+#define _D_PIECE_SELECTOR_H_
+
+#include "common.h"
+
+#include <deque>
+
+#include "SharedHandle.h"
+
+namespace aria2 {
+
+class PieceSelector {
+public:
+  virtual ~PieceSelector() {}
+
+  virtual bool select
+  (size_t& index, const std::deque<size_t>& candidateIndexes) const = 0;
+
+  virtual void addPieceStats(size_t index) = 0;
+
+  virtual void addPieceStats(const unsigned char* bitfield,
+			     size_t bitfieldLength) = 0;
+  
+  virtual void subtractPieceStats(const unsigned char* bitfield,
+				  size_t bitfieldLength) = 0;
+
+  virtual void updatePieceStats(const unsigned char* newBitfield,
+				size_t newBitfieldLength,
+				const unsigned char* oldBitfield) = 0;
+};
+
+} // namespace aria2
+
+#endif // _D_PIECE_SELECTOR_H_
diff --git a/src/RarestPieceSelector.h b/src/RarestPieceSelector.h
index ff6d78a1..25ceab66 100644
--- a/src/RarestPieceSelector.h
+++ b/src/RarestPieceSelector.h
@@ -35,9 +35,7 @@
 #ifndef _D_RAREST_PIECE_SELECTOR_H_
 #define _D_RAREST_PIECE_SELECTOR_H_
 
-#include "common.h"
-#include "SharedHandle.h"
-#include <deque>
+#include "PieceSelector.h"
 
 namespace aria2 {
 
@@ -60,7 +58,7 @@ public:
   size_t getCount() const;
 };
 
-class RarestPieceSelector {
+class RarestPieceSelector:public PieceSelector {
 private:
   std::deque<SharedHandle<PieceStat> > _pieceStats;
 
@@ -68,19 +66,20 @@ private:
 public:
   RarestPieceSelector(size_t pieceNum, bool randomShuffle);
 
-  bool select(size_t& index, const std::deque<size_t>& candidateIndexes) const;
+  virtual bool select
+  (size_t& index, const std::deque<size_t>& candidateIndexes) const;
 
-  void addPieceStats(size_t index);
+  virtual void addPieceStats(size_t index);
 
-  void addPieceStats(const unsigned char* bitfield,
-		     size_t bitfieldLength);
+  virtual void addPieceStats(const unsigned char* bitfield,
+			     size_t bitfieldLength);
   
-  void subtractPieceStats(const unsigned char* bitfield,
-			  size_t bitfieldLength);
+  virtual void subtractPieceStats(const unsigned char* bitfield,
+				  size_t bitfieldLength);
 
-  void updatePieceStats(const unsigned char* newBitfield,
-			size_t newBitfieldLength,
-			const unsigned char* oldBitfield);
+  virtual void updatePieceStats(const unsigned char* newBitfield,
+				size_t newBitfieldLength,
+				const unsigned char* oldBitfield);
 
   const std::deque<SharedHandle<PieceStat> >& getSortedPieceStats() const;
 };
diff --git a/src/RequestGroup.cc b/src/RequestGroup.cc
index 9e246446..483561d1 100644
--- a/src/RequestGroup.cc
+++ b/src/RequestGroup.cc
@@ -76,6 +76,7 @@
 #include "A2STR.h"
 #include "URISelector.h"
 #include "InOrderURISelector.h"
+#include "PieceSelector.h"
 #ifdef ENABLE_MESSAGE_DIGEST
 # include "CheckIntegrityCommand.h"
 #endif // ENABLE_MESSAGE_DIGEST
@@ -97,6 +98,7 @@
 # include "ExtensionMessageFactory.h"
 # include "DHTPeerAnnounceStorage.h"
 # include "DHTEntryPointNameResolveCommand.h"
+# include "LongestSequencePieceSelector.h"
 #endif // ENABLE_BITTORRENT
 #ifdef ENABLE_METALINK
 # include "MetalinkPostDownloadHandler.h"
@@ -359,8 +361,22 @@ void RequestGroup::processCheckIntegrityEntry(std::deque<Command*>& commands,
 void RequestGroup::initPieceStorage()
 {
   if(_downloadContext->knowsTotalLength()) {
-    DefaultPieceStorageHandle ps
+#ifdef ENABLE_BITTORRENT
+    SharedHandle<DefaultPieceStorage> ps;
+    SharedHandle<PieceSelector> selector;
+    // Use LongestSequencePieceSelector when HTTP/FTP/BitTorrent integrated
+    // downloads. Currently multi-file integrated download is not supported.
+    if(!_uris.empty() &&
+       _downloadContext->getFileEntries().size() == 1 &&
+       !dynamic_pointer_cast<BtContext>(_downloadContext).isNull()) {
+      _logger->debug("Using LongestSequencePieceSelector");
+      selector.reset(new LongestSequencePieceSelector());
+    }
+    ps.reset(new DefaultPieceStorage(_downloadContext, _option, selector));
+#else // !ENABLE_BITTORRENT
+    SharedHandle<DefaultPieceStorage> ps
       (new DefaultPieceStorage(_downloadContext, _option));
+#endif // !ENABLE_BITTORRENT
     if(!_diskWriterFactory.isNull()) {
       ps->setDiskWriterFactory(_diskWriterFactory);
     }
diff --git a/test/BtDependencyTest.cc b/test/BtDependencyTest.cc
index be950840..2f192935 100644
--- a/test/BtDependencyTest.cc
+++ b/test/BtDependencyTest.cc
@@ -1,4 +1,9 @@
 #include "BtDependency.h"
+
+#include <iostream>
+
+#include <cppunit/extensions/HelperMacros.h>
+
 #include "SingleFileDownloadContext.h"
 #include "DefaultPieceStorage.h"
 #include "BtContext.h"
@@ -7,8 +12,7 @@
 #include "Exception.h"
 #include "SegmentMan.h"
 #include "FileEntry.h"
-#include <iostream>
-#include <cppunit/extensions/HelperMacros.h>
+#include "PieceSelector.h"
 
 namespace aria2 {
 
diff --git a/test/DefaultPieceStorageTest.cc b/test/DefaultPieceStorageTest.cc
index 92cc5782..24b6c7a1 100644
--- a/test/DefaultPieceStorageTest.cc
+++ b/test/DefaultPieceStorageTest.cc
@@ -12,6 +12,7 @@
 #include "Option.h"
 #include "FileEntry.h"
 #include "MockBtContext.h"
+#include "RarestPieceSelector.h"
 
 namespace aria2 {
 
@@ -36,6 +37,7 @@ private:
   SharedHandle<BtContext> btContext;
   SharedHandle<Peer> peer;
   Option* option;
+  SharedHandle<RarestPieceSelector> _selector;
 public:
   DefaultPieceStorageTest() {
     SharedHandle<FixedNumberRandomizer> randomizer
@@ -51,6 +53,7 @@ public:
     peer->allocateSessionResource(btContext->getPieceLength(),
 				  btContext->getTotalLength());
     option = new Option();
+    _selector.reset(new RarestPieceSelector(btContext->getNumPieces(), false));
   }
 
   void tearDown()
@@ -84,7 +87,7 @@ void DefaultPieceStorageTest::testGetTotalLength() {
 }
 
 void DefaultPieceStorageTest::testGetMissingPiece() {
-  DefaultPieceStorage pss(btContext, option, false);
+  DefaultPieceStorage pss(btContext, option, _selector);
   pss.setEndGamePieceNum(0);
 
   peer->setAllBitfield();
@@ -104,7 +107,7 @@ void DefaultPieceStorageTest::testGetMissingPiece() {
 
 void DefaultPieceStorageTest::testGetMissingPiece_excludedIndexes()
 {
-  DefaultPieceStorage pss(btContext, option, false);
+  DefaultPieceStorage pss(btContext, option, _selector);
   pss.setEndGamePieceNum(0);
 
   peer->setAllBitfield();
@@ -125,7 +128,7 @@ void DefaultPieceStorageTest::testGetMissingPiece_excludedIndexes()
 }
 
 void DefaultPieceStorageTest::testGetMissingFastPiece() {
-  DefaultPieceStorage pss(btContext, option, false);
+  DefaultPieceStorage pss(btContext, option, _selector);
   pss.setEndGamePieceNum(0);
 
   peer->setAllBitfield();
@@ -141,7 +144,7 @@ void DefaultPieceStorageTest::testGetMissingFastPiece() {
 
 void DefaultPieceStorageTest::testGetMissingFastPiece_excludedIndexes()
 {
-  DefaultPieceStorage pss(btContext, option, false);
+  DefaultPieceStorage pss(btContext, option, _selector);
   pss.setEndGamePieceNum(0);
 
   peer->setAllBitfield();
@@ -170,7 +173,7 @@ void DefaultPieceStorageTest::testHasMissingPiece() {
 }
 
 void DefaultPieceStorageTest::testCompletePiece() {
-  DefaultPieceStorage pss(btContext, option, false);
+  DefaultPieceStorage pss(btContext, option, _selector);
   pss.setEndGamePieceNum(0);
 
   peer->setAllBitfield();
diff --git a/test/IteratableChecksumValidatorTest.cc b/test/IteratableChecksumValidatorTest.cc
index 2458cc58..287fd548 100644
--- a/test/IteratableChecksumValidatorTest.cc
+++ b/test/IteratableChecksumValidatorTest.cc
@@ -1,10 +1,13 @@
 #include "IteratableChecksumValidator.h"
+
+#include <cppunit/extensions/HelperMacros.h>
+
 #include "SingleFileDownloadContext.h"
 #include "DefaultPieceStorage.h"
 #include "Option.h"
 #include "DiskAdaptor.h"
 #include "FileEntry.h"
-#include <cppunit/extensions/HelperMacros.h>
+#include "PieceSelector.h"
 
 namespace aria2 {
 
diff --git a/test/LongestSequencePieceSelectorTest.cc b/test/LongestSequencePieceSelectorTest.cc
new file mode 100644
index 00000000..d3b85593
--- /dev/null
+++ b/test/LongestSequencePieceSelectorTest.cc
@@ -0,0 +1,44 @@
+#include "LongestSequencePieceSelector.h"
+
+#include <cppunit/extensions/HelperMacros.h>
+
+#include "array_fun.h"
+
+namespace aria2 {
+
+class LongestSequencePieceSelectorTest:public CppUnit::TestFixture {
+
+  CPPUNIT_TEST_SUITE(LongestSequencePieceSelectorTest);
+  CPPUNIT_TEST(testSelect);
+  CPPUNIT_TEST_SUITE_END();
+public:
+  void setUp() {}
+
+  void tearDown() {}
+
+  void testSelect();
+};
+
+
+CPPUNIT_TEST_SUITE_REGISTRATION(LongestSequencePieceSelectorTest);
+
+void LongestSequencePieceSelectorTest::testSelect()
+{
+  size_t A[] = { 1,2,3,4,7,10,11,12,13,14,15,100,112,113,114 };
+  std::deque<size_t> indexes(&A[0], &A[arrayLength(A)]);
+
+  LongestSequencePieceSelector selector;
+  size_t index;
+
+  CPPUNIT_ASSERT(selector.select(index, indexes));
+  CPPUNIT_ASSERT_EQUAL((size_t)15, index);
+
+  std::deque<size_t> zeroindexes;
+  CPPUNIT_ASSERT(!selector.select(index, zeroindexes));
+
+  std::deque<size_t> oneseq(&A[0], &A[4]);
+  CPPUNIT_ASSERT(selector.select(index, oneseq));
+  CPPUNIT_ASSERT_EQUAL((size_t)4, index);
+}
+
+} // namespace aria2
diff --git a/test/Makefile.am b/test/Makefile.am
index 5d60cc46..88bbfd2d 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -65,7 +65,9 @@ aria2c_SOURCES = AllTest.cc\
 	SimpleDNSCacheTest.cc\
 	DownloadHelperTest.cc\
 	BencodeTest.cc\
-	SequentialPickerTest.cc
+	SequentialPickerTest.cc\
+	RarestPieceSelectorTest.cc\
+	LongestSequencePieceSelectorTest.cc
 
 if HAVE_LIBZ
 aria2c_SOURCES += GZipDecoderTest.cc
@@ -166,8 +168,7 @@ aria2c_SOURCES += BtAllowedFastMessageTest.cc\
 	MockDHTTaskQueue.h\
 	MockExtensionMessage.h\
 	MockExtensionMessageFactory.h\
-	MockPieceStorage.h\
-	RarestPieceSelectorTest.cc
+	MockPieceStorage.h
 endif # ENABLE_BITTORRENT
 
 if ENABLE_METALINK
diff --git a/test/Makefile.in b/test/Makefile.in
index 5ba37c94..0d9e7eb4 100644
--- a/test/Makefile.in
+++ b/test/Makefile.in
@@ -124,8 +124,7 @@ check_PROGRAMS = $(am__EXEEXT_1)
 @ENABLE_BITTORRENT_TRUE@	MockDHTTaskQueue.h\
 @ENABLE_BITTORRENT_TRUE@	MockExtensionMessage.h\
 @ENABLE_BITTORRENT_TRUE@	MockExtensionMessageFactory.h\
-@ENABLE_BITTORRENT_TRUE@	MockPieceStorage.h\
-@ENABLE_BITTORRENT_TRUE@	RarestPieceSelectorTest.cc
+@ENABLE_BITTORRENT_TRUE@	MockPieceStorage.h
 
 @ENABLE_METALINK_TRUE@am__append_5 = MetalinkerTest.cc\
 @ENABLE_METALINK_TRUE@	MetalinkEntryTest.cc\
@@ -193,6 +192,7 @@ am__aria2c_SOURCES_DIST = AllTest.cc TestUtil.cc TestUtil.h \
 	TimeTest.cc CopyDiskAdaptorTest.cc FtpConnectionTest.cc \
 	OptionParserTest.cc SimpleDNSCacheTest.cc \
 	DownloadHelperTest.cc BencodeTest.cc SequentialPickerTest.cc \
+	RarestPieceSelectorTest.cc LongestSequencePieceSelectorTest.cc \
 	GZipDecoderTest.cc Sqlite3MozCookieParserTest.cc \
 	MessageDigestHelperTest.cc \
 	IteratableChunkChecksumValidatorTest.cc \
@@ -238,8 +238,8 @@ am__aria2c_SOURCES_DIST = AllTest.cc TestUtil.cc TestUtil.h \
 	MockDHTMessageFactory.h MockDHTTask.h MockDHTTaskFactory.h \
 	MockDHTTaskQueue.h MockExtensionMessage.h \
 	MockExtensionMessageFactory.h MockPieceStorage.h \
-	RarestPieceSelectorTest.cc MetalinkerTest.cc \
-	MetalinkEntryTest.cc Metalink2RequestGroupTest.cc \
+	MetalinkerTest.cc MetalinkEntryTest.cc \
+	Metalink2RequestGroupTest.cc \
 	MetalinkPostDownloadHandlerTest.cc MetalinkHelperTest.cc \
 	MetalinkParserControllerTest.cc MetalinkProcessorTest.cc
 @HAVE_LIBZ_TRUE@am__objects_1 = GZipDecoderTest.$(OBJEXT)
@@ -316,8 +316,7 @@ am__aria2c_SOURCES_DIST = AllTest.cc TestUtil.cc TestUtil.h \
 @ENABLE_BITTORRENT_TRUE@	DHKeyExchangeTest.$(OBJEXT) \
 @ENABLE_BITTORRENT_TRUE@	ARC4Test.$(OBJEXT) \
 @ENABLE_BITTORRENT_TRUE@	MSEHandshakeTest.$(OBJEXT) \
-@ENABLE_BITTORRENT_TRUE@	DHTUtilTest.$(OBJEXT) \
-@ENABLE_BITTORRENT_TRUE@	RarestPieceSelectorTest.$(OBJEXT)
+@ENABLE_BITTORRENT_TRUE@	DHTUtilTest.$(OBJEXT)
 @ENABLE_METALINK_TRUE@am__objects_5 = MetalinkerTest.$(OBJEXT) \
 @ENABLE_METALINK_TRUE@	MetalinkEntryTest.$(OBJEXT) \
 @ENABLE_METALINK_TRUE@	Metalink2RequestGroupTest.$(OBJEXT) \
@@ -362,8 +361,10 @@ am_aria2c_OBJECTS = AllTest.$(OBJEXT) TestUtil.$(OBJEXT) \
 	FtpConnectionTest.$(OBJEXT) OptionParserTest.$(OBJEXT) \
 	SimpleDNSCacheTest.$(OBJEXT) DownloadHelperTest.$(OBJEXT) \
 	BencodeTest.$(OBJEXT) SequentialPickerTest.$(OBJEXT) \
-	$(am__objects_1) $(am__objects_2) $(am__objects_3) \
-	$(am__objects_4) $(am__objects_5)
+	RarestPieceSelectorTest.$(OBJEXT) \
+	LongestSequencePieceSelectorTest.$(OBJEXT) $(am__objects_1) \
+	$(am__objects_2) $(am__objects_3) $(am__objects_4) \
+	$(am__objects_5)
 aria2c_OBJECTS = $(am_aria2c_OBJECTS)
 am__DEPENDENCIES_1 =
 aria2c_DEPENDENCIES = ../src/libaria2c.a ../src/download_helper.o \
@@ -587,6 +588,7 @@ aria2c_SOURCES = AllTest.cc TestUtil.cc TestUtil.h SocketCoreTest.cc \
 	TimeTest.cc CopyDiskAdaptorTest.cc FtpConnectionTest.cc \
 	OptionParserTest.cc SimpleDNSCacheTest.cc \
 	DownloadHelperTest.cc BencodeTest.cc SequentialPickerTest.cc \
+	RarestPieceSelectorTest.cc LongestSequencePieceSelectorTest.cc \
 	$(am__append_1) $(am__append_2) $(am__append_3) \
 	$(am__append_4) $(am__append_5)
 
@@ -767,6 +769,7 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/InOrderURISelectorTest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/IteratableChecksumValidatorTest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/IteratableChunkChecksumValidatorTest.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/LongestSequencePieceSelectorTest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/MSEHandshakeTest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/MessageDigestHelperTest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/Metalink2RequestGroupTest.Po@am__quote@
diff --git a/test/SegmentManTest.cc b/test/SegmentManTest.cc
index 33e9f95b..8f7eefd8 100644
--- a/test/SegmentManTest.cc
+++ b/test/SegmentManTest.cc
@@ -1,4 +1,7 @@
 #include "SegmentMan.h"
+
+#include <cppunit/extensions/HelperMacros.h>
+
 #include "File.h"
 #include "prefs.h"
 #include "Util.h"
@@ -10,7 +13,7 @@
 #include "FileEntry.h"
 #include "MockPieceStorage.h"
 #include "PeerStat.h"
-#include <cppunit/extensions/HelperMacros.h>
+#include "PieceSelector.h"
 
 namespace aria2 {