text: /**
   *    Copyright (C) 2013 10gen Inc.
   *
   *    This program is free software: you can redistribute it and/or  modify
   *    it under the terms of the GNU Affero General Public License, version 3,
   *    as published by the Free Software Foundation.
   *
   *    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 Affero General Public License for more details.
   *
   *    You should have received a copy of the GNU Affero General Public License
   *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
   *
   *    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 program with the OpenSSL library. You
   *    must comply with the GNU Affero General Public License in all respects for
   *    all of the code used other than as permitted herein. 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 in the license file.
   */
  
  #pragma once
  
  #include "mongo/db/jsobj.h"
  #include "mongo/db/hasher.h"
  #include "mongo/db/query/index_bounds_builder.h"
  
  namespace mongo {
  
      /**
       * Functions that compute expression index mappings.
       *
       * TODO: I think we could structure this more generally with respect to planning.
       */
      class ExpressionMapping {
      public:
          static BSONObj hash(const BSONElement& value) {
              BSONObjBuilder bob;
              bob.append("", BSONElementHasher::hash64(value, BSONElementHasher::DEFAULT_HASH_SEED));
              return bob.obj();
          }
  
          static void cover2dsphere(const S2Region& region, OrderedIntervalList* oilOut) {
              // XXX: should grab coarsest level from the index since the user can possibly change it.
              int coarsestIndexedLevel = 
                          S2::kAvgEdge.GetClosestLevel(100 * 1000.0 / kRadiusOfEarthInMeters);
  
  
              // The min level of our covering is the level whose cells are the closest match to the
              // *area* of the region (or the max indexed level, whichever is smaller) The max level
              // is 4 sizes larger.
              double edgeLen = sqrt(region.GetRectBound().Area());
              S2RegionCoverer coverer;
              coverer.set_min_level(min(coarsestIndexedLevel,
                                        2 + S2::kAvgEdge.GetClosestLevel(edgeLen)));
              coverer.set_max_level(4 + coverer.min_level());
  
              vector<S2CellId> cover;
              coverer.GetCovering(region, &cover);
  
              // Look at the cells we cover and all cells that are within our covering and finer.
              // Anything with our cover as a strict prefix is contained within the cover and should
              // be intersection tested.
              bool considerCoarser = false;
              set<string> intervalSet;
              for (size_t i = 0; i < cover.size(); ++i) {
                  intervalSet.insert(cover[i].toString());
                  // If any of our covers could be covered by something in the index, we have
                  // to look at things coarser.
                  if (cover[i].level() > coarsestIndexedLevel) {
                      considerCoarser = true;
                  }
              }
  
              set<string> exactSet;
              if (considerCoarser) {
                  // Look at the cells that cover us.  We want to look at every cell that contains the
                  // covering we would index on if we were to insert the query geometry.  We generate
                  // the would-index-with-this-covering and find all the cells strictly containing the
                  // cells in that set, until we hit the coarsest indexed cell.  We use equality, not
                  // a prefix match.  Why not prefix?  Because we've already looked at everything
                  // finer or as fine as our initial covering.
                  //
                  // Say we have a fine point with cell id 212121, we go up one, get 21212, we don't
                  // want to look at cells 21212[not-1] because we know they're not going to intersect
                  // with 212121, but entries inserted with cell value 21212 (no trailing digits) may.
                  // And we've already looked at points with the cell id 211111 from the regex search
                  // created above, so we only want things where the value of the last digit is not
                  // stored (and therefore could be 1).
                  for (size_t i = 0; i < cover.size(); ++i) {
                      for (S2CellId id = cover[i].parent(); id.level() >= coarsestIndexedLevel;
                              id = id.parent()) {
                          exactSet.insert(id.toString());
                      }
                  }
              }
  
              // We turned the cell IDs into strings which define point intervals or prefixes of
              // strings we want to look for.
              set<string>::iterator exactIt = exactSet.begin();
              set<string>::iterator intervalIt = intervalSet.begin();
              while (exactSet.end() != exactIt && intervalSet.end() != intervalIt) {
                  const string& exact = *exactIt;
                  const string& ival = *intervalIt;
                  if (exact < ival) {
                      // add exact
                      oilOut->intervals.push_back(IndexBoundsBuilder::makePointInterval(exact));
                      exactIt++;
                  }
                  else {
                      string end = ival;
                      end[end.size() - 1]++;
                      oilOut->intervals.push_back(
                          IndexBoundsBuilder::makeRangeInterval(ival, end, true, false));
                      intervalIt++;
                  }
              }
  
              if (exactSet.end() != exactIt) {
                  verify(intervalSet.end() == intervalIt);
                  do {
                      oilOut->intervals.push_back(IndexBoundsBuilder::makePointInterval(*exactIt));
                      exactIt++;
                  } while (exactSet.end() != exactIt);
              }
              else if (intervalSet.end() != intervalIt) {
                  verify(exactSet.end() == exactIt);
                  do {
                      const string& ival = *intervalIt;
                      string end = ival;
                      end[end.size() - 1]++;
                      oilOut->intervals.push_back(
                          IndexBoundsBuilder::makeRangeInterval(ival, end, true, false));
                      intervalIt++;
                  } while (intervalSet.end() != intervalIt);
              }
  
              // Make sure that our intervals don't overlap each other and are ordered correctly.
              // This perhaps should only be done in debug mode.
              if (!oilOut->isValidFor(1)) {
                  cout << "check your assumptions! OIL = " << oilOut->toString() << endl;
                  verify(0);
              }
          }
      };
  
  }  // namespace mongo
  