2009-05-06 Tatsuhiro Tsujikawa <t-tujikawa@users.sourceforge.net>

	Moved piece statistics stuff to new PieceStatMan class.
	Refactored PieceSelector interface.
	* src/DefaultPieceStorage.cc
	* src/DefaultPieceStorage.h
	* src/LongestSequencePieceSelector.cc
	* src/LongestSequencePieceSelector.h
	* src/Makefile.am
	* src/PieceSelector.h
	* src/PieceStatMan.cc
	* src/PieceStatMan.h
	* src/RarestPieceSelector.cc
	* src/RarestPieceSelector.h
	* src/RequestGroup.cc
	* test/DefaultPieceStorageTest.cc
	* test/InOrderPieceSelector.h
	* test/Makefile.am
	* test/PieceStatManTest.cc
	* test/RarestPieceSelectorTest.cc

12 files changed, 364 insertions, 288 deletions

diff --git a/src/DefaultPieceStorage.cc b/src/DefaultPieceStorage.cc
index 08d48515..696a3613 100644
--- a/src/DefaultPieceStorage.cc
+++ b/src/DefaultPieceStorage.cc
@@ -58,13 +58,12 @@
 #include "StringFormat.h"
 #include "RarestPieceSelector.h"
 #include "array_fun.h"
+#include "PieceStatMan.h"
 
 namespace aria2 {
 
 DefaultPieceStorage::DefaultPieceStorage
-(const DownloadContextHandle& downloadContext,
- const Option* option,
- const SharedHandle<PieceSelector>& pieceSelector):
+(const DownloadContextHandle& downloadContext, const Option* option):
   downloadContext(downloadContext),
   bitfieldMan(BitfieldManFactory::getFactoryInstance()->
 	      createBitfieldMan(downloadContext->getPieceLength(),
@@ -73,13 +72,9 @@ DefaultPieceStorage::DefaultPieceStorage
   endGamePieceNum(END_GAME_PIECE_NUM),
   logger(LogFactory::getInstance()),
   option(option),
-  _pieceSelector(pieceSelector)
-{
-  if(_pieceSelector.isNull()) {
-    _pieceSelector.reset
-      (new RarestPieceSelector(downloadContext->getNumPieces(), true));
-  }
-}
+  _pieceStatMan(new PieceStatMan(downloadContext->getNumPieces(), true)),
+  _pieceSelector(new RarestPieceSelector(_pieceStatMan))
+{}
 
 DefaultPieceStorage::~DefaultPieceStorage() {
   delete bitfieldMan;
@@ -653,26 +648,26 @@ void DefaultPieceStorage::setDiskWriterFactory(const DiskWriterFactoryHandle& di
 void DefaultPieceStorage::addPieceStats(const unsigned char* bitfield,
 					size_t bitfieldLength)
 {
-  _pieceSelector->addPieceStats(bitfield, bitfieldLength);
+  _pieceStatMan->addPieceStats(bitfield, bitfieldLength);
 }
 
 void DefaultPieceStorage::subtractPieceStats(const unsigned char* bitfield,
 					     size_t bitfieldLength)
 {
-  _pieceSelector->subtractPieceStats(bitfield, bitfieldLength);
+  _pieceStatMan->subtractPieceStats(bitfield, bitfieldLength);
 }
 
 void DefaultPieceStorage::updatePieceStats(const unsigned char* newBitfield,
 					   size_t newBitfieldLength,
 					   const unsigned char* oldBitfield)
 {
-  _pieceSelector->updatePieceStats(newBitfield, newBitfieldLength,
+  _pieceStatMan->updatePieceStats(newBitfield, newBitfieldLength,
 				   oldBitfield);
 }
 
 void DefaultPieceStorage::addPieceStats(size_t index)
 {
-  _pieceSelector->addPieceStats(index);
+  _pieceStatMan->addPieceStats(index);
 }
 
 } // namespace aria2
diff --git a/src/DefaultPieceStorage.h b/src/DefaultPieceStorage.h
index 66f7eb84..b00348c9 100644
--- a/src/DefaultPieceStorage.h
+++ b/src/DefaultPieceStorage.h
@@ -45,6 +45,7 @@ class Logger;
 class Option;
 class DiskWriterFactory;
 class FileEntry;
+class PieceStatMan;
 class PieceSelector;
 
 #define END_GAME_PIECE_NUM 20
@@ -81,6 +82,8 @@ private:
   const Option* option;
   Haves haves;
 
+  SharedHandle<PieceStatMan> _pieceStatMan;
+
   SharedHandle<PieceSelector> _pieceSelector;
 
   bool getMissingPieceIndex(size_t& index,
@@ -108,9 +111,7 @@ public:
   // If it is set to false, a piece whose index is smallest has the highest
   // priority.
   DefaultPieceStorage(const SharedHandle<DownloadContext>& downloadContext,
-		      const Option* option,
-		      const SharedHandle<PieceSelector>& pieceSelector
-		      = SharedHandle<PieceSelector>());
+		      const Option* option);
 		      
   virtual ~DefaultPieceStorage();
 
@@ -223,6 +224,16 @@ public:
   void addUsedPiece(const SharedHandle<Piece>& piece);
 
   void setDiskWriterFactory(const SharedHandle<DiskWriterFactory>& diskWriterFactory);
+
+  const SharedHandle<PieceStatMan>& getPieceStatMan() const
+  {
+    return _pieceStatMan;
+  }
+
+  void setPieceSelector(const SharedHandle<PieceSelector>& pieceSelector)
+  {
+    _pieceSelector = pieceSelector;
+  }
 };
 
 typedef SharedHandle<DefaultPieceStorage> DefaultPieceStorageHandle;
diff --git a/src/LongestSequencePieceSelector.cc b/src/LongestSequencePieceSelector.cc
index e1582cca..243175e9 100644
--- a/src/LongestSequencePieceSelector.cc
+++ b/src/LongestSequencePieceSelector.cc
@@ -85,16 +85,4 @@ bool LongestSequencePieceSelector::select
   }
 }
 
-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
index 232b313d..d2284994 100644
--- a/src/LongestSequencePieceSelector.h
+++ b/src/LongestSequencePieceSelector.h
@@ -47,18 +47,6 @@ public:
   // returns 15 because { 10, 11, 12, 13, 14, 15 } is the longest sequence.
   virtual bool select
   (size_t& index, const unsigned char* bitfield, size_t nbits) 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
diff --git a/src/Makefile.am b/src/Makefile.am
index f9e1d774..9945f1a6 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -117,6 +117,7 @@ SRCS =  Socket.h\
 	PieceStorage.h\
 	DefaultPieceStorage.cc DefaultPieceStorage.h\
 	UnknownLengthPieceStorage.cc UnknownLengthPieceStorage.h\
+	PieceStatMan.cc PieceStatMan.h\
 	StatCalc.h\
 	ConsoleStatCalc.cc ConsoleStatCalc.h\
 	TransferStat.cc TransferStat.h\
diff --git a/src/Makefile.in b/src/Makefile.in
index 04ade8b4..9969bf8f 100644
--- a/src/Makefile.in
+++ b/src/Makefile.in
@@ -1,4 +1,4 @@
-# Makefile.in generated by automake 1.10.1 from Makefile.am.
+# Makefile.in generated by automake 1.10.2 from Makefile.am.
 # @configure_input@
 
 # Copyright (C) 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002,
@@ -355,8 +355,8 @@ am__libaria2c_a_SOURCES_DIST = Socket.h SocketCore.cc SocketCore.h \
 	AutoSaveCommand.cc AutoSaveCommand.h PieceStorage.h \
 	DefaultPieceStorage.cc DefaultPieceStorage.h \
 	UnknownLengthPieceStorage.cc UnknownLengthPieceStorage.h \
-	StatCalc.h ConsoleStatCalc.cc ConsoleStatCalc.h \
-	TransferStat.cc TransferStat.h Dependency.h \
+	PieceStatMan.cc PieceStatMan.h StatCalc.h ConsoleStatCalc.cc \
+	ConsoleStatCalc.h TransferStat.cc TransferStat.h Dependency.h \
 	BtProgressInfoFile.h DefaultBtProgressInfoFile.cc \
 	DefaultBtProgressInfoFile.h NullProgressInfoFile.h \
 	FileAllocationIterator.h SingleFileAllocationIterator.cc \
@@ -768,8 +768,9 @@ am__objects_23 = SocketCore.$(OBJEXT) Command.$(OBJEXT) \
 	PStringSegment.$(OBJEXT) PStringBuildVisitor.$(OBJEXT) \
 	ParameterizedStringParser.$(OBJEXT) TimeBasedCommand.$(OBJEXT) \
 	AutoSaveCommand.$(OBJEXT) DefaultPieceStorage.$(OBJEXT) \
-	UnknownLengthPieceStorage.$(OBJEXT) ConsoleStatCalc.$(OBJEXT) \
-	TransferStat.$(OBJEXT) DefaultBtProgressInfoFile.$(OBJEXT) \
+	UnknownLengthPieceStorage.$(OBJEXT) PieceStatMan.$(OBJEXT) \
+	ConsoleStatCalc.$(OBJEXT) TransferStat.$(OBJEXT) \
+	DefaultBtProgressInfoFile.$(OBJEXT) \
 	SingleFileAllocationIterator.$(OBJEXT) \
 	ContentTypeRequestGroupCriteria.$(OBJEXT) \
 	DownloadHandler.$(OBJEXT) DownloadHandlerConstants.$(OBJEXT) \
@@ -1008,6 +1009,7 @@ target_alias = @target_alias@
 target_cpu = @target_cpu@
 target_os = @target_os@
 target_vendor = @target_vendor@
+top_build_prefix = @top_build_prefix@
 top_builddir = @top_builddir@
 top_srcdir = @top_srcdir@
 aria2c_SOURCES = main.cc\
@@ -1084,8 +1086,8 @@ SRCS = Socket.h SocketCore.cc SocketCore.h BinaryStream.h Command.cc \
 	AutoSaveCommand.cc AutoSaveCommand.h PieceStorage.h \
 	DefaultPieceStorage.cc DefaultPieceStorage.h \
 	UnknownLengthPieceStorage.cc UnknownLengthPieceStorage.h \
-	StatCalc.h ConsoleStatCalc.cc ConsoleStatCalc.h \
-	TransferStat.cc TransferStat.h Dependency.h \
+	PieceStatMan.cc PieceStatMan.h StatCalc.h ConsoleStatCalc.cc \
+	ConsoleStatCalc.h TransferStat.cc TransferStat.h Dependency.h \
 	BtProgressInfoFile.h DefaultBtProgressInfoFile.cc \
 	DefaultBtProgressInfoFile.h NullProgressInfoFile.h \
 	FileAllocationIterator.h SingleFileAllocationIterator.cc \
@@ -1169,8 +1171,8 @@ $(srcdir)/Makefile.in:  $(srcdir)/Makefile.am  $(am__configure_deps)
 	@for dep in $?; do \
 	  case '$(am__configure_deps)' in \
 	    *$$dep*) \
-	      cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh \
-		&& exit 0; \
+	      ( cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh ) \
+	        && { if test -f $@; then exit 0; else break; fi; }; \
 	      exit 1;; \
 	  esac; \
 	done; \
@@ -1466,6 +1468,7 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/Piece.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/PieceHashCheckIntegrityEntry.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/PieceHashMetalinkParserState.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/PieceStatMan.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/PiecedSegment.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/PiecesMetalinkParserState.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/Platform.Po@am__quote@
@@ -1568,7 +1571,7 @@ ID: $(HEADERS) $(SOURCES) $(LISP) $(TAGS_FILES)
 	unique=`for i in $$list; do \
 	    if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \
 	  done | \
-	  $(AWK) '{ files[$$0] = 1; nonemtpy = 1; } \
+	  $(AWK) '{ files[$$0] = 1; nonempty = 1; } \
 	      END { if (nonempty) { for (i in files) print i; }; }'`; \
 	mkid -fID $$unique
 tags: TAGS
diff --git a/src/PieceSelector.h b/src/PieceSelector.h
index 0b229258..e6e70f5d 100644
--- a/src/PieceSelector.h
+++ b/src/PieceSelector.h
@@ -37,9 +37,7 @@
 
 #include "common.h"
 
-#include <deque>
-
-#include "SharedHandle.h"
+#include <cstdlib>
 
 namespace aria2 {
 
@@ -49,18 +47,6 @@ public:
 
   virtual bool select
   (size_t& index, const unsigned char* bitfield, size_t nbits) 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
diff --git a/src/PieceStatMan.cc b/src/PieceStatMan.cc
new file mode 100644
index 00000000..1afdf929
--- /dev/null
+++ b/src/PieceStatMan.cc
@@ -0,0 +1,218 @@
+/* <!-- 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 "PieceStatMan.h"
+
+#include <algorithm>
+
+#include "SimpleRandomizer.h"
+
+namespace aria2 {
+
+PieceStat::PieceStat(size_t index):_order(0), _index(index), _count(0) {}
+
+bool PieceStat::operator<(const PieceStat& pieceStat) const
+{
+  if(_count == pieceStat._count) {
+    return _order < pieceStat._order;
+  } else {
+    return _count < pieceStat._count;
+  }
+}
+
+void PieceStat::addCount()
+{
+  if(_count < SIZE_MAX) {
+    ++_count;
+  }
+}
+
+void PieceStat::subCount()
+{
+  if(_count > 0) {
+    --_count;
+  }
+}
+
+size_t PieceStat::getIndex() const
+{
+  return _index;
+}
+
+size_t PieceStat::getCount() const
+{
+  return _count;
+}
+
+void PieceStat::setOrder(size_t order)
+{
+  _order = order;
+}
+
+size_t PieceStat::getOrder() const
+{
+  return _order;
+}
+
+class GenPieceStat {
+private:
+  size_t _index;
+public:
+  GenPieceStat():_index(0) {}
+
+  SharedHandle<PieceStat> operator()()
+  {
+    return SharedHandle<PieceStat>(new PieceStat(_index++));
+  }
+};
+
+PieceStatMan::PieceStatMan(size_t pieceNum, bool randomShuffle):
+  _pieceStats(pieceNum),
+  _sortedPieceStatIndexes(pieceNum)
+{
+  std::generate(_pieceStats.begin(), _pieceStats.end(), GenPieceStat());
+  std::vector<SharedHandle<PieceStat> > sortedPieceStats(_pieceStats);
+  // we need some randomness in ordering.
+  if(randomShuffle) {
+    std::random_shuffle(sortedPieceStats.begin(), sortedPieceStats.end(),
+			*(SimpleRandomizer::getInstance().get()));
+  }
+  {
+    size_t order = 0;
+    for(std::vector<SharedHandle<PieceStat> >::iterator i =
+	  sortedPieceStats.begin(); i != sortedPieceStats.end(); ++i) {
+      _sortedPieceStatIndexes[order] = (*i)->getIndex();
+      (*i)->setOrder(order++);
+    }
+  }  
+}
+
+class PieceStatRarer {
+private:
+  const std::vector<SharedHandle<PieceStat> >& _pieceStats;
+public:
+  PieceStatRarer(const std::vector<SharedHandle<PieceStat> >& ps):
+    _pieceStats(ps) {}
+
+  bool operator()(size_t lhs, size_t rhs) const
+  {
+    return _pieceStats[lhs] < _pieceStats[rhs];
+  }
+};
+
+void PieceStatMan::addPieceStats(const unsigned char* bitfield,
+					size_t bitfieldLength)
+{
+  size_t index = 0;
+  for(size_t bi = 0; bi < bitfieldLength; ++bi) {
+    
+    for(size_t i = 0; i < 8; ++i, ++index) {
+      unsigned char mask = 128 >> i;
+      if(bitfield[bi]&mask) {
+	_pieceStats[index]->addCount();
+      }
+    }
+
+  }
+  std::sort(_sortedPieceStatIndexes.begin(), _sortedPieceStatIndexes.end(),
+	    PieceStatRarer(_pieceStats));
+}
+
+void PieceStatMan::subtractPieceStats(const unsigned char* bitfield,
+					     size_t bitfieldLength)
+{
+  size_t index = 0;
+  for(size_t bi = 0; bi < bitfieldLength; ++bi) {
+    
+    for(size_t i = 0; i < 8; ++i, ++index) {
+      unsigned char mask = 128 >> i;
+      if(bitfield[bi]&mask) {
+	_pieceStats[index]->subCount();
+      }
+    }
+
+  }
+  std::sort(_sortedPieceStatIndexes.begin(), _sortedPieceStatIndexes.end(),
+	    PieceStatRarer(_pieceStats));
+}
+
+void PieceStatMan::updatePieceStats(const unsigned char* newBitfield,
+					   size_t newBitfieldLength,
+					   const unsigned char* oldBitfield)
+{
+  size_t index = 0;
+  for(size_t bi = 0; bi < newBitfieldLength; ++bi) {
+    
+    for(size_t i = 0; i < 8; ++i, ++index) {
+      unsigned char mask = 128 >> i;
+      if((newBitfield[bi]&mask) && !(oldBitfield[bi]&mask)) {
+	_pieceStats[index]->addCount();
+      } else if(!(newBitfield[bi]&mask) && (oldBitfield[bi]&mask)) {
+	_pieceStats[index]->subCount();
+      }
+    }
+
+  }
+  std::sort(_sortedPieceStatIndexes.begin(), _sortedPieceStatIndexes.end(),
+	    PieceStatRarer(_pieceStats));
+}
+
+void PieceStatMan::addPieceStats(size_t index)
+{
+  std::vector<size_t>::iterator cur =
+    std::lower_bound(_sortedPieceStatIndexes.begin(),
+		     _sortedPieceStatIndexes.end(),
+		     index, PieceStatRarer(_pieceStats));
+
+  _pieceStats[index]->addCount();
+
+  std::vector<size_t>::iterator to =
+    std::upper_bound(cur+1, _sortedPieceStatIndexes.end(),
+		     index, PieceStatRarer(_pieceStats));
+  
+  std::rotate(cur, cur+1, to);
+}
+
+const std::vector<size_t>& PieceStatMan::getRarerPieceIndexes() const
+{
+  return _sortedPieceStatIndexes;
+}
+
+const std::vector<SharedHandle<PieceStat> >&
+PieceStatMan::getPieceStats() const
+{
+  return _pieceStats;
+}
+
+} // namespace aria2
diff --git a/src/PieceStatMan.h b/src/PieceStatMan.h
new file mode 100644
index 00000000..45c26ffe
--- /dev/null
+++ b/src/PieceStatMan.h
@@ -0,0 +1,93 @@
+/* <!-- 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_STAT_MAN_H_
+#define _D_PIECE_STAT_MAN_H_
+
+#include "common.h"
+
+#include <vector>
+
+#include "SharedHandle.h"
+
+namespace aria2 {
+
+class PieceStat {
+private:
+  size_t _order;
+  size_t _index;
+  size_t _count;
+public:
+  PieceStat(size_t index);
+
+  bool operator<(const PieceStat& pieceStat) const;
+
+  void addCount();
+  void subCount();
+
+  size_t getOrder() const;
+  void setOrder(size_t order);
+  size_t getIndex() const;
+  size_t getCount() const;
+};
+
+class PieceStatMan {
+private:
+  std::vector<SharedHandle<PieceStat> > _pieceStats;
+
+  std::vector<size_t> _sortedPieceStatIndexes;
+public:
+  PieceStatMan(size_t pieceNum, bool randomShuffle);
+
+  void addPieceStats(size_t index);
+
+  void addPieceStats(const unsigned char* bitfield,
+		     size_t bitfieldLength);
+  
+  void subtractPieceStats(const unsigned char* bitfield,
+			  size_t bitfieldLength);
+
+  void updatePieceStats(const unsigned char* newBitfield,
+			size_t newBitfieldLength,
+			const unsigned char* oldBitfield);
+
+  // Returns piece index in rarest first order.
+  const std::vector<size_t>& getRarerPieceIndexes() const;
+
+  const std::vector<SharedHandle<PieceStat> >& getPieceStats() const;
+};
+
+} // namespace aria2
+
+#endif // _D_PIECE_STAT_MAN_H_
diff --git a/src/RarestPieceSelector.cc b/src/RarestPieceSelector.cc
index 0b7aabb5..2672d6a3 100644
--- a/src/RarestPieceSelector.cc
+++ b/src/RarestPieceSelector.cc
@@ -37,87 +37,12 @@
 #include <cassert>
 #include <algorithm>
 
-#include "SimpleRandomizer.h"
+#include "PieceStatMan.h"
 
 namespace aria2 {
 
-PieceStat::PieceStat(size_t index):_order(0), _index(index), _count(0) {}
-
-bool PieceStat::operator<(const PieceStat& pieceStat) const
-{
-  if(_count == pieceStat._count) {
-    return _order < pieceStat._order;
-  } else {
-    return _count < pieceStat._count;
-  }
-}
-
-void PieceStat::addCount()
-{
-  if(_count < SIZE_MAX) {
-    ++_count;
-  }
-}
-
-void PieceStat::subCount()
-{
-  if(_count > 0) {
-    --_count;
-  }
-}
-
-size_t PieceStat::getIndex() const
-{
-  return _index;
-}
-
-size_t PieceStat::getCount() const
-{
-  return _count;
-}
-
-void PieceStat::setOrder(size_t order)
-{
-  _order = order;
-}
-
-size_t PieceStat::getOrder() const
-{
-  return _order;
-}
-
-class GenPieceStat {
-private:
-  size_t _index;
-public:
-  GenPieceStat():_index(0) {}
-
-  SharedHandle<PieceStat> operator()()
-  {
-    return SharedHandle<PieceStat>(new PieceStat(_index++));
-  }
-};
-
-RarestPieceSelector::RarestPieceSelector(size_t pieceNum, bool randomShuffle):
-  _pieceStats(pieceNum),
-  _sortedPieceStatIndexes(pieceNum)
-{
-  std::generate(_pieceStats.begin(), _pieceStats.end(), GenPieceStat());
-  std::vector<SharedHandle<PieceStat> > sortedPieceStats(_pieceStats);
-  // we need some randomness in ordering.
-  if(randomShuffle) {
-    std::random_shuffle(sortedPieceStats.begin(), sortedPieceStats.end(),
-			*(SimpleRandomizer::getInstance().get()));
-  }
-  {
-    size_t order = 0;
-    for(std::vector<SharedHandle<PieceStat> >::iterator i =
-	  sortedPieceStats.begin(); i != sortedPieceStats.end(); ++i) {
-      _sortedPieceStatIndexes[order] = (*i)->getIndex();
-      (*i)->setOrder(order++);
-    }
-  }  
-}
+RarestPieceSelector::RarestPieceSelector
+(const SharedHandle<PieceStatMan>& pieceStatMan):_pieceStatMan(pieceStatMan) {}
 
 class FindRarestPiece
 {
@@ -139,10 +64,12 @@ public:
 bool RarestPieceSelector::select
 (size_t& index, const unsigned char* bitfield, size_t nbits) const
 {
+  const std::vector<size_t>& pieceIndexes =
+    _pieceStatMan->getRarerPieceIndexes();
   std::vector<size_t>::const_iterator i =
-    std::find_if(_sortedPieceStatIndexes.begin(), _sortedPieceStatIndexes.end(),
+    std::find_if(pieceIndexes.begin(), pieceIndexes.end(),
 		 FindRarestPiece(bitfield, nbits));
-  if(i == _sortedPieceStatIndexes.end()) {
+  if(i == pieceIndexes.end()) {
     return false;
   } else {
     index = *i;
@@ -150,102 +77,4 @@ bool RarestPieceSelector::select
   }
 }
 
-class PieceStatRarer {
-private:
-  const std::vector<SharedHandle<PieceStat> >& _pieceStats;
-public:
-  PieceStatRarer(const std::vector<SharedHandle<PieceStat> >& ps):
-    _pieceStats(ps) {}
-
-  bool operator()(size_t lhs, size_t rhs) const
-  {
-    return _pieceStats[lhs] < _pieceStats[rhs];
-  }
-};
-
-void RarestPieceSelector::addPieceStats(const unsigned char* bitfield,
-					size_t bitfieldLength)
-{
-  size_t index = 0;
-  for(size_t bi = 0; bi < bitfieldLength; ++bi) {
-    
-    for(size_t i = 0; i < 8; ++i, ++index) {
-      unsigned char mask = 128 >> i;
-      if(bitfield[bi]&mask) {
-	_pieceStats[index]->addCount();
-      }
-    }
-
-  }
-  std::sort(_sortedPieceStatIndexes.begin(), _sortedPieceStatIndexes.end(),
-	    PieceStatRarer(_pieceStats));
-}
-
-void RarestPieceSelector::subtractPieceStats(const unsigned char* bitfield,
-					     size_t bitfieldLength)
-{
-  size_t index = 0;
-  for(size_t bi = 0; bi < bitfieldLength; ++bi) {
-    
-    for(size_t i = 0; i < 8; ++i, ++index) {
-      unsigned char mask = 128 >> i;
-      if(bitfield[bi]&mask) {
-	_pieceStats[index]->subCount();
-      }
-    }
-
-  }
-  std::sort(_sortedPieceStatIndexes.begin(), _sortedPieceStatIndexes.end(),
-	    PieceStatRarer(_pieceStats));
-}
-
-void RarestPieceSelector::updatePieceStats(const unsigned char* newBitfield,
-					   size_t newBitfieldLength,
-					   const unsigned char* oldBitfield)
-{
-  size_t index = 0;
-  for(size_t bi = 0; bi < newBitfieldLength; ++bi) {
-    
-    for(size_t i = 0; i < 8; ++i, ++index) {
-      unsigned char mask = 128 >> i;
-      if((newBitfield[bi]&mask) && !(oldBitfield[bi]&mask)) {
-	_pieceStats[index]->addCount();
-      } else if(!(newBitfield[bi]&mask) && (oldBitfield[bi]&mask)) {
-	_pieceStats[index]->subCount();
-      }
-    }
-
-  }
-  std::sort(_sortedPieceStatIndexes.begin(), _sortedPieceStatIndexes.end(),
-	    PieceStatRarer(_pieceStats));
-}
-
-void RarestPieceSelector::addPieceStats(size_t index)
-{
-  std::vector<size_t>::iterator cur =
-    std::lower_bound(_sortedPieceStatIndexes.begin(),
-		     _sortedPieceStatIndexes.end(),
-		     index, PieceStatRarer(_pieceStats));
-
-  _pieceStats[index]->addCount();
-
-  std::vector<size_t>::iterator to =
-    std::upper_bound(cur+1, _sortedPieceStatIndexes.end(),
-		     index, PieceStatRarer(_pieceStats));
-  
-  std::rotate(cur, cur+1, to);
-}
-
-const std::vector<size_t>&
-RarestPieceSelector::getSortedPieceStatIndexes() const
-{
-  return _sortedPieceStatIndexes;
-}
-
-const std::vector<SharedHandle<PieceStat> >&
-RarestPieceSelector::getPieceStats() const
-{
-  return _pieceStats;
-}
-
 } // namespace aria2
diff --git a/src/RarestPieceSelector.h b/src/RarestPieceSelector.h
index 431ed406..132d22f8 100644
--- a/src/RarestPieceSelector.h
+++ b/src/RarestPieceSelector.h
@@ -36,56 +36,20 @@
 #define _D_RAREST_PIECE_SELECTOR_H_
 
 #include "PieceSelector.h"
-
-#include <vector>
+#include "SharedHandle.h"
 
 namespace aria2 {
 
-class PieceStat {
-private:
-  size_t _order;
-  size_t _index;
-  size_t _count;
-public:
-  PieceStat(size_t index);
-
-  bool operator<(const PieceStat& pieceStat) const;
-
-  void addCount();
-  void subCount();
-
-  size_t getOrder() const;
-  void setOrder(size_t order);
-  size_t getIndex() const;
-  size_t getCount() const;
-};
+class PieceStatMan;
 
 class RarestPieceSelector:public PieceSelector {
 private:
-  std::vector<SharedHandle<PieceStat> > _pieceStats;
-
-  std::vector<size_t> _sortedPieceStatIndexes;
+  SharedHandle<PieceStatMan> _pieceStatMan;
 public:
-  RarestPieceSelector(size_t pieceNum, bool randomShuffle);
+  RarestPieceSelector(const SharedHandle<PieceStatMan>& pieceStatMan);
 
   virtual bool select
   (size_t& index, const unsigned char* bitfield, size_t nbits) 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);
-
-  const std::vector<size_t>& getSortedPieceStatIndexes() const;
-
-  const std::vector<SharedHandle<PieceStat> >& getPieceStats() const;
 };
 
 } // namespace aria2
diff --git a/src/RequestGroup.cc b/src/RequestGroup.cc
index 697009d7..b2bb715d 100644
--- a/src/RequestGroup.cc
+++ b/src/RequestGroup.cc
@@ -396,17 +396,17 @@ void RequestGroup::initPieceStorage()
 {
   if(_downloadContext->knowsTotalLength()) {
 #ifdef ENABLE_BITTORRENT
-    SharedHandle<DefaultPieceStorage> ps;
-    SharedHandle<PieceSelector> selector;
+    SharedHandle<DefaultPieceStorage> ps
+      (new DefaultPieceStorage(_downloadContext, _option));
     // 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->setPieceSelector
+	(SharedHandle<PieceSelector>(new LongestSequencePieceSelector()));
     }
-    ps.reset(new DefaultPieceStorage(_downloadContext, _option, selector));
 #else // !ENABLE_BITTORRENT
     SharedHandle<DefaultPieceStorage> ps
       (new DefaultPieceStorage(_downloadContext, _option));