bundles/org.simantics.datatypes/src/org/simantics/datatypes/utils/BTreeUtils.java

   1 package org.simantics.datatypes.utils;\r
   2 \r
   3 import java.io.ByteArrayInputStream;\r
   4 import java.io.DataInput;\r
   5 import java.io.DataOutput;\r
   6 import java.io.IOException;\r
   7 import java.util.ArrayList;\r
   8 import java.util.Collection;\r
   9 import java.util.HashMap;\r
  10 import java.util.IdentityHashMap;\r
  11 import java.util.List;\r
  12 import java.util.Map;\r
  13 import java.util.Set;\r
  14 \r
  15 import org.simantics.databoard.Bindings;\r
  16 import org.simantics.databoard.accessor.reference.ChildReference;\r
  17 import org.simantics.databoard.binding.Binding;\r
  18 import org.simantics.databoard.binding.error.BindingException;\r
  19 import org.simantics.databoard.binding.error.RuntimeBindingConstructionException;\r
  20 import org.simantics.databoard.binding.impl.BindingPrintContext;\r
  21 import org.simantics.databoard.binding.mutable.Variant;\r
  22 import org.simantics.databoard.serialization.RuntimeSerializerConstructionException;\r
  23 import org.simantics.databoard.serialization.Serializer;\r
  24 import org.simantics.databoard.util.IdentityPair;\r
  25 import org.simantics.datatypes.DatatypeResource;\r
  26 import org.simantics.db.ReadGraph;\r
  27 import org.simantics.db.Resource;\r
  28 import org.simantics.db.WriteGraph;\r
  29 import org.simantics.db.common.primitiverequest.RelatedValue;\r
  30 import org.simantics.db.common.procedure.adapter.TransientCacheListener;\r
  31 import org.simantics.db.common.utils.Logger;\r
  32 import org.simantics.db.exception.DatabaseException;\r
  33 import org.simantics.db.service.Bytes;\r
  34 import org.simantics.db.service.SerialisationSupport;\r
  35 import org.simantics.db.service.XSupport;\r
  36 import org.simantics.layer0.Layer0;\r
  37 import org.simantics.scl.runtime.tuple.Tuple2;\r
  38 import org.simantics.utils.datastructures.Pair;\r
  39 \r
  40 import gnu.trove.list.array.TByteArrayList;\r
  41 import gnu.trove.map.hash.TObjectIntHashMap;\r
  42 \r
  43 /*\r
  44  * Implementation from http://www.geeksforgeeks.org/b-tree-set-3delete/\r
  45  * \r
  46  */\r
  47 \r
  48 interface BTreeContentManager {\r
  49         \r
  50         BTreeContentBean getContentBean(ReadGraph graph, Resource node) throws DatabaseException;\r
  51         void setContentBean(WriteGraph graph, Resource node, BTreeContentBean bean) throws DatabaseException;\r
  52         \r
  53 }\r
  54 \r
  55 class PossibleVariantInputStream extends ByteArrayInputStream {\r
  56         \r
  57         PossibleVariantInputStream(byte[] data, int offset) {\r
  58                 super(data, offset, data.length-offset);\r
  59         }\r
  60         \r
  61         public int getOffset() {\r
  62                 return pos;\r
  63         }\r
  64         \r
  65 }\r
  66 \r
  67 class BTreeContentBinding extends Binding {\r
  68 \r
  69         private final SerialisationSupport ss;\r
  70         private final XSupport xs;\r
  71         \r
  72         public BTreeContentBinding(SerialisationSupport ss, XSupport xs) {\r
  73                 this.ss = ss;\r
  74                 this.xs = xs;\r
  75         }\r
  76         \r
  77         private final Serializer serializer = new Serializer() {\r
  78 \r
  79                 @Override\r
  80                 public void serialize(DataOutput out, TObjectIntHashMap<Object> identities, Object obj) throws IOException {\r
  81                         throw new UnsupportedOperationException();\r
  82                 }\r
  83 \r
  84                 @Override\r
  85                 public void serialize(DataOutput out, Object obj) throws IOException {\r
  86                         byte[] data = serialize(obj);\r
  87                         out.write(data);\r
  88                 }\r
  89 \r
  90                 @Override\r
  91                 public Object deserialize(DataInput in, List<Object> identities)\r
  92                                 throws IOException {\r
  93                         throw new UnsupportedOperationException();\r
  94                 }\r
  95 \r
  96                 @Override\r
  97                 public Object deserialize(DataInput in) throws IOException {\r
  98                         throw new UnsupportedOperationException();\r
  99                 }\r
 100 \r
 101                 @Override\r
 102                 public void deserializeTo(DataInput in, List<Object> identities,\r
 103                                 Object dst) throws IOException {\r
 104                         throw new UnsupportedOperationException();\r
 105                 }\r
 106 \r
 107                 @Override\r
 108                 public void deserializeTo(DataInput in, Object dst) throws IOException {\r
 109                         throw new UnsupportedOperationException();\r
 110                 }\r
 111 \r
 112                 @Override\r
 113                 public void skip(DataInput in, List<Object> identities)\r
 114                                 throws IOException {\r
 115                         throw new UnsupportedOperationException();\r
 116                 }\r
 117 \r
 118                 @Override\r
 119                 public void skip(DataInput in) throws IOException {\r
 120                         throw new UnsupportedOperationException();\r
 121                 }\r
 122 \r
 123                 @Override\r
 124                 public Integer getConstantSize() {\r
 125                         throw new UnsupportedOperationException();\r
 126                 }\r
 127 \r
 128                 @Override\r
 129                 public int getSize(Object obj, TObjectIntHashMap<Object> identities)\r
 130                                 throws IOException {\r
 131                         throw new UnsupportedOperationException();\r
 132                 }\r
 133 \r
 134                 @Override\r
 135                 public int getSize(Object obj) throws IOException {\r
 136                         return serialize(obj).length;\r
 137                 }\r
 138 \r
 139                 @Override\r
 140                 public int getMinSize() {\r
 141                         throw new UnsupportedOperationException();\r
 142                 }\r
 143                 \r
 144                 private void addBE(TByteArrayList bytes, int value) {\r
 145                         \r
 146                         bytes.add((byte) ((value >>> 24) & 0xFF));\r
 147                         bytes.add((byte) ((value >>> 16) & 0xFF));\r
 148                         bytes.add((byte) ((value >>> 8) & 0xFF));\r
 149                         bytes.add( (byte) (value & 0xFF));\r
 150 \r
 151                 }\r
 152                 \r
 153                 private void addBE(TByteArrayList bytes, long value) {\r
 154                         \r
 155                         bytes.add((byte) ((value >>> 56) & 0xFF));\r
 156                         bytes.add((byte) ((value >>> 48) & 0xFF));\r
 157                         bytes.add((byte) ((value >>> 40) & 0xFF));\r
 158                         bytes.add((byte) ((value >>> 32) & 0xFF));\r
 159                         bytes.add((byte) ((value >>> 24) & 0xFF));\r
 160                         bytes.add((byte) ((value >>> 16) & 0xFF));\r
 161                         bytes.add((byte) ((value >>> 8) & 0xFF));\r
 162                         bytes.add( (byte) (value & 0xFF));\r
 163 \r
 164                 }\r
 165 \r
 166                 public byte[] serialize(Object obj) throws IOException {\r
 167                         BTreeContentBean bean = (BTreeContentBean)obj;\r
 168                         TByteArrayList bytes = new TByteArrayList();\r
 169                         bytes.add(bean.leaf ? (byte)1 : (byte)0);\r
 170                         addBE(bytes, bean.n);\r
 171                         //addLE(bytes, (bean.key.length+1)/2);\r
 172                         Binding pbv = PossibleVariant.BINDING;\r
 173                         Serializer pbs = pbv.serializer();\r
 174                         addBE(bytes, bean.key.length);\r
 175                         for(PossibleVariant l : bean.key) {\r
 176                                 byte[] ser = pbs.serialize(l);\r
 177                                 bytes.add(ser);\r
 178                         }\r
 179                         addBE(bytes, bean.value.length);\r
 180                         for(PossibleResource pr : bean.value) {\r
 181                                 if(pr.r != null) {\r
 182                                         bytes.add((byte)1);\r
 183                                         addBE(bytes, xs.convertDelayedResourceToResource(pr.r).getResourceId());\r
 184                                 } else {\r
 185                                         bytes.add((byte)0);\r
 186                                 }\r
 187                         }\r
 188                         addBE(bytes, bean.c.length);\r
 189                         for(PossibleResource pr : bean.c) {\r
 190                                 if(pr.r != null) {\r
 191                                         bytes.add((byte)1);\r
 192                                         addBE(bytes, xs.convertDelayedResourceToResource(pr.r).getResourceId());\r
 193                                 } else {\r
 194                                         bytes.add((byte)0);\r
 195                                 }\r
 196                         }\r
 197                         return bytes.toArray();\r
 198                 }\r
 199                 \r
 200                 int readBE4(byte[] bytes, int byteIndex) {\r
 201                         int result = (int) \r
 202                                 (((int)(bytes[byteIndex++] & 0xff))<<24) |\r
 203                                         (((int)(bytes[byteIndex++] & 0xff))<<16) | \r
 204                                         (((int)(bytes[byteIndex++] & 0xff))<<8) | \r
 205                                 (((int)(bytes[byteIndex++] & 0xff)));\r
 206                         return result;\r
 207                 }\r
 208                 \r
 209                 long readBE8(byte[] bytes, int byteIndex) {\r
 210                         long result = (long) \r
 211                                 (((long)(bytes[byteIndex++] & 0xff))<<56) |\r
 212                                 (((long)(bytes[byteIndex++] & 0xff))<<48) | \r
 213                                 (((long)(bytes[byteIndex++] & 0xff))<<40) | \r
 214                                 (((long)(bytes[byteIndex++] & 0xff))<<32) | \r
 215                                 (((long)(bytes[byteIndex++] & 0xff))<<24) | \r
 216                                 (((long)(bytes[byteIndex++] & 0xff))<<16) | \r
 217                                 (((long)(bytes[byteIndex++] & 0xff))<<8) | \r
 218                                 (((long)(bytes[byteIndex++] & 0xff))); \r
 219                         return result;\r
 220                 }\r
 221                 \r
 222                 public Object deserialize(byte[] data) throws IOException {\r
 223                         \r
 224                         BTreeContentBean result = new BTreeContentBean();\r
 225 \r
 226                         try {\r
 227                         \r
 228                                 result.leaf = (data[0] == 1) ? true : false;\r
 229                                 int byteIndex = 1;\r
 230                                 result.n = readBE4(data, byteIndex);\r
 231                                 byteIndex += 4;\r
 232                                 \r
 233                                 Binding pbv = PossibleVariant.BINDING;\r
 234                                 Serializer pbs = pbv.serializer();\r
 235 \r
 236                                 // Redundant array size\r
 237                                 int keySize = readBE4(data, byteIndex);\r
 238                                 result.key = new PossibleVariant[keySize];\r
 239                                 byteIndex += 4;\r
 240                                 for(int i=0;i<keySize;i++) {\r
 241                                         PossibleVariantInputStream is = new PossibleVariantInputStream(data, byteIndex);\r
 242                                         PossibleVariant v = (PossibleVariant)pbs.deserialize(is);\r
 243                                         result.key[i] = v;\r
 244                                         byteIndex = is.getOffset();\r
 245                                 }\r
 246                                 \r
 247                                 // Redundant array size\r
 248                                 int valueSize = readBE4(data, byteIndex);\r
 249                                 result.value = new PossibleResource[valueSize];\r
 250                                 byteIndex += 4;\r
 251                                 for(int i=0;i<valueSize;i++) {\r
 252                                         boolean has = Bytes.read(data, byteIndex++) > 0;\r
 253                                         if(has) {\r
 254                                                 result.value[i] = PossibleResource.read(ss, readBE8(data, byteIndex));\r
 255                                                 byteIndex += 8;\r
 256                                         } else {\r
 257                                                 result.value[i] = new PossibleResource();\r
 258                                         }\r
 259                                 }\r
 260         \r
 261                                 // Redundant array size\r
 262                                 int childSize = readBE4(data, byteIndex);\r
 263                                 result.c = new PossibleResource[childSize];\r
 264                                 byteIndex += 4;\r
 265                                 for(int i=0;i<childSize;i++) {\r
 266                                         boolean has = Bytes.read(data, byteIndex++) > 0;\r
 267                                         if(has) {\r
 268                                                 result.c[i] = PossibleResource.read(ss, readBE8(data, byteIndex));\r
 269                                                 byteIndex += 8;\r
 270                                         } else {\r
 271                                                 result.c[i] = new PossibleResource();\r
 272                                         }\r
 273                                 }\r
 274         \r
 275                         } catch (DatabaseException e) {\r
 276                         \r
 277                                 e.printStackTrace();\r
 278                                 \r
 279                         }\r
 280                         \r
 281                         return result;\r
 282                         \r
 283                 }\r
 284                 \r
 285         };\r
 286         \r
 287         @Override\r
 288         public void accept(Visitor1 v, Object obj) {\r
 289                 throw new UnsupportedOperationException();\r
 290         }\r
 291 \r
 292         @Override\r
 293         public <T> T accept(Visitor<T> v) {\r
 294                 throw new UnsupportedOperationException();\r
 295         }\r
 296 \r
 297         @Override\r
 298         public boolean isInstance(Object obj) {\r
 299                 throw new UnsupportedOperationException();\r
 300         }\r
 301 \r
 302         @Override\r
 303         public void readFrom(Binding srcBinding, Object src, Object dst)\r
 304                         throws BindingException {\r
 305                 throw new UnsupportedOperationException();\r
 306         }\r
 307 \r
 308         @Override\r
 309         public void assertInstaceIsValid(Object obj, Set<Object> validInstances)\r
 310                         throws BindingException {\r
 311                 throw new UnsupportedOperationException();\r
 312         }\r
 313 \r
 314         @Override\r
 315         public int deepHashValue(Object value,\r
 316                         IdentityHashMap<Object, Object> hashedObjects)\r
 317                         throws BindingException {\r
 318                 throw new UnsupportedOperationException();\r
 319         }\r
 320 \r
 321         @Override\r
 322         public int deepCompare(Object o1, Object o2,\r
 323                         Set<IdentityPair<Object, Object>> compareHistory)\r
 324                         throws BindingException {\r
 325                 throw new UnsupportedOperationException();\r
 326         }\r
 327 \r
 328         @Override\r
 329         protected void toString(Object value, BindingPrintContext ctx)\r
 330                         throws BindingException {\r
 331                 throw new UnsupportedOperationException();\r
 332         }\r
 333 \r
 334         @Override\r
 335         public int getComponentCount() {\r
 336                 throw new UnsupportedOperationException();\r
 337         }\r
 338 \r
 339         @Override\r
 340         public Binding getComponentBinding(int index) {\r
 341                 throw new UnsupportedOperationException();\r
 342         }\r
 343 \r
 344         @Override\r
 345         public Binding getComponentBinding(ChildReference path) {\r
 346                 throw new UnsupportedOperationException();\r
 347         }\r
 348         \r
 349         @Override\r
 350         public Serializer serializer() throws RuntimeSerializerConstructionException {\r
 351                 return serializer;\r
 352         }\r
 353         \r
 354 }\r
 355 \r
 356 final public class BTreeUtils implements BTreeContentManager {\r
 357 \r
 358         final private Resource tree;\r
 359         final private Resource ownerRelation;\r
 360         \r
 361         final public Binding CONTENT_BEAN_BINDING;\r
 362         final public DatatypeResource DATA;\r
 363         \r
 364         private long mod;\r
 365         private int t;\r
 366         private Map<Resource, BTreeContentBean> beans;\r
 367         private Map<Resource, Resource> owners;\r
 368         private Resource root;\r
 369         private Resource nodeType;\r
 370         private boolean cached;\r
 371 \r
 372         public BTreeUtils(ReadGraph graph, Resource tree, int t, Resource nodeType, Resource ownerRelation, boolean cached) throws DatabaseException {\r
 373                 try {\r
 374                         SerialisationSupport ss = graph.getService(SerialisationSupport.class);\r
 375                         XSupport xs = graph.getService(XSupport.class);\r
 376                                         \r
 377                         CONTENT_BEAN_BINDING = new BTreeContentBinding(ss, xs);\r
 378                         DATA = DatatypeResource.getInstance(graph);\r
 379                         this.tree = tree;\r
 380                         this.ownerRelation = ownerRelation;\r
 381                         this.nodeType = nodeType != null ? nodeType : DATA.BTreeNode;\r
 382                         this.t = t;\r
 383                         this.mod = 0;\r
 384                         this.cached = cached;\r
 385                         if (cached) {\r
 386                                 this.beans = new HashMap<Resource, BTreeContentBean>();\r
 387                                 this.owners = new HashMap<Resource, Resource>();\r
 388                         }\r
 389                 } catch (RuntimeBindingConstructionException e) {\r
 390                         Logger.defaultLogError(e);\r
 391                         throw new DatabaseException(e);\r
 392                 }\r
 393         }\r
 394         \r
 395         public static BTreeUtils create(WriteGraph graph, Resource ownerRelation, int t, boolean cached) throws DatabaseException {\r
 396                 \r
 397                 DatatypeResource DATA = DatatypeResource.getInstance(graph);\r
 398                 return create(graph, DATA.BTree, DATA.BTreeNode, ownerRelation, t, cached);\r
 399                 \r
 400         }\r
 401 \r
 402         public static BTreeUtils create(WriteGraph graph, Resource type, Resource nodeType, Resource ownerRelation, int t, boolean cached) throws DatabaseException {\r
 403                 \r
 404                 Layer0 L0 = Layer0.getInstance(graph);\r
 405                 DatatypeResource DATA = DatatypeResource.getInstance(graph);\r
 406                 Resource tree = graph.newResource();\r
 407                 graph.claim(tree, L0.InstanceOf, null, type);\r
 408                 \r
 409                 if(ownerRelation != null)\r
 410                         graph.claim(tree, DATA.BTree_HasOwnerRelation, DATA.BTree_HasOwnerRelation_Inverse, ownerRelation);\r
 411                 if(nodeType != null)\r
 412                         graph.claim(tree, DATA.BTree_HasNodeType, DATA.BTree_HasNodeType_Inverse, nodeType);\r
 413                 \r
 414                 graph.claimLiteral(tree, DATA.BTree_t, t, Bindings.INTEGER);\r
 415                 \r
 416                 if (!cached) {\r
 417                         graph.claimLiteral(tree, DATA.BTree_mod, 0L, Bindings.LONG);\r
 418                 }\r
 419 \r
 420                 BTreeUtils utils = new BTreeUtils(graph, tree, t, nodeType, ownerRelation, cached);\r
 421                 Resource node = utils.createNode(graph, utils, t); \r
 422                 utils.setRoot(graph, node);\r
 423                 utils.setOwner(graph, node, tree, true);\r
 424                 \r
 425                 return utils; \r
 426         }       \r
 427         \r
 428         public Resource getTree() {\r
 429                 return tree;\r
 430         }\r
 431 \r
 432         public void insert(WriteGraph graph, Variant k, Resource v) throws DatabaseException {\r
 433 \r
 434                 Resource r = getRoot(graph);\r
 435                 insertImpl(graph, this, r, t, k, v);\r
 436                 \r
 437         }\r
 438 \r
 439         static class BatchContentManager implements BTreeContentManager {\r
 440 \r
 441                 final private BTreeUtils bu;\r
 442                 \r
 443                 final Map<Resource, BTreeContentBean> beans = new HashMap<Resource, BTreeContentBean>();\r
 444                 \r
 445                 public BatchContentManager(BTreeUtils bu) {\r
 446                         this.bu = bu;\r
 447                 }\r
 448                 \r
 449                 @Override\r
 450                 public BTreeContentBean getContentBean(ReadGraph graph, Resource node) throws DatabaseException {\r
 451                         BTreeContentBean bean = beans.get(node);\r
 452                         if(bean != null) return bean;\r
 453                         return bu.getContentBean(graph, node);\r
 454                 }\r
 455 \r
 456                 @Override\r
 457                 public void setContentBean(WriteGraph graph, Resource node, BTreeContentBean bean) throws DatabaseException {\r
 458                         beans.put(node, bean);\r
 459                 }\r
 460                 \r
 461                 public void apply(WriteGraph graph) throws DatabaseException {\r
 462                         for(Map.Entry<Resource, BTreeContentBean> entry : beans.entrySet()) {\r
 463                                 bu.setContentBean(graph, entry.getKey(), entry.getValue());\r
 464                         }\r
 465                 }\r
 466                 \r
 467         }\r
 468         \r
 469         public void insertAll(WriteGraph graph, Collection<Pair<Variant, Resource>> values) throws DatabaseException {\r
 470 \r
 471                 Resource r = getRoot(graph);\r
 472                 BatchContentManager cm = new BatchContentManager(this);\r
 473                 for(Pair<Variant, Resource> entry : values) {\r
 474                         insertImpl(graph, cm, r, t, entry.first, entry.second);\r
 475                 }\r
 476                 cm.apply(graph);\r
 477                 \r
 478         }\r
 479 \r
 480         public Resource search(ReadGraph graph, Variant k) throws DatabaseException {\r
 481 \r
 482                 Resource r = getRoot(graph);\r
 483                 return searchNode(graph, r, k);\r
 484                 \r
 485         }\r
 486         \r
 487         // Implementation\r
 488 \r
 489         private int findKey(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, Variant k) throws DatabaseException {\r
 490 \r
 491                 int idx = 0;\r
 492                 while(idx<bean.n && bean.key[idx].v.compareTo(k) < 0)\r
 493                         idx++;\r
 494                 return idx;\r
 495 \r
 496         }\r
 497         \r
 498         private void insertImpl(WriteGraph graph, BTreeContentManager manager, Resource r, int t, Variant k, Resource v) throws DatabaseException {\r
 499 \r
 500                 BTreeContentBean rContent = manager.getContentBean(graph, r);\r
 501                 if(rContent.n == 2*t-1) {\r
 502                         Resource s = allocateNode(graph, manager, t);\r
 503                         BTreeContentBean sContent = manager.getContentBean(graph, s);\r
 504                         setRoot(graph, s);\r
 505                         setOwner(graph, s, tree, true);\r
 506                         sContent.leaf = false;\r
 507                         sContent.n = 0;\r
 508                         sContent.c[0].r = r;\r
 509                         setOwner(graph, r, s, true);\r
 510                         manager.setContentBean(graph, s, sContent);\r
 511                         splitChild(graph, manager, t, s, 1, r);\r
 512                         insertNonfull(graph, manager, t, s, k, v);\r
 513                 } else {\r
 514                         insertNonfull(graph, manager, t, r, k, v);\r
 515                 }\r
 516                 \r
 517         }\r
 518 \r
 519         public void remove(WriteGraph graph, Variant k) throws DatabaseException {\r
 520 \r
 521                 Resource r = getRoot(graph);\r
 522                 \r
 523                 BTreeContentBean bean = getContentBean(graph, r);\r
 524                 Resource removedResource = removeImpl(graph, this, t, r, bean, k);\r
 525                 if (removedResource != null) {\r
 526                         removeOwner(graph, removedResource, false);\r
 527                         \r
 528                     // If the root node has 0 keys, make its first child as the new root\r
 529                     //  if it has a child, otherwise set root as NULL\r
 530                     if (bean.n==0)\r
 531                     {\r
 532                         //BTreeContentBean tmp = bean;\r
 533                         if (!bean.leaf) {\r
 534                                 removeOwner(graph, r, true);\r
 535                                 setRoot(graph, bean.c[0].r);\r
 536                                 setOwner(graph, bean.c[0].r, tree, true);\r
 537                         }\r
 538                  \r
 539                         // Free the old root\r
 540                         //delete tmp;\r
 541                         \r
 542                     }\r
 543                 }\r
 544 \r
 545                 \r
 546         }\r
 547         \r
 548         public Resource removeImpl(WriteGraph graph, BTreeContentManager manager, int t, Resource r, BTreeContentBean bean, Variant k) throws DatabaseException {\r
 549                 \r
 550                 int idx = findKey(graph, manager, bean, k);\r
 551                 \r
 552                 if(idx < bean.n && bean.key[idx].v.equals(k)) {\r
 553                         Resource removedResource = bean.value[idx].r;\r
 554                         if(bean.leaf)\r
 555                                 removeFromLeaf(graph, manager, r, bean, idx);\r
 556                         else\r
 557                                 removeFromNonLeaf(graph, manager, r, bean, t, idx);\r
 558                         \r
 559                         return removedResource;\r
 560                 } else {\r
 561                         \r
 562                 if (bean.leaf) {\r
 563                         return null;\r
 564                 }\r
 565          \r
 566                 // The key to be removed is present in the sub-tree rooted with this node\r
 567                 // The flag indicates whether the key is present in the sub-tree rooted\r
 568                 // with the last child of this node\r
 569                 boolean flag = ( (idx==bean.n)? true : false );\r
 570          \r
 571                 BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx].r);\r
 572                 \r
 573                 // If the child where the key is supposed to exist has less that t keys,\r
 574                 // we fill that child\r
 575                 if (cContent.n < t)\r
 576                     fill(graph, manager, r, bean, t, idx);\r
 577          \r
 578                 // If the last child has been merged, it must have merged with the previous\r
 579                 // child and so we recurse on the (idx-1)th child. Else, we recurse on the\r
 580                 // (idx)th child which now has atleast t keys\r
 581                 if (flag && idx > bean.n)\r
 582                         return removeImpl(graph, manager, t, bean.c[idx-1].r, manager.getContentBean(graph, bean.c[idx-1].r), k);\r
 583                 else\r
 584                         return removeImpl(graph, manager, t, bean.c[idx].r, cContent, k);\r
 585                 \r
 586                 }\r
 587                 \r
 588                 \r
 589         }\r
 590         \r
 591         // A function to get predecessor of keys[idx]\r
 592         Pair<Variant, Resource> getPred(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, int idx) throws DatabaseException {\r
 593                 \r
 594             // Keep moving to the right most node until we reach a leaf\r
 595         bean = manager.getContentBean(graph, bean.c[idx].r);\r
 596             while (!bean.leaf)\r
 597                 bean = manager.getContentBean(graph, bean.c[bean.n].r);\r
 598          \r
 599             // Return the last key of the leaf\r
 600             return new Pair<Variant, Resource>(bean.key[bean.n-1].v, bean.value[bean.n-1].r);\r
 601             \r
 602         }\r
 603          \r
 604         Pair<Variant, Resource> getSucc(ReadGraph graph, BTreeContentManager manager, BTreeContentBean bean, int idx) throws DatabaseException {\r
 605          \r
 606             // Keep moving the left most node starting from C[idx+1] until we reach a leaf\r
 607         bean = manager.getContentBean(graph, bean.c[idx+1].r);\r
 608             while (!bean.leaf)\r
 609                 bean = manager.getContentBean(graph, bean.c[0].r);\r
 610 \r
 611             // Return the first key of the leaf\r
 612             return new Pair<Variant, Resource>(bean.key[0].v, bean.value[0].r);\r
 613             \r
 614         }\r
 615          \r
 616         // A function to fill child C[idx] which has less than t-1 keys\r
 617         void fill(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int t, int idx) throws DatabaseException {\r
 618 \r
 619             // If the previous child(C[idx-1]) has more than t-1 keys, borrow a key\r
 620             // from that child\r
 621             if (idx!=0) {\r
 622                 BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx-1].r);\r
 623 \r
 624                 if (cContent.n>=t) {\r
 625                         borrowFromPrev(graph, manager, r, bean, idx);\r
 626                         return;\r
 627                 }\r
 628             }\r
 629             \r
 630         // If the next child(C[idx+1]) has more than t-1 keys, borrow a key\r
 631         // from that child\r
 632 \r
 633             if (idx!=bean.n) {\r
 634                 BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx+1].r);\r
 635 \r
 636                 if (cContent.n>=t) {\r
 637                         borrowFromNext(graph, manager, r, bean, idx);\r
 638                         return;\r
 639                 }\r
 640             }\r
 641 \r
 642         // Merge C[idx] with its sibling\r
 643         // If C[idx] is the last child, merge it with with its previous sibling\r
 644         // Otherwise merge it with its next sibling\r
 645                 if (idx != bean.n)\r
 646                         merge(graph, manager, r, bean, t, idx);\r
 647                 else\r
 648                         merge(graph, manager, r, bean, t, idx-1);\r
 649         }\r
 650         \r
 651         // A function to borrow a key from C[idx-1] and insert it\r
 652         // into C[idx]\r
 653         void borrowFromPrev(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {\r
 654          \r
 655         BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);\r
 656         BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx-1].r);\r
 657                 \r
 658             // The last key from C[idx-1] goes up to the parent and key[idx-1]\r
 659             // from parent is inserted as the first key in C[idx]. Thus, the  loses\r
 660             // sibling one key and child gains one key\r
 661          \r
 662             // Moving all key in C[idx] one step ahead\r
 663             for (int i=childContent.n-1; i>=0; --i) {\r
 664                 childContent.key[i+1].v = childContent.key[i].v;\r
 665                 childContent.value[i+1].r = childContent.value[i].r;\r
 666             }\r
 667             \r
 668             // If C[idx] is not a leaf, move all its child pointers one step ahead\r
 669             if (!childContent.leaf) {\r
 670                 for(int i=childContent.n; i>=0; --i) {\r
 671                     childContent.c[i+1].r = childContent.c[i].r;\r
 672                                 setOwner(graph, childContent.c[i+1].r, bean.c[idx].r, true);\r
 673                 }\r
 674             }\r
 675 \r
 676             // Setting child's first key equal to keys[idx-1] from the current node\r
 677             childContent.key[0].v = bean.key[idx-1].v;\r
 678             childContent.value[0].r = bean.value[idx-1].r;\r
 679          \r
 680             // Moving sibling's last child as C[idx]'s first child\r
 681             // TODO: is this correct?\r
 682             if (!bean.leaf) {\r
 683                 Resource lastChild = siblingContent.c[siblingContent.n].r;\r
 684                 if (lastChild != null) {\r
 685                         childContent.c[0].r = lastChild;\r
 686                                 setOwner(graph, childContent.c[0].r, bean.c[idx].r, true);\r
 687                 }\r
 688             }\r
 689 \r
 690             // Moving the key from the sibling to the parent\r
 691             // This reduces the number of keys in the sibling\r
 692             bean.key[idx-1].v = siblingContent.key[siblingContent.n-1].v;\r
 693             bean.value[idx-1].r = siblingContent.value[siblingContent.n-1].r;\r
 694 \r
 695             childContent.n += 1;\r
 696             siblingContent.reduceSize();\r
 697             //siblingContent.n -= 1;\r
 698 \r
 699             manager.setContentBean(graph, r, bean);\r
 700             manager.setContentBean(graph, bean.c[idx].r, childContent);\r
 701             manager.setContentBean(graph, bean.c[idx-1].r, siblingContent);\r
 702 \r
 703         }\r
 704          \r
 705         // A function to borrow a key from the C[idx+1] and place\r
 706         // it in C[idx]\r
 707         void borrowFromNext(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {\r
 708 \r
 709         BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);\r
 710         BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx+1].r);\r
 711 \r
 712             // keys[idx] is inserted as the last key in C[idx]\r
 713         childContent.key[childContent.n].v = bean.key[idx].v;\r
 714         childContent.value[childContent.n].r = bean.value[idx].r;\r
 715          \r
 716             // Sibling's first child is inserted as the last child\r
 717             // into C[idx]\r
 718             if (!childContent.leaf) {\r
 719                 childContent.c[childContent.n+1].r = siblingContent.c[0].r;\r
 720                         setOwner(graph, childContent.c[childContent.n+1].r, bean.c[idx].r, true);\r
 721             }\r
 722          \r
 723             //The first key from sibling is inserted into keys[idx]\r
 724             bean.key[idx].v = siblingContent.key[0].v;\r
 725             bean.value[idx].r = siblingContent.value[0].r;\r
 726          \r
 727             // Moving all keys in sibling one step behind\r
 728             for (int i=1; i<siblingContent.n; ++i) {\r
 729                 siblingContent.key[i-1].v = siblingContent.key[i].v;\r
 730                 siblingContent.value[i-1].r = siblingContent.value[i].r;\r
 731             }\r
 732          \r
 733             // Moving the child pointers one step behind\r
 734             if (!siblingContent.leaf) {\r
 735                 for(int i=1; i<=siblingContent.n; ++i)\r
 736                         siblingContent.c[i-1].r = siblingContent.c[i].r;\r
 737             }\r
 738          \r
 739             // Increasing and decreasing the key count of C[idx] and C[idx+1]\r
 740             // respectively\r
 741             childContent.n += 1;\r
 742             siblingContent.reduceSize();\r
 743             //siblingContent.n -= 1;\r
 744             \r
 745             manager.setContentBean(graph, r, bean);\r
 746             manager.setContentBean(graph, bean.c[idx].r, childContent);\r
 747             manager.setContentBean(graph, bean.c[idx+1].r, siblingContent);\r
 748          \r
 749         }\r
 750          \r
 751         // A function to merge C[idx] with C[idx+1]\r
 752         // C[idx+1] is freed after merging\r
 753         void merge(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int t, int idx) throws DatabaseException {\r
 754                 \r
 755         BTreeContentBean childContent = manager.getContentBean(graph, bean.c[idx].r);\r
 756         BTreeContentBean siblingContent = manager.getContentBean(graph, bean.c[idx+1].r);\r
 757 \r
 758             // Pulling a key from the current node and inserting it into (t-1)th\r
 759             // position of C[idx]\r
 760         childContent.key[t-1].v = bean.key[idx].v;\r
 761         childContent.value[t-1].r = bean.value[idx].r;\r
 762          \r
 763             // Copying the keys from C[idx+1] to C[idx] at the end\r
 764             for (int i=0; i<siblingContent.n; ++i) {\r
 765                 childContent.key[i+t].v = siblingContent.key[i].v;\r
 766                 childContent.value[i+t].r = siblingContent.value[i].r;\r
 767             }\r
 768          \r
 769             // Copying the child pointers from C[idx+1] to C[idx]\r
 770             if (!childContent.leaf) {\r
 771                 for(int i=0; i<=siblingContent.n; ++i) {\r
 772                         childContent.c[i+t].r = siblingContent.c[i].r;\r
 773                                 setOwner(graph, childContent.c[i+t].r, bean.c[idx].r, true);\r
 774                 }\r
 775             }\r
 776             \r
 777             // Moving all keys after idx in the current node one step before -\r
 778             // to fill the gap created by moving keys[idx] to C[idx]\r
 779             for (int i=idx+1; i<bean.n; ++i) {\r
 780                 bean.key[i-1].v = bean.key[i].v;\r
 781                 bean.value[i-1].r = bean.value[i].r;\r
 782             }\r
 783 \r
 784         // Remove the owner of the merged sibling\r
 785         removeOwner(graph, bean.c[idx+1].r, true);\r
 786             \r
 787             // Moving the child pointers after (idx+1) in the current node one\r
 788             // step before\r
 789             for (int i=idx+2; i<=bean.n; ++i)\r
 790                 bean.c[i-1].r = bean.c[i].r;\r
 791          \r
 792             // Updating the key count of child and the current node\r
 793             childContent.n += siblingContent.n+1;\r
 794             bean.reduceSize();\r
 795             //bean.n--;\r
 796          \r
 797             // Freeing the memory occupied by sibling\r
 798             // delete(sibling);\r
 799             \r
 800             manager.setContentBean(graph, r, bean);\r
 801             manager.setContentBean(graph, bean.c[idx].r, childContent);\r
 802 \r
 803         }\r
 804         \r
 805         private void removeOwner(WriteGraph graph, Resource r, boolean force) throws DatabaseException {\r
 806                 if((ownerRelation != null) || force) {\r
 807                         if (cached) {\r
 808                                 owners.put(r, null);\r
 809                         } else {\r
 810                                 Resource own = ownerRelation != null ? ownerRelation : DATA.BTreeNode_IsOwnedBy;\r
 811                                 graph.deny(r, own);\r
 812                         }\r
 813                 }\r
 814         }\r
 815         \r
 816         private void removeFromLeaf(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int idx) throws DatabaseException {\r
 817 \r
 818             // Move all the keys after the idx-th pos one place backward\r
 819             for (int i=idx+1; i<bean.n; ++i) {\r
 820                 bean.key[i-1].v = bean.key[i].v;\r
 821                 bean.value[i-1].r = bean.value[i].r;\r
 822             }\r
 823          \r
 824             // Reduce the count of keys\r
 825             bean.reduceSize();\r
 826             //bean.n--;\r
 827             \r
 828             manager.setContentBean(graph, r, bean);\r
 829             \r
 830         }\r
 831 \r
 832         private void removeFromNonLeaf(WriteGraph graph, BTreeContentManager manager, Resource r, BTreeContentBean bean, int t, int idx) throws DatabaseException {\r
 833 \r
 834                 Variant k = bean.key[idx].v;\r
 835                  \r
 836                 // If the child that precedes k (C[idx]) has atleast t keys,\r
 837                 // find the predecessor 'pred' of k in the subtree rooted at\r
 838                 // C[idx]. Replace k by pred. Recursively delete pred\r
 839                 // in C[idx]\r
 840                 \r
 841         BTreeContentBean cContent = manager.getContentBean(graph, bean.c[idx].r);\r
 842 \r
 843                 if (cContent.n >= t) {\r
 844                         \r
 845                         Pair<Variant, Resource> pred = getPred(graph, manager, bean, idx);\r
 846                         bean.key[idx].v = pred.first;\r
 847                         bean.value[idx].r = pred.second;\r
 848                         removeImpl(graph, manager, t, bean.c[idx].r, cContent, pred.first);\r
 849                         \r
 850                         manager.setContentBean(graph, r, bean);\r
 851                 } else {\r
 852 \r
 853                 BTreeContentBean cContentPlus1 = manager.getContentBean(graph, bean.c[idx+1].r);\r
 854 \r
 855                         // If the child C[idx] has less that t keys, examine C[idx+1].\r
 856                         // If C[idx+1] has atleast t keys, find the successor 'succ' of k in\r
 857                         // the subtree rooted at C[idx+1]\r
 858                         // Replace k by succ\r
 859                         // Recursively delete succ in C[idx+1]\r
 860                         if (cContentPlus1.n >= t) {\r
 861                                 Pair<Variant, Resource> succ = getSucc(graph, manager, bean, idx);\r
 862                                 bean.key[idx].v = succ.first;\r
 863                                 bean.value[idx].r = succ.second;\r
 864                                 removeImpl(graph, manager, t, bean.c[idx+1].r, cContentPlus1, succ.first);\r
 865                                 \r
 866                                 manager.setContentBean(graph, r, bean);\r
 867                         }\r
 868 \r
 869                         // If both C[idx] and C[idx+1] has less that t keys,merge k and all of C[idx+1]\r
 870                         // into C[idx]\r
 871                         // Now C[idx] contains 2t-1 keys\r
 872                         // Free C[idx+1] and recursively delete k from C[idx]\r
 873                         else {\r
 874                                 \r
 875                                 merge(graph, manager, r, bean, t, idx);\r
 876                                 removeImpl(graph, manager, t, bean.c[idx].r, cContent, k);\r
 877                                 \r
 878                         }\r
 879                         \r
 880                 }\r
 881                 \r
 882         }\r
 883 \r
 884         private Resource createNode(WriteGraph graph, BTreeContentManager manager, int t) throws DatabaseException {\r
 885                 Layer0 L0 = Layer0.getInstance(graph);\r
 886                 Resource result = graph.newResource();\r
 887                 mod++;\r
 888                 graph.claim(result, L0.InstanceOf, null, nodeType);\r
 889                 if (!cached) {\r
 890                         graph.claimLiteral(tree, DATA.BTree_mod, mod, Bindings.LONG);\r
 891                 }\r
 892                 graph.addLiteral(result, L0.HasName, L0.NameOf, ""+mod, Bindings.STRING);\r
 893                 manager.setContentBean(graph, result, BTreeContentBean.create(t));\r
 894                 return result;\r
 895         }\r
 896         \r
 897         public Resource searchNode(ReadGraph graph, Resource x, Variant k) throws DatabaseException {\r
 898 \r
 899                 BTreeContentBean xContent = getContentBean(graph, x);\r
 900 \r
 901                 int i=1;\r
 902                 while(i <= xContent.n && k.compareTo(xContent.key[i-1].v) > 0) i++;\r
 903                 if(i <= xContent.n && k.equals(xContent.key[i-1].v)) return xContent.value[i-1].r;\r
 904                 \r
 905                 if(xContent.leaf) return null;\r
 906                 else return searchNode(graph, xContent.c[i-1].r, k);\r
 907                 \r
 908         }\r
 909 \r
 910         private void splitChild(WriteGraph graph, BTreeContentManager manager, int t, Resource x, int i, Resource y) throws DatabaseException {\r
 911                 \r
 912                 Resource z = allocateNode(graph, manager, t);\r
 913                 \r
 914                 BTreeContentBean xContent = manager.getContentBean(graph, x);\r
 915                 BTreeContentBean yContent = manager.getContentBean(graph, y);\r
 916                 BTreeContentBean zContent = manager.getContentBean(graph, z);\r
 917 \r
 918                 zContent.leaf = yContent.leaf;\r
 919                 zContent.n = t-1;\r
 920                 \r
 921                 for(int j=1;j<=t-1;j++) {\r
 922                         zContent.key[j-1].v = yContent.key[j+t-1].v;\r
 923                         zContent.value[j-1].r = yContent.value[j+t-1].r;\r
 924                         setOwner(graph, zContent.value[j-1].r, z, false);\r
 925                 }\r
 926                 if(!yContent.leaf) {\r
 927                         for(int j=1;j<=t;j++) {\r
 928                                 zContent.c[j-1].r = yContent.c[j+t-1].r;\r
 929                                 setOwner(graph, zContent.c[j-1].r, z, true);\r
 930                         }\r
 931                 }\r
 932 \r
 933                 //yContent.n = t-1;\r
 934 \r
 935                 \r
 936                 for(int j=xContent.n+1;j>=i+1;j--) {\r
 937                         xContent.c[j+1-1].r = xContent.c[j-1].r; \r
 938                 }\r
 939                 \r
 940                 xContent.c[i+1-1].r = z;\r
 941                 setOwner(graph, z, x, true);\r
 942 \r
 943                 for(int j=xContent.n;j>=i;j--) {\r
 944                         xContent.key[j+1-1].v = xContent.key[j-1].v; \r
 945                         xContent.value[j+1-1].r = xContent.value[j-1].r; \r
 946                 }\r
 947                 \r
 948                 xContent.key[i-1].v = yContent.key[t-1].v;\r
 949                 xContent.value[i-1].r = yContent.value[t-1].r;\r
 950                 xContent.n++;\r
 951 \r
 952                 while (yContent.n > t-1) yContent.reduceSize();\r
 953                 \r
 954                 setOwner(graph, xContent.value[i-1].r, x, true);\r
 955                 \r
 956                 manager.setContentBean(graph, x, xContent);\r
 957                 manager.setContentBean(graph, y, yContent);\r
 958                 manager.setContentBean(graph, z, zContent);\r
 959                 \r
 960         }\r
 961         \r
 962         private void insertNonfull(WriteGraph graph, BTreeContentManager manager, int t, Resource x, Variant k, Resource v) throws DatabaseException {\r
 963 \r
 964                 BTreeContentBean xContent = manager.getContentBean(graph, x);\r
 965 \r
 966                 int i = xContent.n;\r
 967                 \r
 968                 if(xContent.leaf) {\r
 969                         while(i >= 1 && k.compareTo(xContent.key[i-1].v) < 0) {\r
 970                                 xContent.key[i+1-1].v = xContent.key[i-1].v;\r
 971                                 xContent.value[i+1-1].r = xContent.value[i-1].r;\r
 972                                 i--;\r
 973                         }\r
 974                         \r
 975                         xContent.key[i+1-1].v = k;\r
 976                         xContent.value[i+1-1].r = v;\r
 977                         xContent.n++;\r
 978                         setOwner(graph, v, x, false);\r
 979                         manager.setContentBean(graph, x, xContent);\r
 980                 } else {\r
 981                         while(i >= 1 && k.compareTo(xContent.key[i-1].v) < 0) i--;\r
 982                         i++;\r
 983                         BTreeContentBean xciContent = manager.getContentBean(graph, xContent.c[i-1].r);\r
 984                         if(xciContent.n == 2*t-1) {\r
 985                                 splitChild(graph, manager, t, x, i, xContent.c[i-1].r);\r
 986                                 xContent = manager.getContentBean(graph, x);\r
 987                                 if(k.compareTo(xContent.key[i-1].v) > 0) i++;\r
 988                         }\r
 989                         insertNonfull(graph, manager, t, xContent.c[i-1].r, k, v);\r
 990                 }\r
 991                 \r
 992         }\r
 993         \r
 994         private void setOwner(WriteGraph graph, Resource r, Resource owner, boolean force) throws DatabaseException {\r
 995                 if (r != null) {\r
 996                         if((ownerRelation != null) || force) {\r
 997                                 Resource own = ownerRelation != null ? ownerRelation : DATA.BTreeNode_IsOwnedBy;\r
 998                                 if (cached) {\r
 999                                         owners.put(r, owner);\r
1000                                 } else {\r
1001                                         graph.deny(r, own);\r
1002                                         graph.claim(r, own, owner);\r
1003                                 }\r
1004                         }\r
1005                 }\r
1006         }\r
1007         \r
1008         private Resource getRoot(ReadGraph graph) throws DatabaseException {\r
1009                 if (cached) {\r
1010                         if (root != null) return root;\r
1011                 }\r
1012                 return graph.getPossibleObject(tree, DATA.BTree_root);\r
1013         }\r
1014         \r
1015         private void setRoot(WriteGraph graph, Resource r) throws DatabaseException {\r
1016                 if (cached) {\r
1017                         this.root = r;\r
1018                 } else {\r
1019                         graph.deny(tree, DATA.BTree_root);\r
1020                         graph.claim(tree, DATA.BTree_root, r);\r
1021                 }\r
1022         }\r
1023 \r
1024         private Resource allocateNode(WriteGraph graph, BTreeContentManager manager, int t) throws DatabaseException {\r
1025                 return createNode(graph, manager, t);\r
1026         }\r
1027         \r
1028         public void setContentBean(WriteGraph graph, Resource node, BTreeContentBean bean) throws DatabaseException {\r
1029                 if (cached) {\r
1030                         beans.put(node, bean);\r
1031                 } else {\r
1032                         graph.claimLiteral(node, DATA.BTreeNode_content, DATA.BTreeNode_Content, bean, CONTENT_BEAN_BINDING );\r
1033                 }\r
1034         }\r
1035         \r
1036         public void flushCache(WriteGraph graph) throws DatabaseException {\r
1037                 assert(cached);\r
1038                 \r
1039                 XSupport xs = graph.getService(XSupport.class);\r
1040                 for(Map.Entry<Resource, BTreeContentBean> entry : beans.entrySet()) {\r
1041                         Resource node = xs.convertDelayedResourceToResource(entry.getKey());\r
1042                         if (node != null) {\r
1043                                 graph.claimLiteral(node, DATA.BTreeNode_content, DATA.BTreeNode_Content, entry.getValue(), CONTENT_BEAN_BINDING );\r
1044                         }\r
1045                 }\r
1046 \r
1047                 for(Map.Entry<Resource, Resource> entry : owners.entrySet()) {\r
1048                         Resource r = xs.convertDelayedResourceToResource(entry.getKey());\r
1049                         Resource owner = xs.convertDelayedResourceToResource(entry.getValue());\r
1050                         graph.deny(r, ownerRelation);\r
1051                         if (owner != null) {\r
1052                                 graph.claim(r, ownerRelation, owner);\r
1053                         }\r
1054                 }\r
1055                 \r
1056                 Resource tree2 = xs.convertDelayedResourceToResource(tree);\r
1057                 graph.claimLiteral(tree2, DATA.BTree_mod, mod, Bindings.LONG);\r
1058                 \r
1059                 if (root != null) {\r
1060                         Resource root2 = xs.convertDelayedResourceToResource(root);\r
1061                         graph.deny(tree2, DATA.BTree_root);\r
1062                         graph.claim(tree2, DATA.BTree_root, root2);\r
1063                 }\r
1064         }\r
1065         \r
1066         public BTreeContentBean getContentBean(ReadGraph graph, Resource node) throws DatabaseException {\r
1067                 if (cached) {\r
1068                         BTreeContentBean bean = beans.get(node);\r
1069                         if (bean != null) return bean;\r
1070                 }\r
1071                 return graph.syncRequest(new RelatedValue<BTreeContentBean>(node, DATA.BTreeNode_content, CONTENT_BEAN_BINDING), TransientCacheListener.<BTreeContentBean>instance());\r
1072         }\r
1073         \r
1074         public List<Tuple2> entries(ReadGraph graph) throws DatabaseException {\r
1075                 Resource r = getRoot(graph);\r
1076                 List<Tuple2> results = new ArrayList<Tuple2>();\r
1077                 return collectEntries(graph, r, null, null, results);\r
1078         }\r
1079         \r
1080         private List<Tuple2> collectEntries(ReadGraph graph, Resource x, Variant min, Variant max, List<Tuple2> results) throws DatabaseException {\r
1081 \r
1082                 BTreeContentBean xContent = getContentBean(graph, x);\r
1083 \r
1084                 for (int i = 0; i < xContent.n + 1; i++) {\r
1085                         if (min != null && i < xContent.n && min.compareTo(xContent.key[i].v) > 0) continue;\r
1086                         \r
1087                         if (!xContent.leaf) {\r
1088                                 Resource child = xContent.c[i].r;\r
1089                                 if (child != null) {\r
1090                                         \r
1091                                         // reduce the amount of comparison if we know that the range of the child keys matches\r
1092                                         Variant min2 = (min != null && i > 0 && min.compareTo(xContent.key[i - 1].v) < 0) ? null : min; \r
1093                                         Variant max2 = (max != null && i < xContent.n - 1 && max.compareTo(xContent.key[i + 1].v) > 0) ? null : max;\r
1094 \r
1095                                         collectEntries(graph, child, min2, max2, results);\r
1096                                 }\r
1097                         }\r
1098                         \r
1099                         if (i < xContent.n) {\r
1100                                 if (max != null && max.compareTo(xContent.key[i].v) < 0) return results;\r
1101 \r
1102                                 results.add(new Tuple2(xContent.key[i].v, xContent.value[i].r));\r
1103                         }\r
1104                 }\r
1105                 return results;\r
1106         }\r
1107         \r
1108         public List<Tuple2> searchRange(ReadGraph graph, Variant min, Variant max) throws DatabaseException {\r
1109                 Resource r = getRoot(graph);\r
1110                 List<Tuple2> results = new ArrayList<Tuple2>();\r
1111                 return collectEntries(graph, r, min, max, results);\r
1112         }\r
1113         \r
1114 }\r