nlib
Louds.h
Go to the documentation of this file.
1 
2 /*--------------------------------------------------------------------------------*
3  Project: CrossRoad
4  Copyright (C)Nintendo All rights reserved.
5 
6  These coded instructions, statements, and computer programs contain proprietary
7  information of Nintendo and/or its licensed developers and are protected by
8  national and international copyright laws. They may not be disclosed to third
9  parties or copied or duplicated in any form, in whole or in part, without the
10  prior written consent of Nintendo.
11 
12  The content herein is highly confidential and should be handled accordingly.
13  *--------------------------------------------------------------------------------*/
14 
15 #pragma once
16 #ifndef INCLUDE_NN_NLIB_SUCCINCT_LOUDS_H_
17 #define INCLUDE_NN_NLIB_SUCCINCT_LOUDS_H_
18 
19 #include <utility>
20 #include "nn/nlib/Swap.h"
21 #include "nn/nlib/succinct/Sbv.h"
22 
23 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
24 #undef NLIB_VIS_PUBLIC
25 #define NLIB_VIS_PUBLIC NLIB_WINEXPORT
26 #endif
27 
28 NLIB_NAMESPACE_BEGIN
29 namespace succinct {
30 
32  public:
35 #ifdef __cpp_rvalue_references
36  Louds(Louds&& rhs) NLIB_NOEXCEPT : sbv_(std::move(rhs.sbv_)) {}
38  sbv_ = std::move(rhs.sbv_);
39  return *this;
40  }
41 #endif
42  Louds(Louds& rhs, move_tag) NLIB_NOEXCEPT // NOLINT
43  : sbv_(rhs.sbv_, move_tag()) {}
44  Louds& assign(Louds& rhs, move_tag) NLIB_NOEXCEPT { // NOLINT
45  sbv_.assign(rhs.sbv_, move_tag());
46  return *this;
47  }
48  NLIB_DEPRECATED void swap(Louds& rhs) NLIB_NOEXCEPT { // NOLINT
49  using std::swap;
50  swap(sbv_, rhs.sbv_);
51  }
52  template <class TREEITER>
53  bool Init(TREEITER& iter, uint32_t num_nodes) NLIB_NOEXCEPT; // NOLINT
54 
55  bool InitDirect(const uint32_t* bv, uint32_t bv_size) NLIB_NOEXCEPT;
56  int ToNodeId(uint32_t pos) const NLIB_NOEXCEPT;
57  int ToPos(uint32_t nodeid) const NLIB_NOEXCEPT;
58  int FirstChild(uint32_t pos) const NLIB_NOEXCEPT;
59  int NextSibling(uint32_t pos) const NLIB_NOEXCEPT;
60  int PrevSibling(uint32_t pos) const NLIB_NOEXCEPT;
61  int Parent(uint32_t pos) const NLIB_NOEXCEPT;
62  bool IsLeaf(uint32_t pos) const NLIB_NOEXCEPT {
63  return this->FirstChild(pos) < 0;
64  }
65  size_t MemSize() const NLIB_NOEXCEPT { return sbv_.MemSize(); }
66  void Reset() NLIB_NOEXCEPT { sbv_.Reset(); }
67  bool Export(BinaryWriter* w) const NLIB_NOEXCEPT { return sbv_.Export(w); }
68  bool Import(BinaryReader* r) NLIB_NOEXCEPT { return sbv_.Import(r); }
69 
70  private:
71  Sbv sbv_;
73 };
74 
75 template <class TREEITER>
76 bool Louds::Init(TREEITER& iter, uint32_t num_nodes) NLIB_NOEXCEPT { // NOLINT
77  // TREEITER has following methods:
78  // int GetNumChildren();
79  // bool BfsMoveNext(); // move to the next node by breadth first search
80  sbv_.Init(2 * num_nodes + 1);
81 
82  // diffrent from the Louds paper: reversed bits
83  sbv_.TurnOn(1);
84  uint32_t idx = 2; // consider super-root 01
85  do {
86  idx += iter.GetNumChildren();
87  sbv_.TurnOn(idx++);
88  } while (iter.BfsMoveNext());
89 
90  NLIB_ASSERT(idx == 2 * num_nodes + 1);
91  if (!sbv_.Build()) {
92  sbv_.Reset();
93  return false;
94  }
95  return true;
96 }
97 
98 } // namespace succinct
99 NLIB_NAMESPACE_END
100 
101 NLIB_DEFINE_STD_SWAP(::nlib_ns::succinct::Louds)
102 
103 #if defined(_MSC_VER) && defined(nx_succinct_EXPORTS)
104 #undef NLIB_VIS_PUBLIC
105 #define NLIB_VIS_PUBLIC NLIB_WINIMPORT
106 #endif
107 
108 #endif // INCLUDE_NN_NLIB_SUCCINCT_LOUDS_H_
Defines the basic classes that form the basis to Rank and Select operations.
bool Export(BinaryWriter *w) const noexcept
Writes the object to the file.
Definition: Louds.h:67
constexpr Louds() noexcept
Instantiates the object.
Definition: Louds.h:33
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
Prohibits use of the copy constructor and assignment operator for the class specified by TypeName...
Definition: Config.h:179
Succinct data structure to hold a set of 32-bit unsigned integers for a Rank/Select operation...
Definition: Sbv.h:73
Louds & operator=(Louds &&rhs) noexcept
Move assignment operator. This function is useful when using C++11.
Definition: Louds.h:37
Louds & assign(Louds &rhs, move_tag) noexcept
Corresponds to a move assignment operator.
Definition: Louds.h:44
size_t MemSize() const noexcept
Returns the amount of memory explicitly allocated by the class.
Definition: Louds.h:65
#define NLIB_DEPRECATED
Indicates that a function or something has been deprecated.
Definition: Config.h:109
bool Import(BinaryReader *r) noexcept
Reads the written object.
Definition: Louds.h:68
#define NLIB_VIS_PUBLIC
Symbols for functions and classes are made available outside of the library.
Definition: Platform_unix.h:89
void swap(Louds &rhs) noexcept
Swaps the contents of an object.
Definition: Louds.h:48
An empty structure indicating that an argument to a function needs to be moved.
Definition: Config.h:265
Louds(Louds &rhs, move_tag) noexcept
Corresponds to a move constructor.
Definition: Louds.h:42
~Louds() noexcept
Destructor.
Definition: Louds.h:34
#define NLIB_NOEXCEPT
Defines noexcept geared to the environment, or the equivalent.
Definition: Config.h:105
#define NLIB_CEXPR
Defines constexpr if it is available for use. If not, holds an empty string.
Definition: Config.h:107
void Reset() noexcept
Returns the object to the state immediately after the constructor is called.
Definition: Louds.h:66
bool IsLeaf(uint32_t pos) const noexcept
Determines whether the specified node is a leaf (or external) node.
Definition: Louds.h:62
Provides a compact tree structure that can provide various operations in constant time...
Definition: Louds.h:31
The class for writing binary to streams (to OutputStream).
Definition: BinaryWriter.h:26
#define NLIB_FINAL
Defines final if it is available for use. If not, holds an empty string.
Definition: Config.h:245
The class for reading binary from streams (from InputStream).
Definition: BinaryReader.h:26
Louds(Louds &&rhs) noexcept
Instantiates the object (move constructor). This function is useful when using C++11.
Definition: Louds.h:36