Comments (2)
@andrej-sajenko Do you still have the java implementation of this feature available on gitlab/github?
from sea.
Yes I do. Albeit it is clear, however, I will mention it: we implement only the n + O(log n) bit version.
package de.thm.mni.sea.collection;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import javafx.beans.property.IntegerProperty;
import javafx.beans.property.SimpleIntegerProperty;
/**
* Instant initializable array. Array of an specific length and a init value which
* initialize the array in constant time.
*
* @author Andrej Sajenko
*/
public class InitArray {
private IntegerProperty A[];
private IntegerProperty b = new SimpleIntegerProperty(0);
private int initv;
private ArrayList<ChainListener> chainListeners = new ArrayList<>();
/**
* @param length The array length
* @param initv The initial value
*/
public InitArray(int length, int initv) {
A = new IntegerProperty[length % 2 == 0 ? length : length + 1];
this.initv = initv;
// Randomize
Random random = new Random();
for (int i = 0; i < A.length; i++) {
A[i] = new SimpleIntegerProperty(random.nextInt(A.length));
}
}
/**
* @return The array length
*/
public int length() {
return A.length;
}
@Override
public String toString() {
return "InitArray{" +
"\n\tA = " + Arrays.toString(A) +
"\n\tb = " + b +
"\n\tinitv = " + initv +
"\n}";
}
/**
* Reset the complete array to a new initial value.
*
* @param value new value
*/
public void init(int value) {
b.set(0);
this.initv = value;
}
/**
* Read the i^th value of the array.
*
* @param i index
* @return The value under index i
*/
public int read(int i) {
int _i = i / 2;
int k = chainWith(_i);
if (i < 2 * b.get()) {
if (k != NONE) {
return this.initv;
} else {
return A[i].get();
}
} else {
if (k != NONE) {
if (i % 2 == 0) {
return A[A[i].get() + 1].get();
} else {
return A[i].get();
}
} else {
return this.initv;
}
}
}
/**
* Write a new value under the index i
*
* @param i index
* @param value value to write
*/
public void write(int i, int value) {
int _i = i / 2;
int k = chainWith(_i);
if (_i < b.get()) {
if (k == NONE) {
setA(i, value);
breakChain(_i);
} else {
int j = extend();
if (_i == j) {
setA(i, value);
breakChain(_i);
} else {
setA(2 * j, A[2 * _i].get());
setA(2 * j + 1, A[2 * _i + 1].get());
makeChain(j, k);
initBlock(_i);
setA(i, value);
breakChain(_i);
}
}
} else {
if (k != NONE) {
if (i % 2 == 0) {
setA(2 * k + 1, value);
} else {
setA(i, value);
}
} else {
k = extend();
if (_i == k) {
setA(i, value);
breakChain(_i);
} else {
initBlock(_i);
makeChain(k, _i);
if (i % 2 == 0) {
setA(2 * k + 1, value);
} else {
setA(i, value);
}
}
}
}
}
// tools
private final int NONE = -1;
private int chainWith(int i) {
int _k = A[2 * i].get();
int k = _k / 2;
if (_k % 2 == 0 && _k >= 0
&& _k < A.length && A[_k].get() == 2 * i
&& ((i < b.get() && b.get() <= k) || (k < b.get() && b.get() <= i))) {
return k;
}
return NONE;
}
private void makeChain(int i, int j) {
setA(2 * i, 2 * j);
setA(2 * j, 2 * i);
this.chainListeners.forEach(listener -> listener.onMakeChain(i, j));
}
private void breakChain(int i) {
int k = chainWith(i);
if (k != NONE) {
setA(2 * k, 2 * k);
this.chainListeners.forEach(listener -> listener.onBreakChain(k));
}
}
private void initBlock(int i) {
setA(2 * i, initv);
setA(2 * i + 1, initv);
}
private int extend() {
int k = chainWith(b.get());
b.set(b.get() + 1);
this.chainListeners.forEach(listener -> listener.onBreakChain(b.get() - 1));
if (k == NONE) {
k = b.get() - 1;
} else {
setA(2 * (b.get() - 1), A[2 * k + 1].get());
// setA(2 * (b.get() - 1) + 1, A[2 * b.get() + 1].get()); Not Needed
breakChain(b.get() - 1);
}
initBlock(k);
breakChain(k);
return k;
}
private void setA(int i, int v) {
A[i].set(v);
}
public void registerChainListener(ChainListener listener) {
this.chainListeners.add(listener);
}
public void innerBindAi(int i, IntegerProperty p) {
p.bind(A[i]);
}
public void innerBindB(IntegerProperty p) {
p.bind(b);
}
}
from sea.
Related Issues (20)
- Rank-Select
- Visualisation
- Linear Time DFS HOT 1
- Hierholzer's Algorithm
- Ignore external files from coverage results HOT 1
- Improve the doc comments. HOT 1
- Expand Bitset HOT 5
- iterator_test.cpp fails HOT 12
- g++ linker errors HOT 2
- Master is not up to date HOT 1
- Implement rvalue constructors, rvalue assignment and the move function for all container classes HOT 3
- bfs_test.cpp fails HOT 2
- Master Failed
- Import/Export to the DIMACS graph file format
- BFS_Test fails when using gcc compiler instead of CLang HOT 1
- Implement new space-efficient graph representation
- Implement improved rank/select structure
- Move to atleast c++17, better c++20
- Refactor to a header-only library
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from sea.