RAPair.java 3.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137
  1. /** SRFI-101 Purely Functional Random-Access Pairs and Lists.
  2. * Copyright Per Bothner 2013.
  3. * Copyright (c) David Van Horn 2009. All Rights Reserved.
  4. * Adaptation/translation into Java of low-level core parts
  5. * of Scheme reference implementation.
  6. */
  7. package gnu.lists;
  8. public class RAPair extends ImmutablePair {
  9. public int size;
  10. public Object getTree() { return car; }
  11. public Object getRest() { return cdr; }
  12. public RAPair(int size, Object tree, Object rest) {
  13. super(tree, rest);
  14. this.size = size;
  15. }
  16. private static int half(int n) { return n >> 1; }
  17. private static Object treeVal(Object t) {
  18. return t instanceof Node ? ((Node) t).val : t;
  19. }
  20. public Object getCar() {
  21. if (car instanceof Node)
  22. return treeVal(car);
  23. else
  24. return car;
  25. }
  26. public Object getCdr() {
  27. if (car instanceof Node) {
  28. Node tnode = (Node) car;
  29. int sz = half(size);
  30. return new RAPair(sz,
  31. tnode.left,
  32. new RAPair(sz, tnode.right, cdr));
  33. }
  34. else
  35. return cdr;
  36. }
  37. public static Object treeRef(int size, Object t, int i) {
  38. if (i == 0)
  39. return treeVal(t);
  40. else
  41. return treeRefA(t, i, half(size-1));
  42. }
  43. // Special-cased above to avoid logarathmic amount of cons'ing
  44. // and any multi-values overhead. Operates in constant space.
  45. // [Tree X] Nat Nat -> X
  46. // invariant: (= mid (half (sub1 (tree-count t))))
  47. public static Object treeRefA(Object t, int i, int mid) {
  48. for (;;) {
  49. if (i == 0)
  50. return treeVal(t);
  51. else if (i <= mid) {
  52. t = ((Node) t).left;
  53. i--;
  54. } else {
  55. t = ((Node) t).right;
  56. i = i - mid - 1;
  57. }
  58. mid = half(mid-1);
  59. }
  60. }
  61. public static Object listRef(RAPair ls, int i) {
  62. RAPair xs = ls;
  63. int j = i;
  64. for (;;) {
  65. int xsize = xs.size;
  66. if (j < xsize)
  67. return treeRef(xsize, xs.car, j);
  68. j -= xsize;
  69. xs = (RAPair) xs.cdr;
  70. }
  71. }
  72. public Object get(int i) {
  73. return listRef(this, i);
  74. }
  75. public static RAPair cons(Object x, Object ls) {
  76. if (ls instanceof RAPair) {
  77. RAPair lspair = (RAPair) ls;
  78. int s = lspair.size;
  79. if (lspair.cdr instanceof RAPair) {
  80. RAPair lsrest = (RAPair) lspair.cdr;
  81. if (lsrest.size == s)
  82. return new RAPair(s+s+1,
  83. new Node(x, lspair.car,
  84. lsrest.car),
  85. lsrest.cdr);
  86. }
  87. }
  88. return new RAPair(1, x, ls);
  89. }
  90. public static LList raList(Object[] xs) {
  91. LList result = LList.Empty;
  92. for (int i = xs.length; --i >= 0; )
  93. result = cons(xs[i], result);
  94. return result;
  95. }
  96. public static int raLength(Object ls) {
  97. int sz = 0;
  98. while (ls instanceof RAPair) {
  99. RAPair p = (RAPair) ls;
  100. sz += p.size;
  101. ls = p.cdr;
  102. }
  103. return sz;
  104. }
  105. public int size() {
  106. return raLength(this);
  107. }
  108. public static class Node {
  109. public Object val;
  110. public Object left;
  111. public Object right;
  112. public Node(Object val, Object left, Object right) {
  113. this.val = val;
  114. this.left = left;
  115. this.right = right;
  116. }
  117. }
  118. }