on-disk-point-set-list.h

Go to the documentation of this file.

// Copyright 2007, Massachusetts Institute of Technology.
// The use of this code is permitted for research only. There is
// absolutely no warranty for this software.
//
// Author: John Lee (jjl@mit.edu)
//
// OnDiskPointSets are read-only. They are meant to be used for large
// point set lists which do not fit in memory.
// OnDiskPointSet operates with two caches: an "area" cache and an LRU cache.
// The area cache is a small subsequence of the entire point set list.
// When we want to access something in the point set list, we do the following:
//   1. Check the area cache for it. If it's there, return it.
//   2. Check the LRU cache for it.
//        2a. If it's there, return it, and also move it to the front of
//            the LRU cache. The area cache is unchanged.
//        2b. If it's not there, then add it to the LRU cache, evicting the
//            least-recently-used item if needed. ALSO, we reset the area
//            cache, such that the first element of the area cache is the
//            requested item.
//
// WARNING: the [] operator returns a const ref, which may become invalid
// the next time you invoke the [] operator. BE CAREFUL!
//

#ifndef POINT_SET_ON_DISK_POINT_SET_LIST_H
#define POINT_SET_ON_DISK_POINT_SET_LIST_H

#include <assert.h>
#include <vector>
#include <string>
#include <iostream>
#include <fstream>
#include <list>
#include "point_set/point-set-list.h"
#include "point_set/point-set.h"
#include "point_set/point-ref.h"
#include "point_set/feature.h"

using namespace std;

namespace libpmk {

class OnDiskPointSetList : public PointSetList {
 public:

   OnDiskPointSetList(string filename);


   OnDiskPointSetList(string filename, int lru_cache_size,
                      int area_cache_size);
   virtual ~OnDiskPointSetList();

   virtual int GetNumPointSets() const;
   virtual int GetNumPoints() const;
   virtual int GetFeatureDim() const;
   virtual vector<int> GetSetCardinalities() const;


   virtual const PointSet& operator[](int index) const;

   static const int DEFAULT_LRU_CACHE_SIZE;

   static const int DEFAULT_AREA_CACHE_SIZE;

 private:
   // Returns true iff the <index>th point set in the whole list is
   // in the area cache.
   bool IsInAreaCache(int index) const;

   // Seeks to the <index>th point set list on the disk and fills up
   // the area cache with
   //   <index>, <index> + 1, ..., <index> + cache_size_ - 1.
   //
   // If the end is reached, then cache_ will just end there, so
   // the value of cache_.size() may not always be equal to
   // this.cache_size_ .
   // The resulting location of the file pointer will be the very next
   // point set (i.e., the one that would follow the point set at the
   // end of the current cache). It will be EOF if we've hit the end.
   // This function sets cache_offset_ appropriately.
   void SeekAndFillAreaCache(int index) const;
   

   // Seeks to the start, then scans through and computes
   // num_point_sets_, num_points_, and feature_dim_.  It also
   // populates the vectors <pointers_> and <num_features_> It then
   // returns the file pointer to where it was originally.
   void GetListInfo() const;
   
   // A vector of size <num_point_sets_>. The value of pointers_[ii]
   // gives you the position in the stream where you can find the
   // iith point set.
   mutable vector<streampos> pointers_;

   // A vector of size <num_point_sets_> which tells you how many features
   // there are in each point set.
   mutable vector<int> num_features_;
   
   // Useful metadata
   mutable int num_point_sets_;
   mutable int num_points_;
   mutable int feature_dim_;
   mutable ifstream input_stream_;

   // cache_[0] is the <cache_offset_>th point set in the whole list.
   int max_lru_size_;
   int max_area_size_;

   mutable int area_cache_offset_;
   
   // The LRU cache is such that the most-recently-used is at the front
   // and least-recently-used (to evict) is at the back. We need to store
   // pairs. The first element in each pair is the index of that point in
   // the entire point set list, and the second element in the pair is
   // the point set itself.
   mutable list<pair<int, PointSet> > lru_cache_;
   mutable vector<PointSet> area_cache_;

   // Disallow evil constructors (don't allow users to make copies of 
   // OnDiskPointSetLists)
   OnDiskPointSetList& operator=(const OnDiskPointSetList& foo);
   OnDiskPointSetList(const OnDiskPointSetList& foo);
   
};
}  // namespace libpmk
#endif  // POINT_SET_POINT_SET_LIST_H

---