klee
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
DiscretePDF.h
Go to the documentation of this file.
1 //===-- DiscretePDF.h -------------------------------------------*- C++ -*-===//
2 //
3 // The KLEE Symbolic Virtual Machine
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 namespace klee {
11  template <class T>
12  class DiscretePDF {
13  // not perfectly parameterized, but float/double/int should work ok,
14  // although it would be better to have choose argument range from 0
15  // to queryable max.
16  typedef double weight_type;
17 
18  public:
19  DiscretePDF();
20  ~DiscretePDF();
21 
22  bool empty() const;
23  void insert(T item, weight_type weight);
24  void update(T item, weight_type newWeight);
25  void remove(T item);
26  bool inTree(T item);
27  weight_type getWeight(T item);
28 
29  /* pick a tree element according to its
30  * weight. p should be in [0,1).
31  */
32  T choose(double p);
33 
34  private:
35  class Node;
36  Node *m_root;
37 
38  Node **lookup(T item, Node **parent_out);
39  void split(Node *node);
40  void rotate(Node *node);
41  void lengthen(Node *node);
42  void propogateSumsUp(Node *n);
43  };
44 
45 }
46 
47 #include "DiscretePDF.inc"
void insert(T item, weight_type weight)
void rotate(Node *node)
bool inTree(T item)
void propogateSumsUp(Node *n)
Node ** lookup(T item, Node **parent_out)
void split(Node *node)
void lengthen(Node *node)
T choose(double p)
void update(T item, weight_type newWeight)
weight_type getWeight(T item)
bool empty() const