00001 //===-- DiscretePDF.h -------------------------------------------*- C++ -*-===// 00002 // 00003 // The KLEE Symbolic Virtual Machine 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 00010 namespace klee { 00011 template <class T> 00012 class DiscretePDF { 00013 // not perfectly parameterized, but float/double/int should work ok, 00014 // although it would be better to have choose argument range from 0 00015 // to queryable max. 00016 typedef double weight_type; 00017 00018 public: 00019 DiscretePDF(); 00020 ~DiscretePDF(); 00021 00022 bool empty() const; 00023 void insert(T item, weight_type weight); 00024 void update(T item, weight_type newWeight); 00025 void remove(T item); 00026 bool inTree(T item); 00027 weight_type getWeight(T item); 00028 00029 /* pick a tree element according to its 00030 * weight. p should be in [0,1). 00031 */ 00032 T choose(double p); 00033 00034 private: 00035 class Node; 00036 Node *m_root; 00037 00038 Node **lookup(T item, Node **parent_out); 00039 void split(Node *node); 00040 void rotate(Node *node); 00041 void lengthen(Node *node); 00042 void propogateSumsUp(Node *n); 00043 }; 00044 00045 } 00046 00047 #include "DiscretePDF.inc"
1.5.8