|
70
|
1 ;;;; $Id: elib-node.el,v 1.1.1.1 1996/12/18 22:42:58 steve Exp $
|
|
0
|
2 ;;;; Nodes used in binary trees and doubly linked lists.
|
|
|
3
|
|
|
4 ;; Copyright (C) 1991-1995 Free Software Foundation
|
|
|
5
|
|
|
6 ;; Author: Per Cederqvist <ceder@lysator.liu.se>
|
|
|
7 ;; Inge Wallin <inge@lysator.liu.se>
|
|
|
8 ;; Maintainer: elib-maintainers@lysator.liu.se
|
|
|
9 ;; Created: 20 May 1991
|
|
|
10 ;; Keywords: extensions, lisp
|
|
|
11
|
|
|
12 ;;;; This file is part of the GNU Emacs lisp library, Elib.
|
|
|
13 ;;;;
|
|
|
14 ;;;; GNU Elib is free software; you can redistribute it and/or modify
|
|
|
15 ;;;; it under the terms of the GNU General Public License as published by
|
|
|
16 ;;;; the Free Software Foundation; either version 2, or (at your option)
|
|
|
17 ;;;; any later version.
|
|
|
18 ;;;;
|
|
|
19 ;;;; GNU Elib is distributed in the hope that it will be useful,
|
|
|
20 ;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
21 ;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
22 ;;;; GNU General Public License for more details.
|
|
|
23 ;;;;
|
|
|
24 ;;;; You should have received a copy of the GNU General Public License
|
|
|
25 ;;;; along with GNU Elib; see the file COPYING. If not, write to
|
|
|
26 ;;;; the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
|
|
|
27 ;;;; Boston, MA 02111-1307, USA
|
|
|
28 ;;;;
|
|
|
29 ;;;; Author: Inge Wallin
|
|
|
30 ;;;;
|
|
|
31
|
|
|
32 ;;; Commentary:
|
|
|
33
|
|
|
34 ;;; A node is implemented as an array with three elements, using
|
|
|
35 ;;; (elt node 0) as the left pointer
|
|
|
36 ;;; (elt node 1) as the right pointer
|
|
|
37 ;;; (elt node 2) as the data
|
|
|
38 ;;;
|
|
|
39 ;;; Some types of trees, e.g. AVL trees, need bigger nodes, but
|
|
|
40 ;;; as long as the first three parts are the left pointer, the
|
|
|
41 ;;; right pointer and the data field, these macros can be used.
|
|
|
42 ;;;
|
|
|
43
|
|
|
44 ;;; Code:
|
|
|
45
|
|
|
46 (provide 'elib-node)
|
|
|
47
|
|
|
48
|
|
|
49 (defmacro elib-node-create (left right data)
|
|
|
50
|
|
|
51 ;; Create a tree node from LEFT, RIGHT and DATA.
|
|
|
52 (` (vector (, left) (, right) (, data))))
|
|
|
53
|
|
|
54
|
|
|
55 (defmacro elib-node-left (node)
|
|
|
56
|
|
|
57 ;; Return the left pointer of NODE.
|
|
|
58 (` (aref (, node) 0)))
|
|
|
59
|
|
|
60
|
|
|
61 (defmacro elib-node-right (node)
|
|
|
62
|
|
|
63 ;; Return the right pointer of NODE.
|
|
|
64 (` (aref (, node) 1)))
|
|
|
65
|
|
|
66
|
|
|
67 (defmacro elib-node-data (node)
|
|
|
68
|
|
|
69 ;; Return the data of NODE.
|
|
|
70 (` (aref (, node) 2)))
|
|
|
71
|
|
|
72
|
|
|
73 (defmacro elib-node-set-left (node newleft)
|
|
|
74
|
|
|
75 ;; Set the left pointer of NODE to NEWLEFT.
|
|
|
76 (` (aset (, node) 0 (, newleft))))
|
|
|
77
|
|
|
78
|
|
|
79 (defmacro elib-node-set-right (node newright)
|
|
|
80
|
|
|
81 ;; Set the right pointer of NODE to NEWRIGHT.
|
|
|
82 (` (aset (, node) 1 (, newright))))
|
|
|
83
|
|
|
84
|
|
|
85 (defmacro elib-node-set-data (node newdata)
|
|
|
86 ;; Set the data of NODE to NEWDATA.
|
|
|
87 (` (aset (, node) 2 (, newdata))))
|
|
|
88
|
|
|
89
|
|
|
90
|
|
|
91 (defmacro elib-node-branch (node branch)
|
|
|
92
|
|
|
93 ;; Get value of a branch of a node.
|
|
|
94 ;;
|
|
|
95 ;; NODE is the node, and BRANCH is the branch.
|
|
|
96 ;; 0 for left pointer, 1 for right pointer and 2 for the data."
|
|
|
97 (` (aref (, node) (, branch))))
|
|
|
98
|
|
|
99
|
|
|
100 (defmacro elib-node-set-branch (node branch newval)
|
|
|
101
|
|
|
102 ;; Set value of a branch of a node.
|
|
|
103 ;;
|
|
|
104 ;; NODE is the node, and BRANCH is the branch.
|
|
|
105 ;; 0 for left pointer, 1 for the right pointer and 2 for the data.
|
|
|
106 ;; NEWVAL is new value of the branch."
|
|
|
107 (` (aset (, node) (, branch) (, newval))))
|
|
|
108
|
|
|
109 ;;; elib-node.el ends here.
|
