1 //////////////////////////////////////////////////////////////////////////////
4 // ADLib, Prop and their related set of tools and documentation are in the
5 // public domain. The author(s) of this software reserve no copyrights on
6 // the source code and any code generated using the tools. You are encouraged
7 // to use ADLib and Prop to develop software, in both academic and commercial
8 // settings, and are free to incorporate any part of ADLib and Prop into
11 // Although you are under no obligation to do so, we strongly recommend that
12 // you give away all software developed using our tools.
14 // We also ask that credit be given to us when ADLib and/or Prop are used in
15 // your programs, and that this notice be preserved intact in all the source
18 // This software is still under development and we welcome any suggestions
19 // and help from the users.
23 //////////////////////////////////////////////////////////////////////////////
25 #ifndef hash_table_based_bag_h
26 #define hash_table_based_bag_h
28 ////////////////////////////////////////////////////////////////////////////
29 // Bag (or Multisets) derived from a hash table
30 ////////////////////////////////////////////////////////////////////////////
31 #include <AD/contain/bag.h> // Generic bags
33 template<class T
, class H
>
34 class HashBag
: public Bag
<T
> {
39 //////////////////////////////////////////////////////////////////////
41 //////////////////////////////////////////////////////////////////////
43 typedef Super::Element Element
;
45 //////////////////////////////////////////////////////////////////////
46 // Constructors and destructor
47 //////////////////////////////////////////////////////////////////////
48 HashBag(int size
= Collection_default_size
) : bag(size
) {}
49 HashBag(const HashBag
& b
) : Bag
<T
>(b
.size()), bag(b
.bag
) {}
50 HashBag(const Bag
<T
>& b
) : bag(b
.size()) { *this = b
; }
53 //////////////////////////////////////////////////////////////////////
55 //////////////////////////////////////////////////////////////////////
56 // void operator = (const Bag<T>& b); // inherit
57 void operator = (const HashBag
<T
,H
>& b
) { *this = (Bag
<T
>&)b
; }
59 //////////////////////////////////////////////////////////////////////
61 // size() return the number of elements within the bag.
62 // capacity() return the current capacity.
63 // is_empty() is the bag empty?
64 // contains() does the bag contains the said element
65 // count() returns the number of occurance of an element.
66 //////////////////////////////////////////////////////////////////////
67 // int size() const; // inherited
68 // Bool is_empty() const; // inherited
69 inline int capacity() const { return bag
.capacity(); }
70 inline Ix
lookup(const T
& e
) const { return bag
.lookup(e
); }
71 inline Bool
contains(const T
& e
) const { return bag
.contains(e
); }
72 inline int count(const T
& e
) const
73 { Ix i
; return (i
= bag
.lookup(e
)) ? 0 : bag
.value(i
); }
75 //////////////////////////////////////////////////////////////////////
76 // In place multiset operations
77 //////////////////////////////////////////////////////////////////////
78 inline void clear() { bag
.clear(); tally
= 0; }
79 Ix
insert(const T
& e
, int count
);
80 Bool
remove(const T
& e
, int count
);
81 // Ix insert(const T& e); // inherited
82 // Bool remove(const T& e); // inherited
83 // void Union (const Bag<T>&); // inherited
84 // void Difference (const Bag<T>&); // inherited
86 //////////////////////////////////////////////////////////////////////
88 //////////////////////////////////////////////////////////////////////
89 inline Ix
first() const { return bag
.first(); }
90 inline Ix
next(Ix i
) const { return bag
.next(i
); }
91 inline const T
& operator () (Ix i
) const { return (T
&)bag
.key(i
); }
92 inline T
& operator () (Ix i
) { return (T
&)bag
.key(i
); }
93 inline int occurrence(Ix i
) const { return bag
.value(i
); }
95 //////////////////////////////////////////////////////////////////////
97 //////////////////////////////////////////////////////////////////////
98 const char * myName() const { return "HashBag"; }
101 //////////////////////////////////////////////////////////////////////
102 // Insert a new element into the bag
103 //////////////////////////////////////////////////////////////////////
104 template <class T
, class H
>
105 Ix HashBag
<T
, H
>::insert(const T
& e
, int n
)
106 { Ix total
= bag
.lookup(e
);
107 if (total
) bag
.value(total
) += n
; else total
= bag
.insert(e
,n
);
112 //////////////////////////////////////////////////////////////////////
114 //////////////////////////////////////////////////////////////////////
115 template <class T
, class H
>
116 Bool HashBag
<T
, H
>::remove(const T
& e
, int n
)
117 { Ix total
= bag
.lookup(e
);
119 if (bag
.value(total
) > n
) { bag
.value(total
) -= n
; tally
-= n
; }
120 else { tally
-= bag
.value(total
); bag
.remove(e
); }