SearchablePrefixSums.hpp

Go to the documentation of this file.

/*
 * Sux: Succinct data structures
 *
 * Copyright (C) 2019-2020 Stefano Marchini
 *
 *  This library is free software; you can redistribute it and/or modify it
 *  under the terms of the GNU Lesser General Public License as published by the Free
 *  Software Foundation; either version 3 of the License, or (at your option)
 *  any later version.
 *
 * This library 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; either version 3, or (at your option) any later version.
 *
 * This library 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.
 *
 * Under Section 7 of GPL version 3, you are granted additional permissions
 * described in the GCC Runtime Library Exception, version 3.1, as published by
 * the Free Software Foundation.
 *
 * You should have received a copy of the GNU General Public License and a copy of
 * the GCC Runtime Library Exception along with this program; see the files
 * COPYING3 and COPYING.RUNTIME respectively.  If not, see
 * <http://www.gnu.org/licenses/>.
 */
 
#pragma once
 
#include <cstddef>
#include <cstdint>
 
namespace sux::util {
 
using namespace std;
 
class SearchablePrefixSums {
 
  public:
    virtual ~SearchablePrefixSums() = default;
 
    virtual uint64_t prefix(size_t length) = 0;
 
    virtual void add(size_t idx, int64_t c) = 0;
 
    virtual size_t find(uint64_t *val) = 0;
    size_t find(uint64_t val) { return find(&val); }
 
    virtual size_t compFind(uint64_t *val) = 0;
    size_t compFind(uint64_t val) { return compFind(&val); }
 
    virtual void push(uint64_t val) = 0;
 
    virtual void pop() = 0;
 
    virtual size_t size() const = 0;
 
    virtual size_t bitCount() const = 0;
};
 
} // namespace sux::util