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 <vector>
#include <string>
#include <iostream>
#include <fstream>
#include <list>
#include "point_set/point-set-list.h"
#include "point_set/point-set.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 point_set_size() const;
  virtual int point_size() const;
  virtual int point_dim() const;
  virtual bool GetSetCardinalities(vector<int>* destination) const;


  virtual const PointSet& point_set(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 point_dim_.  It also
  // populates the vectors <pointers_> and <num_points_> 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 points
  // there are in each point set.
  mutable vector<int> num_points_per_set_;

  // Useful metadata
  mutable int num_point_sets_;
  mutable int num_points_;
  mutable int point_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_ON_DISK_POINT_SET_LIST_H

---