summaryrefslogtreecommitdiffstats
path: root/storage/oqgraph/oqgraph_judy.h
blob: 53bb47069673a708729baf374eb32c3a2b200286 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
/* Copyright (C) 2007-2013 Arjen G Lentz & Antony T Curtis for Open Query

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA */

/* ======================================================================
   Open Query Graph Computation Engine, based on a concept by Arjen Lentz
   v3 implementation by Antony Curtis, Arjen Lentz, Andrew McDonnell
   For more information, documentation, support, enhancement engineering,
   see http://openquery.com/graph or contact graph@openquery.com
   ======================================================================
*/

#pragma once

#include <cstddef>

namespace open_query
{

  class judy_bitset
  {
  public:
    typedef std::size_t size_type;
    enum { npos = (size_type) -1 };

    judy_bitset()
      : array(0)
    { }

    judy_bitset(const judy_bitset& src)
      : array(0)
    {
      set(src);
    }

    ~judy_bitset()
    { clear(); }

    judy_bitset& operator=(const judy_bitset& src)
    {
      clear();
      return set(src);
    }

    void clear();
    bool empty() const { return !array; }
    bool none() const { return npos == find_first(); }

    inline judy_bitset& set(size_type n, bool val = true)
    {
      if (!val)
        return reset(n);
      else
        return setbit(n);
    }

    judy_bitset& set(const judy_bitset& src);

    judy_bitset& reset(size_type n);
    judy_bitset& flip(size_type n);
    bool test(size_type) const;
    size_type count() const;
    size_type size() const;
    size_type num_blocks() const;

    class reference
    {
      friend class judy_bitset;
      reference(judy_bitset& array, size_type pos)
        : j(array)
        , n(pos)
      { }
      void operator&(); // not defined
    public:
      reference& operator=(bool value)
      { j.set(n, value); return *this; }
      reference& operator=(const reference& ref)
      { j.set(n, ref); return *this; }

      reference& operator|=(bool value)
      { if (value) j.set(n); return *this; }
      reference& operator&=(bool value)
      { if (!value) j.reset(n); return *this; }
      reference& operator^=(bool value)
      { if (value) j.flip(n); return *this; }
      reference& operator-=(bool value)
      { if (value) j.reset(n); return *this; }

      bool operator~() const { return !j.test(n); }
      operator bool() const { return j.test(n); }
      reference& flip() { j.flip(n); return *this; }

    private:
      judy_bitset& j;
      size_type n;
    };

    reference operator[](size_type n) { return reference(*this, n); }
    bool operator[](size_type n) const { return test(n); }

    size_type find_first() const;
    size_type find_next(size_type n) const;
  private:
    mutable void* array;

    judy_bitset& setbit(size_type n);
  };
}