1

/* $Id$ */

     2

     3

// this test uses CData structure defined in test_autocopyptr.h

     4

     5

static int TestBinaryHeap1(bool silent)

     6

{

     7

	CData::NumInstances() = 0;

     8

	int res = 0;

     9

	{

    10

		const int max_items = 10000;

    11

		const int total_adds = 1000000;

    12

		CBinaryHeapT<CData> bh(max_items);

    13

		CFixedSizeArrayT<CData, max_items> data;

    14

    15

    16

		DBG("\nFilling BinaryHeap with %d items...", max_items);

    17

		CHECK_INT(0, bh.Size(), 0);

    18

		CHECK_INT(1, CData::NumInstances(), 0);

    19

		int i = 0;

    20

		for (; i < max_items; i++) {

    21

			CData& d = data.Add();

    22

			d.val = rand() & 0xFFFF;

    23

			bh.Push(d);

    24

		}

    25

		CHECK_INT(2, bh.Size(), max_items);

    26

		CHECK_INT(3, CData::NumInstances(), max_items);

    27

    28

    29

		DBG("\nShaking items %d times...", total_adds);

    30

		int num_last = bh.GetHead().val;

    31

		for (i = 0; i < total_adds; i++) {

    32

			CData& d = bh.PopHead();

    33

			//printf("\nd->val = %d, num_last = %d", d->val, num_last);

    34

			CHECK_INT(4, d.val < num_last, 0);

    35

			if(d.val < num_last) {

    36

				printf("Sort error @ item %d", i);

    37

			}

    38

			num_last = d.val;

    39

			d.val += rand() & 0xFFFF;

    40

			bh.Push(d);

    41

		}

    42

    43

    44

		DBG("\nDone!");

    45

		CHECK_INT(5, bh.Size(), max_items);

    46

		CHECK_INT(6, CData::NumInstances(), max_items);

    47

	}

    48

	CHECK_INT(7, CData::NumInstances(), 0);

    49

	return res;

    50

}

    51

    52

    53

    54

// this test uses CData and PData structures defined in test_autocopyptr.h

    55

    56

static int TestBinaryHeap2(bool silent)

    57

{

    58

	CData::NumInstances() = 0;

    59

	int res = 0;

    60

	{

    61

		const int max_items = 10000;

    62

		const int total_adds = 1000000;

    63

		CBinaryHeapT<CData> bh(max_items);

    64

		CFixedSizeArrayT<CData, max_items> data;

    65

    66

    67

		DBG("\nFilling BinaryHeap with %d items...", max_items);

    68

		CHECK_INT(0, bh.Size(), 0);

    69

		CHECK_INT(1, CData::NumInstances(), 0);

    70

		int i = 0;

    71

		for (; i < max_items; i++) {

    72

			CData& d = data.Add();

    73

			d.val = rand() & 0xFFFF;

    74

			bh.Push(d);

    75

		}

    76

		CHECK_INT(2, bh.Size(), max_items);

    77

		CHECK_INT(3, CData::NumInstances(), max_items);

    78

    79

    80

		DBG("\nShaking items %d times...", total_adds);

    81

		int num_last = bh.GetHead().val;

    82

		for (i = 0; i < total_adds; i++) {

    83

			CData& d = bh.GetHead();

    84

			bh.RemoveHead();

    85

			//printf("\nd->val = %d, num_last = %d", d->val, num_last);

    86

			CHECK_INT(4, d.val < num_last, 0);

    87

			if(d.val < num_last) {

    88

				printf("Sort error @ item %d", i);

    89

			}

    90

			num_last = d.val;

    91

			d.val += rand() & 0xFFFF;

    92

			bh.Push(d);

    93

		}

    94

    95

    96

		DBG("\nDone!");

    97

		CHECK_INT(5, bh.Size(), max_items);

    98

		CHECK_INT(6, CData::NumInstances(), max_items);

    99

	}

   100

	CHECK_INT(7, CData::NumInstances(), 0);

   101

	return res;

   102

}