1 package org.simantics.datatypes.utils;
3 import java.io.ByteArrayInputStream;
4 import java.io.DataInput;
5 import java.io.DataOutput;
6 import java.io.IOException;
7 import java.util.ArrayList;
8 import java.util.Collection;
9 import java.util.HashMap;
10 import java.util.IdentityHashMap;
11 import java.util.List;
15 import org.simantics.databoard.Bindings;
16 import org.simantics.databoard.accessor.reference.ChildReference;
17 import org.simantics.databoard.binding.Binding;
18 import org.simantics.databoard.binding.error.BindingException;
19 import org.simantics.databoard.binding.error.RuntimeBindingConstructionException;
20 import org.simantics.databoard.binding.impl.BindingPrintContext;
21 import org.simantics.databoard.binding.mutable.Variant;
22 import org.simantics.databoard.serialization.RuntimeSerializerConstructionException;
23 import org.simantics.databoard.serialization.Serializer;
24 import org.simantics.databoard.util.IdentityPair;
25 import org.simantics.datatypes.DatatypeResource;
26 import org.simantics.db.ReadGraph;
27 import org.simantics.db.Resource;
28 import org.simantics.db.WriteGraph;
29 import org.simantics.db.common.primitiverequest.RelatedValue;
30 import org.simantics.db.common.procedure.adapter.TransientCacheListener;
31 import org.simantics.db.common.utils.Logger;
32 import org.simantics.db.exception.DatabaseException;
33 import org.simantics.db.service.Bytes;
34 import org.simantics.db.service.SerialisationSupport;
35 import org.simantics.db.service.XSupport;
36 import org.simantics.layer0.Layer0;
37 import org.simantics.scl.runtime.tuple.Tuple2;
38 import org.simantics.utils.datastructures.Pair;
40 import gnu.trove.list.array.TByteArrayList;
41 import gnu.trove.map.hash.TObjectIntHashMap;
44 * Implementation from http://www.geeksforgeeks.org/b-tree-set-3delete/
48 interface BTreeContentManager {
50 BTreeContentBean getContentBean(ReadGraph graph, Resource node) throws DatabaseException;
51 void setContentBean(WriteGraph graph, Resource node, BTreeContentBean bean) throws DatabaseException;
55 class PossibleVariantInputStream extends ByteArrayInputStream {
57 PossibleVariantInputStream(byte[] data, int offset) {
58 super(data, offset, data.length-offset);
61 public int getOffset() {
67 class BTreeContentBinding extends Binding {
69 private final SerialisationSupport ss;
70 private final XSupport xs;
72 public BTreeContentBinding(SerialisationSupport ss, XSupport xs) {
77 private final Serializer serializer = new Serializer() {
80 public void serialize(DataOutput out, TObjectIntHashMap<Object> identities, Object obj) throws IOException {
81 throw new UnsupportedOperationException();
85 public void serialize(DataOutput out, Object obj) throws IOException {
86 byte[] data = serialize(obj);
91 public Object deserialize(DataInput in, List<Object> identities)
93 throw new UnsupportedOperationException();
97 public Object deserialize(DataInput in) throws IOException {
98 throw new UnsupportedOperationException();
102 public void deserializeTo(DataInput in, List<Object> identities,
103 Object dst) throws IOException {
104 throw new UnsupportedOperationException();
108 public void deserializeTo(DataInput in, Object dst) throws IOException {
109 throw new UnsupportedOperationException();
113 public void skip(DataInput in, List<Object> identities)
115 throw new UnsupportedOperationException();
119 public void skip(DataInput in) throws IOException {
120 throw new UnsupportedOperationException();
124 public Integer getConstantSize() {
125 throw new UnsupportedOperationException();
129 public int getSize(Object obj, TObjectIntHashMap<Object> identities)
131 throw new UnsupportedOperationException();
135 public int getSize(Object obj) throws IOException {
136 return serialize(obj).length;
140 public int getMinSize() {
141 throw new UnsupportedOperationException();
144 private void addBE(TByteArrayList bytes, int value) {
146 bytes.add((byte) ((value >>> 24) & 0xFF));
147 bytes.add((byte) ((value >>> 16) & 0xFF));
148 bytes.add((byte) ((value >>> 8) & 0xFF));
149 bytes.add( (byte) (value & 0xFF));
153 private void addBE(TByteArrayList bytes, long value) {
155 bytes.add((byte) ((value >>> 56) & 0xFF));
156 bytes.add((byte) ((value >>> 48) & 0xFF));
157 bytes.add((byte) ((value >>> 40) & 0xFF));
158 bytes.add((byte) ((value >>> 32) & 0xFF));
159 bytes.add((byte) ((value >>> 24) & 0xFF));
160 bytes.add((byte) ((value >>> 16) & 0xFF));
161 bytes.add((byte) ((value >>> 8) & 0xFF));
162 bytes.add( (byte) (value & 0xFF));
166 public byte[] serialize(Object obj) throws IOException {
167 BTreeContentBean bean = (BTreeContentBean)obj;
168 TByteArrayList bytes = new TByteArrayList();
169 bytes.add(bean.leaf ? (byte)1 : (byte)0);
170 addBE(bytes, bean.n);
171 //addLE(bytes, (bean.key.length+1)/2);
172 Binding pbv = PossibleVariant.BINDING;
173 Serializer pbs = pbv.serializer();
174 addBE(bytes, bean.key.length);
175 for(PossibleVariant l : bean.key) {
176 byte[] ser = pbs.serialize(l);
179 addBE(bytes, bean.value.length);
180 for(PossibleResource pr : bean.value) {
183 addBE(bytes, xs.convertDelayedResourceToResource(pr.r).getResourceId());
188 addBE(bytes, bean.c.length);
189 for(PossibleResource pr : bean.c) {
192 addBE(bytes, xs.convertDelayedResourceToResource(pr.r).getResourceId());
197 return bytes.toArray();
200 int readBE4(byte[] bytes, int byteIndex) {
202 (((int)(bytes[byteIndex++] & 0xff))<<24) |
203 (((int)(bytes[byteIndex++] & 0xff))<<16) |
204 (((int)(bytes[byteIndex++] & 0xff))<<8) |
205 (((int)(bytes[byteIndex++] & 0xff)));
209 long readBE8(byte[] bytes, int byteIndex) {
211 (((long)(bytes[byteIndex++] & 0xff))<<56) |
212 (((long)(bytes[byteIndex++] & 0xff))<<48) |
213 (((long)(bytes[byteIndex++] & 0xff))<<40) |
214 (((long)(bytes[byteIndex++] & 0xff))<<32) |
215 (((long)(bytes[byteIndex++] & 0xff))<<24) |
216 (((long)(bytes[byteIndex++] & 0xff))<<16) |
217 (((long)(bytes[byteIndex++] & 0xff))<<8) |
218 (((long)(bytes[byteIndex++] & 0xff)));
222 public Object deserialize(byte[] data) throws IOException {
224 BTreeContentBean result = new BTreeContentBean();
228 result.leaf = (data[0] == 1) ? true : false;
230 result.n = readBE4(data, byteIndex);
233 Binding pbv = PossibleVariant.BINDING;
234 Serializer pbs = pbv.serializer();
236 // Redundant array size
237 int keySize = readBE4(data, byteIndex);
238 result.key = new PossibleVariant[keySize];
240 for(int i=0;i<keySize;i++) {
241 PossibleVariantInputStream is = new PossibleVariantInputStream(data, byteIndex);
242 PossibleVariant v = (PossibleVariant)pbs.deserialize(is);
244 byteIndex = is.getOffset();
247 // Redundant array size
248 int valueSize = readBE4(data, byteIndex);
249 result.value = new PossibleResource[valueSize];
251 for(int i=0;i<valueSize;i++) {
252 boolean has = Bytes.read(data, byteIndex++) > 0;
254 result.value[i] = PossibleResource.read(ss, readBE8(data, byteIndex));
257 result.value[i] = new PossibleResource();
261 // Redundant array size
262 int childSize = readBE4(data, byteIndex);
263 result.c = new PossibleResource[childSize];
265 for(int i=0;i<childSize;i++) {
266 boolean has = Bytes.read(data, byteIndex++) > 0;
268 result.c[i] = PossibleResource.read(ss, readBE8(data, byteIndex));
271 result.c[i] = new PossibleResource();
275 } catch (DatabaseException e) {
288 public void accept(Visitor1 v, Object obj) {
289 throw new UnsupportedOperationException();
293 public <T> T accept(Visitor<T> v) {
294 throw new UnsupportedOperationException();
298 public boolean isInstance(Object obj) {
299 throw new UnsupportedOperationException();
303 public void readFrom(Binding srcBinding, Object src, Object dst)
304 throws BindingException {
305 throw new UnsupportedOperationException();
309 public void assertInstaceIsValid(Object obj, Set<Object> validInstances)
310 throws BindingException {
311 throw new UnsupportedOperationException();
315 public int deepHashValue(Object value,
316 IdentityHashMap<Object, Object> hashedObjects)
317 throws BindingException {
318 throw new UnsupportedOperationException();
322 public int deepCompare(Object o1, Object o2,
323 Set<IdentityPair<Object, Object>> compareHistory)
324 throws BindingException {
325 throw new UnsupportedOperationException();
329 protected void toString(Object value, BindingPrintContext ctx)
330 throws BindingException {
331 throw new UnsupportedOperationException();
335 public int getComponentCount() {
336 throw new UnsupportedOperationException();
340 public Binding getComponentBinding(int index) {
341 throw new UnsupportedOperationException();
345 public Binding getComponentBinding(ChildReference path) {
346 throw new UnsupportedOperationException();
350 public Serializer serializer() throws RuntimeSerializerConstructionException {
356 final public class BTreeUtils implements BTreeContentManager {
358 final private Resource tree;
359 final private Resource ownerRelation;
361 final public Binding CONTENT_BEAN_BINDING;
362 final public DatatypeResource DATA;
366 private Map<Resource, BTreeContentBean> beans;
367 private Map<Resource, Resource> owners;
368 private Resource root;
369 private Resource nodeType;
370 private boolean cached;
372 public BTreeUtils(ReadGraph graph, Resource tree, int t, Resource nodeType, Resource ownerRelation, boolean cached) throws DatabaseException {
374 SerialisationSupport ss = graph.getService(SerialisationSupport.class);
375 XSupport xs = graph.getService(XSupport.class);
377 CONTENT_BEAN_BINDING = new BTreeContentBinding(ss, xs);
378 DATA = DatatypeResource.getInstance(graph);
380 this.ownerRelation = ownerRelation;
381 this.nodeType = nodeType != null ? nodeType : DATA.BTreeNode;
383 Long possibleMod = graph.getPossibleRelatedValue(tree, DATA.BTree_mod, Bindings.LONG);
384 this.mod = possibleMod != null ? possibleMod : 0;
385 this.cached = cached;
387 this.beans = new HashMap<Resource, BTreeContentBean>();
388 this.owners = new HashMap<Resource, Resource>();
390 } catch (RuntimeBindingConstructionException e) {
391 Logger.defaultLogError(e);
392 throw new DatabaseException(e);
396 public static BTreeUtils create(WriteGraph graph, Resource ownerRelation, int t, boolean cached) throws DatabaseException {
398 DatatypeResource DATA = DatatypeResource.getInstance(graph);
399 return create(graph, DATA.BTree, DATA.BTreeNode, ownerRelation, t, cached);
403 public static BTreeUtils create(WriteGraph graph, Resource type, Resource nodeType, Resource ownerRelation, int t, boolean cached) throws DatabaseException {
405 Layer0 L0 = Layer0.getInstance(graph);
406 DatatypeResource DATA = DatatypeResource.getInstance(graph);
407 Resource tree = graph.newResource();
408 graph.claim(tree, L0.InstanceOf, null, type);
410 if(ownerRelation != null)
411 graph.claim(tree, DATA.BTree_HasOwnerRelation, DATA.BTree_HasOwnerRelation_Inverse, ownerRelation);
413 graph.claim(tree, DATA.BTree_HasNodeType, DATA.BTree_HasNodeType_Inverse, nodeType);
415 graph.claimLiteral(tree, DATA.BTree_t, t, Bindings.INTEGER);
418 graph.claimLiteral(tree, DATA.BTree_mod, 0L, Bindings.LONG);
421 BTreeUtils utils = new BTreeUtils(graph, tree, t, nodeType, ownerRelation, cached);
422 Resource node = utils.createNode(graph, utils, t);
423 utils.setRoot(graph, node);
424 utils.setOwner(graph, node, tree, true);
429 public Resource getTree() {
433 public void insert(WriteGraph graph, Variant k, Resource v) throws DatabaseException {
435 Resource r = getRoot(graph);
436 insertImpl(graph, this, r, t, k, v);
440 static class BatchContentManager implements BTreeContentManager {
442 final private BTreeUtils bu;
444 final Map<Resource, BTreeContentBean> beans = new HashMap<Resource, BTreeContentBean>();
446 public BatchContentManager(BTreeUtils bu) {
451 public BTreeContentBean getContentBean(ReadGraph graph, Resource node) throws DatabaseException {
452 BTreeContentBean bean = beans.get(node);
453 if(bean != null) return bean;
454 return bu.getContentBean(graph, node);
458 public void setContentBean(WriteGraph graph, Resource node, BTreeContentBean bean) throws DatabaseException {
459 beans.put(node, bean);
462 public void apply(WriteGraph graph) throws DatabaseException {
463 for(Map.Entry<Resource, BTreeContentBean> entry : beans.entrySet()) {
464 bu.setContentBean(graph, entry.getKey(), entry.getValue());
470 public void insertAll(WriteGraph graph, Collection<Pair<Variant, Resource>> values) throws DatabaseException {
472 Resource r = getRoot(graph);
473 BatchContentManager cm = new BatchContentManager(this);
474 for(Pair<Variant, Resource> entry : values) {
475 insertImpl(graph, cm, r, t, entry.first, entry.second);
481 public Resource search(ReadGraph graph, Variant k) throws DatabaseException {
483 Resource r = getRoot(graph);
484 return searchNode(graph, r, k);
490 private int findKey(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, Variant k) throws DatabaseException {
493 while(idx<bean.n && bean.key[idx].v.compareTo(k) < 0)
499 private void insertImpl(WriteGraph graph, BTreeContentManager manager, Resource r, int t, Variant k, Resource v) throws DatabaseException {
501 BTreeContentBean rContent = manager.getContentBean(graph, r);
502 if(rContent.n == 2*t-1) {
503 Resource s = allocateNode(graph, manager, t);
504 BTreeContentBean sContent = manager.getContentBean(graph, s);
506 setOwner(graph, s, tree, true);
507 sContent.leaf = false;
510 setOwner(graph, r, s, true);
511 manager.setContentBean(graph, s, sContent);
512 splitChild(graph, manager, t, s, 1, r);
513 insertNonfull(graph, manager, t, s, k, v);
515 insertNonfull(graph, manager, t, r, k, v);
520 public void remove(WriteGraph graph, Variant k) throws DatabaseException {
522 Resource r = getRoot(graph);
524 BTreeContentBean bean = getContentBean(graph, r);
525 Resource removedResource = removeImpl(graph, this, t, r, bean, k);
526 if (removedResource != null) {
527 removeOwner(graph, removedResource, false);
529 // If the root node has 0 keys, make its first child as the new root
530 // if it has a child, otherwise set root as NULL
533 //BTreeContentBean tmp = bean;
535 removeOwner(graph, r, true);
536 setRoot(graph, bean.c[0].r);
537 setOwner(graph, bean.c[0].r, tree, true);
549 public Resource removeImpl(WriteGraph graph, BTreeContentManager manager, int t, Resource r, BTreeContentBean bean, Variant k) throws DatabaseException {
551 int idx = findKey(graph, manager, bean, k);
553 if(idx < bean.n && bean.key[idx].v.equals(k)) {
554 Resource removedResource = bean.value[idx].r;
556 removeFromLeaf(graph, manager, r, bean, idx);
558 removeFromNonLeaf(graph, manager, r, bean, t, idx);
560 return removedResource;
567 // The key to be removed is present in the sub-tree rooted with this node
568 // The flag indicates whether the key is present in the sub-tree rooted
569 // with the last child of this node
570 boolean flag = ( (idx==bean.n)? true : false );
572 BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx].r);
574 // If the child where the key is supposed to exist has less that t keys,
575 // we fill that child
577 fill(graph, manager, r, bean, t, idx);
579 // If the last child has been merged, it must have merged with the previous
580 // child and so we recurse on the (idx-1)th child. Else, we recurse on the
581 // (idx)th child which now has atleast t keys
582 if (flag && idx > bean.n)
583 return removeImpl(graph, manager, t, bean.c[idx-1].r, manager.getContentBean(graph, bean.c[idx-1].r), k);
585 return removeImpl(graph, manager, t, bean.c[idx].r, cContent, k);
592 // A function to get predecessor of keys[idx]
593 Pair<Variant, Resource> getPred(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, int idx) throws DatabaseException {
595 // Keep moving to the right most node until we reach a leaf
596 bean = manager.getContentBean(graph, bean.c[idx].r);
598 bean = manager.getContentBean(graph, bean.c[bean.n].r);
600 // Return the last key of the leaf
601 return new Pair<Variant, Resource>(bean.key[bean.n-1].v, bean.value[bean.n-1].r);
605 Pair<Variant, Resource> getSucc(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, int idx) throws DatabaseException {
607 // Keep moving the left most node starting from C[idx+1] until we reach a leaf
608 bean = manager.getContentBean(graph, bean.c[idx+1].r);
610 bean = manager.getContentBean(graph, bean.c[0].r);
612 // Return the first key of the leaf
613 return new Pair<Variant, Resource>(bean.key[0].v, bean.value[0].r);
617 // A function to fill child C[idx] which has less than t-1 keys
618 void fill(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int t, int idx) throws DatabaseException {
620 // If the previous child(C[idx-1]) has more than t-1 keys, borrow a key
623 BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx-1].r);
626 borrowFromPrev(graph, manager, r, bean, idx);
631 // If the next child(C[idx+1]) has more than t-1 keys, borrow a key
635 BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx+1].r);
638 borrowFromNext(graph, manager, r, bean, idx);
643 // Merge C[idx] with its sibling
644 // If C[idx] is the last child, merge it with with its previous sibling
645 // Otherwise merge it with its next sibling
647 merge(graph, manager, r, bean, t, idx);
649 merge(graph, manager, r, bean, t, idx-1);
652 // A function to borrow a key from C[idx-1] and insert it
654 void borrowFromPrev(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {
656 BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);
657 BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx-1].r);
659 // The last key from C[idx-1] goes up to the parent and key[idx-1]
660 // from parent is inserted as the first key in C[idx]. Thus, the loses
661 // sibling one key and child gains one key
663 // Moving all key in C[idx] one step ahead
664 for (int i=childContent.n-1; i>=0; --i) {
665 childContent.key[i+1].v = childContent.key[i].v;
666 childContent.value[i+1].r = childContent.value[i].r;
669 // If C[idx] is not a leaf, move all its child pointers one step ahead
670 if (!childContent.leaf) {
671 for(int i=childContent.n; i>=0; --i) {
672 childContent.c[i+1].r = childContent.c[i].r;
673 setOwner(graph, childContent.c[i+1].r, bean.c[idx].r, true);
677 // Setting child's first key equal to keys[idx-1] from the current node
678 childContent.key[0].v = bean.key[idx-1].v;
679 childContent.value[0].r = bean.value[idx-1].r;
681 // Moving sibling's last child as C[idx]'s first child
682 // TODO: is this correct?
684 Resource lastChild = siblingContent.c[siblingContent.n].r;
685 if (lastChild != null) {
686 childContent.c[0].r = lastChild;
687 setOwner(graph, childContent.c[0].r, bean.c[idx].r, true);
691 // Moving the key from the sibling to the parent
692 // This reduces the number of keys in the sibling
693 bean.key[idx-1].v = siblingContent.key[siblingContent.n-1].v;
694 bean.value[idx-1].r = siblingContent.value[siblingContent.n-1].r;
697 siblingContent.reduceSize();
698 //siblingContent.n -= 1;
700 manager.setContentBean(graph, r, bean);
701 manager.setContentBean(graph, bean.c[idx].r, childContent);
702 manager.setContentBean(graph, bean.c[idx-1].r, siblingContent);
706 // A function to borrow a key from the C[idx+1] and place
708 void borrowFromNext(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {
710 BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);
711 BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx+1].r);
713 // keys[idx] is inserted as the last key in C[idx]
714 childContent.key[childContent.n].v = bean.key[idx].v;
715 childContent.value[childContent.n].r = bean.value[idx].r;
717 // Sibling's first child is inserted as the last child
719 if (!childContent.leaf) {
720 childContent.c[childContent.n+1].r = siblingContent.c[0].r;
721 setOwner(graph, childContent.c[childContent.n+1].r, bean.c[idx].r, true);
724 //The first key from sibling is inserted into keys[idx]
725 bean.key[idx].v = siblingContent.key[0].v;
726 bean.value[idx].r = siblingContent.value[0].r;
728 // Moving all keys in sibling one step behind
729 for (int i=1; i<siblingContent.n; ++i) {
730 siblingContent.key[i-1].v = siblingContent.key[i].v;
731 siblingContent.value[i-1].r = siblingContent.value[i].r;
734 // Moving the child pointers one step behind
735 if (!siblingContent.leaf) {
736 for(int i=1; i<=siblingContent.n; ++i)
737 siblingContent.c[i-1].r = siblingContent.c[i].r;
740 // Increasing and decreasing the key count of C[idx] and C[idx+1]
743 siblingContent.reduceSize();
744 //siblingContent.n -= 1;
746 manager.setContentBean(graph, r, bean);
747 manager.setContentBean(graph, bean.c[idx].r, childContent);
748 manager.setContentBean(graph, bean.c[idx+1].r, siblingContent);
752 // A function to merge C[idx] with C[idx+1]
753 // C[idx+1] is freed after merging
754 void merge(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int t, int idx) throws DatabaseException {
756 BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);
757 BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx+1].r);
759 // Pulling a key from the current node and inserting it into (t-1)th
760 // position of C[idx]
761 childContent.key[t-1].v = bean.key[idx].v;
762 childContent.value[t-1].r = bean.value[idx].r;
764 // Copying the keys from C[idx+1] to C[idx] at the end
765 for (int i=0; i<siblingContent.n; ++i) {
766 childContent.key[i+t].v = siblingContent.key[i].v;
767 childContent.value[i+t].r = siblingContent.value[i].r;
770 // Copying the child pointers from C[idx+1] to C[idx]
771 if (!childContent.leaf) {
772 for(int i=0; i<=siblingContent.n; ++i) {
773 childContent.c[i+t].r = siblingContent.c[i].r;
774 setOwner(graph, childContent.c[i+t].r, bean.c[idx].r, true);
778 // Moving all keys after idx in the current node one step before -
779 // to fill the gap created by moving keys[idx] to C[idx]
780 for (int i=idx+1; i<bean.n; ++i) {
781 bean.key[i-1].v = bean.key[i].v;
782 bean.value[i-1].r = bean.value[i].r;
785 // Remove the owner of the merged sibling
786 removeOwner(graph, bean.c[idx+1].r, true);
788 // Moving the child pointers after (idx+1) in the current node one
790 for (int i=idx+2; i<=bean.n; ++i)
791 bean.c[i-1].r = bean.c[i].r;
793 // Updating the key count of child and the current node
794 childContent.n += siblingContent.n+1;
798 // Freeing the memory occupied by sibling
801 manager.setContentBean(graph, r, bean);
802 manager.setContentBean(graph, bean.c[idx].r, childContent);
806 private void removeOwner(WriteGraph graph, Resource r, boolean force) throws DatabaseException {
807 if((ownerRelation != null) || force) {
811 Resource own = ownerRelation != null ? ownerRelation : DATA.BTreeNode_IsOwnedBy;
817 private void removeFromLeaf(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {
819 // Move all the keys after the idx-th pos one place backward
820 for (int i=idx+1; i<bean.n; ++i) {
821 bean.key[i-1].v = bean.key[i].v;
822 bean.value[i-1].r = bean.value[i].r;
825 // Reduce the count of keys
829 manager.setContentBean(graph, r, bean);
833 private void removeFromNonLeaf(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int t, int idx) throws DatabaseException {
835 Variant k = bean.key[idx].v;
837 // If the child that precedes k (C[idx]) has atleast t keys,
838 // find the predecessor 'pred' of k in the subtree rooted at
839 // C[idx]. Replace k by pred. Recursively delete pred
842 BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx].r);
844 if (cContent.n >= t) {
846 Pair<Variant, Resource> pred = getPred(graph, manager, bean, idx);
847 bean.key[idx].v = pred.first;
848 bean.value[idx].r = pred.second;
849 removeImpl(graph, manager, t, bean.c[idx].r, cContent, pred.first);
851 manager.setContentBean(graph, r, bean);
854 BTreeContentBean cContentPlus1 = manager.getContentBean(graph, bean.c[idx+1].r);
856 // If the child C[idx] has less that t keys, examine C[idx+1].
857 // If C[idx+1] has atleast t keys, find the successor 'succ' of k in
858 // the subtree rooted at C[idx+1]
860 // Recursively delete succ in C[idx+1]
861 if (cContentPlus1.n >= t) {
862 Pair<Variant, Resource> succ = getSucc(graph, manager, bean, idx);
863 bean.key[idx].v = succ.first;
864 bean.value[idx].r = succ.second;
865 removeImpl(graph, manager, t, bean.c[idx+1].r, cContentPlus1, succ.first);
867 manager.setContentBean(graph, r, bean);
870 // If both C[idx] and C[idx+1] has less that t keys,merge k and all of C[idx+1]
872 // Now C[idx] contains 2t-1 keys
873 // Free C[idx+1] and recursively delete k from C[idx]
876 merge(graph, manager, r, bean, t, idx);
877 removeImpl(graph, manager, t, bean.c[idx].r, cContent, k);
885 private Resource createNode(WriteGraph graph, BTreeContentManager manager, int t) throws DatabaseException {
886 Layer0 L0 = Layer0.getInstance(graph);
887 Resource result = graph.newResource();
889 graph.claim(result, L0.InstanceOf, null, nodeType);
891 graph.claimLiteral(tree, DATA.BTree_mod, mod, Bindings.LONG);
893 graph.addLiteral(result, L0.HasName, L0.NameOf, ""+mod, Bindings.STRING);
894 manager.setContentBean(graph, result, BTreeContentBean.create(t));
898 public Resource searchNode(ReadGraph graph, Resource x, Variant k) throws DatabaseException {
900 BTreeContentBean xContent = getContentBean(graph, x);
903 while(i <= xContent.n && k.compareTo(xContent.key[i-1].v) > 0) i++;
904 if(i <= xContent.n && k.equals(xContent.key[i-1].v)) return xContent.value[i-1].r;
906 if(xContent.leaf) return null;
907 else return searchNode(graph, xContent.c[i-1].r, k);
911 private void splitChild(WriteGraph graph, BTreeContentManager manager, int t, Resource x, int i, Resource y) throws DatabaseException {
913 Resource z = allocateNode(graph, manager, t);
915 BTreeContentBean xContent = manager.getContentBean(graph, x);
916 BTreeContentBean yContent = manager.getContentBean(graph, y);
917 BTreeContentBean zContent = manager.getContentBean(graph, z);
919 zContent.leaf = yContent.leaf;
922 for(int j=1;j<=t-1;j++) {
923 zContent.key[j-1].v = yContent.key[j+t-1].v;
924 zContent.value[j-1].r = yContent.value[j+t-1].r;
925 setOwner(graph, zContent.value[j-1].r, z, false);
928 for(int j=1;j<=t;j++) {
929 zContent.c[j-1].r = yContent.c[j+t-1].r;
930 setOwner(graph, zContent.c[j-1].r, z, true);
937 for(int j=xContent.n+1;j>=i+1;j--) {
938 xContent.c[j+1-1].r = xContent.c[j-1].r;
941 xContent.c[i+1-1].r = z;
942 setOwner(graph, z, x, true);
944 for(int j=xContent.n;j>=i;j--) {
945 xContent.key[j+1-1].v = xContent.key[j-1].v;
946 xContent.value[j+1-1].r = xContent.value[j-1].r;
949 xContent.key[i-1].v = yContent.key[t-1].v;
950 xContent.value[i-1].r = yContent.value[t-1].r;
953 while (yContent.n > t-1) yContent.reduceSize();
955 setOwner(graph, xContent.value[i-1].r, x, true);
957 manager.setContentBean(graph, x, xContent);
958 manager.setContentBean(graph, y, yContent);
959 manager.setContentBean(graph, z, zContent);
963 private void insertNonfull(WriteGraph graph, BTreeContentManager manager, int t, Resource x, Variant k, Resource v) throws DatabaseException {
965 BTreeContentBean xContent = manager.getContentBean(graph, x);
970 while(i >= 1 && k.compareTo(xContent.key[i-1].v) < 0) {
971 xContent.key[i+1-1].v = xContent.key[i-1].v;
972 xContent.value[i+1-1].r = xContent.value[i-1].r;
976 xContent.key[i+1-1].v = k;
977 xContent.value[i+1-1].r = v;
979 setOwner(graph, v, x, false);
980 manager.setContentBean(graph, x, xContent);
982 while(i >= 1 && k.compareTo(xContent.key[i-1].v) < 0) i--;
984 BTreeContentBean xciContent = manager.getContentBean(graph, xContent.c[i-1].r);
985 if(xciContent.n == 2*t-1) {
986 splitChild(graph, manager, t, x, i, xContent.c[i-1].r);
987 xContent = manager.getContentBean(graph, x);
988 if(k.compareTo(xContent.key[i-1].v) > 0) i++;
990 insertNonfull(graph, manager, t, xContent.c[i-1].r, k, v);
995 private void setOwner(WriteGraph graph, Resource r, Resource owner, boolean force) throws DatabaseException {
997 if((ownerRelation != null) || force) {
998 Resource own = ownerRelation != null ? ownerRelation : DATA.BTreeNode_IsOwnedBy;
1000 owners.put(r, owner);
1003 graph.claim(r, own, owner);
1009 private Resource getRoot(ReadGraph graph) throws DatabaseException {
1011 if (root != null) return root;
1013 return graph.getPossibleObject(tree, DATA.BTree_root);
1016 private void setRoot(WriteGraph graph, Resource r) throws DatabaseException {
1020 graph.deny(tree, DATA.BTree_root);
1021 graph.claim(tree, DATA.BTree_root, r);
1025 private Resource allocateNode(WriteGraph graph, BTreeContentManager manager, int t) throws DatabaseException {
1026 return createNode(graph, manager, t);
1029 public void setContentBean(WriteGraph graph, Resource node, BTreeContentBean bean) throws DatabaseException {
1031 beans.put(node, bean);
1033 graph.claimLiteral(node, DATA.BTreeNode_content, DATA.BTreeNode_Content, bean, CONTENT_BEAN_BINDING );
1037 public void flushCache(WriteGraph graph) throws DatabaseException {
1040 XSupport xs = graph.getService(XSupport.class);
1041 for(Map.Entry<Resource, BTreeContentBean> entry : beans.entrySet()) {
1042 Resource node = xs.convertDelayedResourceToResource(entry.getKey());
1044 graph.claimLiteral(node, DATA.BTreeNode_content, DATA.BTreeNode_Content, entry.getValue(), CONTENT_BEAN_BINDING );
1048 for(Map.Entry<Resource, Resource> entry : owners.entrySet()) {
1049 Resource r = xs.convertDelayedResourceToResource(entry.getKey());
1050 Resource owner = xs.convertDelayedResourceToResource(entry.getValue());
1051 graph.deny(r, ownerRelation);
1052 if (owner != null) {
1053 graph.claim(r, ownerRelation, owner);
1057 Resource tree2 = xs.convertDelayedResourceToResource(tree);
1058 graph.claimLiteral(tree2, DATA.BTree_mod, mod, Bindings.LONG);
1061 Resource root2 = xs.convertDelayedResourceToResource(root);
1062 graph.deny(tree2, DATA.BTree_root);
1063 graph.claim(tree2, DATA.BTree_root, root2);
1067 public BTreeContentBean getContentBean(ReadGraph graph, Resource node) throws DatabaseException {
1069 BTreeContentBean bean = beans.get(node);
1070 if (bean != null) return bean;
1072 return graph.syncRequest(new RelatedValue<BTreeContentBean>(node, DATA.BTreeNode_content, CONTENT_BEAN_BINDING), TransientCacheListener.<BTreeContentBean>instance());
1075 public List<Tuple2> entries(ReadGraph graph) throws DatabaseException {
1076 Resource r = getRoot(graph);
1077 List<Tuple2> results = new ArrayList<Tuple2>();
1078 return collectEntries(graph, r, null, null, results);
1081 private List<Tuple2> collectEntries(ReadGraph graph, Resource x, Variant min, Variant max, List<Tuple2> results) throws DatabaseException {
1083 BTreeContentBean xContent = getContentBean(graph, x);
1085 for (int i = 0; i < xContent.n + 1; i++) {
1086 if (min != null && i < xContent.n && min.compareTo(xContent.key[i].v) > 0) continue;
1088 if (!xContent.leaf) {
1089 Resource child = xContent.c[i].r;
1090 if (child != null) {
1092 // reduce the amount of comparison if we know that the range of the child keys matches
1093 Variant min2 = (min != null && i > 0 && min.compareTo(xContent.key[i - 1].v) < 0) ? null : min;
1094 Variant max2 = (max != null && i < xContent.n - 1 && max.compareTo(xContent.key[i + 1].v) > 0) ? null : max;
1096 collectEntries(graph, child, min2, max2, results);
1100 if (i < xContent.n) {
1101 if (max != null && max.compareTo(xContent.key[i].v) < 0) return results;
1103 results.add(new Tuple2(xContent.key[i].v, xContent.value[i].r));
1109 public List<Tuple2> searchRange(ReadGraph graph, Variant min, Variant max) throws DatabaseException {
1110 Resource r = getRoot(graph);
1111 List<Tuple2> results = new ArrayList<Tuple2>();
1112 return collectEntries(graph, r, min, max, results);