text:
using namespace swift;

STATISTIC(NumOptzIterations, "Number of optimization iterations");

llvm::cl::opt<bool> SILPrintAll(
    "sil-print-all", llvm::cl::init(false),
    llvm::cl::desc("Print SIL after each pass"));

llvm::cl::opt<bool> SILPrintPassName(
    "sil-print-pass-name", llvm::cl::init(false),
    llvm::cl::desc("Print the name of each SIL pass before it runs"));

llvm::cl::opt<bool> SILPrintPassTime(
    "sil-print-pass-time", llvm::cl::init(false),
    llvm::cl::desc("Print the execution time of each SIL pass"));

llvm::cl::opt<unsigned> SILNumOptPassesToRun(
    "sil-opt-pass-count", llvm::cl::init(UINT_MAX),
    llvm::cl::desc("Stop optimizing after <N> optimization passes"));

llvm::cl::opt<std::string> SILBreakOnFun(
    "sil-break-on-function", llvm::cl::init(""),
    llvm::cl::desc(
        "Break before running each function pass on a particular function"));

llvm::cl::opt<std::string> SILBreakOnPass(
    "sil-break-on-pass", llvm::cl::init(""),
    llvm::cl::desc("Break before running a particular function pass"));

llvm::cl::opt<std::string>
    SILPrintOnlyFun("sil-print-only-function", llvm::cl::init(""),
                    llvm::cl::desc("Only print out the sil for this function"));

llvm::cl::opt<std::string>
    SILPrintOnlyFuns("sil-print-only-functions", llvm::cl::init(""),
                     llvm::cl::desc("Only print out the sil for the functions "
                                    "whose name contains this substring"));

llvm::cl::list<std::string>
    SILPrintBefore("sil-print-before",
                   llvm::cl::desc("Print out the sil before passes which "
                                  "contain a string from this list."));

llvm::cl::list<std::string>
    SILPrintAfter("sil-print-after",
                  llvm::cl::desc("Print out the sil after passes which contain "
                                 "a string from this list."));

llvm::cl::list<std::string>
    SILPrintAround("sil-print-around",
                   llvm::cl::desc("Print out the sil before and after passes "
                                  "which contain a string from this list"));

llvm::cl::list<std::string>
    SILDisablePass("sil-disable-pass",
                     llvm::cl::desc("Disable passes "
                                    "which contain a string from this list"));

llvm::cl::opt<bool> SILVerifyWithoutInvalidation(
    "sil-verify-without-invalidation", llvm::cl::init(false),
    llvm::cl::desc("Verify after passes even if the pass has not invalidated"));

llvm::cl::opt<bool> SILDisableSkippingPasses(
    "sil-disable-skipping-passes", llvm::cl::init(false),
    llvm::cl::desc("Do not skip passes even if nothing was changed"));

static llvm::ManagedStatic<std::vector<unsigned>> DebugPassNumbers;

namespace {

struct DebugOnlyPassNumberOpt {
  void operator=(const std::string &Val) const {
    if (Val.empty())
      return;
    SmallVector<StringRef, 8> dbgPassNumbers;
    StringRef(Val).split(dbgPassNumbers, ',', -1, false);
    for (auto dbgPassNumber : dbgPassNumbers) {
      int PassNumber;
      if (dbgPassNumber.getAsInteger(10, PassNumber) || PassNumber < 0)
        llvm_unreachable("The pass number should be an integer number >= 0");
      DebugPassNumbers->push_back(static_cast<unsigned>(PassNumber));
    }
  }
};

} // end anonymous namespace

static DebugOnlyPassNumberOpt DebugOnlyPassNumberOptLoc;

static llvm::cl::opt<DebugOnlyPassNumberOpt, true,
                     llvm::cl::parser<std::string>>
    DebugOnly("debug-only-pass-number",
              llvm::cl::desc("Enable a specific type of debug output (comma "
                             "separated list pass numbers)"),
              llvm::cl::Hidden, llvm::cl::ZeroOrMore,
              llvm::cl::value_desc("pass number"),
              llvm::cl::location(DebugOnlyPassNumberOptLoc),
              llvm::cl::ValueRequired);

static bool doPrintBefore(SILTransform *T, SILFunction *F) {
  if (!SILPrintOnlyFun.empty() && F && F->getName() != SILPrintOnlyFun)
    return false;

  if (!SILPrintOnlyFuns.empty() && F &&
      F->getName().find(SILPrintOnlyFuns, 0) == StringRef::npos)
    return false;

  auto MatchFun = [&](const std::string &Str) -> bool {
    return T->getName().find(Str) != StringRef::npos;
  };

  if (SILPrintBefore.end() !=
      std::find_if(SILPrintBefore.begin(), SILPrintBefore.end(), MatchFun))
    return true;

  if (SILPrintAround.end() !=
      std::find_if(SILPrintAround.begin(), SILPrintAround.end(), MatchFun))
    return true;

  return false;
}

static bool doPrintAfter(SILTransform *T, SILFunction *F, bool Default) {
  if (!SILPrintOnlyFun.empty() && F && F->getName() != SILPrintOnlyFun)
    return false;

  if (!SILPrintOnlyFuns.empty() && F &&
      F->getName().find(SILPrintOnlyFuns, 0) == StringRef::npos)
    return false;

  auto MatchFun = [&](const std::string &Str) -> bool {
    return T->getName().find(Str) != StringRef::npos;
  };

  if (SILPrintAfter.end() !=
      std::find_if(SILPrintAfter.begin(), SILPrintAfter.end(), MatchFun))
    return true;

  if (SILPrintAround.end() !=
      std::find_if(SILPrintAround.begin(), SILPrintAround.end(), MatchFun))
    return true;

  return Default;
}

static bool isDisabled(SILTransform *T) {
  for (const std::string &NamePattern : SILDisablePass) {
    if (T->getName().find(NamePattern) != StringRef::npos)
      return true;
  }
  return false;
}

static void printModule(SILModule *Mod, bool EmitVerboseSIL) {
  if (SILPrintOnlyFun.empty() && SILPrintOnlyFuns.empty()) {
    Mod->dump();
    return;
  }
  for (auto &F : *Mod) {
    if (!SILPrintOnlyFun.empty() && F.getName().str() == SILPrintOnlyFun)
      F.dump(EmitVerboseSIL);

    if (!SILPrintOnlyFuns.empty() &&
        F.getName().find(SILPrintOnlyFuns, 0) != StringRef::npos)
      F.dump(EmitVerboseSIL);
  }
}

class DebugPrintEnabler {
#ifndef NDEBUG
  bool OldDebugFlag;
#endif
public:
  DebugPrintEnabler(unsigned PassNumber) {
#ifndef NDEBUG
    OldDebugFlag = llvm::DebugFlag;
    if (llvm::DebugFlag)
      return;
    if (DebugPassNumbers->empty())
      return;
    // Enable debug printing if the pass number matches
    // one of the pass numbers provided as a command line option.
    for (auto DebugPassNumber : *DebugPassNumbers) {
      if (DebugPassNumber == PassNumber) {
        llvm::DebugFlag = true;
        return;
      }
    }
#endif
  }

  ~DebugPrintEnabler() {
#ifndef NDEBUG
    llvm::DebugFlag = OldDebugFlag;
#endif
  }
};

SILPassManager::SILPassManager(SILModule *M, llvm::StringRef Stage) :
  Mod(M), StageName(Stage) {

#define ANALYSIS(NAME) \
  Analysis.push_back(create##NAME##Analysis(Mod));
#include "swift/SILOptimizer/Analysis/Analysis.def"

  for (SILAnalysis *A : Analysis) {
    A->initialize(this);
    M->registerDeleteNotificationHandler(A);
  }
}

SILPassManager::SILPassManager(SILModule *M, irgen::IRGenModule *IRMod,
                               llvm::StringRef Stage)
    : SILPassManager(M, Stage) {
  this->IRMod = IRMod;
}

bool SILPassManager::continueTransforming() {
  return Mod->getStage() == SILStage::Raw ||
         NumPassesRun < SILNumOptPassesToRun;
}

bool SILPassManager::analysesUnlocked() {
  for (auto *A : Analysis)
    if (A->isLocked())
      return false;

  return true;
}

// Test the function and pass names we're given against the debug
// options that force us to break prior to a given pass and/or on a
// given function.
static bool breakBeforeRunning(StringRef fnName, StringRef passName) {
  if (SILBreakOnFun.empty() && SILBreakOnPass.empty())
    return false;

  if (SILBreakOnFun.empty() && passName == SILBreakOnPass)
    return true;

  if (SILBreakOnPass.empty() && fnName == SILBreakOnFun)
    return true;

  return fnName == SILBreakOnFun && passName == SILBreakOnPass;
}

void SILPassManager::runPassOnFunction(SILFunctionTransform *SFT,
                                       SILFunction *F) {

  assert(analysesUnlocked() && "Expected all analyses to be unlocked!");

  PrettyStackTraceSILFunctionTransform X(SFT, NumPassesRun);
  DebugPrintEnabler DebugPrint(NumPassesRun);

  SFT->injectPassManager(this);
  SFT->injectFunction(F);

  // If nothing changed since the last run of this pass, we can skip this
  // pass.
  CompletedPasses &completedPasses = CompletedPassesMap[F];
  if (completedPasses.test((size_t)SFT->getPassKind()) &&
      !SILDisableSkippingPasses) {
    if (SILPrintPassName)
      llvm::dbgs() << "  (Skip) Stage: " << StageName
                   << " Pass: " << SFT->getName()
                   << ", Function: " << F->getName() << "\n";
    return;
  }

  if (isDisabled(SFT)) {
    if (SILPrintPassName)
      llvm::dbgs() << "  (Disabled) Stage: " << StageName
                   << " Pass: " << SFT->getName()
                   << ", Function: " << F->getName() << "\n";
    return;
  }

  CurrentPassHasInvalidated = false;

  if (SILPrintPassName)
    llvm::dbgs() << "  #" << NumPassesRun << " Stage: " << StageName
                 << " Pass: " << SFT->getName()
                 << ", Function: " << F->getName() << "\n";

  if (doPrintBefore(SFT, F)) {
    llvm::dbgs() << "*** SIL function before " << StageName << " "
                 << SFT->getName() << " (" << NumOptimizationIterations
                 << ") ***\n";
    F->dump(getOptions().EmitVerboseSIL);
  }

  llvm::sys::TimePoint<> StartTime = std::chrono::system_clock::now();
  Mod->registerDeleteNotificationHandler(SFT);
  if (breakBeforeRunning(F->getName(), SFT->getName()))
    LLVM_BUILTIN_DEBUGTRAP;
  SFT->run();
  assert(analysesUnlocked() && "Expected all analyses to be unlocked!");
  Mod->removeDeleteNotificationHandler(SFT);

  if (SILPrintPassTime) {
    auto Delta = (std::chrono::system_clock::now() - StartTime).count();
    llvm::dbgs() << Delta << " (" << SFT->getName() << "," << F->getName()
                 << ")\n";
  }

  // If this pass invalidated anything, print and verify.
  if (doPrintAfter(SFT, F, CurrentPassHasInvalidated && SILPrintAll)) {
    llvm::dbgs() << "*** SIL function after " << StageName << " "
                 << SFT->getName() << " (" << NumOptimizationIterations
                 << ") ***\n";
    F->dump(getOptions().EmitVerboseSIL);
  }

  // Remember if this pass didn't change anything.
  if (!CurrentPassHasInvalidated)
    completedPasses.set((size_t)SFT->getPassKind());

  if (getOptions().VerifyAll &&
      (CurrentPassHasInvalidated || SILVerifyWithoutInvalidation)) {
    F->verify();
    verifyAnalyses(F);
  }

  ++NumPassesRun;
}

void SILPassManager::
runFunctionPasses(ArrayRef<SILFunctionTransform *> FuncTransforms) {
  if (FuncTransforms.empty())
    return;

  BasicCalleeAnalysis *BCA = getAnalysis<BasicCalleeAnalysis>();
  BottomUpFunctionOrder BottomUpOrder(*Mod, BCA);
  auto BottomUpFunctions = BottomUpOrder.getFunctions();

  assert(FunctionWorklist.empty() && "Expected empty function worklist!");

  FunctionWorklist.reserve(BottomUpFunctions.size());
  for (auto I = BottomUpFunctions.rbegin(), E = BottomUpFunctions.rend();
       I != E; ++I) {
    auto &F = **I;

    // Only include functions that are definitions, and which have not
    // been intentionally excluded from optimization.
    if (F.isDefinition() && F.shouldOptimize())
      FunctionWorklist.push_back(*I);
  }

  DerivationLevels.clear();

  // The maximum number of times the pass pipeline can be restarted for a
  // function. This is used to ensure we are not going into an infinite loop in
  // cases where (for example) we have recursive type-based specialization
  // happening.
  const unsigned MaxNumRestarts = 20;

  if (SILPrintPassName)
    llvm::dbgs() << "Start function passes at stage: " << StageName << "\n";

  // Run all transforms for all functions, starting at the tail of the worklist.
  while (!FunctionWorklist.empty() && continueTransforming()) {
    unsigned TailIdx = FunctionWorklist.size() - 1;
    unsigned PipelineIdx = FunctionWorklist[TailIdx].PipelineIdx;
    SILFunction *F = FunctionWorklist[TailIdx].F;

    if (PipelineIdx >= FuncTransforms.size()) {
      // All passes did already run for the function. Pop it off the worklist.
      FunctionWorklist.pop_back();
      continue;
    }
    assert(!shouldRestartPipeline() &&
        "Did not expect function pipeline set up to restart from beginning!");

    runPassOnFunction(FuncTransforms[PipelineIdx], F);

    // Note: Don't get entry reference prior to runPassOnFunction().
    // A pass can push a new function to the worklist which may cause a
    // reallocation of the buffer and that would invalidate the reference.
    WorklistEntry &Entry = FunctionWorklist[TailIdx];
    if (shouldRestartPipeline() && Entry.NumRestarts < MaxNumRestarts) {
      ++Entry.NumRestarts;
      Entry.PipelineIdx = 0;
    } else {
      ++Entry.PipelineIdx;
    }
    clearRestartPipeline();
  }
}

void SILPassManager::runModulePass(SILModuleTransform *SMT) {
  if (isDisabled(SMT))
    return;

  const SILOptions &Options = getOptions();

  PrettyStackTraceSILModuleTransform X(SMT, NumPassesRun);
  DebugPrintEnabler DebugPrint(NumPassesRun);

  SMT->injectPassManager(this);
  SMT->injectModule(Mod);

  CurrentPassHasInvalidated = false;

  if (SILPrintPassName)
    llvm::dbgs() << "#" << NumPassesRun << " Stage: " << StageName
                 << " Pass: " << SMT->getName() << " (module pass)\n";

  if (doPrintBefore(SMT, nullptr)) {
    llvm::dbgs() << "*** SIL module before " << StageName << " "
                 << SMT->getName() << " (" << NumOptimizationIterations
                 << ") ***\n";
    printModule(Mod, Options.EmitVerboseSIL);
  }

  llvm::sys::TimePoint<> StartTime = std::chrono::system_clock::now();
  assert(analysesUnlocked() && "Expected all analyses to be unlocked!");
  Mod->registerDeleteNotificationHandler(SMT);
  SMT->run();
  Mod->removeDeleteNotificationHandler(SMT);
  assert(analysesUnlocked() && "Expected all analyses to be unlocked!");

  if (SILPrintPassTime) {
    auto Delta = (std::chrono::system_clock::now() - StartTime).count();
    llvm::dbgs() << Delta << " (" << SMT->getName() << ",Module)\n";
  }

  // If this pass invalidated anything, print and verify.
  if (doPrintAfter(SMT, nullptr,
                   CurrentPassHasInvalidated && SILPrintAll)) {
    llvm::dbgs() << "*** SIL module after " << StageName << " "
                 << SMT->getName() << " (" << NumOptimizationIterations
                 << ") ***\n";
    printModule(Mod, Options.EmitVerboseSIL);
  }

  if (Options.VerifyAll &&
      (CurrentPassHasInvalidated || !SILVerifyWithoutInvalidation)) {
    Mod->verify();
    verifyAnalyses();
  }
}

void SILPassManager::runOneIteration() {
  const SILOptions &Options = getOptions();

  DEBUG(llvm::dbgs() << "*** Optimizing the module (" << StageName
        << ") *** \n");
  if (SILPrintAll && NumOptimizationIterations == 0) {
    llvm::dbgs() << "*** SIL module before "  << StageName
                 << " transformation (" << NumOptimizationIterations
                 << ") ***\n";
    printModule(Mod, Options.EmitVerboseSIL);
  }
  NumOptzIterations++;
  NumOptimizationIterations++;
  SmallVector<SILFunctionTransform *, 16> PendingFuncTransforms;

  // Run the transforms by alternating between function transforms and
  // module transforms. We'll queue up all the function transforms
  // that we see in a row and then run the entire group of transforms
  // on each function in turn. Then we move on to running the next set
  // of consecutive module transforms.
  auto It = Transformations.begin();
  auto End = Transformations.end();

  while (It != End && continueTransforming()) {
    assert((isa<SILFunctionTransform>(*It) || isa<SILModuleTransform>(*It)) &&
           "Unexpected pass kind!");

    while (It != End && isa<SILFunctionTransform>(*It))
      PendingFuncTransforms.push_back(cast<SILFunctionTransform>(*It++));

    runFunctionPasses(PendingFuncTransforms);
    PendingFuncTransforms.clear();

    while (It != End && isa<SILModuleTransform>(*It) &&
           continueTransforming()) {
      runModulePass(cast<SILModuleTransform>(*It));

      ++It;
      ++NumPassesRun;
    }
  }
}

/// D'tor.
SILPassManager::~SILPassManager() {
  assert(IRGenPasses.empty() && "Must add IRGen SIL passes that were "
                                "registered to the list of transformations");

  // Free all transformations.
  for (auto *T : Transformations)
    delete T;

  // delete the analysis.
  for (auto *A : Analysis) {
    Mod->removeDeleteNotificationHandler(A);
    assert(!A->isLocked() &&
           "Deleting a locked analysis. Did we forget to unlock ?");
    delete A;
  }
}

void SILPassManager::addFunctionToWorklist(SILFunction *F,
                                           SILFunction *DerivedFrom) {
  assert(F && F->isDefinition() && F->shouldOptimize() &&
         "Expected optimizable function definition!");

  constexpr int MaxDeriveLevels = 10;

  int NewLevel = 1;
  if (DerivedFrom) {
    // When SILVerifyAll is enabled, individual functions are verified after
    // function passes are run upon them. This means that any functions created
    // by a function pass will not be verified after the pass runs. Thus
    // specialization errors that cause the verifier to trip will be
    // misattributed to the first pass that makes a change to the specialized
    // function. This is very misleading and increases triage time.
    //
    // As a result, when SILVerifyAll is enabled, we always verify newly
    // specialized functions as they are added to the worklist.
    //
    // TODO: Currently, all specialized functions are added to the function
    // worklist in this manner. This is all well and good, but we should really
    // add support for verifying that all specialized functions are added via
    // this function to the pass manager to ensure that we perform this
    // verification.
    if (getOptions().VerifyAll) {
      F->verify();
    }

    NewLevel = DerivationLevels[DerivedFrom] + 1;
    // Limit the number of derivations, i.e. don't allow that a pass specializes
    // a specialized function which is itself a specialized function, and so on.
    if (NewLevel >= MaxDeriveLevels)
      return;
  }
  int &StoredLevel = DerivationLevels[F];

  // Only allow a function to be pushed on the worklist a single time
  // (not counting the initial population of the worklist with the bottom-up
  // function order).
  if (StoredLevel > 0)
    return;

  StoredLevel = NewLevel;
  FunctionWorklist.push_back(F);
}

void SILPassManager::restartWithCurrentFunction(SILTransform *T) {
  assert(isa<SILFunctionTransform>(T) &&
         "Can only restart the pipeline from function passes");
  RestartPipeline = true;
}

/// \brief Reset the state of the pass manager and remove all transformation
/// owned by the pass manager. Analysis passes will be kept.
void SILPassManager::resetAndRemoveTransformations() {
  for (auto *T : Transformations)
    delete T;

  Transformations.clear();
  NumOptimizationIterations = 0;
}

void SILPassManager::setStageName(llvm::StringRef NextStage) {
  StageName = NextStage;
}

const SILOptions &SILPassManager::getOptions() const {
  return Mod->getOptions();
}

void SILPassManager::addPass(PassKind Kind) {
  assert(unsigned(PassKind::AllPasses_Last) >= unsigned(Kind) &&
         "Invalid pass kind");
  switch (Kind) {
#define PASS(ID, NAME, DESCRIPTION)                                            \
  case PassKind::ID: {                                                         \
    SILTransform *T = swift::create##ID();                                     \
    T->setPassKind(PassKind::ID);                                              \
    Transformations.push_back(T);                                              \
    break;                                                                     \
  }
#define IRGEN_PASS(ID, NAME, DESCRIPTION)                                      \
  case PassKind::ID: {                                                         \
    SILTransform *T = IRGenPasses[unsigned(Kind)];                             \
    assert(T && "Missing IRGen pass?");                                        \
    T->setPassKind(PassKind::ID);                                              \
    Transformations.push_back(T);                                              \
    IRGenPasses.erase(unsigned(Kind));                                         \
    break;                                                                     \
  }
#include "swift/SILOptimizer/PassManager/Passes.def"
  case PassKind::invalidPassKind:
    llvm_unreachable("invalid pass kind");
  }
}

void SILPassManager::addPassForName(StringRef Name) {
  PassKind P = llvm::StringSwitch<PassKind>(Name)
#define PASS(ID, NAME, DESCRIPTION) .Case(#ID, PassKind::ID)
#include "swift/SILOptimizer/PassManager/Passes.def"
  ;
  addPass(P);
}

//===----------------------------------------------------------------------===//
//                          View Call-Graph Implementation
//===----------------------------------------------------------------------===//

#ifndef NDEBUG

namespace {

  /// An explicit graph data structure for the call graph.
  /// Used for viewing the callgraph as dot file with llvm::ViewGraph.
  struct CallGraph {

    struct Node;

    struct Edge {
      FullApplySite FAS;
      Node *Child;
      bool Incomplete;
    };

    struct Node {
      SILFunction *F;
      CallGraph *CG;
      int NumCallSites = 0;
      SmallVector<Edge, 8> Children;
    };

    struct child_iterator
        : public std::iterator<std::random_access_iterator_tag, Node *,
                               ptrdiff_t> {
      SmallVectorImpl<Edge>::iterator baseIter;

      child_iterator(SmallVectorImpl<Edge>::iterator baseIter) :
      baseIter(baseIter)
      { }

      child_iterator &operator++() { baseIter++; return *this; }
      child_iterator operator++(int) {
        auto tmp = *this;
        baseIter++;
        return tmp;
      }
      Node *operator*() const { return baseIter->Child; }
      bool operator==(const child_iterator &RHS) const {
        return baseIter == RHS.baseIter;
      }
      bool operator!=(const child_iterator &RHS) const {
        return baseIter != RHS.baseIter;
      }
      difference_type operator-(const child_iterator &RHS) const {
        return baseIter - RHS.baseIter;
      }
    };

    CallGraph(SILModule *M, BasicCalleeAnalysis *BCA);

    std::vector<Node> Nodes;

    /// The SILValue IDs which are printed as edge source labels.
    llvm::DenseMap<const ValueBase *, unsigned> InstToIDMap;

    typedef std::vector<Node>::iterator iterator;
  };

  CallGraph::CallGraph(SILModule *M, BasicCalleeAnalysis *BCA) {
    Nodes.resize(M->getFunctionList().size());
    llvm::DenseMap<SILFunction *, Node *> NodeMap;
    int idx = 0;
    for (SILFunction &F : *M) {
      Node &Nd = Nodes[idx++];
      Nd.F = &F;
      Nd.CG = this;
      NodeMap[&F] = &Nd;

      F.numberValues(InstToIDMap);
    }

    for (Node &Nd : Nodes) {
      for (SILBasicBlock &BB : *Nd.F) {
        for (SILInstruction &I : BB) {
          if (FullApplySite FAS = FullApplySite::isa(&I)) {
            auto CList = BCA->getCalleeList(FAS);
            for (SILFunction *Callee : CList) {
              Node *CalleeNode = NodeMap[Callee];
              Nd.Children.push_back({FAS, CalleeNode,CList.isIncomplete()});
            }
          }
        }
      }
    }
  }

} // end anonymous namespace

namespace llvm {

  /// Wraps a dot node label string to multiple lines. The \p NumEdgeLabels
  /// gives an estimate on the minimum width of the node shape.
  static void wrap(std::string &Str, int NumEdgeLabels) {
    unsigned ColNum = 0;
    unsigned LastSpace = 0;
    unsigned MaxColumns = std::max(60, NumEdgeLabels * 8);
    for (unsigned i = 0; i != Str.length(); ++i) {
      if (ColNum == MaxColumns) {
        if (!LastSpace)
          LastSpace = i;
        Str.insert(LastSpace + 1, "\\l");
        ColNum = i - LastSpace - 1;
        LastSpace = 0;
      } else
        ++ColNum;
      if (Str[i] == ' ' || Str[i] == '.')
        LastSpace = i;
    }
  }

  /// CallGraph GraphTraits specialization so the CallGraph can be
  /// iterable by generic graph iterators.
  template <> struct GraphTraits<CallGraph::Node *> {
    typedef CallGraph::child_iterator ChildIteratorType;
    typedef CallGraph::Node *NodeRef;

    static NodeRef getEntryNode(NodeRef N) { return N; }
    static inline ChildIteratorType child_begin(NodeRef N) {
      return N->Children.begin();
    }
    static inline ChildIteratorType child_end(NodeRef N) {
      return N->Children.end();
    }
  };

  template <> struct GraphTraits<CallGraph *>
  : public GraphTraits<CallGraph::Node *> {
    typedef CallGraph *GraphType;
    typedef CallGraph::Node *NodeRef;

    static NodeRef getEntryNode(GraphType F) { return nullptr; }

    typedef pointer_iterator<CallGraph::iterator> nodes_iterator;
    static nodes_iterator nodes_begin(GraphType CG) {
      return nodes_iterator(CG->Nodes.begin());
    }
    static nodes_iterator nodes_end(GraphType CG) {
      return nodes_iterator(CG->Nodes.end());
    }
    static unsigned size(GraphType CG) { return CG->Nodes.size(); }
  };

  /// This is everything the llvm::GraphWriter needs to write the call graph in
  /// a dot file.
  template <>
  struct DOTGraphTraits<CallGraph *> : public DefaultDOTGraphTraits {

    DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}

    std::string getNodeLabel(const CallGraph::Node *Node,
                             const CallGraph *Graph) {
      std::string Label = Node->F->getName();
      wrap(Label, Node->NumCallSites);
      return Label;
    }

    std::string getNodeDescription(const CallGraph::Node *Node,
                                   const CallGraph *Graph) {
      std::string Label = demangle_wrappers::
      demangleSymbolAsString(Node->F->getName());
      wrap(Label, Node->NumCallSites);
      return Label;
    }

    static std::string getEdgeSourceLabel(const CallGraph::Node *Node,
                                          CallGraph::child_iterator I) {
      std::string Label;
      raw_string_ostream O(Label);
      SILInstruction *Inst = I.baseIter->FAS.getInstruction();
      O << '%' << Node->CG->InstToIDMap[Inst];
      return Label;
    }

    static std::string getEdgeAttributes(const CallGraph::Node *Node,
                                         CallGraph::child_iterator I,
                                         const CallGraph *Graph) {
      CallGraph::Edge *Edge = I.baseIter;
      if (Edge->Incomplete)
        return "color=\"red\"";
      return "";
    }
  };
} // namespace llvm
#endif

void SILPassManager::viewCallGraph() {
  /// When asserts are disabled, this should be a NoOp.
#ifndef NDEBUG
  CallGraph OCG(getModule(), getAnalysis<BasicCalleeAnalysis>());
  llvm::ViewGraph(&OCG, "callgraph");
#endif
}


text:
using System.Collections;
using System.Collections.Generic;
using ResumeEditor.BEncoding;

namespace ResumeEditor.Torrents
{
    public class RawTrackerTier : IList<string>
    {
        public string this[int index] {
            get { return ((BEncodedString) Tier [index]).Text; }
            set { Tier [index] = new BEncodedString (value );}
        }

        internal BEncodedList Tier {
            get; set;
        }

        public RawTrackerTier ()
            : this (new BEncodedList ())
        {
        }

        public RawTrackerTier (BEncodedList tier)
        {
            Tier = tier;
        }

        public RawTrackerTier (IEnumerable<string> announces)
            : this ()
        {
            foreach (var v in announces)
                Add (v);
        }

        public int IndexOf (string item)
        {
            return Tier.IndexOf ((BEncodedString) item);
        }

        public void Insert (int index, string item)
        {
            Tier.Insert (index, (BEncodedString) item);
        }

        public void RemoveAt (int index)
        {
            Tier.RemoveAt (index);
        }

        public void Add (string item)
        {
            Tier.Add ((BEncodedString) item);
        }

        public void Clear ()
        {
            Tier.Clear ();
        }

        public bool Contains (string item)
        {
            return Tier.Contains ((BEncodedString) item);
        }

        public void CopyTo (string[] array, int arrayIndex)
        {
            foreach (var s in this)
                array [arrayIndex ++] = s;
        }

        public bool Remove (string item)
        {
            return Tier.Remove ((BEncodedString) item);
        }

        public int Count {
            get { return Tier.Count; }
        }

        public bool IsReadOnly {
            get { return Tier.IsReadOnly; }
        }

        public IEnumerator<string> GetEnumerator ()
        {
            foreach (BEncodedString v in Tier)
                yield return v.Text;
        }

        IEnumerator IEnumerable.GetEnumerator ()
        {
            return GetEnumerator ();
        }
    }
}

redpajama_set_name: RedPajamaGithub


text:
module Megam
  class BoltdefnsCollection
    include Enumerable

    attr_reader :iterator
    def initialize
      @boltdefns = Array.new
      @boltdefns_by_name = Hash.new
      @insert_after_idx = nil
    end

    def all_boltdefns
      @boltdefns
    end

    def [](index)
      @boltdefns[index]
    end

    def []=(index, arg)
      is_megam_boltdefn(arg)
      @boltdefns[index] = arg
      @boltdefns_by_name[arg.id] = index
    end

    def <<(*args)
      args.flatten.each do |a|
        is_megam_boltdefn(a)
        @boltdefns << a
        @boltdefns_by_name[a.id] = @boltdefns.length - 1
      end
      self
    end

    # 'push' is an alias method to <<
    alias_method :push, :<<

    def insert(boltdefn)
      is_megam_boltdefn(boltdefn)
      if @insert_after_idx
        # in the middle of executing a run, so any boltdefnss inserted now should
        # be placed after the most recent addition done by the currently executing
        # boltdefns
        @boltdefns.insert(@insert_after_idx + 1, boltdefn)
        # update name -> location mappings and register new boltdefns
        @boltdefns_by_name.each_key do |key|
        @boltdefns_by_name[key] += 1 if @boltdefns_by_name[key] > @insert_after_idx
        end
        @boltdefns_by_name[boltdefn.id] = @insert_after_idx + 1
        @insert_after_idx += 1
      else
      @boltdefns << boltdefn
      @boltdefns_by_name[boltdefn.id] = @boltdefns.length - 1
      end
    end

    def each
      @boltdefns.each do |boltdefn|
        yield boltdefn
      end
    end

    def each_index
      @boltdefns.each_index do |i|
        yield i
      end
    end

    def empty?
      @boltdefns.empty?
    end

    def lookup(boltdefn)
      lookup_by = nil
      if boltdefn.kind_of?(Megam::Boltdefns)
      lookup_by = boltdefn.id
      elsif boltdefn.kind_of?(String)
      lookup_by = boltdefn
      else
        raise ArgumentError, "Must pass a Megam::Boltdefns or String to lookup"
      end
      res = @boltdefns_by_name[lookup_by]
      unless res
        raise ArgumentError, "Cannot find a boltdefn matching #{lookup_by} (did you define it first?)"
      end
      @boltdefns[res]
    end

     # Transform the ruby obj ->  to a Hash
    def to_hash
      index_hash = Hash.new
      self.each do |boltdefn|
        index_hash[boltdefn.id] = boltdefn.to_s
      end
      index_hash
    end

    # Serialize this object as a hash: called from JsonCompat.
    # Verify if this called from JsonCompat during testing.
    def to_json(*a)
      for_json.to_json(*a)
    end

    def self.json_create(o)
      collection = self.new()
      o["results"].each do |boltdefns_list|
       boltdefns_array = boltdefns_list.kind_of?(Array) ? boltdefns_list : [ boltdefns_list ]
        boltdefns_array.each do |boltdefn|
          collection.insert(boltdefn)
        end
      end
      collection
    end

    private

    def is_megam_boltdefn(arg)
      unless arg.kind_of?(Megam::Boltdefns)
        raise ArgumentError, "Members must be Megam::Boltdefn's"
      end
      true
    end

    def to_s
      Megam::Stuff.styled_hash(to_hash)
    end

  end
end


text:
package com.deleidos.rtws.commons.net.listener.util;

public final class ParameterUtil {

	private ParameterUtil() {
		// Not instantiable.
	}

	public static boolean anyNull(Object ... parameters) {

		for (Object param : parameters) {
			if (param == null) {
				return true;
			}
		}

		return false;

	}

}


text:
import sys
import control
import utils
import urllib
import re
import json
import http_request
import xml.etree.ElementTree
from BeautifulSoup import SoupStrainer
from BeautifulSoup import BeautifulSoup

# Main class
class Main:
    def __init__(self):
        params = dict(part.split('=') for part in sys.argv[2][1:].split('&'))
        self.action = params.get("action", 'view-course')
        self.sort_method = params.get("sort", '')
        self.topic_url = urllib.unquote_plus(params.get("url", ''))
        self.course_id = urllib.unquote_plus(params.get("id", None))
        utils.set_no_sort()
        self.browse()
        return

    def browse(self):
        url = "%s%s" % (utils.url_root, self.topic_url)
        print "url: %s" % url
        if self.course_id is None:
            raise Exception("Missing required course id")
        else:
            course_code = self.course_id

        print "code: %s" % course_code
        data_url = "%sservices/products/anonymous/%s?version=1.0.0.0&isTranscript=false&languageId=12" % (
            utils.url_api, course_code)
        json_data = http_request.get(data_url)

        # "https:\/\/cp-mlxprod-static.microsoft.com\/012044-1000\/en-us"
        scorm_data_url = json.loads(json_data).replace("\\/", "/")

        manifest_url = "%s/imsmanifestlite.json" % scorm_data_url
        thumbnail = "%s/thumbnail.png" % scorm_data_url

        course_details_url = "%s/coursedetails.xml?v=1446384003349" % scorm_data_url
        course_details_data = http_request.get(course_details_url)
        course_details_xml = xml.etree.ElementTree.XML(course_details_data)
        print course_details_xml
        # course_details_root = course_details_xml.getroot()
        course_level = course_details_xml.findall(".//Level")[0].text
        description = course_details_xml.findall('.//Introduction')[0].text

        json_data = http_request.get(manifest_url)
        manifest_data = json.loads(json_data)

        print manifest_data
        manifest = manifest_data["manifest"]
        organizations = manifest["organizations"]

        for org in organizations["organization"]:
            for item in org["item"]:
                try:
                    for video_item in item["item"]:
                        # identifier = item["@identifier"]
                        title = item["title"]
                        resource = video_item["resource"]
                        href = resource["@href"]
                        settings_url = href.split("=")[1]

                        resource_meta = resource["metadata"]
                        print "resource_meta: %s" % resource_meta
                        resource_type = resource_meta["learningresourcetype"]
                        print "resource_type: %s" % resource_type
                        if not re.match("^[Vv]ideo$", resource_type):
                            continue

                        video_duration = resource_meta["duration"]

                        video_settings_url = "%s/%s/videosettings.xml?v=1" % (scorm_data_url, settings_url)
                        video_settings_data = http_request.get(video_settings_url)
                        video_settings = xml.etree.ElementTree.XML(video_settings_data)

                        media_sources = video_settings.findall('.//MediaSources')
                        default_media = None
                        for source in media_sources:
                            if source.attrib["videoType"] == "progressive":
                                progressives = source.findall(".//MediaSource")
                                for prog in progressives:
                                    if prog.attrib["default"] == "true":
                                        if prog.text is not None and prog.text != "":
                                            print "using media mode: %s" % prog.attrib["videoMode"]
                                            default_media = prog.text
                                            break
                                    else:
                                        if default_media is None and (prog.text is not None and prog.text != ""):
                                            print "using media mode: %s" % prog.attrib["videoMode"]
                                            default_media = prog.text
                                continue
                        if default_media is not None:
                            utils.add_video(title, thumbnail, description, "Level %s" % course_level, default_media,
                                            course_code, video_duration)
                        else:
                            print "unable to find media for %s" % video_settings_url
                except Exception, e:
                    print str(e)

        control.directory_end()
        return


text:
/**
 * Smacks implementation of XEP-0077: In-Band Registration.
 */
package org.jivesoftware.smackx.iqregister;


text:
    module.exports = header: 'MapReduce JHS Check ', handler: ({options}) ->

## Wait

Wait for the server to be started before executing the tests.

      @call once: true, '@rybajs/metal/hadoop/mapred_jhs/wait', options.wait

## Check HTTP

Check if the JobHistoryServer is started with an HTTP REST command. Once
started, the server take some time before it can correctly answer HTTP request.
For this reason, the "retry" property is set to the high value of "10".

      protocol = if options.mapred_site['mapreduce.jobhistory.http.policy'] is 'HTTP_ONLY' then 'http' else 'https'
      [host, port] = if protocol is 'http'
      then options.mapred_site['mapreduce.jobhistory.webapp.address'].split ':'
      else options.mapred_site['mapreduce.jobhistory.webapp.https.address'].split ':'
      @system.execute
        header: 'HTTP'
        retry: 200
        cmd: mkcmd.test options.test_krb5_user, """
        curl -s --insecure --negotiate -u : #{protocol}://#{host}:#{port}/ws/v1/history/info
        """
        # code_skipped: 2 # doesnt seems to be used
      , (err, obj) ->
        throw err if err
        JSON.parse(obj.stdout).historyInfo.hadoopVersion

## Dependencies

    mkcmd = require '../../lib/mkcmd'


text:
'''
Manage the password database on BSD systems
'''

# Import python libs
try:
    import pwd
except ImportError:
    pass

# Define the module's virtual name
__virtualname__ = 'shadow'

def __virtual__():
    return __virtualname__ if 'BSD' in __grains__.get('os', '') else False

def default_hash():
    '''
    Returns the default hash used for unset passwords

    CLI Example:

    .. code-block:: bash

        salt '*' shadow.default_hash
    '''
    return '*' if __grains__['os'].lower() == 'freebsd' else '*************'

def info(name):
    '''
    Return information for the specified user

    CLI Example:

    .. code-block:: bash

        salt '*' shadow.info someuser
    '''
    try:
        data = pwd.getpwnam(name)
        ret = {
            'name': data.pw_name,
            'passwd': data.pw_passwd}
    except KeyError:
        return {
            'name': '',
            'passwd': ''}

    # Get password aging info on FreeBSD
    # TODO: Implement this for NetBSD, OpenBSD
    if __salt__['cmd.has_exec']('pw'):
        cmd = 'pw user show {0} | cut -f6,7 -d:'.format(name)
        try:
            change, expire = __salt__['cmd.run_all'](cmd)['stdout'].split(':')
        except ValueError:
            pass
        else:
            ret['change'] = change
            ret['expire'] = expire

    return ret

def set_password(name, password):
    '''
    Set the password for a named user. The password must be a properly defined
    hash. The password hash can be generated with this command:

    ``python -c "import crypt; print crypt.crypt('password', ciphersalt)"``

    :strong:`NOTE:` When constructing the ``ciphersalt`` string, you must
    escape any dollar signs, to avoid them being interpolated by the shell.

    ``'password'`` is, of course, the password for which you want to generate
    a hash.

    ``ciphersalt`` is a combination of a cipher identifier, an optional number
    of rounds, and the cryptographic salt. The arrangement and format of these
    fields depends on the cipher and which flavor of BSD you are using. For
    more information on this, see the manpage for ``crpyt(3)``. On NetBSD,
    additional information is available in ``passwd.conf(5)``.

    It is important to make sure that a supported cipher is used.

    CLI Example:

    .. code-block:: bash

        salt '*' shadow.set_password someuser '$1$UYCIxa628.9qXjpQCjM4a..'
    '''
    if __grains__.get('os', '') == 'FreeBSD':
        cmd = 'pw user mod {0} -H 0'.format(name)
        stdin = password
    else:
        cmd = 'usermod -p \'{0}\' {1}'.format(password, name)
        stdin = None
    __salt__['cmd.run'](cmd, stdin=stdin)
    return info(name)['passwd'] == password


text:
"""This code example creates new companies.

To determine which companies exist, run get_all_companies.py.

Tags: CompanyService.createCompanies
"""

__author__ = ('Nicholas Chen',
              'Joseph DiLallo')

import uuid

# Import appropriate classes from the client library.
from googleads import dfp

def main(client):
  # Initialize appropriate service.
  company_service = client.GetService('CompanyService', version='v201311')

  # Create company objects.
  companies = [
      {
          'name': 'Advertiser #%s' % uuid.uuid4(),
          'type': 'ADVERTISER'
      },
      {
          'name': 'Agency #%s' % uuid.uuid4(),
          'type': 'AGENCY'
      }
  ]

  # Add companies.
  companies = company_service.createCompanies(companies)

  # Display results.
  for company in companies:
    print ('Company with ID \'%s\', name \'%s\', and type \'%s\' was created.'
           % (company['id'], company['name'], company['type']))

if __name__ == '__main__':
  # Initialize client object.
  dfp_client = dfp.DfpClient.LoadFromStorage()
  main(dfp_client)


text:
<?php
//
// +----------------------------------------------------------------------+
// | PHP Version 4                                                        |
// +----------------------------------------------------------------------+
// | Copyright (c) 1997-2003 The PHP Group                                |
// +----------------------------------------------------------------------+
// | This source file is subject to version 2.0 of the PHP license,       |
// | that is bundled with this package in the file LICENSE, and is        |
// | available at through the world-wide-web at                           |
// | http://www.php.net/license/2_02.txt.                                 |
// | If you did not receive a copy of the PHP license and are unable to   |
// | obtain it through the world-wide-web, please send a note to          |
// | license@php.net so we can mail you a copy immediately.               |
// +----------------------------------------------------------------------+
// | Authors: Jesus M. Castagnetto <jmcastagnetto@php.net>                |
// +----------------------------------------------------------------------+
//
// $Id: Stats.php,v 1.15 2003/06/01 11:40:30 jmcastagnetto Exp $
//

include_once 'PEAR.php';

/**
* @package Math_Stats
*/

// Constants for defining the statistics to calculate /*{{{*/
/**
* STATS_BASIC to generate the basic descriptive statistics
*/
define('STATS_BASIC', 1);
/**
* STATS_FULL to generate also higher moments, mode, median, etc.
*/
define('STATS_FULL', 2);
/*}}}*/

// Constants describing the data set format /*{{{*/
/**
* STATS_DATA_SIMPLE for an array of numeric values. This is the default.
* e.g. $data = array(2,3,4,5,1,1,6);
*/
define('STATS_DATA_SIMPLE', 0);
/**
* STATS_DATA_CUMMULATIVE for an associative array of frequency values,
* where in each array entry, the index is the data point and the
* value the count (frequency):
* e.g. $data = array(3=>4, 2.3=>5, 1.25=>6, 0.5=>3)
*/
define('STATS_DATA_CUMMULATIVE', 1);
/*}}}*/

// Constants defining how to handle nulls /*{{{*/
/**
* STATS_REJECT_NULL, reject data sets with null values. This is the default.
* Any non-numeric value is considered a null in this context.
*/
define('STATS_REJECT_NULL', -1);
/**
* STATS_IGNORE_NULL, ignore null values and prune them from the data.
* Any non-numeric value is considered a null in this context.
*/
define('STATS_IGNORE_NULL', -2);
/**
* STATS_USE_NULL_AS_ZERO, assign the value of 0 (zero) to null values.
* Any non-numeric value is considered a null in this context.
*/
define('STATS_USE_NULL_AS_ZERO', -3);
/*}}}*/

/**
* A class to calculate descriptive statistics from a data set.
* Data sets can be simple arrays of data, or a cummulative hash.
* The second form is useful when passing large data set,
* for example the data set:
*
*

* $data1 = array (1,2,1,1,1,1,3,3,4.1,3,2,2,4.1,1,1,2,3,3,2,2,1,1,2,2);
*

*
* can be epxressed more compactly as:
*
*

* $data2 = array('1'=>9, '2'=>8, '3'=>5, '4.1'=>2);
*

*
* Example of use:
*
*

* include_once 'Math/Stats.php';
* $s = new Math_Stats();
* $s->setData($data1);
* // or
* // $s->setData($data2, STATS_DATA_CUMMULATIVE);
* $stats = $s->calcBasic();
* echo 'Mean: '.$stats['mean'].' StDev: '.$stats['stdev'].'
\n';
*
* // using data with nulls
* // first ignoring them:
* $data3 = array(1.2, 'foo', 2.4, 3.1, 4.2, 3.2, null, 5.1, 6.2);
* $s->setNullOption(STATS_IGNORE_NULL);
* $s->setData($data3);
* $stats3 = $s->calcFull();
*
* // and then assuming nulls == 0
* $s->setNullOption(STATS_USE_NULL_AS_ZERO);
* $s->setData($data3);
* $stats3 = $s->calcFull();
*

*
* Originally this class was part of NumPHP (Numeric PHP package)
*
* @author  Jesus M. Castagnetto <jmcastagnetto@php.net>
* @version 0.8
* @access  public
* @package Math_Stats
*/
class Base {/*{{{*/
    // properties /*{{{*/

    /**
     * The simple or cummulative data set.
     * Null by default.
     *
     * @access  private
     * @var array
     */
    var $_data = null;

    /**
     * Expanded data set. Only set when cummulative data
     * is being used. Null by default.
     *
     * @access  private
     * @var array
     */
    var $_dataExpanded = null;

    /**
     * Flag for data type, one of STATS_DATA_SIMPLE or
     * STATS_DATA_CUMMULATIVE. Null by default.
     *
     * @access  private
     * @var int
     */
    var $_dataOption = null;

    /**
     * Flag for null handling options. One of STATS_REJECT_NULL,
     * STATS_IGNORE_NULL or STATS_USE_NULL_AS_ZERO
     *
     * @access  private
     * @var int
     */
    var $_nullOption;

    /**
     * Array for caching result values, should be reset
     * when using setData()
     *
     * @access private
     * @var array
     */
    var $_calculatedValues = array();

    /*}}}*/

    /**
     * Constructor for the class
     *
     * @access  public
     * @param   optional    int $nullOption how to handle null values
     * @return  object  Math_Stats
     */
    function Math_Stats($nullOption=STATS_REJECT_NULL) {/*{{{*/
        $this->_nullOption = $nullOption;
    }/*}}}*/

    /**
     * Sets and verifies the data, checking for nulls and using
     * the current null handling option
     *
     * @access public
     * @param   array   $arr    the data set
     * @param   optional    int $opt    data format: STATS_DATA_CUMMULATIVE or STATS_DATA_SIMPLE (default)
     * @return  mixed   true on success, a PEAR_Error object otherwise
     */
    function setData($arr, $opt=STATS_DATA_SIMPLE) {/*{{{*/
        if (!is_array($arr)) {
            return PEAR::raiseError('invalid data, an array of numeric data was expected');
        }
        $this->_data = null;
        $this->_dataExpanded = null;
        $this->_dataOption = null;
        $this->_calculatedValues = array();
        if ($opt == STATS_DATA_SIMPLE) {
            $this->_dataOption = $opt;
            $this->_data = array_values($arr);
        } else if ($opt == STATS_DATA_CUMMULATIVE) {
            $this->_dataOption = $opt;
            $this->_data = $arr;
            $this->_dataExpanded = array();
        }
        return $this->_validate();
    }/*}}}*/

    /**
     * Returns the data which might have been modified
     * according to the current null handling options.
     *
     * @access  public
     * @param boolean $expanded whether to return a expanded list, default is false
     * @return  mixed   array of data on success, a PEAR_Error object otherwise
     * @see _validate()
     */
    function getData($expanded=false) {/*{{{*/
        if ($this->_data == null) {
            return PEAR::raiseError('data has not been set');
        }
        if ($this->_dataOption == STATS_DATA_CUMMULATIVE && $expanded) {
            return $this->_dataExpanded;
        } else {
            return $this->_data;
        }
    }/*}}}*/

    /**
     * Sets the null handling option.
     * Must be called before assigning a new data set containing null values
     *
     * @access  public
     * @return  mixed   true on success, a PEAR_Error object otherwise
     * @see _validate()
     */
    function setNullOption($nullOption) {/*{{{*/
        if ($nullOption == STATS_REJECT_NULL
            || $nullOption == STATS_IGNORE_NULL
            || $nullOption == STATS_USE_NULL_AS_ZERO) {
            $this->_nullOption = $nullOption;
            return true;
        } else {
            return PEAR::raiseError('invalid null handling option expecting: '.
                        'STATS_REJECT_NULL, STATS_IGNORE_NULL or STATS_USE_NULL_AS_ZERO');
        }
    }/*}}}*/

    /**
     * Transforms the data by substracting each entry from the mean and
     * dividing by its standard deviation. This will reset all pre-calculated
     * values to their original (unset) defaults.
     *
     * @access public
     * @return mixed true on success, a PEAR_Error object otherwise
     * @see mean()
     * @see stDev()
     * @see setData()
     */
    function studentize() {/*{{{*/
        $mean = $this->mean();
        if (PEAR::isError($mean)) {
            return $mean;
        }
        $std = $this->stDev();
        if (PEAR::isError($std)) {
            return $std;
        }
        if ($std == 0) {
            return PEAR::raiseError('cannot studentize data, standard deviation is zero.');
        }
        $arr  = array();
        if ($this->_dataOption == STATS_DATA_CUMMULATIVE) {
            foreach ($this->_data as $val=>$freq) {
                $newval = ($val - $mean) / $std;
                $arr["$newval"] = $freq;
            }
        } else {
            foreach ($this->_data as $val) {
                $newval = ($val - $mean) / $std;
                $arr[] = $newval;
            }
        }
        return $this->setData($arr, $this->_dataOption);
    }/*}}}*/

    /**
     * Transforms the data by substracting each entry from the mean.
     * This will reset all pre-calculated values to their original (unset) defaults.
     *
     * @access public
     * @return mixed true on success, a PEAR_Error object otherwise
     * @see mean()
     * @see setData()
     */
    function center() {/*{{{*/
        $mean = $this->mean();
        if (PEAR::isError($mean)) {
            return $mean;
        }
        $arr  = array();
        if ($this->_dataOption == STATS_DATA_CUMMULATIVE) {
            foreach ($this->_data as $val=>$freq) {
                $newval = $val - $mean;
                $arr["$newval"] = $freq;
            }
        } else {
            foreach ($this->_data as $val) {
                $newval = $val - $mean;
                $arr[] = $newval;
            }
        }
        return $this->setData($arr, $this->_dataOption);
    }/*}}}*/

    /**
     * Calculates the basic or full statistics for the data set
     *
     * @access  public
     * @param   int $mode   one of STATS_BASIC or STATS_FULL
     * @param boolean $returnErrorObject whether the raw PEAR_Error (when true, default),
     *                  or only the error message will be returned (when false), if an error happens.
     * @return  mixed   an associative array of statistics on success, a PEAR_Error object otherwise
     * @see calcBasic()
     * @see calcFull()
     */
    function calc($mode, $returnErrorObject=true) {/*{{{*/
        if ($this->_data == null) {
            return PEAR::raiseError('data has not been set');
        }
        if ($mode == STATS_BASIC) {
            return $this->calcBasic($returnErrorObject);
        } elseif ($mode == STATS_FULL) {
            return $this->calcFull($returnErrorObject);
        } else {
            return PEAR::raiseError('incorrect mode, expected STATS_BASIC or STATS_FULL');
        }
    }/*}}}*/

    /**
     * Calculates a basic set of statistics
     *
     * @access  public
     * @param boolean $returnErrorObject whether the raw PEAR_Error (when true, default),
     *                  or only the error message will be returned (when false), if an error happens.
     * @return  mixed   an associative array of statistics on success, a PEAR_Error object otherwise
     * @see calc()
     * @see calcFull()
     */
    function calcBasic($returnErrorObject=true) {/*{{{*/
            return array (
                'min' => $this->__format($this->min(), $returnErrorObject),
                'max' => $this->__format($this->max(), $returnErrorObject),
                'sum' => $this->__format($this->sum(), $returnErrorObject),
                'sum2' => $this->__format($this->sum2(), $returnErrorObject),
                'count' => $this->__format($this->count(), $returnErrorObject),
                'mean' => $this->__format($this->mean(), $returnErrorObject),
                'stdev' => $this->__format($this->stDev(), $returnErrorObject),
                'variance' => $this->__format($this->variance(), $returnErrorObject),
                'range' => $this->__format($this->range(), $returnErrorObject)
            );
    }/*}}}*/

    /**
     * Calculates a full set of statistics
     *
     * @access  public
     * @param boolean $returnErrorObject whether the raw PEAR_Error (when true, default),
     *                  or only the error message will be returned (when false), if an error happens.
     * @return  mixed   an associative array of statistics on success, a PEAR_Error object otherwise
     * @see calc()
     * @see calcBasic()
     */
    function calcFull($returnErrorObject=true) {/*{{{*/
            return array (
                'min' => $this->__format($this->min(), $returnErrorObject),
                'max' => $this->__format($this->max(), $returnErrorObject),
                'sum' => $this->__format($this->sum(), $returnErrorObject),
                'sum2' => $this->__format($this->sum2(), $returnErrorObject),
                'count' => $this->__format($this->count(), $returnErrorObject),
                'mean' => $this->__format($this->mean(), $returnErrorObject),
                'median' => $this->__format($this->median(), $returnErrorObject),
                'mode' => $this->__format($this->mode(), $returnErrorObject),
                'midrange' => $this->__format($this->midrange(), $returnErrorObject),
                'geometric_mean' => $this->__format($this->geometricMean(), $returnErrorObject),
                'harmonic_mean' => $this->__format($this->harmonicMean(), $returnErrorObject),
                'stdev' => $this->__format($this->stDev(), $returnErrorObject),
                'absdev' => $this->__format($this->absDev(), $returnErrorObject),
                'variance' => $this->__format($this->variance(), $returnErrorObject),
                'range' => $this->__format($this->range(), $returnErrorObject),
                'std_error_of_mean' => $this->__format($this->stdErrorOfMean(), $returnErrorObject),
                'skewness' => $this->__format($this->skewness(), $returnErrorObject),
                'kurtosis' => $this->__format($this->kurtosis(), $returnErrorObject),
                'coeff_of_variation' => $this->__format($this->coeffOfVariation(), $returnErrorObject),
                'sample_central_moments' => array (
                            1 => $this->__format($this->sampleCentralMoment(1), $returnErrorObject),
                            2 => $this->__format($this->sampleCentralMoment(2), $returnErrorObject),
                            3 => $this->__format($this->sampleCentralMoment(3), $returnErrorObject),
                            4 => $this->__format($this->sampleCentralMoment(4), $returnErrorObject),
                            5 => $this->__format($this->sampleCentralMoment(5), $returnErrorObject)
                            ),
                'sample_raw_moments' => array (
                            1 => $this->__format($this->sampleRawMoment(1), $returnErrorObject),
                            2 => $this->__format($this->sampleRawMoment(2), $returnErrorObject),
                            3 => $this->__format($this->sampleRawMoment(3), $returnErrorObject),
                            4 => $this->__format($this->sampleRawMoment(4), $returnErrorObject),
                            5 => $this->__format($this->sampleRawMoment(5), $returnErrorObject)
                            ),
                'frequency' => $this->__format($this->frequency(), $returnErrorObject),
                'quartiles' => $this->__format($this->quartiles(), $returnErrorObject),
                'interquartile_range' => $this->__format($this->interquartileRange(), $returnErrorObject),
                'interquartile_mean' => $this->__format($this->interquartileMean(), $returnErrorObject),
                'quartile_deviation' => $this->__format($this->quartileDeviation(), $returnErrorObject),
                'quartile_variation_coefficient' => $this->__format($this->quartileVariationCoefficient(), $returnErrorObject),
                'quartile_skewness_coefficient' => $this->__format($this->quartileSkewnessCoefficient(), $returnErrorObject)
            );
    }/*}}}*/

    /**
     * Calculates the minimum of a data set.
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @return  mixed   the minimum value on success, a PEAR_Error object otherwise
     * @see calc()
     * @see max()
     */
    function min() {/*{{{*/
        if ($this->_data == null) {
            return PEAR::raiseError('data has not been set');
        }
        if (!array_key_exists('min', $this->_calculatedValues)) {
            if ($this->_dataOption == STATS_DATA_CUMMULATIVE) {
                $min = min(array_keys($this->_data));
            } else {
                $min = min($this->_data);
            }
            $this->_calculatedValues['min'] = $min;
        }
        return $this->_calculatedValues['min'];
    }/*}}}*/

    /**
     * Calculates the maximum of a data set.
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @return  mixed   the maximum value on success, a PEAR_Error object otherwise
     * @see calc()
     * @see min()
     */
    function max() {/*{{{*/
        if ($this->_data == null) {
            return PEAR::raiseError('data has not been set');
        }
        if (!array_key_exists('max', $this->_calculatedValues)) {
            if ($this->_dataOption == STATS_DATA_CUMMULATIVE) {
                $max = max(array_keys($this->_data));
            } else {
                $max = max($this->_data);
            }
            $this->_calculatedValues['max'] = $max;
        }
        return $this->_calculatedValues['max'];
    }/*}}}*/

    /**
     * Calculates SUM { xi }
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @return  mixed   the sum on success, a PEAR_Error object otherwise
     * @see calc()
     * @see sum2()
     * @see sumN()
     */
    function sum() {/*{{{*/
        if (!array_key_exists('sum', $this->_calculatedValues)) {
            $sum = $this->sumN(1);
            if (PEAR::isError($sum)) {
                return $sum;
            } else {
                $this->_calculatedValues['sum'] = $sum;
            }
        }
        return $this->_calculatedValues['sum'];
    }/*}}}*/

    /**
     * Calculates SUM { (xi)^2 }
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @return  mixed   the sum on success, a PEAR_Error object otherwise
     * @see calc()
     * @see sum()
     * @see sumN()
     */
    function sum2() {/*{{{*/
        if (!array_key_exists('sum2', $this->_calculatedValues)) {
            $sum2 = $this->sumN(2);
            if (PEAR::isError($sum2)) {
                return $sum2;
            } else {
                $this->_calculatedValues['sum2'] = $sum2;
            }
        }
        return $this->_calculatedValues['sum2'];
    }/*}}}*/

    /**
     * Calculates SUM { (xi)^n }
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @param   numeric $n  the exponent
     * @return  mixed   the sum on success, a PEAR_Error object otherwise
     * @see calc()
     * @see sum()
     * @see sum2()
     */
    function sumN($n) {/*{{{*/
        if ($this->_data == null) {
            return PEAR::raiseError('data has not been set');
        }
        $sumN = 0;
        if ($this->_dataOption == STATS_DATA_CUMMULATIVE) {
            foreach($this->_data as $val=>$freq) {
                $sumN += $freq * pow((double)$val, (double)$n);
            }
        } else {
            foreach($this->_data as $val) {
                $sumN += pow((double)$val, (double)$n);
            }
        }
        return $sumN;
    }/*}}}*/

    /**
     * Calculates PROD { (xi) }, (the product of all observations)
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @return  mixed   the product on success, a PEAR_Error object otherwise
     * @see productN()
     */
    function product() {/*{{{*/
        if (!array_key_exists('product', $this->_calculatedValues)) {
            $product = $this->productN(1);
            if (PEAR::isError($product)) {
                return $product;
            } else {
                $this->_calculatedValues['product'] = $product;
            }
        }
        return $this->_calculatedValues['product'];
    }/*}}}*/

    /**
     * Calculates PROD { (xi)^n }, which is the product of all observations
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @param   numeric $n  the exponent
     * @return  mixed   the product on success, a PEAR_Error object otherwise
     * @see product()
     */
    function productN($n) {/*{{{*/
        if ($this->_data == null) {
            return PEAR::raiseError('data has not been set');
        }
        $prodN = 1.0;
        if ($this->_dataOption == STATS_DATA_CUMMULATIVE) {
            foreach($this->_data as $val=>$freq) {
                if ($val == 0) {
                    return 0.0;
                }
                $prodN *= $freq * pow((double)$val, (double)$n);
            }
        } else {
            foreach($this->_data as $val) {
                if ($val == 0) {
                    return 0.0;
                }
                $prodN *= pow((double)$val, (double)$n);
            }
        }
        return $prodN;

    }/*}}}*/

    /**
     * Calculates the number of data points in the set
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @return  mixed   the count on success, a PEAR_Error object otherwise
     * @see calc()
     */
    function count() {/*{{{*/
        if ($this->_data == null) {
            return PEAR::raiseError('data has not been set');
        }
        if (!array_key_exists('count', $this->_calculatedValues)) {
            if ($this->_dataOption == STATS_DATA_CUMMULATIVE) {
                $count = count($this->_dataExpanded);
            } else {
                $count = count($this->_data);
            }
            $this->_calculatedValues['count'] = $count;
        }
        return $this->_calculatedValues['count'];
    }/*}}}*/

    /**
     * Calculates the mean (average) of the data points in the set
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @return  mixed   the mean value on success, a PEAR_Error object otherwise
     * @see calc()
     * @see sum()
     * @see count()
     */
    function mean() {/*{{{*/
        if (!array_key_exists('mean', $this->_calculatedValues)) {
            $sum = $this->sum();
            if (PEAR::isError($sum)) {
                return $sum;
            }
            $count = $this->count();
            if (PEAR::isError($count)) {
                return $count;
            }
            $this->_calculatedValues['mean'] = $sum / $count;
        }
        return $this->_calculatedValues['mean'];
    }/*}}}*/

    /**
     * Calculates the range of the data set = max - min
     *
     * @access public
     * @return mixed the value of the range on success, a PEAR_Error object otherwise.
     */
    function range() {/*{{{*/
        if (!array_key_exists('range', $this->_calculatedValues)) {
            $min = $this->min();
            if (PEAR::isError($min)) {
                return $min;
            }
            $max = $this->max();
            if (PEAR::isError($max)) {
                return $max;
            }
            $this->_calculatedValues['range'] = $max - $min;
        }
        return $this->_calculatedValues['range'];

    }/*}}}*/

    /**
     * Calculates the variance (unbiased) of the data points in the set
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @return  mixed   the variance value on success, a PEAR_Error object otherwise
     * @see calc()
     * @see __sumdiff()
     * @see count()
     */
    function variance() {/*{{{*/
        if (!array_key_exists('variance', $this->_calculatedValues)) {
            $variance = $this->__calcVariance();
            if (PEAR::isError($variance)) {
                return $variance;
            }
            $this->_calculatedValues['variance'] = $variance;
        }
        return $this->_calculatedValues['variance'];
    }/*}}}*/

    /**
     * Calculates the standard deviation (unbiased) of the data points in the set
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @return  mixed   the standard deviation on success, a PEAR_Error object otherwise
     * @see calc()
     * @see variance()
     */
    function stDev() {/*{{{*/
        if (!array_key_exists('stDev', $this->_calculatedValues)) {
            $variance = $this->variance();
            if (PEAR::isError($variance)) {
                return $variance;
            }
            $this->_calculatedValues['stDev'] = sqrt($variance);
        }
        return $this->_calculatedValues['stDev'];
    }/*}}}*/

    /**
     * Calculates the variance (unbiased) of the data points in the set
     * given a fixed mean (average) value. Not used in calcBasic(), calcFull()
     * or calc().
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @param   numeric $mean   the fixed mean value
     * @return  mixed   the variance on success, a PEAR_Error object otherwise
     * @see __sumdiff()
     * @see count()
     * @see variance()
     */
    function varianceWithMean($mean) {/*{{{*/
        return $this->__calcVariance($mean);
    }/*}}}*/

    /**
     * Calculates the standard deviation (unbiased) of the data points in the set
     * given a fixed mean (average) value. Not used in calcBasic(), calcFull()
     * or calc().
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @param   numeric $mean   the fixed mean value
     * @return  mixed   the standard deviation on success, a PEAR_Error object otherwise
     * @see varianceWithMean()
     * @see stDev()
     */
    function stDevWithMean($mean) {/*{{{*/
        $varianceWM = $this->varianceWithMean($mean);
        if (PEAR::isError($varianceWM)) {
            return $varianceWM;
        }
        return sqrt($varianceWM);
    }/*}}}*/

    /**
     * Calculates the absolute deviation of the data points in the set
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @return  mixed   the absolute deviation on success, a PEAR_Error object otherwise
     * @see calc()
     * @see __sumabsdev()
     * @see count()
     * @see absDevWithMean()
     */
    function absDev() {/*{{{*/
        if (!array_key_exists('absDev', $this->_calculatedValues)) {
            $absDev = $this->__calcAbsoluteDeviation();
            if (PEAR::isError($absdev)) {
                return $absdev;
            }
            $this->_calculatedValues['absDev'] = $absDev;
        }
        return $this->_calculatedValues['absDev'];
    }/*}}}*/

    /**
     * Calculates the absolute deviation of the data points in the set
     * given a fixed mean (average) value. Not used in calcBasic(), calcFull()
     * or calc().
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @param   numeric $mean   the fixed mean value
     * @return  mixed   the absolute deviation on success, a PEAR_Error object otherwise
     * @see __sumabsdev()
     * @see absDev()
     */
    function absDevWithMean($mean) {/*{{{*/
        return $this->__calcAbsoluteDeviation($mean);
    }/*}}}*/

    /**
     * Calculates the skewness of the data distribution in the set
     * The skewness measures the degree of asymmetry of a distribution,
     * and is related to the third central moment of a distribution.
     * A normal distribution has a skewness = 0
     * A distribution with a tail off towards the high end of the scale
     * (positive skew) has a skewness > 0
     * A distribution with a tail off towards the low end of the scale
     * (negative skew) has a skewness < 0
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @return  mixed   the skewness value on success, a PEAR_Error object otherwise
     * @see __sumdiff()
     * @see count()
     * @see stDev()
     * @see calc()
     */
    function skewness() {/*{{{*/
        if (!array_key_exists('skewness', $this->_calculatedValues)) {
            $count = $this->count();
            if (PEAR::isError($count)) {
                return $count;
            }
            $stDev = $this->stDev();
            if (PEAR::isError($stDev)) {
                return $stDev;
            }
            $sumdiff3 = $this->__sumdiff(3);
            if (PEAR::isError($sumdiff3)) {
                return $sumdiff3;
            }
            $this->_calculatedValues['skewness'] = ($sumdiff3 / ($count * pow($stDev, 3)));
        }
        return $this->_calculatedValues['skewness'];
    }/*}}}*/

    /**
     * Calculates the kurtosis of the data distribution in the set
     * The kurtosis measures the degrees of peakedness of a distribution.
     * It is also called the "excess" or "excess coefficient", and is
     * a normalized form of the fourth central moment of a distribution.
     * A normal distributions has kurtosis = 0
     * A narrow and peaked (leptokurtic) distribution has a
     * kurtosis > 0
     * A flat and wide (platykurtic) distribution has a kurtosis < 0
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @return  mixed   the kurtosis value on success, a PEAR_Error object otherwise
     * @see __sumdiff()
     * @see count()
     * @see stDev()
     * @see calc()
     */
    function kurtosis() {/*{{{*/
        if (!array_key_exists('kurtosis', $this->_calculatedValues)) {
            $count = $this->count();
            if (PEAR::isError($count)) {
                return $count;
            }
            $stDev = $this->stDev();
            if (PEAR::isError($stDev)) {
                return $stDev;
            }
            $sumdiff4 = $this->__sumdiff(4);
            if (PEAR::isError($sumdiff4)) {
                return $sumdiff4;
            }
            $this->_calculatedValues['kurtosis'] = ($sumdiff4 / ($count * pow($stDev, 4))) - 3;
        }
        return $this->_calculatedValues['kurtosis'];
    }/*}}}*/

    /**
     * Calculates the median of a data set.
     * The median is the value such that half of the points are below it
     * in a sorted data set.
     * If the number of values is odd, it is the middle item.
     * If the number of values is even, is the average of the two middle items.
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @return  mixed   the median value on success, a PEAR_Error object otherwise
     * @see count()
     * @see calc()
     */
    function median() {/*{{{*/
        if ($this->_data == null) {
            return PEAR::raiseError('data has not been set');
        }
        if (!array_key_exists('median', $this->_calculatedValues)) {
            if ($this->_dataOption == STATS_DATA_CUMMULATIVE) {
                $arr =& $this->_dataExpanded;
            } else {
                $arr =& $this->_data;
            }
            $n = $this->count();
            if (PEAR::isError($n)) {
                return $n;
            }
            $h = intval($n / 2);
            if ($n % 2 == 0) {
                $median = ($arr[$h] + $arr[$h - 1]) / 2;
            } else {
                $median = $arr[$h + 1];
            }
            $this->_calculatedValues['median'] = $median;
        }
        return $this->_calculatedValues['median'];
    }/*}}}*/

    /**
     * Calculates the mode of a data set.
     * The mode is the value with the highest frequency in the data set.
     * There can be more than one mode.
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @return  mixed   an array of mode value on success, a PEAR_Error object otherwise
     * @see frequency()
     * @see calc()
     */
    function mode() {/*{{{*/
        if ($this->_data == null) {
            return PEAR::raiseError('data has not been set');
        }
        if (!array_key_exists('mode', $this->_calculatedValues)) {
            if ($this->_dataOption == STATS_DATA_CUMMULATIVE) {
                $arr = $this->_data;
            } else {
                $arr = $this->frequency();
            }
            arsort($arr);
            $mcount = 1;
            foreach ($arr as $val=>$freq) {
                if ($mcount == 1) {
                    $mode = array($val);
                    $mfreq = $freq;
                    $mcount++;
                    continue;
                }
                if ($mfreq == $freq)
                    $mode[] = $val;
                if ($mfreq > $freq)
                    break;
            }
            $this->_calculatedValues['mode'] = $mode;
        }
        return $this->_calculatedValues['mode'];
    }/*}}}*/

    /**
     * Calculates the midrange of a data set.
     * The midrange is the average of the minimum and maximum of the data set.
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @return  mixed   the midrange value on success, a PEAR_Error object otherwise
     * @see min()
     * @see max()
     * @see calc()
     */
    function midrange() {/*{{{*/
        if (!array_key_exists('midrange', $this->_calculatedValues)) {
            $min = $this->min();
            if (PEAR::isError($min)) {
                return $min;
            }
            $max = $this->max();
            if (PEAR::isError($max)) {
                return $max;
            }
            $this->_calculatedValues['midrange'] = (($max + $min) / 2);
        }
        return $this->_calculatedValues['midrange'];
    }/*}}}*/

    /**
     * Calculates the geometrical mean of the data points in the set
     * Handles cummulative data sets correctly
     *
     * @access public
     * @return mixed the geometrical mean value on success, a PEAR_Error object otherwise
     * @see calc()
     * @see product()
     * @see count()
     */
    function geometricMean() {/*{{{*/
        if (!array_key_exists('geometricMean', $this->_calculatedValues)) {
            $count = $this->count();
            if (PEAR::isError($count)) {
                return $count;
            }
            $prod = $this->product();
            if (PEAR::isError($prod)) {
                return $prod;
            }
            if ($prod == 0.0) {
                return 0.0;
            }
            if ($prod < 0) {
                return PEAR::raiseError('The product of the data set is negative, geometric mean undefined.');
            }
            $this->_calculatedValues['geometricMean'] = pow($prod , 1 / $count);
        }
        return $this->_calculatedValues['geometricMean'];
    }/*}}}*/

    /**
     * Calculates the harmonic mean of the data points in the set
     * Handles cummulative data sets correctly
     *
     * @access public
     * @return mixed the harmonic mean value on success, a PEAR_Error object otherwise
     * @see calc()
     * @see count()
     */
    function harmonicMean() {/*{{{*/
        if ($this->_data == null) {
            return PEAR::raiseError('data has not been set');
        }
        if (!array_key_exists('harmonicMean', $this->_calculatedValues)) {
            $count = $this->count();
            if (PEAR::isError($count)) {
                return $count;
            }
            $invsum = 0.0;
            if ($this->_dataOption == STATS_DATA_CUMMULATIVE) {
                foreach($this->_data as $val=>$freq) {
                    if ($val == 0) {
                        return PEAR::raiseError('cannot calculate a '.
                                'harmonic mean with data values of zero.');
                    }
                    $invsum += $freq / $val;
                }
            } else {
                foreach($this->_data as $val) {
                    if ($val == 0) {
                        return PEAR::raiseError('cannot calculate a '.
                                'harmonic mean with data values of zero.');
                    }
                    $invsum += 1 / $val;
                }
            }
            $this->_calculatedValues['harmonicMean'] = $count / $invsum;
        }
        return $this->_calculatedValues['harmonicMean'];
    }/*}}}*/

    /**
     * Calculates the nth central moment (m{n}) of a data set.
     *
     * The definition of a sample central moment is:
     *
     *     m{n} = 1/N * SUM { (xi - avg)^n }
     *
     * where: N = sample size, avg = sample mean.
     *
     * @access public
     * @param integer $n moment to calculate
     * @return mixed the numeric value of the moment on success, PEAR_Error otherwise
     */
    function sampleCentralMoment($n) {/*{{{*/
        if (!is_int($n) || $n < 1) {
            return PEAR::isError('moment must be a positive integer >= 1.');
        }

        if ($n == 1) {
            return 0;
        }
        $count = $this->count();
        if (PEAR::isError($count)) {
            return $count;
        }
        if ($count == 0) {
            return PEAR::raiseError("Cannot calculate {$n}th sample moment, ".
                    'there are zero data entries');
        }
        $sum = $this->__sumdiff($n);
        if (PEAR::isError($sum)) {
            return $sum;
        }
        return ($sum / $count);
    }/*}}}*/

    /**
     * Calculates the nth raw moment (m{n}) of a data set.
     *
     * The definition of a sample central moment is:
     *
     *     m{n} = 1/N * SUM { xi^n }
     *
     * where: N = sample size, avg = sample mean.
     *
     * @access public
     * @param integer $n moment to calculate
     * @return mixed the numeric value of the moment on success, PEAR_Error otherwise
     */
    function sampleRawMoment($n) {/*{{{*/
        if (!is_int($n) || $n < 1) {
            return PEAR::isError('moment must be a positive integer >= 1.');
        }

        $count = $this->count();
        if (PEAR::isError($count)) {
            return $count;
        }
        if ($count == 0) {
            return PEAR::raiseError("Cannot calculate {$n}th raw moment, ".
                    'there are zero data entries.');
        }
        $sum = $this->sumN($n);
        if (PEAR::isError($sum)) {
            return $sum;
        }
        return ($sum / $count);
    }/*}}}*/

    /**
     * Calculates the coefficient of variation of a data set.
     * The coefficient of variation measures the spread of a set of data
     * as a proportion of its mean. It is often expressed as a percentage.
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @return  mixed   the coefficient of variation on success, a PEAR_Error object otherwise
     * @see stDev()
     * @see mean()
     * @see calc()
     */
    function coeffOfVariation() {/*{{{*/
        if (!array_key_exists('coeffOfVariation', $this->_calculatedValues)) {
            $mean = $this->mean();
            if (PEAR::isError($mean)) {
                return $mean;
            }
            if ($mean == 0.0) {
                return PEAR::raiseError('cannot calculate the coefficient '.
                        'of variation, mean of sample is zero');
            }
            $stDev = $this->stDev();
            if (PEAR::isError($stDev)) {
                return $stDev;
            }

            $this->_calculatedValues['coeffOfVariation'] = $stDev / $mean;
        }
        return $this->_calculatedValues['coeffOfVariation'];
    }/*}}}*/

    /**
     * Calculates the standard error of the mean.
     * It is the standard deviation of the sampling distribution of
     * the mean. The formula is:
     *
     * S.E. Mean = SD / (N)^(1/2)
     *
     * This formula does not assume a normal distribution, and shows
     * that the size of the standard error of the mean is inversely
     * proportional to the square root of the sample size.
     *
     * @access  public
     * @return  mixed   the standard error of the mean on success, a PEAR_Error object otherwise
     * @see stDev()
     * @see count()
     * @see calc()
     */
    function stdErrorOfMean() {/*{{{*/
        if (!array_key_exists('stdErrorOfMean', $this->_calculatedValues)) {
            $count = $this->count();
            if (PEAR::isError($count)) {
                return $count;
            }
            $stDev = $this->stDev();
            if (PEAR::isError($stDev)) {
                return $stDev;
            }
            $this->_calculatedValues['stdErrorOfMean'] = $stDev / sqrt($count);
        }
        return $this->_calculatedValues['stdErrorOfMean'];
    }/*}}}*/

    /**
     * Calculates the value frequency table of a data set.
     * Handles cummulative data sets correctly
     *
     * @access  public
     * @return  mixed   an associative array of value=>frequency items on success, a PEAR_Error object otherwise
     * @see min()
     * @see max()
     * @see calc()
     */
    function frequency() {/*{{{*/
        if ($this->_data == null) {
            return PEAR::raiseError('data has not been set');
        }
        if (!array_key_exists('frequency', $this->_calculatedValues)) {
            if ($this->_dataOption == STATS_DATA_CUMMULATIVE) {
                $freq = $this->_data;
            } else {
                $freq = array();
                foreach ($this->_data as $val) {
                    $freq["$val"]++;
                }
                ksort($freq);
            }
            $this->_calculatedValues['frequency'] = $freq;
        }
        return $this->_calculatedValues['frequency'];
    }/*}}}*/

    /**
     * The quartiles are defined as the values that divide a sorted
     * data set into four equal-sized subsets, and correspond to the
     * 25th, 50th, and 75th percentiles.
     *
     * @access public
     * @return mixed an associative array of quartiles on success, a PEAR_Error otherwise
     * @see percentile()
     */
    function quartiles() {/*{{{*/
        if (!array_key_exists('quartiles', $this->_calculatedValues)) {
            $q1 = $this->percentile(25);
            if (PEAR::isError($q1)) {
                return $q1;
            }
            $q2 = $this->percentile(50);
            if (PEAR::isError($q2)) {
                return $q2;
            }
            $q3 = $this->percentile(75);
            if (PEAR::isError($q3)) {
                return $q3;
            }
            $this->_calculatedValues['quartiles'] = array (
                                        '25' => $q1,
                                        '50' => $q2,
                                        '75' => $q3
                                        );
        }
        return $this->_calculatedValues['quartiles'];
    }/*}}}*/

    /**
     * The interquartile mean is defined as the mean of the values left
     * after discarding the lower 25% and top 25% ranked values, i.e.:
     *
     *  interquart mean = mean(
)
     *
     *  where: P = percentile
     *
     * @todo need to double check the equation
     * @access public
     * @return mixed a numeric value on success, a PEAR_Error otherwise
     * @see quartiles()
     */
    function interquartileMean() {/*{{{*/
        if (!array_key_exists('interquartileMean', $this->_calculatedValues)) {
            $quart = $this->quartiles();
            if (PEAR::isError($quart)) {
                return $quart;
            }
            $q3 = $quart['75'];
            $q1 = $quart['25'];
            $sum = 0;
            $n = 0;
            foreach ($this->getData(true) as $val) {
                if ($val >= $q1 && $val <= $q3) {
                    $sum += $val;
                    $n++;
                }
            }
            if ($n == 0) {
                return PEAR::raiseError('error calculating interquartile mean, '.
                                        'empty interquartile range of values.');
            }
            $this->_calculatedValues['interquartileMean'] = $sum / $n;
        }
        return $this->_calculatedValues['interquartileMean'];
    }/*}}}*/

    /**
     * The interquartile range is the distance between the 75th and 25th
     * percentiles. Basically the range of the middle 50% of the data set,
     * and thus is not affected by outliers or extreme values.
     *
     *  interquart range = P(75) - P(25)
     *
     *  where: P = percentile
     *
     * @access public
     * @return mixed a numeric value on success, a PEAR_Error otherwise
     * @see quartiles()
     */
    function interquartileRange() {/*{{{*/
        if (!array_key_exists('interquartileRange', $this->_calculatedValues)) {
            $quart = $this->quartiles();
            if (PEAR::isError($quart)) {
                return $quart;
            }
            $q3 = $quart['75'];
            $q1 = $quart['25'];
            $this->_calculatedValues['interquartileRange'] = $q3 - $q1;
        }
        return $this->_calculatedValues['interquartileRange'];
    }/*}}}*/

    /**
     * The quartile deviation is half of the interquartile range value
     *
     *  quart dev = (P(75) - P(25)) / 2
     *
     *  where: P = percentile
     *
     * @access public
     * @return mixed a numeric value on success, a PEAR_Error otherwise
     * @see quartiles()
     * @see interquartileRange()
     */
    function quartileDeviation() {/*{{{*/
        if (!array_key_exists('quartileDeviation', $this->_calculatedValues)) {
            $iqr = $this->interquartileRange();
            if (PEAR::isError($iqr)) {
                return $iqr;
            }
            $this->_calculatedValues['quartileDeviation'] = $iqr / 2;
        }
        return $this->_calculatedValues['quartileDeviation'];
    }/*}}}*/

    /**
     * The quartile variation coefficient is defines as follows:
     *
     *  quart var coeff = 100 * (P(75) - P(25)) / (P(75) + P(25))
     *
     *  where: P = percentile
     *
     * @todo need to double check the equation
     * @access public
     * @return mixed a numeric value on success, a PEAR_Error otherwise
     * @see quartiles()
     */
    function quartileVariationCoefficient() {/*{{{*/
        if (!array_key_exists('quartileVariationCoefficient', $this->_calculatedValues)) {
            $quart = $this->quartiles();
            if (PEAR::isError($quart)) {
                return $quart;
            }
            $q3 = $quart['75'];
            $q1 = $quart['25'];
            $d = $q3 - $q1;
            $s = $q3 + $q1;
            $this->_calculatedValues['quartileVariationCoefficient'] = 100 * $d / $s;
        }
        return $this->_calculatedValues['quartileVariationCoefficient'];
    }/*}}}*/

    /**
     * The quartile skewness coefficient (also known as Bowley Skewness),
     * is defined as follows:
     *
     *  quart skewness coeff = (P(25) - 2*P(50) + P(75)) / (P(75) - P(25))
     *
     *  where: P = percentile
     *
     * @todo need to double check the equation
     * @access public
     * @return mixed a numeric value on success, a PEAR_Error otherwise
     * @see quartiles()
     */
    function quartileSkewnessCoefficient() {/*{{{*/
        if (!array_key_exists('quartileSkewnessCoefficient', $this->_calculatedValues)) {
            $quart = $this->quartiles();
            if (PEAR::isError($quart)) {
                return $quart;
            }
            $q3 = $quart['75'];
            $q2 = $quart['50'];
            $q1 = $quart['25'];
            $d = $q3 - 2*$q2 + $q1;
            $s = $q3 - $q1;
            $this->_calculatedValues['quartileSkewnessCoefficient'] = $d / $s;
        }
        return $this->_calculatedValues['quartileSkewnessCoefficient'];
    }/*}}}*/

    /**
     * The pth percentile is the value such that p% of the a sorted data set
     * is smaller than it, and (100 - p)% of the data is larger.
     *
     * A quick algorithm to pick the appropriate value from a sorted data
     * set is as follows:
     *
     * - Count the number of values: n
     * - Calculate the position of the value in the data list: i = p * (n + 1)
     * - if i is an integer, return the data at that position
     * - if i < 1, return the minimum of the data set
     * - if i > n, return the maximum of the data set
     * - otherwise, average the entries at adjacent positions to i
     *
     * The median is the 50th percentile value.
     *
     * @todo need to double check generality of the algorithm
     *
     * @access public
     * @param numeric $p the percentile to estimate, e.g. 25 for 25th percentile
     * @return mixed a numeric value on success, a PEAR_Error otherwise
     * @see quartiles()
     * @see median()
     */
    function percentile($p) {/*{{{*/
        $count = $this->count();
        if (PEAR::isError($count)) {
            return $count;
        }
        if ($this->_dataOption == STATS_DATA_CUMMULATIVE) {
            $data =& $this->_dataExpanded;
        } else {
            $data =& $this->_data;
        }
        $obsidx = $p * ($count + 1) / 100;
        if (intval($obsidx) == $obsidx) {
            return $data[($obsidx - 1)];
        } elseif ($obsidx < 1) {
            return $data[0];
        } elseif ($obsidx > $count) {
            return $data[($count - 1)];
        } else {
            $left = floor($obsidx - 1);
            $right = ceil($obsidx - 1);
            return ($data[$left] + $data[$right]) / 2;
        }
    }/*}}}*/

    // private methods

    /**
     * Utility function to calculate: SUM { (xi - mean)^n }
     *
     * @access private
     * @param   numeric $power  the exponent
     * @param   optional    double   $mean   the data set mean value
     * @return  mixed   the sum on success, a PEAR_Error object otherwise
     *
     * @see stDev()
     * @see variaceWithMean();
     * @see skewness();
     * @see kurtosis();
     */
    function __sumdiff($power, $mean=null) {/*{{{*/
        if ($this->_data == null) {
            return PEAR::raiseError('data has not been set');
        }
        if (is_null($mean)) {
            $mean = $this->mean();
            if (PEAR::isError($mean)) {
                return $mean;
            }
        }
        $sdiff = 0;
        if ($this->_dataOption == STATS_DATA_CUMMULATIVE) {
            foreach ($this->_data as $val=>$freq) {
                $sdiff += $freq * pow((double)($val - $mean), (double)$power);
            }
        } else {
            foreach ($this->_data as $val)
                $sdiff += pow((double)($val - $mean), (double)$power);
        }
        return $sdiff;
    }/*}}}*/

    /**
     * Utility function to calculate the variance with or without
     * a fixed mean
     *
     * @access private
     * @param $mean the fixed mean to use, null as default
     * @return mixed a numeric value on success, a PEAR_Error otherwise
     * @see variance()
     * @see varianceWithMean()
     */
    function __calcVariance($mean = null) {/*{{{*/
        if ($this->_data == null) {
            return PEAR::raiseError('data has not been set');
        }
        $sumdiff2 = $this->__sumdiff(2, $mean);
        if (PEAR::isError($sumdiff2)) {
            return $sumdiff2;
        }
        $count = $this->count();
        if (PEAR::isError($count)) {
            return $count;
        }
        if ($count == 1) {
            return PEAR::raiseError('cannot calculate variance of a singe data point');
        }
        return  ($sumdiff2 / ($count - 1));
    }/*}}}*/

    /**
     * Utility function to calculate the absolute deviation with or without
     * a fixed mean
     *
     * @access private
     * @param $mean the fixed mean to use, null as default
     * @return mixed a numeric value on success, a PEAR_Error otherwise
     * @see absDev()
     * @see absDevWithMean()
     */
    function __calcAbsoluteDeviation($mean = null) {/*{{{*/
        if ($this->_data == null) {
            return PEAR::raiseError('data has not been set');
        }
        $count = $this->count();
        if (PEAR::isError($count)) {
            return $count;
        }
        $sumabsdev = $this->__sumabsdev($mean);
        if (PEAR::isError($sumabsdev)) {
            return $sumabsdev;
        }
        return $sumabsdev / $count;
    }/*}}}*/

    /**
     * Utility function to calculate: SUM { | xi - mean | }
     *
     * @access  private
     * @param   optional    double   $mean   the mean value for the set or population
     * @return  mixed   the sum on success, a PEAR_Error object otherwise
     *
     * @see absDev()
     * @see absDevWithMean()
     */
    function __sumabsdev($mean=null) {/*{{{*/
        if ($this->_data == null) {
            return PEAR::raiseError('data has not been set');
        }
        if (is_null($mean)) {
            $mean = $this->mean();
        }
        $sdev = 0;
        if ($this->_dataOption == STATS_DATA_CUMMULATIVE) {
            foreach ($this->_data as $val=>$freq) {
                $sdev += $freq * abs($val - $mean);
            }
        } else {
            foreach ($this->_data as $val) {
                $sdev += abs($val - $mean);
            }
        }
        return $sdev;
    }/*}}}*/

    /**
     * Utility function to format a PEAR_Error to be used by calc(),
     * calcBasic() and calcFull()
     *
     * @access private
     * @param mixed $v value to be formatted
     * @param boolean $returnErrorObject whether the raw PEAR_Error (when true, default),
     *                  or only the error message will be returned (when false)
     * @return mixed if the value is a PEAR_Error object, and $useErrorObject
     *              is false, then a string with the error message will be returned,
     *              otherwise the value will not be modified and returned as passed.
     */
    function __format($v, $useErrorObject=true) {/*{{{*/
        if (PEAR::isError($v) && $useErrorObject == false) {
            return $v->getMessage();
        } else {
            return $v;
        }
    }/*}}}*/

    /**
     * Utility function to validate the data and modify it
     * according to the current null handling option
     *
     * @access  private
     * @return  mixed true on success, a PEAR_Error object otherwise
     *
     * @see setData()
     */
    function _validate() {/*{{{*/
        $flag = ($this->_dataOption == STATS_DATA_CUMMULATIVE);
        foreach ($this->_data as $key=>$value) {
            $d = ($flag) ? $key : $value;
            $v = ($flag) ? $value : $key;
            if (!is_numeric($d)) {
                switch ($this->_nullOption) {
                    case STATS_IGNORE_NULL :
                        unset($this->_data["$key"]);
                        break;
                    case STATS_USE_NULL_AS_ZERO:
                        if ($flag) {
                            unset($this->_data["$key"]);
                            $this->_data[0] += $v;
                        } else {
                            $this->_data[$key] = 0;
                        }
                        break;
                    case STATS_REJECT_NULL :
                    default:
                        return PEAR::raiseError('data rejected, contains NULL values');
                        break;
                }
            }
        }
        if ($flag) {
            ksort($this->_data);
            $this->_dataExpanded = array();
            foreach ($this->_data as $val=>$freq) {
                $this->_dataExpanded = array_pad($this->_dataExpanded, count($this->_dataExpanded) + $freq, $val);
            }
            sort($this->_dataExpanded);
        } else {
            sort($this->_data);
        }
        return true;
    }/*}}}*/

}/*}}}*/

// vim: ts=4:sw=4:et:
// vim6: fdl=1: fdm=marker:

?>


text:
#include <linux/types.h>
#include <linux/ip.h>
#include <linux/netfilter.h>
#include <linux/module.h>
#include <linux/skbuff.h>
#include <linux/icmp.h>
#include <linux/sysctl.h>
#include <net/ip.h>

#include <linux/netfilter_ipv4.h>
#include <net/netfilter/nf_conntrack.h>
#include <net/netfilter/nf_conntrack_l4proto.h>
#include <net/netfilter/nf_conntrack_l3proto.h>
#include <net/netfilter/nf_conntrack_core.h>
#include <net/netfilter/ipv4/nf_conntrack_ipv4.h>

static bool generic_pkt_to_tuple(const struct sk_buff *skb, unsigned int nhoff,
				 struct nf_conntrack_tuple *tuple)
{
	memset(&tuple->src.u3, 0, sizeof(tuple->src.u3));
	memset(&tuple->dst.u3, 0, sizeof(tuple->dst.u3));

	return true;
}

static bool generic_invert_tuple(struct nf_conntrack_tuple *tuple,
				 const struct nf_conntrack_tuple *orig)
{
	memset(&tuple->src.u3, 0, sizeof(tuple->src.u3));
	memset(&tuple->dst.u3, 0, sizeof(tuple->dst.u3));

	return true;
}

static int generic_print_tuple(struct seq_file *s,
			    const struct nf_conntrack_tuple *tuple)
{
	return 0;
}

static int generic_get_l4proto(const struct sk_buff *skb, unsigned int nhoff,
			       unsigned int *dataoff, u_int8_t *protonum)
{
	/* Never track !!! */
	return -NF_ACCEPT;
}

struct nf_conntrack_l3proto nf_conntrack_l3proto_generic __read_mostly = {
	.l3proto	 = PF_UNSPEC,
	.name		 = "unknown",
	.pkt_to_tuple	 = generic_pkt_to_tuple,
	.invert_tuple	 = generic_invert_tuple,
	.print_tuple	 = generic_print_tuple,
	.get_l4proto	 = generic_get_l4proto,
};
EXPORT_SYMBOL_GPL(nf_conntrack_l3proto_generic);